roaring_test.go

package roaring

import (
	"bytes"
	"fmt"
	"math"
	"math/rand"
	"strconv"
	"testing"

	"github.com/bits-and-blooms/bitset"
	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

func TestIssue440(t *testing.T) {
	a := NewBitmap()
	a.AddMany([]uint32{1, 2, 3})
	a.RunOptimize()
	b1, err := a.MarshalBinary()
	require.NoError(t, err)
	a.RunOptimize()
	b2, err := a.MarshalBinary()
	require.NoError(t, err)
	require.Equal(t, b1, b2)
}

func TestIssue440_2(t *testing.T) {
	a := NewBitmap()
	a.AddMany([]uint32{1, 2, 3, 4})
	a.RunOptimize()
	b1, err := a.MarshalBinary()
	require.NoError(t, err)
	a.RunOptimize()
	b2, err := a.MarshalBinary()
	require.NoError(t, err)
	require.Equal(t, b1, b2)
}

func TestIssue440_3(t *testing.T) {
	a := NewBitmap()
	a.AddMany([]uint32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13})
	a.RunOptimize()
	b1, err := a.MarshalBinary()
	require.NoError(t, err)
	a.RunOptimize()
	b2, err := a.MarshalBinary()
	require.NoError(t, err)
	require.Equal(t, b1, b2)
}

func TestIssue440_4(t *testing.T) {
	a := NewBitmap()
	a.AddMany([]uint32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13})
	a.RunOptimize()
	b1, err := a.MarshalBinary()
	require.NoError(t, err)
	a.RunOptimize()
	b2, err := a.MarshalBinary()
	require.NoError(t, err)
	require.Equal(t, b1, b2)
}

func TestIssue440_5(t *testing.T) {
	a := NewBitmap()
	a.AddMany([]uint32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14})
	a.RunOptimize()
	b1, err := a.MarshalBinary()
	require.NoError(t, err)
	a.RunOptimize()
	b2, err := a.MarshalBinary()
	require.NoError(t, err)
	require.Equal(t, b1, b2)
}

func checkValidity(t *testing.T, rb *Bitmap) {
	t.Helper()

	for _, c := range rb.highlowcontainer.containers {
		switch c.(type) {
		case *arrayContainer:
			if c.getCardinality() > arrayDefaultMaxSize {
				t.Error("Array containers are limited to size ", arrayDefaultMaxSize)
			}
		case *bitmapContainer:
			if c.getCardinality() <= arrayDefaultMaxSize {
				t.Error("Bitmaps would be more concise as an array!")
			}
		case *runContainer16:
			if c.getSizeInBytes() > minOfInt(bitmapContainerSizeInBytes(), arrayContainerSizeInBytes(c.getCardinality())) {
				t.Error("Inefficient run container!")
			}
		}
	}
}

func hashTest(t *testing.T, N uint64) {
	hashes := map[uint64]struct{}{}
	count := 0

	for gap := uint64(1); gap <= 65536; gap *= 2 {
		rb1, rb2 := NewBitmap(), NewBitmap()
		for x := uint64(0); x <= N*gap; x += gap {
			rb1.AddInt(int(x))
			rb2.AddInt(int(x))
		}

		assert.EqualValues(t, rb1.Checksum(), rb2.Checksum())
		count++
		hashes[rb1.Checksum()] = struct{}{}

		rb1, rb2 = NewBitmap(), NewBitmap()
		for x := uint64(0); x <= N*gap; x += gap {
			// x+3 guarantees runs, gap/2 guarantees some variety
			if x+3+gap/2 > MaxUint32 {
				break
			}
			rb1.AddRange(uint64(x), uint64(x+3+gap/2))
			rb2.AddRange(uint64(x), uint64(x+3+gap/2))
		}

		rb1.RunOptimize()
		rb2.RunOptimize()

		assert.EqualValues(t, rb1.Checksum(), rb2.Checksum())
		count++
		hashes[rb1.Checksum()] = struct{}{}
	}

	// Make sure that at least for this reduced set we have no collisions.
	assert.Equal(t, count, len(hashes))
}

func buildRuns(includeBroken bool) *runContainer16 {
	rc := &runContainer16{}
	if includeBroken {
		for i := 0; i < 100; i++ {
			start := i * 100
			end := start + 100
			rc.iv = append(rc.iv, newInterval16Range(uint16(start), uint16(end)))
		}
	}

	for i := 0; i < 100; i++ {
		start := i*100 + i*2
		end := start + 100
		rc.iv = append(rc.iv, newInterval16Range(uint16(start), uint16(end)))
	}

	return rc
}

func TestReverseIteratorCount(t *testing.T) {
	array := []int{2, 63, 64, 65, 4095, 4096, 4097, 4159, 4160, 4161, 5000, 20000, 66666}
	for _, testSize := range array {
		b := New()
		for i := uint32(0); i < uint32(testSize); i++ {
			b.Add(i)
		}
		it := b.ReverseIterator()
		count := 0
		for it.HasNext() {
			it.Next()
			count++
		}

		assert.Equal(t, testSize, count)
	}
}

func TestRoaringIntervalCheck(t *testing.T) {
	r := BitmapOf(1, 2, 3, 1000)
	rangeb := New()
	rangeb.AddRange(10, 1000+1)

	assert.True(t, r.Intersects(rangeb))

	rangeb2 := New()
	rangeb2.AddRange(10, 1000)

	assert.False(t, r.Intersects(rangeb2))
}

func TestRoaringRangeEnd(t *testing.T) {
	r := New()
	r.Add(MaxUint32)
	assert.EqualValues(t, 1, r.GetCardinality())

	r.RemoveRange(0, MaxUint32)
	assert.EqualValues(t, 1, r.GetCardinality())

	r.RemoveRange(0, math.MaxUint64)
	assert.EqualValues(t, 0, r.GetCardinality())

	r.Add(MaxUint32)
	assert.EqualValues(t, 1, r.GetCardinality())

	r.RemoveRange(0, 0x100000001)
	assert.EqualValues(t, 0, r.GetCardinality())

	r.Add(MaxUint32)
	assert.EqualValues(t, 1, r.GetCardinality())

	r.RemoveRange(0, 0x100000000)
	assert.EqualValues(t, 0, r.GetCardinality())
}

func TestMaxPanic(t *testing.T) {
	defer func() {
		if r := recover(); r != nil {
		}
	}()
	bm := New()
	bm.Maximum()
	t.Errorf("The code did not panic")
}

func TestMinPanic(t *testing.T) {
	defer func() {
		if r := recover(); r != nil {
		}
	}()
	bm := New()
	bm.Minimum()
	t.Errorf("The code did not panic")
}

func TestFirstLast(t *testing.T) {
	bm := New()
	bm.AddInt(2)
	bm.AddInt(4)
	bm.AddInt(8)

	assert.EqualValues(t, 2, bm.Minimum())
	assert.EqualValues(t, 8, bm.Maximum())

	i := 1 << 5

	for ; i < (1 << 17); i++ {
		bm.AddInt(i)

		assert.EqualValues(t, 2, bm.Minimum())
		assert.EqualValues(t, i, bm.Maximum())
	}

	bm.RunOptimize()

	assert.EqualValues(t, 2, bm.Minimum())
	assert.EqualValues(t, i-1, bm.Maximum())
}

func TestRoaringBitmapBitmapOf(t *testing.T) {
	array := []uint32{5580, 33722, 44031, 57276, 83097}
	bmp := BitmapOf(array...)

	assert.EqualValues(t, len(array), bmp.GetCardinality())

	by, _ := bmp.ToBytes()

	assert.EqualValues(t, len(by), bmp.GetSerializedSizeInBytes())
}

func TestRoaringBitmapAdd(t *testing.T) {
	array := []uint32{5580, 33722, 44031, 57276, 83097}
	bmp := New()
	for _, v := range array {
		bmp.Add(v)
	}

	assert.EqualValues(t, len(array), bmp.GetCardinality())
}

func TestRoaringBitmapAddMany(t *testing.T) {
	array := []uint32{5580, 33722, 44031, 57276, 83097}
	bmp := NewBitmap()
	bmp.AddMany(array)

	assert.EqualValues(t, len(array), bmp.GetCardinality())
}

func testAddOffset(t *testing.T, arr []uint32, offset int64) {
	expected := make([]uint32, 0, len(arr))
	for _, i := range arr {
		v := int64(i) + offset
		if v >= 0 && v <= MaxUint32 {
			expected = append(expected, uint32(v))
		}
	}

	bmp := NewBitmap()
	bmp.AddMany(arr)

	cop := AddOffset64(bmp, offset)

	if !assert.EqualValues(t, len(expected), cop.GetCardinality()) {
		t.Logf("Applying offset %d", offset)
	}
	if !assert.EqualValues(t, expected, cop.ToArray()) {
		t.Logf("Applying offset %d", offset)
	}

	// Now check backing off gets us back all non-discarded numbers
	expected2 := make([]uint32, 0, len(expected))
	for _, i := range expected {
		v := int64(i) - offset
		if v >= 0 && v <= MaxUint32 {
			expected2 = append(expected2, uint32(v))
		}
	}

	cop2 := AddOffset64(cop, -offset)

	if !assert.EqualValues(t, len(expected2), cop2.GetCardinality()) {
		t.Logf("Restoring from offset %d", offset)
	}
	if !assert.EqualValues(t, expected2, cop2.ToArray()) {
		t.Logf("Restoring from offset %d", offset)
	}
}

func TestRoaringBitmapAddOffset(t *testing.T) {
	type testCase struct {
		arr    []uint32
		offset int64
	}
	cases := []testCase{
		{
			arr:    []uint32{5580, 33722, 44031, 57276, 83097},
			offset: 25000,
		},
		{
			arr:    []uint32{5580, 33722, 44031, 57276, 83097},
			offset: -25000,
		},
		{
			arr:    []uint32{5580, 33722, 44031, 57276, 83097},
			offset: -83097,
		},
		{
			arr:    []uint32{5580, 33722, 44031, 57276, 83097},
			offset: MaxUint32,
		},
		{
			arr:    []uint32{5580, 33722, 44031, 57276, 83097},
			offset: -MaxUint32,
		},
		{
			arr:    []uint32{5580, 33722, 44031, 57276, 83097},
			offset: 0,
		},
		{
			arr:    []uint32{0},
			offset: 100,
		},
		{
			arr:    []uint32{0},
			offset: 0xffff0000,
		},
		{
			arr:    []uint32{0},
			offset: 0xffff0001,
		},
	}

	arr := []uint32{10, 0xffff, 0x010101}
	for i := uint32(100000); i < 200000; i += 4 {
		arr = append(arr, i)
	}
	arr = append(arr, 400000)
	arr = append(arr, 1400000)
	for offset := int64(3); offset < 1000000; offset *= 3 {
		c := testCase{arr, offset}
		cases = append(cases, c)
	}
	for offset := int64(1024); offset < 1000000; offset *= 2 {
		c := testCase{arr, offset}
		cases = append(cases, c)
	}

	for _, c := range cases {
		// Positive offset
		testAddOffset(t, c.arr, c.offset)
		// Negative offset
		testAddOffset(t, c.arr, -c.offset)
	}
}

func TestRoaringInPlaceAndNotBitmapContainer(t *testing.T) {
	bm := NewBitmap()
	for i := 0; i < 8192; i++ {
		bm.Add(uint32(i))
	}
	toRemove := NewBitmap()
	for i := 128; i < 8192; i++ {
		toRemove.Add(uint32(i))
	}
	bm.AndNot(toRemove)

	var b bytes.Buffer
	_, err := bm.WriteTo(&b)

	require.NoError(t, err)

	bm2 := NewBitmap()
	bm2.ReadFrom(bytes.NewBuffer(b.Bytes()))

	assert.True(t, bm2.Equals(bm))
}

// https://github.com/RoaringBitmap/roaring/issues/64
func TestFlip64(t *testing.T) {
	bm := New()
	bm.AddInt(0)
	bm.Flip(1, 2)
	i := bm.Iterator()

	assert.False(t, i.Next() != 0 || i.Next() != 1 || i.HasNext())
}

// https://github.com/RoaringBitmap/roaring/issues/64
func TestFlip64Off(t *testing.T) {
	bm := New()
	bm.AddInt(10)
	bm.Flip(11, 12)
	i := bm.Iterator()

	assert.False(t, i.Next() != 10 || i.Next() != 11 || i.HasNext())
}

func TestStringer(t *testing.T) {
	v := NewBitmap()
	for i := uint32(0); i < 10; i++ {
		v.Add(i)
	}

	assert.Equal(t, "{0,1,2,3,4,5,6,7,8,9}", v.String())

	v.RunOptimize()

	assert.Equal(t, "{0,1,2,3,4,5,6,7,8,9}", v.String())
}

