1package roaring
2
3import (
4	"fmt"
5)
6
7//go:generate msgp -unexported
8
9type arrayContainer struct {
10	content []uint16
11}
12
13func (ac *arrayContainer) String() string {
14	s := "{"
15	for it := ac.getShortIterator(); it.hasNext(); {
16		s += fmt.Sprintf("%v, ", it.next())
17	}
18	return s + "}"
19}
20
21func (ac *arrayContainer) fillLeastSignificant16bits(x []uint32, i int, mask uint32) {
22	for k := 0; k < len(ac.content); k++ {
23		x[k+i] = uint32(ac.content[k]) | mask
24	}
25}
26
27func (ac *arrayContainer) getShortIterator() shortPeekable {
28	return &shortIterator{ac.content, 0}
29}
30
31func (ac *arrayContainer) getReverseIterator() shortIterable {
32	return &reverseIterator{ac.content, len(ac.content) - 1}
33}
34
35func (ac *arrayContainer) getManyIterator() manyIterable {
36	return &shortIterator{ac.content, 0}
37}
38
39func (ac *arrayContainer) minimum() uint16 {
40	return ac.content[0] // assume not empty
41}
42
43func (ac *arrayContainer) maximum() uint16 {
44	return ac.content[len(ac.content)-1] // assume not empty
45}
46
47func (ac *arrayContainer) getSizeInBytes() int {
48	return ac.getCardinality() * 2
49}
50
51func (ac *arrayContainer) serializedSizeInBytes() int {
52	return ac.getCardinality() * 2
53}
54
55func arrayContainerSizeInBytes(card int) int {
56	return card * 2
57}
58
59// add the values in the range [firstOfRange,endx)
60func (ac *arrayContainer) iaddRange(firstOfRange, endx int) container {
61	if firstOfRange >= endx {
62		return ac
63	}
64	indexstart := binarySearch(ac.content, uint16(firstOfRange))
65	if indexstart < 0 {
66		indexstart = -indexstart - 1
67	}
68	indexend := binarySearch(ac.content, uint16(endx-1))
69	if indexend < 0 {
70		indexend = -indexend - 1
71	} else {
72		indexend++
73	}
74	rangelength := endx - firstOfRange
75	newcardinality := indexstart + (ac.getCardinality() - indexend) + rangelength
76	if newcardinality > arrayDefaultMaxSize {
77		a := ac.toBitmapContainer()
78		return a.iaddRange(firstOfRange, endx)
79	}
80	if cap(ac.content) < newcardinality {
81		tmp := make([]uint16, newcardinality, newcardinality)
82		copy(tmp[:indexstart], ac.content[:indexstart])
83		copy(tmp[indexstart+rangelength:], ac.content[indexend:])
84
85		ac.content = tmp
86	} else {
87		ac.content = ac.content[:newcardinality]
88		copy(ac.content[indexstart+rangelength:], ac.content[indexend:])
89
90	}
91	for k := 0; k < rangelength; k++ {
92		ac.content[k+indexstart] = uint16(firstOfRange + k)
93	}
94	return ac
95}
96
97// remove the values in the range [firstOfRange,endx)
98func (ac *arrayContainer) iremoveRange(firstOfRange, endx int) container {
99	if firstOfRange >= endx {
100		return ac
101	}
102	indexstart := binarySearch(ac.content, uint16(firstOfRange))
103	if indexstart < 0 {
104		indexstart = -indexstart - 1
105	}
106	indexend := binarySearch(ac.content, uint16(endx-1))
107	if indexend < 0 {
108		indexend = -indexend - 1
109	} else {
110		indexend++
111	}
112	rangelength := indexend - indexstart
113	answer := ac
114	copy(answer.content[indexstart:], ac.content[indexstart+rangelength:])
115	answer.content = answer.content[:ac.getCardinality()-rangelength]
116	return answer
117}
118
119// flip the values in the range [firstOfRange,endx)
120func (ac *arrayContainer) not(firstOfRange, endx int) container {
121	if firstOfRange >= endx {
122		return ac.clone()
123	}
124	return ac.notClose(firstOfRange, endx-1) // remove everything in [firstOfRange,endx-1]
125}
126
127// flip the values in the range [firstOfRange,lastOfRange]
128func (ac *arrayContainer) notClose(firstOfRange, lastOfRange int) container {
129	if firstOfRange > lastOfRange { // unlike add and remove, not uses an inclusive range [firstOfRange,lastOfRange]
130		return ac.clone()
131	}
132
133	// determine the span of array indices to be affected^M
134	startIndex := binarySearch(ac.content, uint16(firstOfRange))
135	if startIndex < 0 {
136		startIndex = -startIndex - 1
137	}
138	lastIndex := binarySearch(ac.content, uint16(lastOfRange))
139	if lastIndex < 0 {
140		lastIndex = -lastIndex - 2
141	}
142	currentValuesInRange := lastIndex - startIndex + 1
143	spanToBeFlipped := lastOfRange - firstOfRange + 1
144	newValuesInRange := spanToBeFlipped - currentValuesInRange
145	cardinalityChange := newValuesInRange - currentValuesInRange
146	newCardinality := len(ac.content) + cardinalityChange
147	if newCardinality > arrayDefaultMaxSize {
148		return ac.toBitmapContainer().not(firstOfRange, lastOfRange+1)
149	}
150	answer := newArrayContainer()
151	answer.content = make([]uint16, newCardinality, newCardinality) //a hack for sure
152
153	copy(answer.content, ac.content[:startIndex])
154	outPos := startIndex
155	inPos := startIndex
156	valInRange := firstOfRange
157	for ; valInRange <= lastOfRange && inPos <= lastIndex; valInRange++ {
158		if uint16(valInRange) != ac.content[inPos] {
159			answer.content[outPos] = uint16(valInRange)
160			outPos++
161		} else {
162			inPos++
163		}
164	}
165
166	for ; valInRange <= lastOfRange; valInRange++ {
167		answer.content[outPos] = uint16(valInRange)
168		outPos++
169	}
170
171	for i := lastIndex + 1; i < len(ac.content); i++ {
172		answer.content[outPos] = ac.content[i]
173		outPos++
174	}
175	answer.content = answer.content[:newCardinality]
176	return answer
177
178}
179
180func (ac *arrayContainer) equals(o container) bool {
181
182	srb, ok := o.(*arrayContainer)
183	if ok {
184		// Check if the containers are the same object.
185		if ac == srb {
186			return true
187		}
188
189		if len(srb.content) != len(ac.content) {
190			return false
191		}
192
193		for i, v := range ac.content {
194			if v != srb.content[i] {
195				return false
196			}
197		}
198		return true
199	}
200
201	// use generic comparison
202	bCard := o.getCardinality()
203	aCard := ac.getCardinality()
204	if bCard != aCard {
205		return false
206	}
207
208	ait := ac.getShortIterator()
209	bit := o.getShortIterator()
210	for ait.hasNext() {
211		if bit.next() != ait.next() {
212			return false
213		}
214	}
215	return true
216}
217
218func (ac *arrayContainer) toBitmapContainer() *bitmapContainer {
219	bc := newBitmapContainer()
220	bc.loadData(ac)
221	return bc
222
223}
224func (ac *arrayContainer) iadd(x uint16) (wasNew bool) {
225	// Special case adding to the end of the container.
226	l := len(ac.content)
227	if l > 0 && l < arrayDefaultMaxSize && ac.content[l-1] < x {
228		ac.content = append(ac.content, x)
229		return true
230	}
231
232	loc := binarySearch(ac.content, x)
233
234	if loc < 0 {
235		s := ac.content
236		i := -loc - 1
237		s = append(s, 0)
238		copy(s[i+1:], s[i:])
239		s[i] = x
240		ac.content = s
241		return true
242	}
243	return false
244}
245
246func (ac *arrayContainer) iaddReturnMinimized(x uint16) container {
247	// Special case adding to the end of the container.
248	l := len(ac.content)
249	if l > 0 && l < arrayDefaultMaxSize && ac.content[l-1] < x {
250		ac.content = append(ac.content, x)
251		return ac
252	}
253
254	loc := binarySearch(ac.content, x)
255
256	if loc < 0 {
257		if len(ac.content) >= arrayDefaultMaxSize {
258			a := ac.toBitmapContainer()
259			a.iadd(x)
260			return a
261		}
262		s := ac.content
263		i := -loc - 1
264		s = append(s, 0)
265		copy(s[i+1:], s[i:])
266		s[i] = x
267		ac.content = s
268	}
269	return ac
270}
271
272// iremoveReturnMinimized is allowed to change the return type to minimize storage.
273func (ac *arrayContainer) iremoveReturnMinimized(x uint16) container {
274	ac.iremove(x)
275	return ac
276}
277
278func (ac *arrayContainer) iremove(x uint16) bool {
279	loc := binarySearch(ac.content, x)
280	if loc >= 0 {
281		s := ac.content
282		s = append(s[:loc], s[loc+1:]...)
283		ac.content = s
284		return true
285	}
286	return false
287}
288
289func (ac *arrayContainer) remove(x uint16) container {
290	out := &arrayContainer{make([]uint16, len(ac.content))}
291	copy(out.content, ac.content[:])
292
293	loc := binarySearch(out.content, x)
294	if loc >= 0 {
295		s := out.content
296		s = append(s[:loc], s[loc+1:]...)
297		out.content = s
298	}
299	return out
300}
301
302func (ac *arrayContainer) or(a container) container {
303	switch x := a.(type) {
304	case *arrayContainer:
305		return ac.orArray(x)
306	case *bitmapContainer:
307		return x.orArray(ac)
308	case *runContainer16:
309		if x.isFull() {
310			return x.clone()
311		}
312		return x.orArray(ac)
313	}
314	panic("unsupported container type")
315}
316
317func (ac *arrayContainer) orCardinality(a container) int {
318	switch x := a.(type) {
319	case *arrayContainer:
320		return ac.orArrayCardinality(x)
321	case *bitmapContainer:
322		return x.orArrayCardinality(ac)
323	case *runContainer16:
324		return x.orArrayCardinality(ac)
325	}
326	panic("unsupported container type")
327}
328
329func (ac *arrayContainer) ior(a container) container {
330	switch x := a.(type) {
331	case *arrayContainer:
332		return ac.iorArray(x)
333	case *bitmapContainer:
334		return a.(*bitmapContainer).orArray(ac)
335		//return ac.iorBitmap(x) // note: this does not make sense
336	case *runContainer16:
337		if x.isFull() {
338			return x.clone()
339		}
340		return ac.iorRun16(x)
341	}
342	panic("unsupported container type")
343}
344
345func (ac *arrayContainer) iorArray(value2 *arrayContainer) container {
346	value1 := ac
347	len1 := value1.getCardinality()
348	len2 := value2.getCardinality()
349	maxPossibleCardinality := len1 + len2
350	if maxPossibleCardinality > arrayDefaultMaxSize { // it could be a bitmap!
351		bc := newBitmapContainer()
352		for k := 0; k < len(value2.content); k++ {
353			v := value2.content[k]
354			i := uint(v) >> 6
355			mask := uint64(1) << (v % 64)
356			bc.bitmap[i] |= mask
357		}
358		for k := 0; k < len(ac.content); k++ {
359			v := ac.content[k]
360			i := uint(v) >> 6
361			mask := uint64(1) << (v % 64)
362			bc.bitmap[i] |= mask
363		}
364		bc.cardinality = int(popcntSlice(bc.bitmap))
365		if bc.cardinality <= arrayDefaultMaxSize {
366			return bc.toArrayContainer()
367		}
368		return bc
369	}
370	if maxPossibleCardinality > cap(value1.content) {
371		newcontent := make([]uint16, 0, maxPossibleCardinality)
372		copy(newcontent[len2:maxPossibleCardinality], ac.content[0:len1])
373		ac.content = newcontent
374	} else {
375		copy(ac.content[len2:maxPossibleCardinality], ac.content[0:len1])
376	}
377	nl := union2by2(value1.content[len2:maxPossibleCardinality], value2.content, ac.content)
378	ac.content = ac.content[:nl] // reslice to match actual used capacity
379	return ac
380}
381
382// Note: such code does not make practical sense, except for lazy evaluations
383func (ac *arrayContainer) iorBitmap(bc2 *bitmapContainer) container {
384	bc1 := ac.toBitmapContainer()
385	bc1.iorBitmap(bc2)
386	*ac = *newArrayContainerFromBitmap(bc1)
387	return ac
388}
389
390func (ac *arrayContainer) iorRun16(rc *runContainer16) container {
391	bc1 := ac.toBitmapContainer()
392	bc2 := rc.toBitmapContainer()
393	bc1.iorBitmap(bc2)
394	*ac = *newArrayContainerFromBitmap(bc1)
395	return ac
396}
397
398func (ac *arrayContainer) lazyIOR(a container) container {
399	switch x := a.(type) {
400	case *arrayContainer:
401		return ac.lazyIorArray(x)
402	case *bitmapContainer:
403		return ac.lazyIorBitmap(x)
404	case *runContainer16:
405		if x.isFull() {
406			return x.clone()
407		}
408		return ac.lazyIorRun16(x)
409
410	}
411	panic("unsupported container type")
412}
413
414func (ac *arrayContainer) lazyIorArray(ac2 *arrayContainer) container {
415	// TODO actually make this lazy
416	return ac.iorArray(ac2)
417}
418
419func (ac *arrayContainer) lazyIorBitmap(bc *bitmapContainer) container {
420	// TODO actually make this lazy
421	return ac.iorBitmap(bc)
422}
423
424func (ac *arrayContainer) lazyIorRun16(rc *runContainer16) container {
425	// TODO actually make this lazy
426	return ac.iorRun16(rc)
427}
428
429func (ac *arrayContainer) lazyOR(a container) container {
430	switch x := a.(type) {
431	case *arrayContainer:
432		return ac.lazyorArray(x)
433	case *bitmapContainer:
434		return a.lazyOR(ac)
435	case *runContainer16:
436		if x.isFull() {
437			return x.clone()
438		}
439		return x.orArray(ac)
440	}
441	panic("unsupported container type")
442}
443
444func (ac *arrayContainer) orArray(value2 *arrayContainer) container {
445	value1 := ac
446	maxPossibleCardinality := value1.getCardinality() + value2.getCardinality()
447	if maxPossibleCardinality > arrayDefaultMaxSize { // it could be a bitmap!
448		bc := newBitmapContainer()
449		for k := 0; k < len(value2.content); k++ {
450			v := value2.content[k]
451			i := uint(v) >> 6
452			mask := uint64(1) << (v % 64)
453			bc.bitmap[i] |= mask
454		}
455		for k := 0; k < len(ac.content); k++ {
456			v := ac.content[k]
457			i := uint(v) >> 6
458			mask := uint64(1) << (v % 64)
459			bc.bitmap[i] |= mask
460		}
461		bc.cardinality = int(popcntSlice(bc.bitmap))
462		if bc.cardinality <= arrayDefaultMaxSize {
463			return bc.toArrayContainer()
464		}
465		return bc
466	}
467	answer := newArrayContainerCapacity(maxPossibleCardinality)
468	nl := union2by2(value1.content, value2.content, answer.content)
469	answer.content = answer.content[:nl] // reslice to match actual used capacity
470	return answer
471}
472
473func (ac *arrayContainer) orArrayCardinality(value2 *arrayContainer) int {
474	return union2by2Cardinality(ac.content, value2.content)
475}
476
477func (ac *arrayContainer) lazyorArray(value2 *arrayContainer) container {
478	value1 := ac
479	maxPossibleCardinality := value1.getCardinality() + value2.getCardinality()
480	if maxPossibleCardinality > arrayLazyLowerBound { // it could be a bitmap!^M
481		bc := newBitmapContainer()
482		for k := 0; k < len(value2.content); k++ {
483			v := value2.content[k]
484			i := uint(v) >> 6
485			mask := uint64(1) << (v % 64)
486			bc.bitmap[i] |= mask
487		}
488		for k := 0; k < len(ac.content); k++ {
489			v := ac.content[k]
490			i := uint(v) >> 6
491			mask := uint64(1) << (v % 64)
492			bc.bitmap[i] |= mask
493		}
494		bc.cardinality = invalidCardinality
495		return bc
496	}
497	answer := newArrayContainerCapacity(maxPossibleCardinality)
498	nl := union2by2(value1.content, value2.content, answer.content)
499	answer.content = answer.content[:nl] // reslice to match actual used capacity
500	return answer
501}
502
503func (ac *arrayContainer) and(a container) container {
504	switch x := a.(type) {
505	case *arrayContainer:
506		return ac.andArray(x)
507	case *bitmapContainer:
508		return x.and(ac)
509	case *runContainer16:
510		if x.isFull() {
511			return ac.clone()
512		}
513		return x.andArray(ac)
514	}
515	panic("unsupported container type")
516}
517
518func (ac *arrayContainer) andCardinality(a container) int {
519	switch x := a.(type) {
520	case *arrayContainer:
521		return ac.andArrayCardinality(x)
522	case *bitmapContainer:
523		return x.andCardinality(ac)
524	case *runContainer16:
525		return x.andArrayCardinality(ac)
526	}
527	panic("unsupported container type")
528}
529
530func (ac *arrayContainer) intersects(a container) bool {
531	switch x := a.(type) {
532	case *arrayContainer:
533		return ac.intersectsArray(x)
534	case *bitmapContainer:
535		return x.intersects(ac)
536	case *runContainer16:
537		return x.intersects(ac)
538	}
539	panic("unsupported container type")
540}
541
542func (ac *arrayContainer) iand(a container) container {
543	switch x := a.(type) {
544	case *arrayContainer:
545		return ac.iandArray(x)
546	case *bitmapContainer:
547		return ac.iandBitmap(x)
548	case *runContainer16:
549		if x.isFull() {
550			return ac
551		}
552		return x.andArray(ac)
553	}
554	panic("unsupported container type")
555}
556
557func (ac *arrayContainer) iandBitmap(bc *bitmapContainer) container {
558	pos := 0
559	c := ac.getCardinality()
560	for k := 0; k < c; k++ {
561		// branchless
562		v := ac.content[k]
563		ac.content[pos] = v
564		pos += int(bc.bitValue(v))
565	}
566	ac.content = ac.content[:pos]
567	return ac
568
569}
570
571func (ac *arrayContainer) xor(a container) container {
572	switch x := a.(type) {
573	case *arrayContainer:
574		return ac.xorArray(x)
575	case *bitmapContainer:
576		return a.xor(ac)
577	case *runContainer16:
578		return x.xorArray(ac)
579	}
580	panic("unsupported container type")
581}
582
583func (ac *arrayContainer) xorArray(value2 *arrayContainer) container {
584	value1 := ac
585	totalCardinality := value1.getCardinality() + value2.getCardinality()
586	if totalCardinality > arrayDefaultMaxSize { // it could be a bitmap!
587		bc := newBitmapContainer()
588		for k := 0; k < len(value2.content); k++ {
589			v := value2.content[k]
590			i := uint(v) >> 6
591			bc.bitmap[i] ^= (uint64(1) << (v % 64))
592		}
593		for k := 0; k < len(ac.content); k++ {
594			v := ac.content[k]
595			i := uint(v) >> 6
596			bc.bitmap[i] ^= (uint64(1) << (v % 64))
597		}
598		bc.computeCardinality()
599		if bc.cardinality <= arrayDefaultMaxSize {
600			return bc.toArrayContainer()
601		}
602		return bc
603	}
604	desiredCapacity := totalCardinality
605	answer := newArrayContainerCapacity(desiredCapacity)
606	length := exclusiveUnion2by2(value1.content, value2.content, answer.content)
607	answer.content = answer.content[:length]
608	return answer
609
610}
611
612func (ac *arrayContainer) andNot(a container) container {
613	switch x := a.(type) {
614	case *arrayContainer:
615		return ac.andNotArray(x)
616	case *bitmapContainer:
617		return ac.andNotBitmap(x)
618	case *runContainer16:
619		return ac.andNotRun16(x)
620	}
621	panic("unsupported container type")
622}
623
624func (ac *arrayContainer) andNotRun16(rc *runContainer16) container {
625	acb := ac.toBitmapContainer()
626	rcb := rc.toBitmapContainer()
627	return acb.andNotBitmap(rcb)
628}
629
630func (ac *arrayContainer) iandNot(a container) container {
631	switch x := a.(type) {
632	case *arrayContainer:
633		return ac.iandNotArray(x)
634	case *bitmapContainer:
635		return ac.iandNotBitmap(x)
636	case *runContainer16:
637		return ac.iandNotRun16(x)
638	}
639	panic("unsupported container type")
640}
641
642func (ac *arrayContainer) iandNotRun16(rc *runContainer16) container {
643	rcb := rc.toBitmapContainer()
644	acb := ac.toBitmapContainer()
645	acb.iandNotBitmapSurely(rcb)
646	*ac = *(acb.toArrayContainer())
647	return ac
648}
649
650func (ac *arrayContainer) andNotArray(value2 *arrayContainer) container {
651	value1 := ac
652	desiredcapacity := value1.getCardinality()
653	answer := newArrayContainerCapacity(desiredcapacity)
654	length := difference(value1.content, value2.content, answer.content)
655	answer.content = answer.content[:length]
656	return answer
657}
658
659func (ac *arrayContainer) iandNotArray(value2 *arrayContainer) container {
660	length := difference(ac.content, value2.content, ac.content)
661	ac.content = ac.content[:length]
662	return ac
663}
664
665func (ac *arrayContainer) andNotBitmap(value2 *bitmapContainer) container {
666	desiredcapacity := ac.getCardinality()
667	answer := newArrayContainerCapacity(desiredcapacity)
668	answer.content = answer.content[:desiredcapacity]
669	pos := 0
670	for _, v := range ac.content {
671		answer.content[pos] = v
672		pos += 1 - int(value2.bitValue(v))
673	}
674	answer.content = answer.content[:pos]
675	return answer
676}
677
678func (ac *arrayContainer) andBitmap(value2 *bitmapContainer) container {
679	desiredcapacity := ac.getCardinality()
680	answer := newArrayContainerCapacity(desiredcapacity)
681	answer.content = answer.content[:desiredcapacity]
682	pos := 0
683	for _, v := range ac.content {
684		answer.content[pos] = v
685		pos += int(value2.bitValue(v))
686	}
687	answer.content = answer.content[:pos]
688	return answer
689}
690
691func (ac *arrayContainer) iandNotBitmap(value2 *bitmapContainer) container {
692	pos := 0
693	for _, v := range ac.content {
694		ac.content[pos] = v
695		pos += 1 - int(value2.bitValue(v))
696	}
697	ac.content = ac.content[:pos]
698	return ac
699}
700
701func copyOf(array []uint16, size int) []uint16 {
702	result := make([]uint16, size)
703	for i, x := range array {
704		if i == size {
705			break
706		}
707		result[i] = x
708	}
709	return result
710}
711
712// flip the values in the range [firstOfRange,endx)
713func (ac *arrayContainer) inot(firstOfRange, endx int) container {
714	if firstOfRange >= endx {
715		return ac
716	}
717	return ac.inotClose(firstOfRange, endx-1) // remove everything in [firstOfRange,endx-1]
718}
719
720// flip the values in the range [firstOfRange,lastOfRange]
721func (ac *arrayContainer) inotClose(firstOfRange, lastOfRange int) container {
722	if firstOfRange > lastOfRange { // unlike add and remove, not uses an inclusive range [firstOfRange,lastOfRange]
723		return ac
724	}
725	// determine the span of array indices to be affected
726	startIndex := binarySearch(ac.content, uint16(firstOfRange))
727	if startIndex < 0 {
728		startIndex = -startIndex - 1
729	}
730	lastIndex := binarySearch(ac.content, uint16(lastOfRange))
731	if lastIndex < 0 {
732		lastIndex = -lastIndex - 1 - 1
733	}
734	currentValuesInRange := lastIndex - startIndex + 1
735	spanToBeFlipped := lastOfRange - firstOfRange + 1
736
737	newValuesInRange := spanToBeFlipped - currentValuesInRange
738	buffer := make([]uint16, newValuesInRange)
739	cardinalityChange := newValuesInRange - currentValuesInRange
740	newCardinality := len(ac.content) + cardinalityChange
741	if cardinalityChange > 0 {
742		if newCardinality > len(ac.content) {
743			if newCardinality > arrayDefaultMaxSize {
744				bcRet := ac.toBitmapContainer()
745				bcRet.inot(firstOfRange, lastOfRange+1)
746				*ac = *bcRet.toArrayContainer()
747				return bcRet
748			}
749			ac.content = copyOf(ac.content, newCardinality)
750		}
751		base := lastIndex + 1
752		copy(ac.content[lastIndex+1+cardinalityChange:], ac.content[base:base+len(ac.content)-1-lastIndex])
753		ac.negateRange(buffer, startIndex, lastIndex, firstOfRange, lastOfRange+1)
754	} else { // no expansion needed
755		ac.negateRange(buffer, startIndex, lastIndex, firstOfRange, lastOfRange+1)
756		if cardinalityChange < 0 {
757
758			for i := startIndex + newValuesInRange; i < newCardinality; i++ {
759				ac.content[i] = ac.content[i-cardinalityChange]
760			}
761		}
762	}
763	ac.content = ac.content[:newCardinality]
764	return ac
765}
766
767func (ac *arrayContainer) negateRange(buffer []uint16, startIndex, lastIndex, startRange, lastRange int) {
768	// compute the negation into buffer
769	outPos := 0
770	inPos := startIndex // value here always >= valInRange,
771	// until it is exhausted
772	// n.b., we can start initially exhausted.
773
774	valInRange := startRange
775	for ; valInRange < lastRange && inPos <= lastIndex; valInRange++ {
776		if uint16(valInRange) != ac.content[inPos] {
777			buffer[outPos] = uint16(valInRange)
778			outPos++
779		} else {
780			inPos++
781		}
782	}
783
784	// if there are extra items (greater than the biggest
785	// pre-existing one in range), buffer them
786	for ; valInRange < lastRange; valInRange++ {
787		buffer[outPos] = uint16(valInRange)
788		outPos++
789	}
790
791	if outPos != len(buffer) {
792		panic("negateRange: internal bug")
793	}
794
795	for i, item := range buffer {
796		ac.content[i+startIndex] = item
797	}
798}
799
800func (ac *arrayContainer) isFull() bool {
801	return false
802}
803
804func (ac *arrayContainer) andArray(value2 *arrayContainer) container {
805	desiredcapacity := minOfInt(ac.getCardinality(), value2.getCardinality())
806	answer := newArrayContainerCapacity(desiredcapacity)
807	length := intersection2by2(
808		ac.content,
809		value2.content,
810		answer.content)
811	answer.content = answer.content[:length]
812	return answer
813}
814
815func (ac *arrayContainer) andArrayCardinality(value2 *arrayContainer) int {
816	return intersection2by2Cardinality(
817		ac.content,
818		value2.content)
819}
820
821func (ac *arrayContainer) intersectsArray(value2 *arrayContainer) bool {
822	return intersects2by2(
823		ac.content,
824		value2.content)
825}
826
827func (ac *arrayContainer) iandArray(value2 *arrayContainer) container {
828	length := intersection2by2(
829		ac.content,
830		value2.content,
831		ac.content)
832	ac.content = ac.content[:length]
833	return ac
834}
835
836func (ac *arrayContainer) getCardinality() int {
837	return len(ac.content)
838}
839
840func (ac *arrayContainer) rank(x uint16) int {
841	answer := binarySearch(ac.content, x)
842	if answer >= 0 {
843		return answer + 1
844	}
845	return -answer - 1
846
847}
848
849func (ac *arrayContainer) selectInt(x uint16) int {
850	return int(ac.content[x])
851}
852
853func (ac *arrayContainer) clone() container {
854	ptr := arrayContainer{make([]uint16, len(ac.content))}
855	copy(ptr.content, ac.content[:])
856	return &ptr
857}
858
859func (ac *arrayContainer) contains(x uint16) bool {
860	return binarySearch(ac.content, x) >= 0
861}
862
863func (ac *arrayContainer) loadData(bitmapContainer *bitmapContainer) {
864	ac.content = make([]uint16, bitmapContainer.cardinality, bitmapContainer.cardinality)
865	bitmapContainer.fillArray(ac.content)
866}
867func newArrayContainer() *arrayContainer {
868	p := new(arrayContainer)
869	return p
870}
871
872func newArrayContainerFromBitmap(bc *bitmapContainer) *arrayContainer {
873	ac := &arrayContainer{}
874	ac.loadData(bc)
875	return ac
876}
877
878func newArrayContainerCapacity(size int) *arrayContainer {
879	p := new(arrayContainer)
880	p.content = make([]uint16, 0, size)
881	return p
882}
883
884func newArrayContainerSize(size int) *arrayContainer {
885	p := new(arrayContainer)
886	p.content = make([]uint16, size, size)
887	return p
888}
889
890func newArrayContainerRange(firstOfRun, lastOfRun int) *arrayContainer {
891	valuesInRange := lastOfRun - firstOfRun + 1
892	this := newArrayContainerCapacity(valuesInRange)
893	for i := 0; i < valuesInRange; i++ {
894		this.content = append(this.content, uint16(firstOfRun+i))
895	}
896	return this
897}
898
899func (ac *arrayContainer) numberOfRuns() (nr int) {
900	n := len(ac.content)
901	var runlen uint16
902	var cur, prev uint16
903
904	switch n {
905	case 0:
906		return 0
907	case 1:
908		return 1
909	default:
910		for i := 1; i < n; i++ {
911			prev = ac.content[i-1]
912			cur = ac.content[i]
913
914			if cur == prev+1 {
915				runlen++
916			} else {
917				if cur < prev {
918					panic("then fundamental arrayContainer assumption of sorted ac.content was broken")
919				}
920				if cur == prev {
921					panic("then fundamental arrayContainer assumption of deduplicated content was broken")
922				} else {
923					nr++
924					runlen = 0
925				}
926			}
927		}
928		nr++
929	}
930	return
931}
932
933// convert to run or array *if needed*
934func (ac *arrayContainer) toEfficientContainer() container {
935
936	numRuns := ac.numberOfRuns()
937
938	sizeAsRunContainer := runContainer16SerializedSizeInBytes(numRuns)
939	sizeAsBitmapContainer := bitmapContainerSizeInBytes()
940	card := ac.getCardinality()
941	sizeAsArrayContainer := arrayContainerSizeInBytes(card)
942
943	if sizeAsRunContainer <= minOfInt(sizeAsBitmapContainer, sizeAsArrayContainer) {
944		return newRunContainer16FromArray(ac)
945	}
946	if card <= arrayDefaultMaxSize {
947		return ac
948	}
949	return ac.toBitmapContainer()
950}
951
952func (ac *arrayContainer) containerType() contype {
953	return arrayContype
954}
955
956func (ac *arrayContainer) addOffset(x uint16) []container {
957	low := &arrayContainer{}
958	high := &arrayContainer{}
959	for _, val := range ac.content {
960		y := uint32(val) + uint32(x)
961		if highbits(y) > 0 {
962			high.content = append(high.content, lowbits(y))
963		} else {
964			low.content = append(low.content, lowbits(y))
965		}
966	}
967	return []container{low, high}
968}
969