forked from Workiva/go-datastructures
/
symmerge.go
196 lines (169 loc) · 4.55 KB
/
symmerge.go
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
package merge
import (
"math"
"sync"
)
// symSearch is like symBinarySearch but operates
// on two sorted lists instead of a sorted list and an index.
// It's duplication of code but you buy performance.
func symSearch(u, w Comparators) int {
start, stop, p := 0, len(u), len(w)-1
for start < stop {
mid := (start + stop) / 2
if u[mid].Compare(w[p-mid]) <= 0 {
start = mid + 1
} else {
stop = mid
}
}
return start
}
// swap will swap positions of the two lists from index
// to the end of the list. It expects that these lists
// are the same size or one different.
func swap(u, w Comparators, index int) {
for i := index; i < len(u); i++ {
u[i], w[i-index] = w[i-index], u[i]
}
}
// decomposeForSymMerge pulls an active site out of the list
// of length in size. W becomes the active site for future sym
// merges and v1, v2 are decomposed and split among the other
// list to be merged and w.
func decomposeForSymMerge(length int,
comparators Comparators) (v1 Comparators,
w Comparators, v2 Comparators) {
if length >= len(comparators) {
panic(`INCORRECT PARAMS FOR SYM MERGE.`)
}
overhang := (len(comparators) - length) / 2
v1 = comparators[:overhang]
w = comparators[overhang : overhang+length]
v2 = comparators[overhang+length:]
return
}
// symBinarySearch will perform a binary search between the provided
// indices and find the index at which a rotation should occur.
func symBinarySearch(u Comparators, start, stop, total int) int {
for start < stop {
mid := (start + stop) / 2
if u[mid].Compare(u[total-mid]) <= 0 {
start = mid + 1
} else {
stop = mid
}
}
return start
}
// symSwap will perform a rotation or swap between the provided
// indices. Again, there is duplication here with swap, but
// we are buying performance.
func symSwap(u Comparators, start1, start2, end int) {
for i := 0; i < end; i++ {
u[start1+i], u[start2+i] = u[start2+i], u[start1+i]
}
}
// symRotate determines the indices to use in a symSwap and
// performs the swap.
func symRotate(u Comparators, start1, start2, end int) {
i := start2 - start1
if i == 0 {
return
}
j := end - start2
if j == 0 {
return
}
if i == j {
symSwap(u, start1, start2, i)
return
}
p := start1 + i
for i != j {
if i > j {
symSwap(u, p-i, p, j)
i -= j
} else {
symSwap(u, p-i, p+j-i, i)
j -= i
}
}
symSwap(u, p-i, p, i)
}
// symMerge is the recursive and internal form of SymMerge.
func symMerge(u Comparators, start1, start2, last int) {
if start1 < start2 && start2 < last {
mid := (start1 + last) / 2
n := mid + start2
var start int
if start2 > mid {
start = symBinarySearch(u, n-last, mid, n-1)
} else {
start = symBinarySearch(u, start1, start2, n-1)
}
end := n - start
symRotate(u, start, start2, end)
symMerge(u, start1, start, mid)
symMerge(u, mid, end, last)
}
}
// SymMerge will perform a symmetrical merge of the two provided
// lists. It is expected that these lists are pre-sorted. Failure
// to do so will result in undefined behavior. This function does
// make use of goroutines, so multithreading can aid merge time.
// This makes M*log(N/M+1) comparisons where M is the length
// of the shorter list and N is the length of the longer list.
func SymMerge(u, w Comparators) Comparators {
lenU, lenW := len(u), len(w)
if lenU == 0 {
return w
}
if lenW == 0 {
return u
}
diff := lenU - lenW
if math.Abs(float64(diff)) > 1 {
u1, w1, u2, w2 := prepareForSymMerge(u, w)
lenU1 := len(u1)
lenU2 := len(u2)
u = append(u1, w1...)
w = append(u2, w2...)
var wg sync.WaitGroup
wg.Add(2)
go func() {
symMerge(u, 0, lenU1, len(u))
wg.Done()
}()
go func() {
symMerge(w, 0, lenU2, len(w))
wg.Done()
}()
wg.Wait()
u = append(u, w...)
return u
}
u = append(u, w...)
symMerge(u, 0, lenU, len(u))
return u
}
// prepareForSymMerge performs a symmetrical decomposition on two
// lists of different sizes. It breaks apart the longer list into
// an active site (equal to the size of the shorter list) and performs
// a symmetrical rotation with the active site and the shorter list.
// The two stubs are then split between the active site and shorter list
// ensuring two equally sized lists where every value in u' is less
// than w'.
func prepareForSymMerge(u, w Comparators) (u1, w1, u2, w2 Comparators) {
if u.Len() > w.Len() {
u, w = w, u
}
v1, w, v2 := decomposeForSymMerge(len(u), w)
i := symSearch(u, w)
u1 = make(Comparators, i)
copy(u1, u[:i])
w1 = append(v1, w[:len(w)-i]...)
u2 = make(Comparators, len(u)-i)
copy(u2, u[i:])
w2 = append(w[len(w)-i:], v2...)
return
}