func TestFastCard(t *testing.T) {
	bm := NewBitmap()
	bm.Add(1)
	bm.AddRange(21, 260000)
	bm2 := NewBitmap()
	bm2.Add(25)

	assert.EqualValues(t, 1, bm2.AndCardinality(bm))
	assert.Equal(t, bm.GetCardinality(), bm2.OrCardinality(bm))
	assert.EqualValues(t, 1, bm.AndCardinality(bm2))
	assert.Equal(t, bm.GetCardinality(), bm.OrCardinality(bm2))
	assert.EqualValues(t, 1, bm2.AndCardinality(bm))
	assert.Equal(t, bm.GetCardinality(), bm2.OrCardinality(bm))

	bm.RunOptimize()

	assert.EqualValues(t, 1, bm2.AndCardinality(bm))
	assert.Equal(t, bm.GetCardinality(), bm2.OrCardinality(bm))
	assert.EqualValues(t, 1, bm.AndCardinality(bm2))
	assert.Equal(t, bm.GetCardinality(), bm.OrCardinality(bm2))
	assert.EqualValues(t, 1, bm2.AndCardinality(bm))
	assert.Equal(t, bm.GetCardinality(), bm2.OrCardinality(bm))
}

func TestFastCardUnequalKeys(t *testing.T) {
	// These tests will excercise the interior code branches of OrCardinality

	t.Run("Merge small into large", func(t *testing.T) {
		bm := NewBitmap()
		bm.AddRange(0, 1024)
		bm2 := NewBitmap()
		start := uint64(2 << 16)
		bm2.AddRange(start, start+3)

		assert.Equal(t, uint64(1027), bm2.OrCardinality(bm))
	})
	t.Run("Merge large into small", func(t *testing.T) {
		bm := NewBitmap()
		bm.AddRange(0, 1024)
		bm2 := NewBitmap()
		start := uint64(2 << 16)
		bm2.AddRange(start, start+3)

		assert.Equal(t, uint64(1027), bm.OrCardinality(bm2))
	})

	t.Run("Merge large into small same keyrange start", func(t *testing.T) {
		bm := NewBitmap()
		start := uint64(2 << 16)
		bm.AddRange(0, 1024)
		bm.AddRange(start, start+3)

		bm2 := NewBitmap()
		bm2.AddRange(0, 512)
		bm2.AddRange(start, start+3)

		assert.Equal(t, uint64(1027), bm.OrCardinality(bm2))
	})
}

func TestIntersects1(t *testing.T) {
	bm := NewBitmap()
	bm.Add(1)
	bm.AddRange(21, 26)
	bm2 := NewBitmap()
	bm2.Add(25)

	assert.True(t, bm2.Intersects(bm))

	bm.Remove(25)
	assert.Equal(t, false, bm2.Intersects(bm))

	bm.AddRange(1, 100000)
	assert.True(t, bm2.Intersects(bm))
}

func TestIntersectsWithInterval(t *testing.T) {
	bm := NewBitmap()
	bm.AddRange(21, 26)

	// Empty interval in range
	assert.False(t, bm.IntersectsWithInterval(22, 22))
	// Empty interval out of range
	assert.False(t, bm.IntersectsWithInterval(27, 27))

	// Non-empty interval in range, fully included
	assert.True(t, bm.IntersectsWithInterval(22, 23))
	// Non-empty intervals partially overlapped
	assert.True(t, bm.IntersectsWithInterval(19, 23))
	assert.True(t, bm.IntersectsWithInterval(23, 30))
	// Non-empty interval covering the full range
	assert.True(t, bm.IntersectsWithInterval(19, 30))

	// Non-empty interval before start of bitmap
	assert.False(t, bm.IntersectsWithInterval(19, 20))
	// Non-empty interval after end of bitmap
	assert.False(t, bm.IntersectsWithInterval(28, 30))

	// Non-empty interval inside "hole" in bitmap
	bm.AddRange(30, 40)
	assert.False(t, bm.IntersectsWithInterval(28, 29))

	// Non-empty interval, non-overlapping on the open side
	assert.False(t, bm.IntersectsWithInterval(28, 30))
	// Non-empty interval, overlapping on the open side
	assert.True(t, bm.IntersectsWithInterval(28, 31))
}

func TestRangePanic(t *testing.T) {
	bm := NewBitmap()
	bm.Add(1)
	bm.AddRange(21, 26)
	bm.AddRange(9, 14)
	bm.AddRange(11, 16)
}

func TestRangeRemoval(t *testing.T) {
	bm := NewBitmap()
	bm.Add(1)
	bm.AddRange(21, 26)
	bm.AddRange(9, 14)
	bm.RemoveRange(11, 16)
	bm.RemoveRange(1, 26)
	c := bm.GetCardinality()

	assert.EqualValues(t, 0, c)

	bm.AddRange(1, 10000)
	c = bm.GetCardinality()

	assert.EqualValues(t, 10000-1, c)

	bm.RemoveRange(1, 10000)
	c = bm.GetCardinality()

	assert.EqualValues(t, 0, c)
}

func TestRangeRemovalFromContent(t *testing.T) {
	bm := NewBitmap()
	for i := 100; i < 10000; i++ {
		bm.AddInt(i * 3)
	}
	bm.AddRange(21, 26)
	bm.AddRange(9, 14)
	bm.RemoveRange(11, 16)
	bm.RemoveRange(0, 30000)
	c := bm.GetCardinality()

	assert.EqualValues(t, 0o0, c)
}

func TestFlipOnEmpty(t *testing.T) {
	t.Run("TestFlipOnEmpty in-place", func(t *testing.T) {
		bm := NewBitmap()
		bm.Flip(0, 10)
		c := bm.GetCardinality()

		assert.EqualValues(t, 10, c)
	})

	t.Run("TestFlipOnEmpty, generating new result", func(t *testing.T) {
		bm := NewBitmap()
		bm = Flip(bm, 0, 10)
		c := bm.GetCardinality()

		assert.EqualValues(t, 10, c)
	})
}

func TestBitmapRank2(t *testing.T) {
	r := NewBitmap()
	for i := uint32(1); i < 8194; i += 2 {
		r.Add(i)
	}

	rank := r.Rank(63)
	assert.EqualValues(t, 32, rank)
}

func TestBitmapRank(t *testing.T) {
	for N := uint32(1); N <= 1048576; N *= 2 {
		t.Run("rank tests"+strconv.Itoa(int(N)), func(t *testing.T) {
			for gap := uint32(1); gap <= 65536; gap *= 2 {
				rb1 := NewBitmap()
				for x := uint32(0); x <= N; x += gap {
					rb1.Add(x)
				}
				for y := uint32(0); y <= N; y++ {
					if rb1.Rank(y) != uint64((y+1+gap-1)/gap) {
						assert.Equal(t, (y+1+gap-1)/gap, rb1.Rank(y))
					}
				}
			}
		})
	}
}

func TestBitmapSelect(t *testing.T) {
	for N := uint32(1); N <= 1048576; N *= 2 {
		t.Run("rank tests"+strconv.Itoa(int(N)), func(t *testing.T) {
			for gap := uint32(1); gap <= 65536; gap *= 2 {
				rb1 := NewBitmap()
				for x := uint32(0); x <= N; x += gap {
					rb1.Add(x)
				}
				for y := uint32(0); y <= N/gap; y++ {
					expectedInt := y * gap
					i, err := rb1.Select(y)
					if err != nil {
						t.Fatal(err)
					}

					if i != expectedInt {
						assert.Equal(t, expectedInt, i)
					}
				}
			}
		})
	}
}

// some extra tests
func TestBitmapExtra(t *testing.T) {
	for N := uint32(1); N <= 65536; N *= 2 {
		t.Run("extra tests"+strconv.Itoa(int(N)), func(t *testing.T) {
			for gap := uint32(1); gap <= 65536; gap *= 2 {
				bs1 := bitset.New(0)
				rb1 := NewBitmap()
				for x := uint32(0); x <= N; x += gap {
					bs1.Set(uint(x))
					rb1.Add(x)
				}

				assert.EqualValues(t, rb1.GetCardinality(), bs1.Count())
				assert.True(t, equalsBitSet(bs1, rb1))

				for offset := uint32(1); offset <= gap; offset *= 2 {
					bs2 := bitset.New(0)
					rb2 := NewBitmap()
					for x := uint32(0); x <= N; x += gap {
						bs2.Set(uint(x + offset))
						rb2.Add(x + offset)
					}

					assert.EqualValues(t, rb2.GetCardinality(), bs2.Count())
					assert.True(t, equalsBitSet(bs2, rb2))

					clonebs1 := bs1.Clone()
					clonebs1.InPlaceIntersection(bs2)

					if !equalsBitSet(clonebs1, And(rb1, rb2)) {
						v := rb1.Clone()
						v.And(rb2)

						assert.True(t, equalsBitSet(clonebs1, v))
					}

					// testing OR
					clonebs1 = bs1.Clone()
					clonebs1.InPlaceUnion(bs2)

					assert.True(t, equalsBitSet(clonebs1, Or(rb1, rb2)))
					// testing XOR
					clonebs1 = bs1.Clone()
					clonebs1.InPlaceSymmetricDifference(bs2)
					assert.True(t, equalsBitSet(clonebs1, Xor(rb1, rb2)))

					// testing NOTAND
					clonebs1 = bs1.Clone()
					clonebs1.InPlaceDifference(bs2)
					assert.True(t, equalsBitSet(clonebs1, AndNot(rb1, rb2)))
				}
			}
		})
	}
}

func FlipRange(start, end int, bs *bitset.BitSet) {
	for i := start; i < end; i++ {
		bs.Flip(uint(i))
	}
}

