arraycontainer_test.go

package roaring

// to run just these tests: go test -run TestArrayContainer*

import (
	"math/rand"
	"testing"

	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

func TestArrayContainerTransition(t *testing.T) {
	v := container(newArrayContainer())

	for i := 0; i < arrayDefaultMaxSize; i++ {
		v = v.iaddReturnMinimized(uint16(i))
	}

	assert.Equal(t, arrayDefaultMaxSize, v.getCardinality())
	assert.IsType(t, newArrayContainer(), v)

	for i := 0; i < arrayDefaultMaxSize; i++ {
		v = v.iaddReturnMinimized(uint16(i))
	}

	assert.Equal(t, arrayDefaultMaxSize, v.getCardinality())
	assert.IsType(t, newArrayContainer(), v)

	v = v.iaddReturnMinimized(uint16(arrayDefaultMaxSize))

	assert.Equal(t, arrayDefaultMaxSize+1, v.getCardinality())
	assert.IsType(t, newBitmapContainer(), v)

	v = v.iremoveReturnMinimized(uint16(arrayDefaultMaxSize))

	assert.Equal(t, arrayDefaultMaxSize, v.getCardinality())
	assert.IsType(t, newArrayContainer(), v)
}

func TestArrayContainerRank(t *testing.T) {
	v := container(newArrayContainer())
	v = v.iaddReturnMinimized(10)
	v = v.iaddReturnMinimized(100)
	v = v.iaddReturnMinimized(1000)

	assert.Equal(t, 3, v.getCardinality())

	for i := 0; i <= arrayDefaultMaxSize; i++ {
		thisrank := v.rank(uint16(i))

		if i < 10 {
			assert.Equalf(t, 0, thisrank, "At %d should be zero but is %d", i, thisrank)
		} else if i < 100 {
			assert.Equalf(t, 1, thisrank, "At %d should be one but is %d", i, thisrank)
		} else if i < 1000 {
			assert.Equalf(t, 2, thisrank, "At %d should be two but is %d", i, thisrank)
		} else {
			assert.Equalf(t, 3, thisrank, "At %d should be three but is %d", i, thisrank)
		}
	}
}

func TestArrayOffset(t *testing.T) {
	nums := []uint16{10, 100, 1000}
	expected := make([]int, len(nums))
	offtest := uint16(65000)
	v := container(newArrayContainer())
	for i, n := range nums {
		v = v.iaddReturnMinimized(n)
		expected[i] = int(n) + int(offtest)
	}
	l, h := v.addOffset(offtest)

	var w0card, w1card int
	wout := make([]int, len(nums))

	if l != nil {
		w0card = l.getCardinality()

		for i := 0; i < w0card; i++ {
			wout[i] = l.selectInt(uint16(i))
		}
	}

	if h != nil {
		w1card = h.getCardinality()

		for i := 0; i < w1card; i++ {
			wout[i+w0card] = h.selectInt(uint16(i)) + 65536
		}
	}

	assert.Equal(t, 3, w0card+w1card)
	for i, x := range wout {
		assert.Equal(t, expected[i], x)
	}
}

func TestArrayContainerMassiveSetAndGet(t *testing.T) {
	v := container(newArrayContainer())

	for j := 0; j <= arrayDefaultMaxSize; j++ {
		v = v.iaddReturnMinimized(uint16(j))
		assert.Equal(t, 1+j, v.getCardinality())

		success := true
		i := 0

		for ; i <= arrayDefaultMaxSize && success; i++ {
			if i <= j {
				success = v.contains(uint16(i))
			} else {
				success = !v.contains(uint16(i))
			}
		}

		assert.Truef(t, success, "failed at %d iteration", i)
	}
}

func TestArrayContainerUnsupportedType(t *testing.T) {
	a := container(newArrayContainer())
	testContainerPanics(t, a)

	b := container(newBitmapContainer())
	testContainerPanics(t, b)
}

func testContainerPanics(t *testing.T, c container) {
	f := &struct {
		arrayContainer
	}{}

	assert.Panics(t, func() { c.or(f) })
	assert.Panics(t, func() { c.ior(f) })
	assert.Panics(t, func() { c.lazyIOR(f) })
	assert.Panics(t, func() { c.lazyOR(f) })
	assert.Panics(t, func() { c.and(f) })
	assert.Panics(t, func() { c.intersects(f) })
	assert.Panics(t, func() { c.iand(f) })
	assert.Panics(t, func() { c.xor(f) })
	assert.Panics(t, func() { c.andNot(f) })
	assert.Panics(t, func() { c.iandNot(f) })
}

func TestArrayContainerNumberOfRuns025(t *testing.T) {
	seed := int64(42)
	rand.Seed(seed)

	trials := []trial{
		{n: 1000, percentFill: .1, ntrial: 10},
		/*
			trial{n: 100, percentFill: .5, ntrial: 10},
			trial{n: 100, percentFill: .01, ntrial: 10},
			trial{n: 100, percentFill: .99, ntrial: 10},
		*/
	}

	tester := func(tr trial) {
		for j := 0; j < tr.ntrial; j++ {
			ma := make(map[int]bool)

			n := tr.n
			a := []uint16{}

			draw := int(float64(n) * tr.percentFill)
			for i := 0; i < draw; i++ {
				r0 := rand.Intn(n)
				a = append(a, uint16(r0))
				ma[r0] = true
			}

			// RunContainer computes this automatically
			rc := newRunContainer16FromVals(false, a...)
			rcNr := rc.numberOfRuns()

			// vs arrayContainer
			ac := newArrayContainer()
			for k := range ma {
				ac.iadd(uint16(k))
			}

			acNr := ac.numberOfRuns()
			assert.Equal(t, acNr, rcNr)

			// get coverage of arrayContainer coners...
			assert.Equal(t, 2*len(ma), ac.serializedSizeInBytes())
			assert.NotPanics(t, func() { ac.iaddRange(2, 1) })
			assert.NotPanics(t, func() { ac.iremoveRange(2, 1) })

			ac.iremoveRange(0, 2)
			ac.iremoveRange(0, 2)
			delete(ma, 0)
			delete(ma, 1)

			assert.Equal(t, len(ma), ac.getCardinality())

			ac.iadd(0)
			ac.iadd(1)
			ac.iadd(2)
			ma[0] = true
			ma[1] = true
			ma[2] = true
			newguy := ac.not(0, 3).(*arrayContainer)

			assert.False(t, newguy.contains(0))
			assert.False(t, newguy.contains(1))
			assert.False(t, newguy.contains(2))

			newguy.notClose(0, 2)
			newguy.remove(2)
			newguy.remove(2)
			newguy.ior(ac)

			messedUp := newArrayContainer()

			assert.Equal(t, 0, messedUp.numberOfRuns())

			// messed up
			messedUp.content = []uint16{1, 1}
			assert.Panics(t, func() { messedUp.numberOfRuns() })

			messedUp.content = []uint16{2, 1}
			assert.Panics(t, func() { messedUp.numberOfRuns() })

			shouldBeBit := newArrayContainer()
			for i := 0; i < arrayDefaultMaxSize+1; i++ {
				shouldBeBit.iadd(uint16(i * 2))
			}
			bit := shouldBeBit.toEfficientContainer()
			_, isBit := bit.(*bitmapContainer)

			assert.True(t, isBit)
		}
	}

	for i := range trials {
		tester(trials[i])
	}
}

func TestArrayContainerIaddRangeNearMax068(t *testing.T) {
	iv := []interval16{
		newInterval16Range(65525, 65527),
		newInterval16Range(65530, 65530),
		newInterval16Range(65534, 65535),
	}
	rc := newRunContainer16TakeOwnership(iv)

	ac2 := rc.toArrayContainer()

	assert.True(t, ac2.equals(rc))
	assert.True(t, rc.equals(ac2))

	ac := newArrayContainer()
	endx := int(MaxUint16) + 1
	first := endx - 3
	ac.iaddRange(first-20, endx-20)
	ac.iaddRange(first-6, endx-6)
	ac.iaddRange(first, endx)

	assert.Equal(t, 9, ac.getCardinality())
}

func TestArrayContainerEtc070(t *testing.T) {
	iv := []interval16{
		newInterval16Range(65525, 65527),
		newInterval16Range(65530, 65530),
		newInterval16Range(65534, 65535),
	}
	rc := newRunContainer16TakeOwnership(iv)
	ac := rc.toArrayContainer()

	// not when nothing to do just returns a clone
	assert.True(t, ac.equals(ac.not(0, 0)))
	assert.True(t, ac.equals(ac.notClose(1, 0)))

	// not will promote to bitmapContainer if card is big enough
	ac = newArrayContainer()
	ac.inot(0, MaxUint16+1)
	rc = newRunContainer16Range(0, MaxUint16)

	assert.True(t, rc.equals(ac))

	// comparing two array containers with different card
	ac2 := newArrayContainer()
	assert.False(t, ac2.equals(ac))

	// comparing two arrays with same card but different content
	ac3 := newArrayContainer()
	ac4 := newArrayContainer()
	ac3.iadd(1)
	ac3.iadd(2)
	ac4.iadd(1)

	assert.False(t, ac3.equals(ac4))

	// compare array vs other with different card
	assert.False(t, ac3.equals(rc))

	// compare array vs other, same card, different content
	rc = newRunContainer16Range(0, 0)
	assert.False(t, ac4.equals(rc))

	// remove from middle of array
	ac5 := newArrayContainer()
	ac5.iaddRange(0, 10)

	assert.Equal(t, 10, ac5.getCardinality())

	ac6 := ac5.remove(5)
	assert.Equal(t, 9, ac6.getCardinality())

	// lazyorArray that converts to bitmap
	ac5.iaddRange(0, arrayLazyLowerBound-1)
	ac6.iaddRange(arrayLazyLowerBound, 2*arrayLazyLowerBound-2)
	ac6a := ac6.(*arrayContainer)
	bc := ac5.lazyorArray(ac6a)
	_, isBitmap := bc.(*bitmapContainer)

	assert.True(t, isBitmap)

	// andBitmap
	ac = newArrayContainer()
	ac.iaddRange(0, 10)
	bc9 := newBitmapContainer()
	bc9.iaddRange(0, 5)
	and := ac.andBitmap(bc9)

	assert.Equal(t, 5, and.getCardinality())

	// numberOfRuns with 1 member
	ac10 := newArrayContainer()
	ac10.iadd(1)

	assert.Equal(t, 1, ac10.numberOfRuns())
}

func TestArrayContainerIAndNot(t *testing.T) {
	var ac container
	ac = newArrayContainer()
	ac.iadd(12)
	ac.iadd(27)
	ac.iadd(32)
	ac.iadd(88)
	ac.iadd(188)
	ac.iadd(289)

	var rc container
	rc = newRunContainer16Range(0, 15)
	rc = rc.iaddRange(1500, 2000)
	rc = rc.iaddRange(55, 100)
	rc = rc.iaddRange(25, 50)
	ac = ac.iandNot(rc)

	require.ElementsMatch(t, []uint16{188, 289}, ac.(*arrayContainer).content)
	require.Equal(t, 2, ac.getCardinality())
}

func TestArrayContainerAndNotRun(t *testing.T) {
	tests := []struct {
		name      string
		content   []uint16
		intervals []interval16
		want      []uint16
	}{
		{
			name:    "empty run",
			content: []uint16{0, 10, MaxUint16},
			want:    []uint16{0, 10, MaxUint16},
		},
		{
			name:      "empty array",
			intervals: []interval16{newInterval16Range(0, 0)},
			want:      []uint16{},
		},
		{
			name:      "single run",
			content:   []uint16{0, 2, 3, 4, 6, 8, 10},
			intervals: []interval16{newInterval16Range(3, 8)},
			want:      []uint16{0, 2, 10},
		},
		{
			name:      "full run",
			content:   []uint16{0, 2, MaxUint16},
			intervals: []interval16{newInterval16Range(0, MaxUint16)},
			want:      []uint16{},
		},
		{
			name:      "run after array",
			content:   []uint16{1, 3, 5},
			intervals: []interval16{newInterval16Range(10, 20)},
			want:      []uint16{1, 3, 5},
		},
		{
			name:      "run before array",
			content:   []uint16{10, 20, 30},
			intervals: []interval16{newInterval16Range(0, 5)},
			want:      []uint16{10, 20, 30},
		},
		{
			name:    "multiple runs",
			content: []uint16{0, 3, 4, 10, 12, 15, MaxUint16},
			intervals: []interval16{
				newInterval16Range(0, 0),
				newInterval16Range(4, 10),
				newInterval16Range(MaxUint16, MaxUint16),
			},
			want: []uint16{3, 12, 15},
		},
	}

	for _, test := range tests {
		t.Run(test.name, func(t *testing.T) {
			ac := &arrayContainer{content: append([]uint16(nil), test.content...)}
			rc := newRunContainer16CopyIv(test.intervals)
			originalContent := append([]uint16(nil), ac.content...)
			originalIntervals := make([]interval16, len(rc.iv))
			copy(originalIntervals, rc.iv)

			got := ac.andNotRun16(rc).(*arrayContainer)
			assert.Equal(t, test.want, got.content)
			assert.Equal(t, originalContent, ac.content)
			assert.Equal(t, originalIntervals, rc.iv)
			assert.NotSame(t, ac, got)
			if len(got.content) > 0 {
				got.content[0]++
				assert.Equal(t, originalContent, ac.content)
			}
		})
	}
}

func TestArrayContainerIand(t *testing.T) {
	a := NewBitmap()
	a.AddRange(0, 200000)
	b := BitmapOf(50, 100000, 150000)
	b.And(a)
	r := b.ToArray()

	assert.Len(t, r, 3)
	assert.EqualValues(t, 50, r[0])
	assert.EqualValues(t, 100000, r[1])
	assert.EqualValues(t, 150000, r[2])
}

func TestArrayIteratorPeekNext(t *testing.T) {
	testContainerIteratorPeekNext(t, newArrayContainer())
}

func TestArrayIteratorAdvance(t *testing.T) {
	testContainerIteratorAdvance(t, newArrayContainer())
}

func TestArrayContainerResetTo(t *testing.T) {
	array := newArrayContainer()
	for i := 0; i < 1000; i++ {
		array.iadd(uint16(i*1000 + i + 50))
	}

	bitmap := newBitmapContainer()
	for i := 0; i < 10000; i++ {
		bitmap.iadd(uint16(i*1000 + i + 50))
	}

	run := newRunContainer16()
	for i := 0; i < 10; i++ {
		start := i*1000 + i + 50
		run.iaddRange(start, start+100+i)
	}

	makeDirty := func() *arrayContainer {
		ret := newArrayContainer()
		for i := 0; i < arrayDefaultMaxSize; i += 3 {
			ret.iadd(uint16(i))
		}
		return ret
	}

	t.Run("to array container", func(t *testing.T) {
		clean := newArrayContainer()
		clean.resetTo(array)
		assert.True(t, clean.equals(array))

		dirty := makeDirty()
		dirty.resetTo(array)
		assert.True(t, dirty.equals(array))
	})

	t.Run("to bitmap container", func(t *testing.T) {
		clean := newArrayContainer()
		clean.resetTo(bitmap)
		assert.True(t, clean.equals(bitmap))

		dirty := makeDirty()
		dirty.resetTo(bitmap)
		assert.True(t, dirty.equals(bitmap.toArrayContainer()))
	})

	t.Run("to run container", func(t *testing.T) {
		clean := newArrayContainer()
		clean.resetTo(run)
		assert.True(t, clean.toEfficientContainer().equals(run))

		dirty := makeDirty()
		dirty.resetTo(run)
		assert.True(t, dirty.toEfficientContainer().equals(run))
	})
}

func TestNextValueArray(t *testing.T) {
	t.Run("Java Port 1", func(t *testing.T) {
		// [Example 1]  https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/buffer/TestMappeableArrayContainer.java#L495
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		assert.Equal(t, 64, ac.nextValue(0))
		assert.Equal(t, 64, ac.nextValue(64))
		assert.Equal(t, 65, ac.nextValue(65))
		assert.Equal(t, 128, ac.nextValue(128))
		assert.Equal(t, -1, ac.nextValue(129))
		assert.Equal(t, -1, ac.nextValue(5000))
	})

	t.Run("Java Port 2", func(t *testing.T) {
		// [Example 2]  https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/buffer/TestMappeableArrayContainer.java#L507
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		ac.iaddRange(256, 321)
		assert.Equal(t, 64, ac.nextValue(0))
		assert.Equal(t, 64, ac.nextValue(63))
		assert.Equal(t, 64, ac.nextValue(64))
		assert.Equal(t, 65, ac.nextValue(65))
		assert.Equal(t, 128, ac.nextValue(128))
		assert.Equal(t, 256, ac.nextValue(129))
		assert.Equal(t, -1, ac.nextValue(512))
	})

	t.Run("Java Port 3", func(t *testing.T) {
		// [Example 3]  https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/buffer/TestMappeableArrayContainer.java#L525
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		ac.iaddRange(200, 501)
		ac.iaddRange(5000, 5201)

		assert.Equal(t, 64, ac.nextValue(0))
		assert.Equal(t, 64, ac.nextValue(63))
		assert.Equal(t, 64, ac.nextValue(64))
		assert.Equal(t, 65, ac.nextValue(65))
		assert.Equal(t, 128, ac.nextValue(128))
		assert.Equal(t, 200, ac.nextValue(129))
		assert.Equal(t, 200, ac.nextValue(199))
		assert.Equal(t, 200, ac.nextValue(200))
		assert.Equal(t, 250, ac.nextValue(250))
		assert.Equal(t, 5000, ac.nextValue(2500))
		assert.Equal(t, 5000, ac.nextValue(5000))
		assert.Equal(t, 5200, ac.nextValue(5200))
		assert.Equal(t, -1, ac.nextValue(5201))
	})
}

func TestNextAbsentValueArray(t *testing.T) {
	t.Run("Java Port 1", func(t *testing.T) {
		// [Java 1]  https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestArrayContainer.java#L850
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		assert.Equal(t, 0, ac.nextAbsentValue(0))
		assert.Equal(t, 63, ac.nextAbsentValue(63))
		assert.Equal(t, 129, ac.nextAbsentValue(64))
		assert.Equal(t, 129, ac.nextAbsentValue(65))
		assert.Equal(t, 129, ac.nextAbsentValue(128))
		assert.Equal(t, 129, ac.nextAbsentValue(129))
	})

	t.Run("Java Port 2", func(t *testing.T) {
		// [Example 2] https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestArrayContainer.java#L861
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		ac.iaddRange(200, 501)
		ac.iaddRange(5000, 5201)
		assert.Equal(t, 0, ac.nextAbsentValue(0))
		assert.Equal(t, 63, ac.nextAbsentValue(63))
		assert.Equal(t, 129, ac.nextAbsentValue(64))
		assert.Equal(t, 129, ac.nextAbsentValue(65))
		assert.Equal(t, 129, ac.nextAbsentValue(128))
		assert.Equal(t, 129, ac.nextAbsentValue(129))
		assert.Equal(t, 199, ac.nextAbsentValue(199))
		assert.Equal(t, 501, ac.nextAbsentValue(200))
		assert.Equal(t, 501, ac.nextAbsentValue(250))
		assert.Equal(t, 2500, ac.nextAbsentValue(2500))
		assert.Equal(t, 5201, ac.nextAbsentValue(5000))
		assert.Equal(t, 5201, ac.nextAbsentValue(5200))
	})

	t.Run("Java Port 3", func(t *testing.T) {
		// [Java  3]  https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestArrayContainer.java#L878
		ac := newArrayContainer()
		for i := 0; i < 1000; i++ {
			assert.Equal(t, i, ac.nextAbsentValue(uint16(i)))
		}
	})
}

func TestPreviousValueArray(t *testing.T) {
	t.Run("Java Port 1", func(t *testing.T) {
		// [Example 1] https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestArrayContainer.java#L721
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		assert.Equal(t, -1, ac.previousValue(0))
		assert.Equal(t, -1, ac.previousValue(63))
		assert.Equal(t, 64, ac.previousValue(64))
		assert.Equal(t, 65, ac.previousValue(65))
		assert.Equal(t, 128, ac.previousValue(128))
		assert.Equal(t, 128, ac.previousValue(129))
	})

	t.Run("Java Port 2", func(t *testing.T) {
		// [Example 2]   https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestArrayContainer.java#L733
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		ac.iaddRange(200, 501)
		ac.iaddRange(5000, 5201)
		assert.Equal(t, -1, ac.previousValue(0))
		assert.Equal(t, -1, ac.previousValue(63))
		assert.Equal(t, 64, ac.previousValue(64))
		assert.Equal(t, 65, ac.previousValue(65))
		assert.Equal(t, 128, ac.previousValue(128))
		assert.Equal(t, 128, ac.previousValue(129))
		assert.Equal(t, 128, ac.previousValue(199))
		assert.Equal(t, 200, ac.previousValue(200))
		assert.Equal(t, 250, ac.previousValue(250))
		assert.Equal(t, 500, ac.previousValue(2500))
		assert.Equal(t, 5000, ac.previousValue(5000))
		assert.Equal(t, 5200, ac.previousValue(5200))
	})

	t.Run("Java Port 3", func(t *testing.T) {
		// [Example 3] https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestArrayContainer.java#L751
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		assert.Equal(t, -1, ac.previousValue(5))
	})
}

// uint16(65535)+1 wraps to 0.
func TestArrayContainerNextAbsentValueAtEnd(t *testing.T) {
	t.Run("One value at the end", func(t *testing.T) {
		ac := newArrayContainer()
		ac.iadd(65535)
		assert.Equal(t, 1<<16, ac.nextAbsentValue(65535))
	})

	t.Run("Two values at the end", func(t *testing.T) {
		ac := newArrayContainer()
		ac.iadd(65534)
		ac.iadd(65535)
		assert.Equal(t, 1<<16, ac.nextAbsentValue(65534))
		assert.Equal(t, 1<<16, ac.nextAbsentValue(65535))
	})

	t.Run("In a bitmap", func(t *testing.T) {
		bmp := BitmapOf(1, 65535)
		assert.Equal(t, int64(65536), bmp.NextAbsentValue(65535))
	})
}

func TestPreviousAbsentValueArray(t *testing.T) {
	t.Run("Java Port 1", func(t *testing.T) {
		// [Example 1] https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestArrayContainer.java#L793
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		assert.Equal(t, 0, ac.previousAbsentValue(0))
		assert.Equal(t, 63, ac.previousAbsentValue(63))
		assert.Equal(t, 63, ac.previousAbsentValue(64))
		assert.Equal(t, 63, ac.previousAbsentValue(65))
		assert.Equal(t, 63, ac.previousAbsentValue(128))
		assert.Equal(t, 129, ac.previousAbsentValue(129))
	})

	t.Run("Java Port 2", func(t *testing.T) {
		// [Example 2] https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestArrayContainer.java#L804
		ac := newArrayContainer()
		ac.iaddRange(64, 129)
		ac.iaddRange(200, 500)
		ac.iaddRange(5000, 5201)
		assert.Equal(t, 0, ac.previousAbsentValue(0))
		assert.Equal(t, 63, ac.previousAbsentValue(63))
		assert.Equal(t, 63, ac.previousAbsentValue(64))
		assert.Equal(t, 63, ac.previousAbsentValue(65))
		assert.Equal(t, 63, ac.previousAbsentValue(128))
		assert.Equal(t, 129, ac.previousAbsentValue(129))
		assert.Equal(t, 199, ac.previousAbsentValue(199))
		assert.Equal(t, 199, ac.previousAbsentValue(200))
		assert.Equal(t, 199, ac.previousAbsentValue(250))
		assert.Equal(t, 2500, ac.previousAbsentValue(2500))
		assert.Equal(t, 4999, ac.previousAbsentValue(5000))
		assert.Equal(t, 4999, ac.previousAbsentValue(5200))
	})

	t.Run("Java Port 3", func(t *testing.T) {
		// [Example 3] https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestArrayContainer.java#L821
		ac := newArrayContainer()
		for i := 0; i < 1000; i++ {
			assert.Equal(t, i, ac.previousAbsentValue(uint16(i)))
		}
	})
}

func TestArrayContainerValidation(t *testing.T) {
	array := newArrayContainer()
	upperBound := arrayDefaultMaxSize

	err := array.validate()
	assert.Error(t, err)

	for i := 0; i < upperBound; i++ {
		array.iadd(uint16(i))
	}
	err = array.validate()
	assert.NoError(t, err)

	// Introduce a sort error
	// We know that upperbound is unsorted because we populated up to upperbound
	array.content[500] = uint16(upperBound + upperBound)

	err = array.validate()
	assert.ErrorIs(t, err, ErrArrayIncorrectSort)

	// Adjacent duplicates must be rejected (strictly increasing), matching
	// CRoaring, Java, and Rust validators (previous >= next).
	array = newArrayContainer()
	for i := 0; i < 10; i++ {
		array.iadd(uint16(i))
	}
	array.content[5] = array.content[4]
	err = array.validate()
	assert.ErrorIs(t, err, ErrArrayIncorrectSort)

	// Repeated iadd of the same value is a no-op; container stays valid.
	array = newArrayContainer()
	for i := 0; i < upperBound; i++ {
		array.iadd(uint16(1))
	}
	err = array.validate()
	assert.NoError(t, err)

	array = newArrayContainer()

	for i := 0; i < 2*upperBound; i++ {
		array.iadd(uint16(i))
	}
	err = array.validate()
	assert.Error(t, err)
}

// go test -bench BenchmarkShortIteratorAdvance -run -
func BenchmarkShortIteratorAdvanceArray(b *testing.B) {
	benchmarkContainerIteratorAdvance(b, newArrayContainer())
}

// go test -bench BenchmarkShortIteratorNext -run -
func BenchmarkShortIteratorNextArray(b *testing.B) {
	benchmarkContainerIteratorNext(b, newArrayContainer())
}