1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
package fzf
import "fmt"
// EmptyMerger is a Merger with no data
var EmptyMerger = NewMerger(nil, [][]Result{}, false, false)
// Merger holds a set of locally sorted lists of items and provides the view of
// a single, globally-sorted list
type Merger struct {
pattern *Pattern
lists [][]Result
merged []Result
chunks *[]*Chunk
cursors []int
sorted bool
tac bool
final bool
count int
}
// PassMerger returns a new Merger that simply returns the items in the
// original order
func PassMerger(chunks *[]*Chunk, tac bool) *Merger {
mg := Merger{
pattern: nil,
chunks: chunks,
tac: tac,
count: 0}
for _, chunk := range *mg.chunks {
mg.count += chunk.count
}
return &mg
}
// NewMerger returns a new Merger
func NewMerger(pattern *Pattern, lists [][]Result, sorted bool, tac bool) *Merger {
mg := Merger{
pattern: pattern,
lists: lists,
merged: []Result{},
chunks: nil,
cursors: make([]int, len(lists)),
sorted: sorted,
tac: tac,
final: false,
count: 0}
for _, list := range mg.lists {
mg.count += len(list)
}
return &mg
}
// Length returns the number of items
func (mg *Merger) Length() int {
return mg.count
}
// Get returns the pointer to the Result object indexed by the given integer
func (mg *Merger) Get(idx int) Result {
if mg.chunks != nil {
if mg.tac {
idx = mg.count - idx - 1
}
chunk := (*mg.chunks)[idx/chunkSize]
return Result{item: &chunk.items[idx%chunkSize]}
}
if mg.sorted {
return mg.mergedGet(idx)
}
if mg.tac {
idx = mg.count - idx - 1
}
for _, list := range mg.lists {
numItems := len(list)
if idx < numItems {
return list[idx]
}
idx -= numItems
}
panic(fmt.Sprintf("Index out of bounds (unsorted, %d/%d)", idx, mg.count))
}
func (mg *Merger) cacheable() bool {
return mg.count < mergerCacheMax
}
func (mg *Merger) mergedGet(idx int) Result {
for i := len(mg.merged); i <= idx; i++ {
minRank := minRank()
minIdx := -1
for listIdx, list := range mg.lists {
cursor := mg.cursors[listIdx]
if cursor < 0 || cursor == len(list) {
mg.cursors[listIdx] = -1
continue
}
if cursor >= 0 {
rank := list[cursor]
if minIdx < 0 || compareRanks(rank, minRank, mg.tac) {
minRank = rank
minIdx = listIdx
}
}
}
if minIdx >= 0 {
chosen := mg.lists[minIdx]
mg.merged = append(mg.merged, chosen[mg.cursors[minIdx]])
mg.cursors[minIdx]++
} else {
panic(fmt.Sprintf("Index out of bounds (sorted, %d/%d)", i, mg.count))
}
}
return mg.merged[idx]
}
|