func TestBitmap(t *testing.T) {
	t.Run("Test Contains", func(t *testing.T) {
		rbm1 := NewBitmap()
		for k := 0; k < 1000; k++ {
			rbm1.AddInt(17 * k)
		}

		for k := 0; k < 17*1000; k++ {
			assert.Equal(t, (k/17*17 == k), rbm1.ContainsInt(k))
		}
	})

	t.Run("Test Clone", func(t *testing.T) {
		rb1 := NewBitmap()
		rb1.Add(10)

		rb2 := rb1.Clone()
		rb2.Remove(10)

		assert.True(t, rb1.Contains(10))
	})

	t.Run("Test run array not equal", func(t *testing.T) {
		rb := NewBitmap()
		rb2 := NewBitmap()
		rb.AddRange(0, 1<<16)
		for i := 0; i < 10; i++ {
			rb2.AddInt(i)
		}

		assert.EqualValues(t, 1<<16, rb.GetCardinality())
		assert.EqualValues(t, 10, rb2.GetCardinality())
		assert.False(t, rb.Equals(rb2))

		rb.RunOptimize()
		rb2.RunOptimize()

		assert.EqualValues(t, 1<<16, rb.GetCardinality())
		assert.EqualValues(t, 10, rb2.GetCardinality())
		assert.False(t, rb.Equals(rb2))
	})

	t.Run("Test ANDNOT4", func(t *testing.T) {
		rb := NewBitmap()
		rb2 := NewBitmap()

		for i := 0; i < 200000; i += 4 {
			rb2.AddInt(i)
		}
		for i := 200000; i < 400000; i += 14 {
			rb2.AddInt(i)
		}

		off := AndNot(rb2, rb)
		andNotresult := AndNot(rb, rb2)

		assert.True(t, rb.Equals(andNotresult))
		assert.True(t, rb2.Equals(off))

		rb2.AndNot(rb)
		assert.True(t, rb2.Equals(off))
	})

	t.Run("Test AND", func(t *testing.T) {
		rr := NewBitmap()
		for k := 0; k < 4000; k++ {
			rr.AddInt(k)
		}
		rr.Add(100000)
		rr.Add(110000)
		rr2 := NewBitmap()
		rr2.Add(13)
		rrand := And(rr, rr2)
		array := rrand.ToArray()

		assert.Equal(t, 1, len(array))
		assert.EqualValues(t, 13, array[0])

		rr.And(rr2)
		array = rr.ToArray()

		assert.Equal(t, 1, len(array))
		assert.EqualValues(t, 13, array[0])
	})

	t.Run("Test AND 2", func(t *testing.T) {
		rr := NewBitmap()
		for k := 4000; k < 4256; k++ {
			rr.AddInt(k)
		}
		for k := 65536; k < 65536+4000; k++ {
			rr.AddInt(k)
		}
		for k := 3 * 65536; k < 3*65536+9000; k++ {
			rr.AddInt(k)
		}
		for k := 4 * 65535; k < 4*65535+7000; k++ {
			rr.AddInt(k)
		}
		for k := 6 * 65535; k < 6*65535+10000; k++ {
			rr.AddInt(k)
		}
		for k := 8 * 65535; k < 8*65535+1000; k++ {
			rr.AddInt(k)
		}
		for k := 9 * 65535; k < 9*65535+30000; k++ {
			rr.AddInt(k)
		}

		rr2 := NewBitmap()
		for k := 4000; k < 4256; k++ {
			rr2.AddInt(k)
		}
		for k := 65536; k < 65536+4000; k++ {
			rr2.AddInt(k)
		}
		for k := 3*65536 + 2000; k < 3*65536+6000; k++ {
			rr2.AddInt(k)
		}
		for k := 6 * 65535; k < 6*65535+1000; k++ {
			rr2.AddInt(k)
		}
		for k := 7 * 65535; k < 7*65535+1000; k++ {
			rr2.AddInt(k)
		}
		for k := 10 * 65535; k < 10*65535+5000; k++ {
			rr2.AddInt(k)
		}
		correct := And(rr, rr2)
		rr.And(rr2)

		assert.True(t, correct.Equals(rr))
	})

	t.Run("Test AND 2", func(t *testing.T) {
		rr := NewBitmap()
		for k := 0; k < 4000; k++ {
			rr.AddInt(k)
		}
		rr.AddInt(100000)
		rr.AddInt(110000)
		rr2 := NewBitmap()
		rr2.AddInt(13)

		rrand := And(rr, rr2)
		array := rrand.ToArray()

		assert.Equal(t, 1, len(array))
		assert.EqualValues(t, 13, array[0])
	})

	t.Run("Test AND 3a", func(t *testing.T) {
		rr := NewBitmap()
		rr2 := NewBitmap()
		for k := 6 * 65536; k < 6*65536+10000; k++ {
			rr.AddInt(k)
		}
		for k := 6 * 65536; k < 6*65536+1000; k++ {
			rr2.AddInt(k)
		}
		result := And(rr, rr2)

		assert.EqualValues(t, 1000, result.GetCardinality())
	})

	t.Run("Test AND 3", func(t *testing.T) {
		var arrayand [11256]uint32
		// 393,216
		pos := 0
		rr := NewBitmap()
		for k := 4000; k < 4256; k++ {
			rr.AddInt(k)
		}
		for k := 65536; k < 65536+4000; k++ {
			rr.AddInt(k)
		}
		for k := 3 * 65536; k < 3*65536+1000; k++ {
			rr.AddInt(k)
		}
		for k := 3*65536 + 1000; k < 3*65536+7000; k++ {
			rr.AddInt(k)
		}
		for k := 3*65536 + 7000; k < 3*65536+9000; k++ {
			rr.AddInt(k)
		}
		for k := 4 * 65536; k < 4*65536+7000; k++ {
			rr.AddInt(k)
		}
		for k := 8 * 65536; k < 8*65536+1000; k++ {
			rr.AddInt(k)
		}
		for k := 9 * 65536; k < 9*65536+30000; k++ {
			rr.AddInt(k)
		}

		rr2 := NewBitmap()
		for k := 4000; k < 4256; k++ {
			rr2.AddInt(k)
			arrayand[pos] = uint32(k)
			pos++
		}
		for k := 65536; k < 65536+4000; k++ {
			rr2.AddInt(k)
			arrayand[pos] = uint32(k)
			pos++
		}
		for k := 3*65536 + 1000; k < 3*65536+7000; k++ {
			rr2.AddInt(k)
			arrayand[pos] = uint32(k)
			pos++
		}
		for k := 6 * 65536; k < 6*65536+10000; k++ {
			rr.AddInt(k)
		}
		for k := 6 * 65536; k < 6*65536+1000; k++ {
			rr2.AddInt(k)
			arrayand[pos] = uint32(k)
			pos++
		}

		for k := 7 * 65536; k < 7*65536+1000; k++ {
			rr2.AddInt(k)
		}
		for k := 10 * 65536; k < 10*65536+5000; k++ {
			rr2.AddInt(k)
		}
		rrand := And(rr, rr2)

		arrayres := rrand.ToArray()
		ok := true
		for i := range arrayres {
			if i < len(arrayand) {
				if arrayres[i] != arrayand[i] {
					t.Log(i, arrayres[i], arrayand[i])
					ok = false
				}
			} else {
				t.Log('x', arrayres[i])
				ok = false
			}
		}

		assert.Equal(t, len(arrayres), len(arrayand))
		assert.True(t, ok)
	})

	t.Run("Test AND 4", func(t *testing.T) {
		rb := NewBitmap()
		rb2 := NewBitmap()

		for i := 0; i < 200000; i += 4 {
			rb2.AddInt(i)
		}
		for i := 200000; i < 400000; i += 14 {
			rb2.AddInt(i)
		}
		// TODO: Bitmap.And(bm,bm2)
		andresult := And(rb, rb2)
		off := And(rb2, rb)

		assert.True(t, andresult.Equals(off))
		assert.EqualValues(t, 0, andresult.GetCardinality())

		for i := 500000; i < 600000; i += 14 {
			rb.AddInt(i)
		}
		for i := 200000; i < 400000; i += 3 {
			rb2.AddInt(i)
		}
		andresult2 := And(rb, rb2)

		assert.EqualValues(t, 0, andresult.GetCardinality())
		assert.EqualValues(t, 0, andresult2.GetCardinality())

		for i := 0; i < 200000; i += 4 {
			rb.AddInt(i)
		}
		for i := 200000; i < 400000; i += 14 {
			rb.AddInt(i)
		}

		assert.EqualValues(t, 0, andresult.GetCardinality())

		rc := And(rb, rb2)
		rb.And(rb2)

		assert.Equal(t, rb.GetCardinality(), rc.GetCardinality())
	})

	t.Run("ArrayContainerCardinalityTest", func(t *testing.T) {
		ac := newArrayContainer()
		for k := uint16(0); k < 100; k++ {
			ac.iadd(k)
			assert.EqualValues(t, k+1, ac.getCardinality())
		}
		for k := uint16(0); k < 100; k++ {
			ac.iadd(k)
			assert.EqualValues(t, 100, ac.getCardinality())
		}
	})

	t.Run("or test", func(t *testing.T) {
		rr := NewBitmap()
		for k := 0; k < 4000; k++ {
			rr.AddInt(k)
		}
		rr2 := NewBitmap()
		for k := 4000; k < 8000; k++ {
			rr2.AddInt(k)
		}
		result := Or(rr, rr2)

		assert.Equal(t, rr.GetCardinality()+rr2.GetCardinality(), result.GetCardinality())
	})

	t.Run("basic test", func(t *testing.T) {
		rr := NewBitmap()
		var a [4002]uint32
		pos := 0
		for k := 0; k < 4000; k++ {
			rr.AddInt(k)
			a[pos] = uint32(k)
			pos++
		}
		rr.AddInt(100000)
		a[pos] = 100000
		pos++
		rr.AddInt(110000)
		a[pos] = 110000
		pos++
		array := rr.ToArray()
		ok := true
		for i := range a {
			if array[i] != a[i] {
				t.Log("rr : ", array[i], " a : ", a[i])
				ok = false
			}
		}

		assert.Equal(t, len(a), len(array))
		assert.True(t, ok)
	})

	t.Run("BitmapContainerCardinalityTest", func(t *testing.T) {
		ac := newBitmapContainer()
		for k := uint16(0); k < 100; k++ {
			ac.iadd(k)
			assert.EqualValues(t, k+1, ac.getCardinality())
		}
		for k := uint16(0); k < 100; k++ {
			ac.iadd(k)
			assert.EqualValues(t, 100, ac.getCardinality())
		}
	})

	t.Run("BitmapContainerTest", func(t *testing.T) {
		rr := newBitmapContainer()
		rr.iadd(uint16(110))
		rr.iadd(uint16(114))
		rr.iadd(uint16(115))
		var array [3]uint16
		pos := 0
		for itr := rr.getShortIterator(); itr.hasNext(); {
			array[pos] = itr.next()
			pos++
		}

		assert.EqualValues(t, 110, array[0])
		assert.EqualValues(t, 114, array[1])
		assert.EqualValues(t, 115, array[2])
	})

	t.Run("cardinality test", func(t *testing.T) {
		N := 1024
		for gap := 7; gap < 100000; gap *= 10 {
			for offset := 2; offset <= 1024; offset *= 2 {
				rb := NewBitmap()
				for k := 0; k < N; k++ {
					rb.AddInt(k * gap)
					assert.EqualValues(t, k+1, rb.GetCardinality())
				}

				assert.EqualValues(t, N, rb.GetCardinality())

				// check the add of existing values
				for k := 0; k < N; k++ {
					rb.AddInt(k * gap)
					assert.EqualValues(t, N, rb.GetCardinality())
				}

				rb2 := NewBitmap()

				for k := 0; k < N; k++ {
					rb2.AddInt(k * gap * offset)
					assert.EqualValues(t, k+1, rb2.GetCardinality())
				}

				assert.EqualValues(t, N, rb2.GetCardinality())

				for k := 0; k < N; k++ {
					rb2.AddInt(k * gap * offset)
					assert.EqualValues(t, N, rb2.GetCardinality())
				}

				assert.EqualValues(t, N/offset, And(rb, rb2).GetCardinality())
				assert.EqualValues(t, 2*N-2*N/offset, Xor(rb, rb2).GetCardinality())
				assert.EqualValues(t, 2*N-N/offset, Or(rb, rb2).GetCardinality())
			}
		}
	})

	t.Run("clear test", func(t *testing.T) {
		rb := NewBitmap()
		for i := 0; i < 200000; i += 7 {
			// dense
			rb.AddInt(i)
		}
		for i := 200000; i < 400000; i += 177 {
			// sparse
			rb.AddInt(i)
		}

		rb2 := NewBitmap()
		rb3 := NewBitmap()
		for i := 0; i < 200000; i += 4 {
			rb2.AddInt(i)
		}
		for i := 200000; i < 400000; i += 14 {
			rb2.AddInt(i)
		}

		rb.Clear()

		assert.EqualValues(t, 0, rb.GetCardinality())
		assert.NotEqual(t, 0, rb2.GetCardinality())

		rb.AddInt(4)
		rb3.AddInt(4)
		andresult := And(rb, rb2)
		orresult := Or(rb, rb2)

		assert.EqualValues(t, 1, andresult.GetCardinality())
		assert.Equal(t, rb2.GetCardinality(), orresult.GetCardinality())

		for i := 0; i < 200000; i += 4 {
			rb.AddInt(i)
			rb3.AddInt(i)
		}
		for i := 200000; i < 400000; i += 114 {
			rb.AddInt(i)
			rb3.AddInt(i)
		}
		checkValidity(t, rb)
		checkValidity(t, rb2)
		checkValidity(t, rb3)
		arrayrr := rb.ToArray()
		arrayrr3 := rb3.ToArray()
		ok := true
		for i := range arrayrr {
			if arrayrr[i] != arrayrr3[i] {
				ok = false
			}
		}

		assert.Equal(t, len(arrayrr3), len(arrayrr))
		assert.True(t, ok)
	})

	t.Run("container factory ", func(t *testing.T) {
		bc1 := newBitmapContainer()
		bc2 := newBitmapContainer()
		bc3 := newBitmapContainer()
		ac1 := newArrayContainer()
		ac2 := newArrayContainer()
		ac3 := newArrayContainer()

		for i := 0; i < 5000; i++ {
			bc1.iadd(uint16(i * 70))
		}
		for i := 0; i < 5000; i++ {
			bc2.iadd(uint16(i * 70))
		}
		for i := 0; i < 5000; i++ {
			bc3.iadd(uint16(i * 70))
		}
		for i := 0; i < 4000; i++ {
			ac1.iadd(uint16(i * 50))
		}
		for i := 0; i < 4000; i++ {
			ac2.iadd(uint16(i * 50))
		}
		for i := 0; i < 4000; i++ {
			ac3.iadd(uint16(i * 50))
		}

		rbc := ac1.clone().(*arrayContainer).toBitmapContainer()
		validate(t, rbc, ac1)

		rbc = ac2.clone().(*arrayContainer).toBitmapContainer()
		validate(t, rbc, ac2)

		rbc = ac3.clone().(*arrayContainer).toBitmapContainer()
		validate(t, rbc, ac3)
	})

	t.Run("flipTest1 ", func(t *testing.T) {
		rb := NewBitmap()
		rb.Flip(100000, 200000) // in-place on empty bitmap
		rbcard := rb.GetCardinality()

		assert.EqualValues(t, 100000, rbcard)

		bs := bitset.New(20000 - 10000)
		for i := uint(100000); i < 200000; i++ {
			bs.Set(i)
		}

		assert.True(t, equalsBitSet(bs, rb))
	})

	t.Run("flipTest1A", func(t *testing.T) {
		rb := NewBitmap()
		rb1 := Flip(rb, 100000, 200000)
		rbcard := rb1.GetCardinality()

		assert.EqualValues(t, 100000, rbcard)
		assert.EqualValues(t, 0, rb.GetCardinality())

		bs := bitset.New(0)
		assert.True(t, equalsBitSet(bs, rb))

		for i := uint(100000); i < 200000; i++ {
			bs.Set(i)
		}
		checkValidity(t, rb1)
		checkValidity(t, rb)
		assert.True(t, equalsBitSet(bs, rb1))
	})

	t.Run("flipTest2", func(t *testing.T) {
		rb := NewBitmap()
		rb.Flip(100000, 100000)
		rbcard := rb.GetCardinality()

		assert.EqualValues(t, 0, rbcard)

		bs := bitset.New(0)
		assert.True(t, equalsBitSet(bs, rb))
	})

	t.Run("flipTest2A", func(t *testing.T) {
		rb := NewBitmap()
		rb1 := Flip(rb, 100000, 100000)

		rb.AddInt(1)
		rbcard := rb1.GetCardinality()

		assert.EqualValues(t, 0, rbcard)
		assert.EqualValues(t, 1, rb.GetCardinality())

		bs := bitset.New(0)
		assert.True(t, equalsBitSet(bs, rb1))

		bs.Set(1)
		assert.True(t, equalsBitSet(bs, rb))
	})

	t.Run("flipTest3A", func(t *testing.T) {
		rb := NewBitmap()
		rb.Flip(100000, 200000) // got 100k-199999
		rb.Flip(100000, 199991) // give back 100k-199990
		rbcard := rb.GetCardinality()

		assert.EqualValues(t, 9, rbcard)

		bs := bitset.New(0)
		for i := uint(199991); i < 200000; i++ {
			bs.Set(i)
		}

		assert.True(t, equalsBitSet(bs, rb))
	})

	t.Run("flipTest4A", func(t *testing.T) {
		// fits evenly on both ends
		rb := NewBitmap()
		rb.Flip(100000, 200000) // got 100k-199999
		rb.Flip(65536, 4*65536)
		rbcard := rb.GetCardinality()

		// 65536 to 99999 are 1s
		// 200000 to 262143 are 1s: total card

		assert.EqualValues(t, 96608, rbcard)

		bs := bitset.New(0)
		for i := uint(65536); i < 100000; i++ {
			bs.Set(i)
		}
		for i := uint(200000); i < 262144; i++ {
			bs.Set(i)
		}

		assert.True(t, equalsBitSet(bs, rb))
	})

	t.Run("flipTest5", func(t *testing.T) {
		// fits evenly on small end, multiple
		// containers
		rb := NewBitmap()
		rb.Flip(100000, 132000)
		rb.Flip(65536, 120000)
		rbcard := rb.GetCardinality()

		// 65536 to 99999 are 1s
		// 120000 to 131999

		assert.EqualValues(t, 46464, rbcard)

		bs := bitset.New(0)
		for i := uint(65536); i < 100000; i++ {
			bs.Set(i)
		}
		for i := uint(120000); i < 132000; i++ {
			bs.Set(i)
		}

		assert.True(t, equalsBitSet(bs, rb))
	})

	t.Run("flipTest6", func(t *testing.T) {
		rb := NewBitmap()
		rb1 := Flip(rb, 100000, 132000)
		rb2 := Flip(rb1, 65536, 120000)
		// rbcard := rb2.GetCardinality()

		bs := bitset.New(0)
		for i := uint(65536); i < 100000; i++ {
			bs.Set(i)
		}
		for i := uint(120000); i < 132000; i++ {
			bs.Set(i)
		}

		assert.True(t, equalsBitSet(bs, rb2))
	})

	t.Run("flipTest6A", func(t *testing.T) {
		rb := NewBitmap()
		rb1 := Flip(rb, 100000, 132000)
		rb2 := Flip(rb1, 99000, 2*65536)
		rbcard := rb2.GetCardinality()

		assert.EqualValues(t, rbcard, 1928)

		bs := bitset.New(0)
		for i := uint(99000); i < 100000; i++ {
			bs.Set(i)
		}
		for i := uint(2 * 65536); i < 132000; i++ {
			bs.Set(i)
		}
		assert.True(t, equalsBitSet(bs, rb2))
	})

	t.Run("flipTest7", func(t *testing.T) {
		// within 1 word, first container
		rb := NewBitmap()
		rb.Flip(650, 132000)
		rb.Flip(648, 651)
		rbcard := rb.GetCardinality()

		// 648, 649, 651-131999

		assert.EqualValues(t, rbcard, 132000-651+2)

		bs := bitset.New(0)
		bs.Set(648)
		bs.Set(649)
		for i := uint(651); i < 132000; i++ {
			bs.Set(i)
		}

		assert.True(t, equalsBitSet(bs, rb))
	})

	t.Run("flipTestBig", func(t *testing.T) {
		numCases := 1000
		rb := NewBitmap()
		bs := bitset.New(0)
		// Random r = new Random(3333);
		checkTime := 2.0

		for i := 0; i < numCases; i++ {
			start := rand.Intn(65536 * 20)
			end := rand.Intn(65536 * 20)
			if rand.Float64() < float64(0.1) {
				end = start + rand.Intn(100)
			}
			rb.Flip(uint64(start), uint64(end))
			if start < end {
				FlipRange(start, end, bs) // throws exception
			}
			// otherwise
			// insert some more ANDs to keep things sparser
			if rand.Float64() < 0.2 {
				mask := NewBitmap()
				mask1 := bitset.New(0)
				startM := rand.Intn(65536 * 20)
				endM := startM + 100000
				mask.Flip(uint64(startM), uint64(endM))
				FlipRange(startM, endM, mask1)
				mask.Flip(0, 65536*20+100000)
				FlipRange(0, 65536*20+100000, mask1)
				rb.And(mask)
				bs.InPlaceIntersection(mask1)
			}
			// see if we can detect incorrectly shared containers
			if rand.Float64() < 0.1 {
				irrelevant := Flip(rb, 10, 100000)
				irrelevant.Flip(5, 200000)
				irrelevant.Flip(190000, 260000)
			}
			if float64(i) > checkTime {
				assert.True(t, equalsBitSet(bs, rb))
				checkTime *= 1.5
			}
		}
	})

	t.Run("ortest", func(t *testing.T) {
		rr := NewBitmap()
		for k := 0; k < 4000; k++ {
			rr.AddInt(k)
		}
		rr.AddInt(100000)
		rr.AddInt(110000)
		rr2 := NewBitmap()
		for k := 0; k < 4000; k++ {
			rr2.AddInt(k)
		}

		rror := Or(rr, rr2)

		array := rror.ToArray()

		rr.Or(rr2)
		arrayirr := rr.ToArray()

		assert.True(t, IntsEquals(array, arrayirr))
	})

	t.Run("ORtest", func(t *testing.T) {
		rr := NewBitmap()
		for k := 4000; k < 4256; k++ {
			rr.AddInt(k)
		}
		for k := 65536; k < 65536+4000; k++ {
			rr.AddInt(k)
		}
		for k := 3 * 65536; k < 3*65536+9000; k++ {
			rr.AddInt(k)
		}
		for k := 4 * 65535; k < 4*65535+7000; k++ {
			rr.AddInt(k)
		}
		for k := 6 * 65535; k < 6*65535+10000; k++ {
			rr.AddInt(k)
		}
		for k := 8 * 65535; k < 8*65535+1000; k++ {
			rr.AddInt(k)
		}
		for k := 9 * 65535; k < 9*65535+30000; k++ {
			rr.AddInt(k)
		}

		rr2 := NewBitmap()
		for k := 4000; k < 4256; k++ {
			rr2.AddInt(k)
		}
		for k := 65536; k < 65536+4000; k++ {
			rr2.AddInt(k)
		}
		for k := 3*65536 + 2000; k < 3*65536+6000; k++ {
			rr2.AddInt(k)
		}
		for k := 6 * 65535; k < 6*65535+1000; k++ {
			rr2.AddInt(k)
		}
		for k := 7 * 65535; k < 7*65535+1000; k++ {
			rr2.AddInt(k)
		}
		for k := 10 * 65535; k < 10*65535+5000; k++ {
			rr2.AddInt(k)
		}
		correct := Or(rr, rr2)
		rr.Or(rr2)

		assert.True(t, correct.Equals(rr))
	})

	t.Run("ortest2", func(t *testing.T) {
		arrayrr := make([]uint32, 4000+4000+2)
		pos := 0
		rr := NewBitmap()
		for k := 0; k < 4000; k++ {
			rr.AddInt(k)
			arrayrr[pos] = uint32(k)
			pos++
		}
		rr.AddInt(100000)
		rr.AddInt(110000)
		rr2 := NewBitmap()
		for k := 4000; k < 8000; k++ {
			rr2.AddInt(k)
			arrayrr[pos] = uint32(k)
			pos++
		}

		arrayrr[pos] = 100000
		pos++
		arrayrr[pos] = 110000
		pos++

		rror := Or(rr, rr2)

		checkValidity(t, rror)
		arrayor := rror.ToArray()

		assert.True(t, IntsEquals(arrayor, arrayrr))
	})

	t.Run("ortest3", func(t *testing.T) {
		V1 := make(map[int]bool)
		V2 := make(map[int]bool)

		rr := NewBitmap()
		rr2 := NewBitmap()
		for k := 0; k < 4000; k++ {
			rr2.AddInt(k)
			V1[k] = true
		}
		for k := 3500; k < 4500; k++ {
			rr.AddInt(k)
			V1[k] = true
		}
		for k := 4000; k < 65000; k++ {
			rr2.AddInt(k)
			V1[k] = true
		}

		// In the second node of each roaring bitmap, we have two bitmap
		// containers.
		// So, we will check the union between two BitmapContainers
		for k := 65536; k < 65536+10000; k++ {
			rr.AddInt(k)
			V1[k] = true
		}

		for k := 65536; k < 65536+14000; k++ {
			rr2.AddInt(k)
			V1[k] = true
		}

		// In the 3rd node of each Roaring Bitmap, we have an
		// ArrayContainer, so, we will try the union between two
		// ArrayContainers.
		for k := 4 * 65535; k < 4*65535+1000; k++ {
			rr.AddInt(k)
			V1[k] = true
		}

		for k := 4 * 65535; k < 4*65535+800; k++ {
			rr2.AddInt(k)
			V1[k] = true
		}

		// For the rest, we will check if the union will take them in
		// the result
		for k := 6 * 65535; k < 6*65535+1000; k++ {
			rr.AddInt(k)
			V1[k] = true
		}

		for k := 7 * 65535; k < 7*65535+2000; k++ {
			rr2.AddInt(k)
			V1[k] = true
		}

		rror := Or(rr, rr2)
		valide := true
		checkValidity(t, rror)
		for _, k := range rror.ToArray() {
			_, found := V1[int(k)]
			if !found {
				valide = false
			}
			V2[int(k)] = true
		}

		for k := range V1 {
			_, found := V2[k]
			if !found {
				valide = false
			}
		}

		assert.True(t, valide)
	})

	t.Run("ortest4", func(t *testing.T) {
		rb := NewBitmap()
		rb2 := NewBitmap()

		for i := 0; i < 200000; i += 4 {
			rb2.AddInt(i)
		}
		for i := 200000; i < 400000; i += 14 {
			rb2.AddInt(i)
		}
		rb2card := rb2.GetCardinality()

		// check or against an empty bitmap
		orresult := Or(rb, rb2)
		off := Or(rb2, rb)

		assert.True(t, orresult.Equals(off))
		assert.Equal(t, orresult.GetCardinality(), rb2card)

		for i := 500000; i < 600000; i += 14 {
			rb.AddInt(i)
		}
		for i := 200000; i < 400000; i += 3 {
			rb2.AddInt(i)
		}
		// check or against an empty bitmap
		orresult2 := Or(rb, rb2)
		checkValidity(t, orresult2)
		assert.Equal(t, orresult.GetCardinality(), rb2card)
		assert.Equal(t, rb2.GetCardinality()+rb.GetCardinality(), orresult2.GetCardinality())

		rb.Or(rb2)
		assert.True(t, rb.Equals(orresult2))
	})

	t.Run("randomTest", func(t *testing.T) {
		rTest(t, 15)
		rTest(t, 1024)
		rTest(t, 4096)
		rTest(t, 65536)
		rTest(t, 65536*16)
	})

	t.Run("SimpleCardinality", func(t *testing.T) {
		N := 512
		gap := 70

		rb := NewBitmap()
		for k := 0; k < N; k++ {
			rb.AddInt(k * gap)
			assert.EqualValues(t, k+1, rb.GetCardinality())
		}

		assert.EqualValues(t, N, rb.GetCardinality())

		for k := 0; k < N; k++ {
			rb.AddInt(k * gap)
			assert.EqualValues(t, N, rb.GetCardinality())
		}
	})

	t.Run("XORtest", func(t *testing.T) {
		rr := NewBitmap()
		for k := 4000; k < 4256; k++ {
			rr.AddInt(k)
		}
		for k := 65536; k < 65536+4000; k++ {
			rr.AddInt(k)
		}
		for k := 3 * 65536; k < 3*65536+9000; k++ {
			rr.AddInt(k)
		}
		for k := 4 * 65535; k < 4*65535+7000; k++ {
			rr.AddInt(k)
		}
		for k := 6 * 65535; k < 6*65535+10000; k++ {
			rr.AddInt(k)
		}
		for k := 8 * 65535; k < 8*65535+1000; k++ {
			rr.AddInt(k)
		}
		for k := 9 * 65535; k < 9*65535+30000; k++ {
			rr.AddInt(k)
		}

		rr2 := NewBitmap()
		for k := 4000; k < 4256; k++ {
			rr2.AddInt(k)
		}
		for k := 65536; k < 65536+4000; k++ {
			rr2.AddInt(k)
		}
		for k := 3*65536 + 2000; k < 3*65536+6000; k++ {
			rr2.AddInt(k)
		}
		for k := 6 * 65535; k < 6*65535+1000; k++ {
			rr2.AddInt(k)
		}
		for k := 7 * 65535; k < 7*65535+1000; k++ {
			rr2.AddInt(k)
		}
		for k := 10 * 65535; k < 10*65535+5000; k++ {
			rr2.AddInt(k)
		}

		correct := Xor(rr, rr2)
		checkValidity(t, correct)

		rr.Xor(rr2)

		assert.True(t, correct.Equals(rr))
	})

	t.Run("xortest1", func(t *testing.T) {
		V1 := make(map[int]bool)
		V2 := make(map[int]bool)

		rr := NewBitmap()
		rr2 := NewBitmap()
		// For the first 65536: rr2 has a bitmap container, and rr has
		// an array container.
		// We will check the union between a BitmapCintainer and an
		// arrayContainer
		for k := 0; k < 4000; k++ {
			rr2.AddInt(k)
			if k < 3500 {
				V1[k] = true
			}
		}
		for k := 3500; k < 4500; k++ {
			rr.AddInt(k)
		}
		for k := 4000; k < 65000; k++ {
			rr2.AddInt(k)
			if k >= 4500 {
				V1[k] = true
			}
		}

		for k := 65536; k < 65536+30000; k++ {
			rr.AddInt(k)
		}

		for k := 65536; k < 65536+50000; k++ {
			rr2.AddInt(k)
			if k >= 65536+30000 {
				V1[k] = true
			}
		}

		// In the 3rd node of each Roaring Bitmap, we have an
		// ArrayContainer. So, we will try the union between two
		// ArrayContainers.
		for k := 4 * 65535; k < 4*65535+1000; k++ {
			rr.AddInt(k)
			if k >= (4*65535 + 800) {
				V1[k] = true
			}
		}

		for k := 4 * 65535; k < 4*65535+800; k++ {
			rr2.AddInt(k)
		}

		for k := 6 * 65535; k < 6*65535+1000; k++ {
			rr.AddInt(k)
			V1[k] = true
		}

		for k := 7 * 65535; k < 7*65535+2000; k++ {
			rr2.AddInt(k)
			V1[k] = true
		}

		rrxor := Xor(rr, rr2)
		valide := true

		for _, i := range rrxor.ToArray() {
			_, found := V1[int(i)]
			if !found {
				valide = false
			}
			V2[int(i)] = true
		}
		for k := range V1 {
			_, found := V2[k]
			if !found {
				valide = false
			}
		}

		assert.True(t, valide)
	})
}

