1package roaring
2
3import (
4	"math"
5	"math/rand"
6	"sort"
7)
8
9const (
10	arrayDefaultMaxSize        = 4096 // containers with 4096 or fewer integers should be array containers.
11	arrayLazyLowerBound        = 1024
12	maxCapacity                = 1 << 16
13	serialCookieNoRunContainer = 12346 // only arrays and bitmaps
14	invalidCardinality         = -1
15	serialCookie               = 12347 // runs, arrays, and bitmaps
16	noOffsetThreshold          = 4
17
18	// MaxUint32 is the largest uint32 value.
19	MaxUint32 = math.MaxUint32
20
21	// MaxRange is One more than the maximum allowed bitmap bit index. For use as an upper
22	// bound for ranges.
23	MaxRange uint64 = MaxUint32 + 1
24
25	// MaxUint16 is the largest 16 bit unsigned int.
26	// This is the largest value an interval16 can store.
27	MaxUint16 = math.MaxUint16
28
29	// Compute wordSizeInBytes, the size of a word in bytes.
30	_m              = ^uint64(0)
31	_logS           = _m>>8&1 + _m>>16&1 + _m>>32&1
32	wordSizeInBytes = 1 << _logS
33
34	// other constants used in ctz_generic.go
35	wordSizeInBits = wordSizeInBytes << 3 // word size in bits
36)
37
38const maxWord = 1<<wordSizeInBits - 1
39
40// doesn't apply to runContainers
41func getSizeInBytesFromCardinality(card int) int {
42	if card > arrayDefaultMaxSize {
43		// bitmapContainer
44		return maxCapacity / 8
45	}
46	// arrayContainer
47	return 2 * card
48}
49
50func fill(arr []uint64, val uint64) {
51	for i := range arr {
52		arr[i] = val
53	}
54}
55func fillRange(arr []uint64, start, end int, val uint64) {
56	for i := start; i < end; i++ {
57		arr[i] = val
58	}
59}
60
61func fillArrayAND(container []uint16, bitmap1, bitmap2 []uint64) {
62	if len(bitmap1) != len(bitmap2) {
63		panic("array lengths don't match")
64	}
65	// TODO: rewrite in assembly
66	pos := 0
67	for k := range bitmap1 {
68		bitset := bitmap1[k] & bitmap2[k]
69		for bitset != 0 {
70			t := bitset & -bitset
71			container[pos] = uint16((k*64 + int(popcount(t-1))))
72			pos = pos + 1
73			bitset ^= t
74		}
75	}
76}
77
78func fillArrayANDNOT(container []uint16, bitmap1, bitmap2 []uint64) {
79	if len(bitmap1) != len(bitmap2) {
80		panic("array lengths don't match")
81	}
82	// TODO: rewrite in assembly
83	pos := 0
84	for k := range bitmap1 {
85		bitset := bitmap1[k] &^ bitmap2[k]
86		for bitset != 0 {
87			t := bitset & -bitset
88			container[pos] = uint16((k*64 + int(popcount(t-1))))
89			pos = pos + 1
90			bitset ^= t
91		}
92	}
93}
94
95func fillArrayXOR(container []uint16, bitmap1, bitmap2 []uint64) {
96	if len(bitmap1) != len(bitmap2) {
97		panic("array lengths don't match")
98	}
99	// TODO: rewrite in assembly
100	pos := 0
101	for k := 0; k < len(bitmap1); k++ {
102		bitset := bitmap1[k] ^ bitmap2[k]
103		for bitset != 0 {
104			t := bitset & -bitset
105			container[pos] = uint16((k*64 + int(popcount(t-1))))
106			pos = pos + 1
107			bitset ^= t
108		}
109	}
110}
111
112func highbits(x uint32) uint16 {
113	return uint16(x >> 16)
114}
115func lowbits(x uint32) uint16 {
116	return uint16(x & maxLowBit)
117}
118
119const maxLowBit = 0xFFFF
120
121func flipBitmapRange(bitmap []uint64, start int, end int) {
122	if start >= end {
123		return
124	}
125	firstword := start / 64
126	endword := (end - 1) / 64
127	bitmap[firstword] ^= ^(^uint64(0) << uint(start%64))
128	for i := firstword; i < endword; i++ {
129		bitmap[i] = ^bitmap[i]
130	}
131	bitmap[endword] ^= ^uint64(0) >> (uint(-end) % 64)
132}
133
134func resetBitmapRange(bitmap []uint64, start int, end int) {
135	if start >= end {
136		return
137	}
138	firstword := start / 64
139	endword := (end - 1) / 64
140	if firstword == endword {
141		bitmap[firstword] &= ^((^uint64(0) << uint(start%64)) & (^uint64(0) >> (uint(-end) % 64)))
142		return
143	}
144	bitmap[firstword] &= ^(^uint64(0) << uint(start%64))
145	for i := firstword + 1; i < endword; i++ {
146		bitmap[i] = 0
147	}
148	bitmap[endword] &= ^(^uint64(0) >> (uint(-end) % 64))
149
150}
151
152func setBitmapRange(bitmap []uint64, start int, end int) {
153	if start >= end {
154		return
155	}
156	firstword := start / 64
157	endword := (end - 1) / 64
158	if firstword == endword {
159		bitmap[firstword] |= (^uint64(0) << uint(start%64)) & (^uint64(0) >> (uint(-end) % 64))
160		return
161	}
162	bitmap[firstword] |= ^uint64(0) << uint(start%64)
163	for i := firstword + 1; i < endword; i++ {
164		bitmap[i] = ^uint64(0)
165	}
166	bitmap[endword] |= ^uint64(0) >> (uint(-end) % 64)
167}
168
169func flipBitmapRangeAndCardinalityChange(bitmap []uint64, start int, end int) int {
170	before := wordCardinalityForBitmapRange(bitmap, start, end)
171	flipBitmapRange(bitmap, start, end)
172	after := wordCardinalityForBitmapRange(bitmap, start, end)
173	return int(after - before)
174}
175
176func resetBitmapRangeAndCardinalityChange(bitmap []uint64, start int, end int) int {
177	before := wordCardinalityForBitmapRange(bitmap, start, end)
178	resetBitmapRange(bitmap, start, end)
179	after := wordCardinalityForBitmapRange(bitmap, start, end)
180	return int(after - before)
181}
182
183func setBitmapRangeAndCardinalityChange(bitmap []uint64, start int, end int) int {
184	before := wordCardinalityForBitmapRange(bitmap, start, end)
185	setBitmapRange(bitmap, start, end)
186	after := wordCardinalityForBitmapRange(bitmap, start, end)
187	return int(after - before)
188}
189
190func wordCardinalityForBitmapRange(bitmap []uint64, start int, end int) uint64 {
191	answer := uint64(0)
192	if start >= end {
193		return answer
194	}
195	firstword := start / 64
196	endword := (end - 1) / 64
197	for i := firstword; i <= endword; i++ {
198		answer += popcount(bitmap[i])
199	}
200	return answer
201}
202
203func selectBitPosition(w uint64, j int) int {
204	seen := 0
205
206	// Divide 64bit
207	part := w & 0xFFFFFFFF
208	n := popcount(part)
209	if n <= uint64(j) {
210		part = w >> 32
211		seen += 32
212		j -= int(n)
213	}
214	w = part
215
216	// Divide 32bit
217	part = w & 0xFFFF
218	n = popcount(part)
219	if n <= uint64(j) {
220		part = w >> 16
221		seen += 16
222		j -= int(n)
223	}
224	w = part
225
226	// Divide 16bit
227	part = w & 0xFF
228	n = popcount(part)
229	if n <= uint64(j) {
230		part = w >> 8
231		seen += 8
232		j -= int(n)
233	}
234	w = part
235
236	// Lookup in final byte
237	var counter uint
238	for counter = 0; counter < 8; counter++ {
239		j -= int((w >> counter) & 1)
240		if j < 0 {
241			break
242		}
243	}
244	return seen + int(counter)
245
246}
247
248func panicOn(err error) {
249	if err != nil {
250		panic(err)
251	}
252}
253
254type ph struct {
255	orig int
256	rand int
257}
258
259type pha []ph
260
261func (p pha) Len() int           { return len(p) }
262func (p pha) Less(i, j int) bool { return p[i].rand < p[j].rand }
263func (p pha) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
264
265func getRandomPermutation(n int) []int {
266	r := make([]ph, n)
267	for i := 0; i < n; i++ {
268		r[i].orig = i
269		r[i].rand = rand.Intn(1 << 29)
270	}
271	sort.Sort(pha(r))
272	m := make([]int, n)
273	for i := range m {
274		m[i] = r[i].orig
275	}
276	return m
277}
278
279func minOfInt(a, b int) int {
280	if a < b {
281		return a
282	}
283	return b
284}
285
286func maxOfInt(a, b int) int {
287	if a > b {
288		return a
289	}
290	return b
291}
292
293func maxOfUint16(a, b uint16) uint16 {
294	if a > b {
295		return a
296	}
297	return b
298}
299
300func minOfUint16(a, b uint16) uint16 {
301	if a < b {
302		return a
303	}
304	return b
305}
306