func TestXORtest4(t *testing.T) {
	t.Run("XORtest 4", func(t *testing.T) {
		rb := NewBitmap()
		rb2 := NewBitmap()
		counter := 0

		for i := 0; i < 200000; i += 4 {
			rb2.AddInt(i)
			counter++
		}

		assert.EqualValues(t, counter, rb2.GetCardinality())

		for i := 200000; i < 400000; i += 14 {
			rb2.AddInt(i)
			counter++
		}

		assert.EqualValues(t, counter, rb2.GetCardinality())

		rb2card := rb2.GetCardinality()
		assert.EqualValues(t, counter, rb2card)

		// check or against an empty bitmap
		xorresult := Xor(rb, rb2)
		assert.EqualValues(t, counter, xorresult.GetCardinality())
		off := Or(rb2, rb)

		assert.EqualValues(t, counter, off.GetCardinality())
		assert.True(t, xorresult.Equals(off))

		assert.Equal(t, xorresult.GetCardinality(), rb2card)
		for i := 500000; i < 600000; i += 14 {
			rb.AddInt(i)
		}
		for i := 200000; i < 400000; i += 3 {
			rb2.AddInt(i)
		}
		// check or against an empty bitmap
		xorresult2 := Xor(rb, rb2)

		assert.EqualValues(t, xorresult.GetCardinality(), rb2card)
		assert.Equal(t, xorresult2.GetCardinality(), rb2.GetCardinality()+rb.GetCardinality())

		rb.Xor(rb2)
		assert.True(t, xorresult2.Equals(rb))
	})
	// need to add the massives
}

func TestNextMany(t *testing.T) {
	count := 70000

	for _, gap := range []uint32{1, 8, 32, 128} {
		expected := make([]uint32, count)
		{
			v := uint32(0)
			for i := range expected {
				expected[i] = v
				v += gap
			}
		}
		bm := BitmapOf(expected...)
		for _, bufSize := range []int{1, 64, 4096, count} {
			buf := make([]uint32, bufSize)
			it := bm.ManyIterator()
			cur := 0
			for n := it.NextMany(buf); n != 0; n = it.NextMany(buf) {
				// much faster tests... (10s -> 5ms)
				if cur+n > count {
					assert.LessOrEqual(t, count, cur+n)
				}

				for i, v := range buf[:n] {
					// much faster tests...
					if v != expected[cur+i] {
						assert.Equal(t, expected[cur+i], v)
					}
				}

				cur += n
			}

			assert.Equal(t, count, cur)
		}
	}
}

func TestBigRandom(t *testing.T) {
	rTest(t, 15)
	rTest(t, 100)
	rTest(t, 512)
	rTest(t, 1023)
	rTest(t, 1025)
	rTest(t, 4095)
	rTest(t, 4096)
	rTest(t, 4097)
	rTest(t, 65536)
	rTest(t, 65536*16)
}

func TestHash(t *testing.T) {
	hashTest(t, 15)
	hashTest(t, 100)
	hashTest(t, 512)
	hashTest(t, 1023)
	hashTest(t, 1025)
	hashTest(t, 4095)
	hashTest(t, 4096)
	hashTest(t, 4097)
}

func rTest(t *testing.T, N int) {
	for gap := 1; gap <= 65536; gap *= 2 {
		bs1 := bitset.New(0)
		rb1 := NewBitmap()
		for x := 0; x <= N; x += gap {
			bs1.Set(uint(x))
			rb1.AddInt(x)
		}

		assert.EqualValues(t, rb1.GetCardinality(), bs1.Count())
		assert.True(t, equalsBitSet(bs1, rb1))

		for offset := 1; offset <= gap; offset *= 2 {
			bs2 := bitset.New(0)
			rb2 := NewBitmap()
			for x := 0; x <= N; x += gap {
				bs2.Set(uint(x + offset))
				rb2.AddInt(x + offset)
			}

			assert.EqualValues(t, rb2.GetCardinality(), bs2.Count())
			assert.True(t, equalsBitSet(bs2, rb2))

			clonebs1 := bs1.Clone()
			clonebs1.InPlaceIntersection(bs2)

			if !equalsBitSet(clonebs1, And(rb1, rb2)) {
				v := rb1.Clone()
				v.And(rb2)
				assert.True(t, equalsBitSet(clonebs1, v))
			}

			// testing OR
			clonebs1 = bs1.Clone()
			clonebs1.InPlaceUnion(bs2)

			assert.True(t, equalsBitSet(clonebs1, Or(rb1, rb2)))

			// testing XOR
			clonebs1 = bs1.Clone()
			clonebs1.InPlaceSymmetricDifference(bs2)

			assert.True(t, equalsBitSet(clonebs1, Xor(rb1, rb2)))

			// testing NOTAND
			clonebs1 = bs1.Clone()
			clonebs1.InPlaceDifference(bs2)

			assert.True(t, equalsBitSet(clonebs1, AndNot(rb1, rb2)))
		}
	}
}

func equalsBitSet(a *bitset.BitSet, b *Bitmap) bool {
	for i, e := a.NextSet(0); e; i, e = a.NextSet(i + 1) {
		if !b.ContainsInt(int(i)) {
			return false
		}
	}
	i := b.Iterator()
	for i.HasNext() {
		if !a.Test(uint(i.Next())) {
			return false
		}
	}
	return true
}

func equalsArray(a []int, b *Bitmap) bool {
	if uint64(len(a)) != b.GetCardinality() {
		return false
	}
	for _, x := range a {
		if !b.ContainsInt(x) {
			return false
		}
	}
	return true
}

func IntsEquals(a, b []uint32) bool {
	if len(a) != len(b) {
		return false
	}
	for i, v := range a {
		if v != b[i] {
			return false
		}
	}
	return true
}

func validate(t *testing.T, bc *bitmapContainer, ac *arrayContainer) {
	// Checking the cardinalities of each container
	t.Helper()

	if bc.getCardinality() != ac.getCardinality() {
		t.Error("cardinality differs")
	}
	// Checking that the two containers contain the same values
	counter := 0

	for i := bc.NextSetBit(0); i >= 0; i = bc.NextSetBit(uint(i) + 1) {
		counter++
		if !ac.contains(uint16(i)) {
			t.Log("content differs")
			t.Log(bc)
			t.Log(ac)
			t.Fail()
		}

	}

	// checking the cardinality of the BitmapContainer
	assert.Equal(t, counter, bc.getCardinality())
}

func TestRoaringArray(t *testing.T) {
	a := newRoaringArray()

	t.Run("Test Init", func(t *testing.T) {
		assert.Equal(t, 0, a.size())
	})

	t.Run("Test Insert", func(t *testing.T) {
		a.appendContainer(0, newArrayContainer(), false)
		assert.Equal(t, 1, a.size())
	})

	t.Run("Test Remove", func(t *testing.T) {
		a.remove(0)
		assert.Equal(t, 0, a.size())
	})

	t.Run("Test popcount Full", func(t *testing.T) {
		res := popcount(uint64(0xffffffffffffffff))
		assert.EqualValues(t, 64, res)
	})

	t.Run("Test popcount Empty", func(t *testing.T) {
		res := popcount(0)
		assert.EqualValues(t, 0, res)
	})

	t.Run("Test popcount 16", func(t *testing.T) {
		res := popcount(0xff00ff)
		assert.EqualValues(t, 16, res)
	})

	t.Run("Test ArrayContainer Add", func(t *testing.T) {
		ar := newArrayContainer()
		ar.iadd(1)

		assert.EqualValues(t, 1, ar.getCardinality())
	})

	t.Run("Test ArrayContainer Add wacky", func(t *testing.T) {
		ar := newArrayContainer()
		ar.iadd(0)
		ar.iadd(5000)

		assert.EqualValues(t, 2, ar.getCardinality())
	})

	t.Run("Test ArrayContainer Add Reverse", func(t *testing.T) {
		ar := newArrayContainer()
		ar.iadd(5000)
		ar.iadd(2048)
		ar.iadd(0)

		assert.EqualValues(t, 3, ar.getCardinality())
	})

	t.Run("Test BitmapContainer Add ", func(t *testing.T) {
		bm := newBitmapContainer()
		bm.iadd(0)

		assert.EqualValues(t, 1, bm.getCardinality())
	})
}

func TestFlipBigA(t *testing.T) {
	numCases := 1000
	bs := bitset.New(0)
	checkTime := 2.0
	rb1 := NewBitmap()
	rb2 := NewBitmap()

	for i := 0; i < numCases; i++ {
		start := rand.Intn(65536 * 20)
		end := rand.Intn(65536 * 20)
		if rand.Float64() < 0.1 {
			end = start + rand.Intn(100)
		}

		if (i & 1) == 0 {
			rb2 = FlipInt(rb1, start, end)
			// tweak the other, catch bad sharing
			rb1.FlipInt(rand.Intn(65536*20), rand.Intn(65536*20))
		} else {
			rb1 = FlipInt(rb2, start, end)
			rb2.FlipInt(rand.Intn(65536*20), rand.Intn(65536*20))
		}

		if start < end {
			FlipRange(start, end, bs) // throws exception
		}
		// otherwise
		// insert some more ANDs to keep things sparser
		if (rand.Float64() < 0.2) && (i&1) == 0 {
			mask := NewBitmap()
			mask1 := bitset.New(0)
			startM := rand.Intn(65536 * 20)
			endM := startM + 100000
			mask.FlipInt(startM, endM)
			FlipRange(startM, endM, mask1)
			mask.FlipInt(0, 65536*20+100000)
			FlipRange(0, 65536*20+100000, mask1)
			rb2.And(mask)
			bs.InPlaceIntersection(mask1)
		}

		if float64(i) > checkTime {
			var rb *Bitmap

			if (i & 1) == 0 {
				rb = rb2
			} else {
				rb = rb1
			}

			assert.True(t, equalsBitSet(bs, rb))
			checkTime *= 1.5
		}
	}
}

func TestNextManyOfAddRangeAcrossContainers(t *testing.T) {
	rb := NewBitmap()
	rb.AddRange(65530, 65540)
	expectedCard := 10
	expected := []uint32{65530, 65531, 65532, 65533, 65534, 65535, 65536, 65537, 65538, 65539, 0}

	// test where all values can be returned in a single buffer
	it := rb.ManyIterator()
	buf := make([]uint32, 11)
	n := it.NextMany(buf)

	assert.Equal(t, expectedCard, n)

	for i, e := range expected {
		assert.Equal(t, e, buf[i])
	}

	// test where buf is size 1, so many iterations
	it = rb.ManyIterator()
	n = 0
	buf = make([]uint32, 1)

	for i := 0; i < expectedCard; i++ {
		n = it.NextMany(buf)

		assert.Equal(t, 1, n)
		assert.Equal(t, expected[i], buf[0])
	}

	n = it.NextMany(buf)
	assert.Equal(t, 0, n)
}

func TestDoubleAdd(t *testing.T) {
	t.Run("doubleadd ", func(t *testing.T) {
		rb := NewBitmap()
		rb.AddRange(65533, 65536)
		rb.AddRange(65530, 65536)
		rb2 := NewBitmap()
		rb2.AddRange(65530, 65536)

		assert.True(t, rb.Equals(rb2))

		rb2.RemoveRange(65530, 65536)

		assert.EqualValues(t, 0, rb2.GetCardinality())
	})

	t.Run("doubleadd2 ", func(t *testing.T) {
		rb := NewBitmap()
		rb.AddRange(65533, 65536*20)
		rb.AddRange(65530, 65536*20)
		rb2 := NewBitmap()
		rb2.AddRange(65530, 65536*20)

		assert.True(t, rb.Equals(rb2))

		rb2.RemoveRange(65530, 65536*20)

		assert.EqualValues(t, 0, rb2.GetCardinality())
	})

	t.Run("doubleadd3 ", func(t *testing.T) {
		rb := NewBitmap()
		rb.AddRange(65533, 65536*20+10)
		rb.AddRange(65530, 65536*20+10)
		rb2 := NewBitmap()
		rb2.AddRange(65530, 65536*20+10)

		assert.True(t, rb.Equals(rb2))

		rb2.RemoveRange(65530, 65536*20+1)

		assert.EqualValues(t, 9, rb2.GetCardinality())
	})

	t.Run("doubleadd4 ", func(t *testing.T) {
		rb := NewBitmap()
		rb.AddRange(65533, 65536*20)
		rb.RemoveRange(65533+5, 65536*20)

		assert.EqualValues(t, 5, rb.GetCardinality())
	})

	t.Run("doubleadd5 ", func(t *testing.T) {
		rb := NewBitmap()
		rb.AddRange(65533, 65536*20)
		rb.RemoveRange(65533+5, 65536*20-5)

		assert.EqualValues(t, 10, rb.GetCardinality())
	})

	t.Run("doubleadd6 ", func(t *testing.T) {
		rb := NewBitmap()
		rb.AddRange(65533, 65536*20-5)
		rb.RemoveRange(65533+5, 65536*20-10)

		assert.EqualValues(t, 10, rb.GetCardinality())
	})

	t.Run("doubleadd7 ", func(t *testing.T) {
		rb := NewBitmap()
		rb.AddRange(65533, 65536*20+1)
		rb.RemoveRange(65533+1, 65536*20)

		assert.EqualValues(t, 2, rb.GetCardinality())
	})

	t.Run("AndNotBug01 ", func(t *testing.T) {
		rb1 := NewBitmap()
		rb1.AddRange(0, 60000)
		rb2 := NewBitmap()
		rb2.AddRange(60000-10, 60000+10)
		rb2.AndNot(rb1)
		rb3 := NewBitmap()
		rb3.AddRange(60000, 60000+10)

		assert.True(t, rb2.Equals(rb3))
	})
}

func TestAndNot(t *testing.T) {
	rr := NewBitmap()

	for k := 4000; k < 4256; k++ {
		rr.AddInt(k)
	}
	for k := 65536; k < 65536+4000; k++ {
		rr.AddInt(k)
	}
	for k := 3 * 65536; k < 3*65536+9000; k++ {
		rr.AddInt(k)
	}
	for k := 4 * 65535; k < 4*65535+7000; k++ {
		rr.AddInt(k)
	}
	for k := 6 * 65535; k < 6*65535+10000; k++ {
		rr.AddInt(k)
	}
	for k := 8 * 65535; k < 8*65535+1000; k++ {
		rr.AddInt(k)
	}
	for k := 9 * 65535; k < 9*65535+30000; k++ {
		rr.AddInt(k)
	}

	rr2 := NewBitmap()

	for k := 4000; k < 4256; k++ {
		rr2.AddInt(k)
	}
	for k := 65536; k < 65536+4000; k++ {
		rr2.AddInt(k)
	}
	for k := 3*65536 + 2000; k < 3*65536+6000; k++ {
		rr2.AddInt(k)
	}
	for k := 6 * 65535; k < 6*65535+1000; k++ {
		rr2.AddInt(k)
	}
	for k := 7 * 65535; k < 7*65535+1000; k++ {
		rr2.AddInt(k)
	}
	for k := 10 * 65535; k < 10*65535+5000; k++ {
		rr2.AddInt(k)
	}

	correct := AndNot(rr, rr2)
	rr.AndNot(rr2)

	assert.True(t, correct.Equals(rr))
}

func TestStats(t *testing.T) {
	t.Run("Test Stats with empty bitmap", func(t *testing.T) {
		expectedStats := Statistics{}
		rr := NewBitmap()

		assert.EqualValues(t, expectedStats, rr.Stats())
	})

	t.Run("Test Stats with bitmap Container", func(t *testing.T) {
		// Given a bitmap that should have a single bitmap container
		expectedStats := Statistics{
			Cardinality: 60000,
			Containers:  1,

			BitmapContainers:      1,
			BitmapContainerValues: 60000,
			BitmapContainerBytes:  8192,

			RunContainers:      0,
			RunContainerBytes:  0,
			RunContainerValues: 0,
		}

		rr := NewBitmap()

		for i := uint32(0); i < 60000; i++ {
			rr.Add(i)
		}

		assert.EqualValues(t, expectedStats, rr.Stats())
	})

	t.Run("Test Stats with Array Container", func(t *testing.T) {
		// Given a bitmap that should have a single array container
		expectedStats := Statistics{
			Cardinality: 2,
			Containers:  1,

			ArrayContainers:      1,
			ArrayContainerValues: 2,
			ArrayContainerBytes:  4,
		}
		rr := NewBitmap()
		rr.Add(2)
		rr.Add(4)

		assert.EqualValues(t, expectedStats, rr.Stats())
	})
}

func TestFlipVerySmall(t *testing.T) {
	rb := NewBitmap()
	rb.Flip(0, 10) // got [0,9], card is 10
	rb.Flip(0, 1)  // give back the number 0, card goes to 9
	rbcard := rb.GetCardinality()

	assert.EqualValues(t, 9, rbcard)
}

func TestReverseIterator(t *testing.T) {
	t.Run("#1", func(t *testing.T) {
		values := []uint32{0, 2, 15, 16, 31, 32, 33, 9999, MaxUint16, MaxUint32}
		bm := New()
		for n := 0; n < len(values); n++ {
			bm.Add(values[n])
		}
		i := bm.ReverseIterator()
		n := len(values) - 1

		for i.HasNext() {
			assert.EqualValues(t, i.Next(), values[n])
			n--
		}

		// HasNext() was terminating early - add test
		i = bm.ReverseIterator()
		n = len(values) - 1
		for ; n >= 0; n-- {
			assert.EqualValues(t, i.Next(), values[n])
			assert.False(t, n > 0 && !i.HasNext())
		}
	})

	t.Run("#2", func(t *testing.T) {
		bm := New()
		i := bm.ReverseIterator()

		assert.False(t, i.HasNext())
	})

	t.Run("#3", func(t *testing.T) {
		bm := New()
		bm.AddInt(0)
		i := bm.ReverseIterator()

		assert.True(t, i.HasNext())
		assert.EqualValues(t, 0, i.Next())
		assert.False(t, i.HasNext())
	})

	t.Run("#4", func(t *testing.T) {
		bm := New()
		bm.AddInt(9999)
		i := bm.ReverseIterator()

		assert.True(t, i.HasNext())
		assert.EqualValues(t, 9999, i.Next())
		assert.False(t, i.HasNext())
	})

	t.Run("#5", func(t *testing.T) {
		bm := New()
		bm.AddInt(MaxUint16)
		i := bm.ReverseIterator()

		assert.True(t, i.HasNext())
		assert.EqualValues(t, MaxUint16, i.Next())
		assert.False(t, i.HasNext())
	})

	t.Run("#6", func(t *testing.T) {
		bm := New()
		bm.Add(MaxUint32)
		i := bm.ReverseIterator()

		assert.True(t, i.HasNext())
		assert.EqualValues(t, uint32(MaxUint32), i.Next())
		assert.False(t, i.HasNext())
	})
}

func TestIteratorPeekNext(t *testing.T) {
	values := []uint32{0, 2, 15, 16, 31, 32, 33, 9999, MaxUint16, MaxUint32}
	bm := New()

	for n := 0; n < len(values); n++ {
		bm.Add(values[n])
	}

	i := bm.Iterator()
	assert.True(t, i.HasNext())

	for i.HasNext() {
		assert.Equal(t, i.PeekNext(), i.Next())
	}
}

func TestIteratorAdvance(t *testing.T) {
	values := []uint32{1, 2, 15, 16, 31, 32, 33, 9999, MaxUint16}
	bm := New()

	for n := 0; n < len(values); n++ {
		bm.Add(values[n])
	}

	cases := []struct {
		minval   uint32
		expected uint32
	}{
		{0, 1},
		{1, 1},
		{2, 2},
		{3, 15},
		{30, 31},
		{33, 33},
		{9998, 9999},
		{MaxUint16, MaxUint16},
	}

	t.Run("advance by using a new int iterator", func(t *testing.T) {
		for _, c := range cases {
			i := bm.Iterator()
			i.AdvanceIfNeeded(c.minval)

			assert.True(t, i.HasNext())
			assert.Equal(t, c.expected, i.PeekNext())
		}
	})

	t.Run("advance by using the same int iterator", func(t *testing.T) {
		i := bm.Iterator()

		for _, c := range cases {
			i.AdvanceIfNeeded(c.minval)

			assert.True(t, i.HasNext())
			assert.Equal(t, c.expected, i.PeekNext())
		}
	})

	t.Run("advance out of a container value", func(t *testing.T) {
		i := bm.Iterator()

		i.AdvanceIfNeeded(MaxUint32)
		assert.False(t, i.HasNext())

		i.AdvanceIfNeeded(MaxUint32)
		assert.False(t, i.HasNext())
	})

	t.Run("advance on a value that is less than the pointed value", func(t *testing.T) {
		i := bm.Iterator()
		i.AdvanceIfNeeded(29)

		assert.True(t, i.HasNext())
		assert.EqualValues(t, 31, i.PeekNext())

		i.AdvanceIfNeeded(13)

		assert.True(t, i.HasNext())
		assert.EqualValues(t, 31, i.PeekNext())
	})
}

func TestPackageFlipMaxRangeEnd(t *testing.T) {
	var empty Bitmap
	flipped := Flip(&empty, 0, MaxRange)

	assert.EqualValues(t, MaxRange, flipped.GetCardinality())
}

func TestBitmapFlipMaxRangeEnd(t *testing.T) {
	var bm Bitmap
	bm.Flip(0, MaxRange)

	assert.EqualValues(t, MaxRange, bm.GetCardinality())
}

func TestIterate(t *testing.T) {
	rb := NewBitmap()

	for i := 0; i < 300; i++ {
		rb.Add(uint32(i))
	}

	var values []uint32
	rb.Iterate(func(x uint32) bool {
		values = append(values, x)
		return true
	})

	assert.Equal(t, rb.ToArray(), values)
}

func TestIterateCompressed(t *testing.T) {
	rb := NewBitmap()

	for i := 0; i < 300; i++ {
		rb.Add(uint32(i))
	}

	rb.RunOptimize()

	var values []uint32
	rb.Iterate(func(x uint32) bool {
		values = append(values, x)
		return true
	})

	assert.Equal(t, rb.ToArray(), values)
}

func TestIterateLargeValues(t *testing.T) {
	rb := NewBitmap()

	// This range of values ensures that all different types of containers will be used
	for i := 150000; i < 450000; i++ {
		rb.Add(uint32(i))
	}

	var values []uint32
	rb.Iterate(func(x uint32) bool {
		values = append(values, x)
		return true
	})

	assert.Equal(t, rb.ToArray(), values)
}

func TestIterateHalt(t *testing.T) {
	rb := NewBitmap()

	// This range of values ensures that all different types of containers will be used
	for i := 150000; i < 450000; i++ {
		rb.Add(uint32(i))
	}

	var values []uint32
	count := uint64(0)
	stopAt := rb.GetCardinality() - 1
	rb.Iterate(func(x uint32) bool {
		values = append(values, x)
		count++
		if count == stopAt {
			return false
		}
		return true
	})

	expected := rb.ToArray()
	expected = expected[0 : len(expected)-1]
	assert.Equal(t, expected, values)
}

func testDense(fn func(string, *Bitmap)) {
	bc := New()
	for i := 0; i <= arrayDefaultMaxSize; i++ {
		bc.Add(uint32(1 + MaxUint16 + i*2))
	}

	rc := New()
	rc.AddRange(1, 2)
	rc.AddRange(bc.GetCardinality(), bc.GetCardinality()*2)

	ac := New()
	for i := 1; i <= arrayDefaultMaxSize; i++ {
		ac.Add(uint32(MaxUint16 + i*2))
	}

	brc := New()
	for i := 150000; i < 450000; i++ {
		brc.Add(uint32(i))
	}

	for _, tc := range []struct {
		name string
		rb   *Bitmap
	}{
		{"bitmap", bc},
		{"run", rc},
		{"array", ac},
		{"bitmaps-and-runs", brc},
	} {
		fn(tc.name+"-"+strconv.FormatUint(tc.rb.GetCardinality(), 10), tc.rb)
	}
}

func TestToDense(t *testing.T) {
	testDense(func(name string, rb *Bitmap) {
		t.Run(name, func(t *testing.T) {
			bm := bitset.From(rb.ToDense())
			assert.EqualValues(t, rb.GetCardinality(), uint64(bm.Count()))
			rb.Iterate(func(x uint32) bool {
				return assert.True(t, bm.Test(uint(x)), "value %d should be set", x)
			})
		})
	})
}

func TestFromDense(t *testing.T) {
	testDense(func(name string, rb *Bitmap) {
		for _, doCopy := range []bool{false, true} {
			t.Run(fmt.Sprintf("%s,doCopy=%t", name, doCopy), func(t *testing.T) {
				dense := rb.ToDense()
				cp := FromDense(dense, doCopy)
				if doCopy {
					// Clear the original dense slice to ensure we don't have any
					// references to it
					for i := range dense {
						dense[i] = 0
					}
				}
				assert.True(t, rb.Equals(cp))
			})
		}
	})
}

func TestFromBitSet(t *testing.T) {
	testDense(func(name string, rb *Bitmap) {
		t.Run(fmt.Sprintf("%s", name), func(t *testing.T) {
			dense := rb.ToBitSet()
			cp := FromBitSet(dense)
			assert.True(t, rb.Equals(cp))
		})
	})
}

func TestRoaringArrayValidation(t *testing.T) {
	a := newRoaringArray()

	a.keys = append(a.keys, uint16(3), uint16(1))
	assert.ErrorIs(t, a.validate(), ErrKeySortOrder)
	a.clear()

	// build up cardinality coherent arrays
	a.keys = append(a.keys, uint16(1), uint16(3), uint16(10))
	assert.ErrorIs(t, a.validate(), ErrCardinalityConstraint)
	a.containers = append(a.containers, &runContainer16{}, &runContainer16{}, &runContainer16{})
	assert.ErrorIs(t, a.validate(), ErrCardinalityConstraint)
	a.needCopyOnWrite = append(a.needCopyOnWrite, true, false, true)
	assert.ErrorIs(t, a.validate(), ErrRunIntervalsEmpty)
}

func TestBitMapValidation(t *testing.T) {
	bm := NewBitmap()
	bm.AddRange(0, 100)
	bm.AddRange(306, 406)
	bm.AddRange(102, 202)
	bm.AddRange(204, 304)
	assert.NoError(t, bm.Validate())

	randomEntries := make([]uint32, 0, 1000)
	for i := 0; i < 1000; i++ {
		randomEntries = append(randomEntries, rand.Uint32())
	}

	bm.AddMany(randomEntries)
	assert.NoError(t, bm.Validate())

	randomEntries = make([]uint32, 0, 1000)
	for i := 0; i < 1000; i++ {
		randomEntries = append(randomEntries, uint32(i))
	}
	bm.AddMany(randomEntries)
	assert.NoError(t, bm.Validate())
}

func TestBitMapValidationFromDeserialization(t *testing.T) {
	// To understand what is going on here, read https://github.com/RoaringBitmap/RoaringFormatSpec
	// Maintainers: The loader and corruptor are dependent on one another
	// The tests expect a certain size, with values at certain location.
	// The tests are geared toward single byte corruption.

	// There is no way to test Bitmap container corruption once the bitmap is deserialzied

	deserializationTests := []struct {
		name      string
		loader    func(bm *Bitmap)
		corruptor func(s []byte)
		err       error
	}{
		{
			name: "Corrupts Run Length vs Num Runs",
			loader: func(bm *Bitmap) {
				bm.AddRange(0, 2)
				bm.AddRange(4, 6)
				bm.AddRange(8, 100)
			},
			corruptor: func(s []byte) {
				// 21 is the length of the run of the last run/range
				// Shortening causes interval sum to be to short
				s[21] = 1
			},
			err: ErrRunIntervalSize,
		},
		{
			name: "Corrupts Run Length",
			loader: func(bm *Bitmap) {
				bm.AddRange(100, 110)
			},
			corruptor: func(s []byte) {
				s[13] = 0
			},
			err: ErrRunIntervalSize,
		},
		{
			name: "Creates Interval Overlap",
			loader: func(bm *Bitmap) {
				bm.AddRange(100, 110)
				bm.AddRange(115, 125)
			},
			corruptor: func(s []byte) {
				// sets the start of the second run
				// Creates overlapping intervals
				s[15] = 108
			},
			err: ErrRunIntervalOverlap,
		},
		{
			name: "Break Array Sort Order",
			loader: func(bm *Bitmap) {
				arrayEntries := make([]uint32, 0, 10)
				for i := 0; i < 10; i++ {
					arrayEntries = append(arrayEntries, uint32(i))
				}
				bm.AddMany(arrayEntries)
			},
			corruptor: func(s []byte) {
				// breaks the sort order
				s[34] = 0
			},
			err: ErrArrayIncorrectSort,
		},
	}

	for _, tt := range deserializationTests {
		t.Run(tt.name, func(t *testing.T) {
			defer func() {
				if err := recover(); err != nil {
				}
			}()

			bm := NewBitmap()
			tt.loader(bm)
			assert.NoError(t, bm.Validate())
			serialized, err := bm.ToBytes()
			assert.NoError(t, err)
			tt.corruptor(serialized)
			corruptedDeserializedBitMap := NewBitmap()
			corruptedDeserializedBitMap.ReadFrom(bytes.NewReader(serialized))
			assert.ErrorIs(t, corruptedDeserializedBitMap.Validate(), tt.err)

			corruptedDeserializedBitMap = NewBitmap()
			corruptedDeserializedBitMap.MustReadFrom(bytes.NewReader(serialized))
			// We will never hit this because of the recover
			t.Errorf("did not panic")
		})
	}
}

func TestNextAndPreviousValue(t *testing.T) {
	t.Run("Java Regression1 ", func(t *testing.T) {
		// [Java1] https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestRunContainer.java#L3645
		bmp := New()
		bmp.AddRange(64, 129)
		assert.Equal(t, int64(64), bmp.NextValue(64))
		assert.Equal(t, int64(64), bmp.NextValue(0))
		assert.Equal(t, int64(64), bmp.NextValue(64))
		assert.Equal(t, int64(65), bmp.NextValue(65))
		assert.Equal(t, int64(128), bmp.NextValue(128))
		assert.Equal(t, int64(-1), bmp.NextValue(129))

		assert.Equal(t, int64(-1), bmp.PreviousValue(0))
		assert.Equal(t, int64(-1), bmp.PreviousValue(63))
		assert.Equal(t, int64(64), bmp.PreviousValue(64))
		assert.Equal(t, int64(65), bmp.PreviousValue(65))
		assert.Equal(t, int64(128), bmp.PreviousValue(128))
		assert.Equal(t, int64(128), bmp.PreviousValue(129))

		assert.Equal(t, int64(0), bmp.NextAbsentValue(0))
		assert.Equal(t, int64(63), bmp.NextAbsentValue(63))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(64))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(65))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(128))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(129))

		assert.Equal(t, int64(0), bmp.PreviousAbsentValue(0))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(63))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(64))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(65))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(128))
	})
	t.Run("Java Regression2", func(t *testing.T) {
		// [Java2] https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestRunContainer.java#L3655

		bmp := New()
		bmp.AddRange(64, 129)
		bmp.AddRange(256, 256+64+1)
		assert.Equal(t, int64(64), bmp.NextValue(0))
		assert.Equal(t, int64(64), bmp.NextValue(64))
		assert.Equal(t, int64(65), bmp.NextValue(65))
		assert.Equal(t, int64(128), bmp.NextValue(128))
		assert.Equal(t, int64(256), bmp.NextValue(129))
		assert.Equal(t, int64(-1), bmp.NextValue(512))

		assert.Equal(t, int64(-1), bmp.PreviousValue(0))
		assert.Equal(t, int64(-1), bmp.PreviousValue(63))
		assert.Equal(t, int64(64), bmp.PreviousValue(64))
		assert.Equal(t, int64(65), bmp.PreviousValue(65))
		assert.Equal(t, int64(128), bmp.PreviousValue(128))
		assert.Equal(t, int64(128), bmp.PreviousValue(129))
		assert.Equal(t, int64(128), bmp.PreviousValue(199))
		assert.Equal(t, int64(128), bmp.PreviousValue(200))
		assert.Equal(t, int64(128), bmp.PreviousValue(250))
		assert.Equal(t, int64(256), bmp.PreviousValue(256))
		assert.Equal(t, int64(320), bmp.PreviousValue(2500))

		assert.Equal(t, int64(0), bmp.NextAbsentValue(0))
		assert.Equal(t, int64(63), bmp.NextAbsentValue(63))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(64))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(65))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(128))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(129))
		assert.Equal(t, int64(199), bmp.NextAbsentValue(199))
		assert.Equal(t, int64(200), bmp.NextAbsentValue(200))
		assert.Equal(t, int64(250), bmp.NextAbsentValue(250))
		assert.Equal(t, int64(321), bmp.NextAbsentValue(256))
		assert.Equal(t, int64(321), bmp.NextAbsentValue(320))

		assert.Equal(t, int64(0), bmp.PreviousAbsentValue(0))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(63))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(64))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(65))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(128))
		assert.Equal(t, int64(129), bmp.PreviousAbsentValue(129))
		assert.Equal(t, int64(199), bmp.PreviousAbsentValue(199))
		assert.Equal(t, int64(200), bmp.PreviousAbsentValue(200))
		assert.Equal(t, int64(250), bmp.PreviousAbsentValue(250))
		assert.Equal(t, int64(255), bmp.PreviousAbsentValue(256))
		assert.Equal(t, int64(255), bmp.PreviousAbsentValue(300))
		assert.Equal(t, int64(500), bmp.PreviousAbsentValue(500))
		assert.Equal(t, int64(501), bmp.PreviousAbsentValue(501))
	})

	t.Run("Java Regression3", func(t *testing.T) {
		// [Java3] https://github.com/RoaringBitmap/RoaringBitmap/blob/5235aa62c32fa3bf7fae40a562e3edc75f61be4e/RoaringBitmap/src/test/java/org/roaringbitmap/TestRunContainer.java#L3666

		bmp := New()
		bmp.AddRange(64, 129)
		bmp.AddRange(200, 200+300+1)
		bmp.AddRange(5000, 5000+200+1)
		assert.Equal(t, int64(64), bmp.NextValue(0))
		assert.Equal(t, int64(64), bmp.NextValue(63))
		assert.Equal(t, int64(64), bmp.NextValue(64))
		assert.Equal(t, int64(65), bmp.NextValue(65))
		assert.Equal(t, int64(128), bmp.NextValue(128))
		assert.Equal(t, int64(200), bmp.NextValue(129))
		assert.Equal(t, int64(200), bmp.NextValue(199))
		assert.Equal(t, int64(200), bmp.NextValue(200))
		assert.Equal(t, int64(250), bmp.NextValue(250))
		assert.Equal(t, int64(5000), bmp.NextValue(2500))
		assert.Equal(t, int64(5000), bmp.NextValue(5000))
		assert.Equal(t, int64(5200), bmp.NextValue(5200))
		assert.Equal(t, int64(-1), bmp.NextValue(5201))

		assert.Equal(t, int64(-1), bmp.PreviousValue(0))
		assert.Equal(t, int64(-1), bmp.PreviousValue(63))
		assert.Equal(t, int64(64), bmp.PreviousValue(64))
		assert.Equal(t, int64(65), bmp.PreviousValue(65))
		assert.Equal(t, int64(128), bmp.PreviousValue(128))
		assert.Equal(t, int64(128), bmp.PreviousValue(129))
		assert.Equal(t, int64(128), bmp.PreviousValue(199))
		assert.Equal(t, int64(200), bmp.PreviousValue(200))
		assert.Equal(t, int64(250), bmp.PreviousValue(250))
		assert.Equal(t, int64(500), bmp.PreviousValue(2500))
		assert.Equal(t, int64(5000), bmp.PreviousValue(5000))
		assert.Equal(t, int64(5200), bmp.PreviousValue(5200))
		assert.Equal(t, int64(5200), bmp.PreviousValue(5201))

		assert.Equal(t, int64(0), bmp.NextAbsentValue(0))
		assert.Equal(t, int64(63), bmp.NextAbsentValue(63))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(64))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(65))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(128))
		assert.Equal(t, int64(129), bmp.NextAbsentValue(129))
		assert.Equal(t, int64(199), bmp.NextAbsentValue(199))
		assert.Equal(t, int64(501), bmp.NextAbsentValue(200))
		assert.Equal(t, int64(501), bmp.NextAbsentValue(250))
		assert.Equal(t, int64(2500), bmp.NextAbsentValue(2500))
		assert.Equal(t, int64(5201), bmp.NextAbsentValue(5000))
		assert.Equal(t, int64(5201), bmp.NextAbsentValue(5200))
		assert.Equal(t, int64(5201), bmp.NextAbsentValue(5201))

		assert.Equal(t, int64(0), bmp.PreviousAbsentValue(0))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(63))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(64))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(65))
		assert.Equal(t, int64(63), bmp.PreviousAbsentValue(128))
		assert.Equal(t, int64(129), bmp.PreviousAbsentValue(129))
		assert.Equal(t, int64(199), bmp.PreviousAbsentValue(199))
		assert.Equal(t, int64(199), bmp.PreviousAbsentValue(200))
		assert.Equal(t, int64(199), bmp.PreviousAbsentValue(250))
		assert.Equal(t, int64(2500), bmp.PreviousAbsentValue(2500))
		assert.Equal(t, int64(4999), bmp.PreviousAbsentValue(5000))
		assert.Equal(t, int64(4999), bmp.PreviousAbsentValue(5200))
		assert.Equal(t, int64(5201), bmp.PreviousAbsentValue(5201))
	})

	t.Run("skip odd ", func(t *testing.T) {
		bmp := New()
		for i := 0; i < 2000; i++ {
			bmp.Add(uint32(i * 2))
		}
		for i := 0; i < 2000; i++ {
			assert.Equal(t, int64(i*2), bmp.NextValue(uint32(i*2)))
			assert.Equal(t, int64(i*2), bmp.PreviousValue(uint32(i*2)))
			assert.Equal(t, int64(i*2+1), bmp.NextAbsentValue(uint32(i*2+1)))

			if i != 0 {
				assert.Equal(t, int64(i*2-1), bmp.PreviousAbsentValue(uint32(i*2)))
			}
		}
	})

	t.Run("Absent target container", func(t *testing.T) {
		bmp := BitmapOf(2, 3, 131072, MaxUint32)

		assert.Equal(t, int64(3), bmp.PreviousValue(65536))
		assert.Equal(t, int64(131072), bmp.PreviousValue(MaxUint32>>1))
		assert.Equal(t, int64(131072), bmp.PreviousValue(MaxUint32-131071))

		bmp = BitmapOf(131072)
		assert.Equal(t, int64(-1), bmp.PreviousValue(65536))
	})

	t.Run("skipping with ranges", func(t *testing.T) {
		bmp := New()
		intervalEnd := 512
		rangeStart := intervalEnd * 2
		rangeEnd := 2048
		for i := 0; i < intervalEnd; i++ {
			bmp.Add(uint32(i * 2))
		}
		bmp.AddRange(uint64(rangeStart), uint64(rangeEnd))

		for i := 0; i < intervalEnd; i++ {
			assert.Equal(t, int64(i*2), bmp.NextValue(uint32(i*2)))
			assert.Equal(t, int64(i*2), bmp.PreviousValue(uint32(i*2)))
			assert.Equal(t, int64(i*2+1), bmp.NextAbsentValue(uint32(i*2)))
			if i != 0 {
				assert.Equal(t, int64(i*2-1), bmp.PreviousAbsentValue(uint32(i*2)))
			}
		}
		for i := rangeStart; i < rangeEnd; i++ {
			assert.Equal(t, int64(i), bmp.NextValue(uint32(i)))
			assert.Equal(t, int64(i), bmp.PreviousValue(uint32(i)))
			assert.Equal(t, int64(rangeEnd), bmp.NextAbsentValue(uint32(i)))
			assert.Equal(t, int64(rangeStart-1), bmp.PreviousAbsentValue(uint32((i))))
		}
	})

	t.Run("randomized", func(t *testing.T) {
		bmp := New()

		intervalEnd := 4096
		entries := make([]uint32, 0, intervalEnd)

		for i := 0; i < intervalEnd; i++ {
			entry := rand.Uint32()
			bmp.Add(entry)
			entries = append(entries, entry)
		}

		for i := 0; i < intervalEnd; i++ {
			entry := entries[i]
			assert.Equal(t, int64(entry), bmp.NextValue(entry))
			assert.Equal(t, int64(entry), bmp.PreviousValue(entry))
			assert.NotEqual(t, int64(entry), bmp.NextAbsentValue(entry))
			assert.NotEqual(t, int64(entry), bmp.PreviousAbsentValue(entry))

		}
	})
}

func BenchmarkFromDense(b *testing.B) {
	testDense(func(name string, rb *Bitmap) {
		dense := make([]uint64, rb.DenseSize())
		rb.WriteDenseTo(dense)
		cp := FromDense(dense, false)

		for _, doCopy := range []bool{false, true} {
			b.Run(fmt.Sprintf("%s,doCopy=%t", name, doCopy), func(b *testing.B) {
				b.ReportAllocs()
				b.SetBytes(int64(len(dense) * 8))
				b.ResetTimer()
				for i := 0; i < b.N; i++ {
					cp.FromDense(dense, doCopy)
					cp.Clear()
				}
			})
		}
	})
}

func BenchmarkWriteDenseTo(b *testing.B) {
	testDense(func(name string, rb *Bitmap) {
		b.Run(name, func(b *testing.B) {
			dense := make([]uint64, rb.DenseSize())
			b.ReportAllocs()
			b.SetBytes(int64(len(dense) * 8))
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				rb.WriteDenseTo(dense)
			}
		})
	})
}

func BenchmarkEvenIntervalArrayUnions(b *testing.B) {
	inputBitmaps := make([]*Bitmap, 40)
	for i := 0; i < 40; i++ {
		bitmap := NewBitmap()
		for j := 0; j < 100; j++ {
			bitmap.Add(uint32(2 * (j + 10*i)))
		}
		inputBitmaps[i] = bitmap
	}

	b.ResetTimer()
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		bitmap := NewBitmap()
		for _, input := range inputBitmaps {
			bitmap.Or(input)
		}
	}
}

func BenchmarkInPlaceArrayUnions(b *testing.B) {
	rand.Seed(100)
	b.ReportAllocs()
	componentBitmaps := make([]*Bitmap, 100)
	for i := 0; i < 100; i++ {
		bitmap := NewBitmap()
		for j := 0; j < 100; j++ {
			// keep all entries in [0,4096), so they stay arrays.
			bitmap.Add(uint32(rand.Intn(arrayDefaultMaxSize)))
		}
		componentBitmaps[i] = bitmap
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		bitmap := NewBitmap()
		for j := 0; j < 100; j++ {
			bitmap.Or(componentBitmaps[rand.Intn(100)])
		}
	}
}

func BenchmarkAntagonisticArrayUnionsGrowth(b *testing.B) {
	left := NewBitmap()
	right := NewBitmap()
	for i := 0; i < 4096; i++ {
		left.Add(uint32(2 * i))
		right.Add(uint32(2*i + 1))
	}
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		left.Clone().Or(right)
	}
}

func BenchmarkRepeatedGrowthArrayUnion(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		sink := NewBitmap()
		source := NewBitmap()
		for i := 0; i < 2048; i++ {
			source.Add(uint32(2 * i))
			sink.Or(source)
		}
	}
}

func BenchmarkRepeatedSelfArrayUnion(b *testing.B) {
	bitmap := NewBitmap()
	for i := 0; i < 4096; i++ {
		bitmap.Add(uint32(2 * i))
	}
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		receiver := NewBitmap()
		for j := 0; j < 1000; j++ {
			receiver.Or(bitmap)
		}
	}
}

// BenchmarkArrayIorMergeThreshold tests performance
// when unioning two array containers when the cardinality sum is over 4096
func BenchmarkArrayUnionThreshold(b *testing.B) {
	testOddPoint := map[string]int{
		"mostly-overlap": 4900,
		"little-overlap": 2000,
		"no-overlap":     0,
	}
	for name, oddPoint := range testOddPoint {
		b.Run(name, func(b *testing.B) {
			left := NewBitmap()
			right := NewBitmap()
			for i := 0; i < 5000; i++ {
				if i%2 == 0 {
					left.Add(uint32(i))
				}
				if i%2 == 0 && i < oddPoint {
					right.Add(uint32(i))
				} else if i%2 == 1 && i >= oddPoint {
					right.Add(uint32(i))
				}
			}
			b.ResetTimer()
			b.ReportAllocs()
			for i := 0; i < b.N; i++ {
				right.Clone().Or(left)
			}
		})
	}
}

func TestIssue467CaseSmall(t *testing.T) {
	b := New()
	b.AddRange(0, 16385)
	b.AddRange(16385, 20482)
	b.AddRange(20482, 27862)
	b.AddRange(27862, 44247)
	b.AddRange(45576, 61961)
	b.AddRange(61961, 66058)
	b.AddRange(66058, 67247)
	b.AddRange(68819, 73028)
	b.AddRange(73028, 89413)
	b.AddRange(92266, 108651)
	b.AddRange(108651, 113772)
	b.AddRange(113772, 118757)
	b.AddRange(118757, 132098)
	b.RunOptimize()
	require.NoError(t, b.Validate())
}

func TestIssue467CaseLarge(t *testing.T) {
	b := New()
	b.RemoveRange(0, 16385)
	b.RemoveRange(16385, 20482)
	b.RemoveRange(20482, 27862)
	b.AddRange(0, 16385)
	b.AddRange(16385, 20482)
	b.AddRange(20482, 27862)
	b.RemoveRange(27862, 44247)
	b.RemoveRange(44247, 45576)
	b.RemoveRange(45576, 61961)
	b.RemoveRange(61961, 66058)
	b.RemoveRange(66058, 67247)
	b.AddRange(27862, 44247)
	b.AddRange(45576, 61961)
	b.AddRange(44247, 45576)
	b.AddRange(61961, 66058)
	b.AddRange(66058, 67247)
	b.RemoveRange(67247, 68819)
	b.RemoveRange(68819, 73028)
	b.RemoveRange(73028, 89413)
	b.RemoveRange(89413, 92266)
	b.RemoveRange(92266, 108651)
	b.RemoveRange(108651, 113772)
	b.RemoveRange(113772, 118757)
	b.AddRange(68819, 73028)
	b.AddRange(73028, 89413)
	b.AddRange(92266, 108651)
	b.AddRange(89413, 92266)
	b.AddRange(108651, 113772)
	b.AddRange(113772, 118757)
	b.RemoveRange(118757, 132098)
	b.AddRange(118757, 132098)
	b.RemoveRange(132098, 137544)
	b.AddRange(132098, 137544)
	b.RemoveRange(137544, 153929)
	b.RemoveRange(153929, 155151)
	b.RemoveRange(155151, 162078)
	b.RemoveRange(162078, 167119)
	b.RemoveRange(167119, 181012)
	b.RemoveRange(181012, 197397)
	b.RemoveRange(197397, 201244)
	b.RemoveRange(201244, 217629)
	b.RemoveRange(217629, 222750)
	b.RemoveRange(222750, 227708)
	b.RemoveRange(227708, 235777)
	b.RemoveRange(235777, 252162)
	b.RemoveRange(252162, 256259)
	b.AddRange(252162, 256259)
	b.AddRange(227708, 235777)
	b.AddRange(235777, 252162)
	b.RunOptimize()
	require.NoError(t, b.Validate())
}

func TestValidateEmpty(t *testing.T) {
	require.NoError(t, New().Validate())
}

func TestValidate469(t *testing.T) {
	b := New()
	b.RemoveRange(0, 180)
	b.AddRange(0, 180)
	require.NoError(t, b.Validate())
	b.RemoveRange(180, 217)
	b.AddRange(180, 217)
	require.NoError(t, b.Validate())
	b.RemoveRange(217, 2394)
	b.RemoveRange(2394, 2427)
	b.AddRange(2394, 2427)
	require.NoError(t, b.Validate())
	b.RemoveRange(2427, 2428)
	b.AddRange(2427, 2428)
	require.NoError(t, b.Validate())
	b.RemoveRange(2428, 3345)
	require.NoError(t, b.Validate())
	b.RemoveRange(3345, 3346)
	require.NoError(t, b.Validate())
	b.RemoveRange(3346, 3597)
	require.NoError(t, b.Validate())
	b.RemoveRange(3597, 3815)
	require.NoError(t, b.Validate())
	b.RemoveRange(3815, 3816)
	require.NoError(t, b.Validate())
	b.AddRange(3815, 3816)
	require.NoError(t, b.Validate())
	b.RemoveRange(3816, 3856)
	b.RemoveRange(3856, 4067)
	b.RemoveRange(4067, 4069)
	b.RemoveRange(4069, 4071)
	b.RemoveRange(4071, 4095)
	b.RemoveRange(4095, 4096)
	require.NoError(t, b.Validate())
	b.RunOptimize()
	require.False(t, b.IsEmpty())
	require.NoError(t, b.Validate())
}

func TestValidateFromV1(t *testing.T) {
	v1 := New()
	for i := 0; i <= 2; i++ {
		v1.Add(uint32(i))
	}
	v1.RunOptimize()
	b, err := v1.MarshalBinary()
	require.NoError(t, err)
	v2 := New()
	require.NoError(t, v2.UnmarshalBinary(b))
	require.NoError(t, v2.Validate())
}