roaring_test.go

package roaring

import (
	"bytes"
	"encoding/base64"
	"fmt"
	"math"
	"math/rand"
	randv2 "math/rand/v2"

	"strconv"
	"testing"

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

func TestFuzzerRepro_1761183632825411000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OjAAAAIAAAAJAAAADwAAABgAAAAaAAAAVeD8/w==")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	bm.Describe()
	if err := bm.Validate(); err != nil {
		t.Errorf("Initial Validate failed: %v", err)
	}
	b2, _ := base64.StdEncoding.DecodeString("OjAAAAEAAAAJAAAAEAAAAFXg")
	bm2 := NewBitmap()
	bm2.UnmarshalBinary(b2)
	bm2.Describe()
	bm.AndNot(bm2)
	if err := bm.Validate(); err != nil {
		t.Errorf("Validate failed: %v", err)
	} else {
		t.Logf("Validate succeeded")
	}
}

func TestFuzzerRepro_1761181918459062000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OjAAAAIAAAAJAAAADwAAABgAAAAaAAAAVeD8/w==")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	if err := bm.Validate(); err != nil {
		t.Errorf("Initial Validate failed: %v", err)
	}
	b2, _ := base64.StdEncoding.DecodeString("OjAAAAEAAAAJAAAAEAAAAFXg")
	bm2 := NewBitmap()
	bm2.UnmarshalBinary(b2)
	bm.AndNot(bm2)
	if err := bm.Validate(); err != nil {
		t.Errorf("Validate failed: %v", err)
	} else {
		t.Logf("Validate succeeded")
	}
}

func TestFuzzerRepro_1761177588768443000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OzAAAAEAAAMAAQADAAMA")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	if err := bm.Validate(); err != nil {
		t.Errorf("Initial Validate failed: %v", err)
	}
	bm.Describe()
	b2, _ := base64.StdEncoding.DecodeString("OjAAAAEAAAAAAAAAEAAAAAEA")
	bm2 := NewBitmap()
	bm2.UnmarshalBinary(b2)
	bm2.Describe()
	bm.Or(bm2)
	if err := bm.Validate(); err != nil {
		t.Errorf("Validate failed: %v", err)
	} else {
		t.Logf("Validate succeeded")
	}
}

func TestFuzzerPanicRepro_1761177447422379000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OjAAAAIAAAAJAAAADwAAABgAAAAaAAAAVeD8/w==")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	b2, _ := base64.StdEncoding.DecodeString("OjAAAAEAAAAJAAAAEAAAAFXg")
	bm2 := NewBitmap()
	bm2.UnmarshalBinary(b2)
	bm.AndNot(bm2)
}

func TestFuzzerPanicRepro_1761174531957958000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OjAAAAIAAAAAAAAADwAAABgAAAAaAAAAAAD//w==")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	b2, _ := base64.StdEncoding.DecodeString("OjAAAAIAAAAAAAAADwAAABgAAAAaAAAAAAD//w==")
	bm2 := NewBitmap()
	bm2.UnmarshalBinary(b2)
	bm.Xor(bm2)
}

func TestFuzzerPanicRepro_1761174003952142000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OjAAAAIAAAAAAAAADwAAABgAAAAaAAAAAAD//w==")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	b2, _ := base64.StdEncoding.DecodeString("OjAAAAIAAAAAAAAADwAAABgAAAAaAAAAAAD//w==")
	bm2 := NewBitmap()
	bm2.UnmarshalBinary(b2)
	bm.Xor(bm2)
}

func TestFuzzerPanicRepro_1761173763060614000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OjAAAAIAAAAAAAAADwAAABgAAAAaAAAAAAD//w==")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	bm.Describe()
	b2, _ := base64.StdEncoding.DecodeString("OjAAAAIAAAAAAAAADwAAABgAAAAaAAAAAAD//w==")
	bm2 := NewBitmap()
	bm2.UnmarshalBinary(b2)
	bm2.Describe()
	bm.Or(bm2)
	bm.Describe()
}

func TestFuzzerPanicRepro_1761171725501558000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OzAAAAEPAAMAAQD1/wMA")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	bm.Describe()
	b2, _ := base64.StdEncoding.DecodeString("OjAAAAEAAAAPAAEAEAAAAPb/9/8=")
	bm2 := NewBitmap()
	bm2.UnmarshalBinary(b2)
	bm2.Describe()
	bm.AndNot(bm2)
	bm.Describe()
}

func TestFuzzerRepro_1761171217612329001(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OzAAAAEPAAMAAQDo/wMA")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	if err := bm.Validate(); err != nil {
		t.Errorf("Initial Validate failed: %v", err)
	}
	bm.Flip(uint64(1048555), uint64(1048555)+1)
	if err := bm.Validate(); err != nil {
		t.Errorf("Validate failed: %v", err)
	} else {
		t.Logf("Validate succeeded")
	}
}

func TestFuzzerRepro_1761171217612329000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OzAAAAEPAAMAAQDo/wMA")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	if err := bm.Validate(); err != nil {
		t.Errorf("Initial Validate failed: %v", err)
	}
	bm.Flip(uint64(1048555), uint64(1048555)+1)
	if err := bm.Validate(); err != nil {
		t.Errorf("Validate failed: %v", err)
	} else {
		t.Logf("Validate succeeded")
	}
}

func TestFuzzerRepro_1761171056770369000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OzAAAAEAAAMAAQACAAMA")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	if err := bm.Validate(); err != nil {
		t.Errorf("Initial Validate failed: %v", err)
	}
	bm.Remove(3)
	if err := bm.Validate(); err != nil {
		t.Errorf("Validate failed: %v", err)
	} else {
		t.Logf("Validate succeeded")
	}
}
func TestFuzzerRepro_1761170740641699000(t *testing.T) {
	b, _ := base64.StdEncoding.DecodeString("OzAAAAEAAAMAAQA2AAMA")
	bm := NewBitmap()
	bm.UnmarshalBinary(b)
	if err := bm.Validate(); err != nil {
		t.Errorf("Initial Validate failed: %v", err)
	}
	bm.AddInt(112)
	if err := bm.Validate(); err != nil {
		t.Errorf("Validate failed: %v", err)
	} else {
		t.Logf("Validate succeeded")
	}
}

var bm1Arr = []uint32{279981785, 279982923, 279988809, 279995913}

const bm2Bytes = "OzAAAAGwEO2EbwQBdgoADXZFAFR2BABadgYAYnaiAAZ3GwAjdx0AQndaAJ533AB8eA4AjHgUAKJ4IQDFeA8B1nkLAON5FgD7eRQAEXoDABZ6AAAYeggAInpRAHV6BwB+egMAg3oFAIp6NgDCegYAynoVAOF6AQDkehYA/HpCAEF7ZACnewMArXsBALB7CQC7ewUAw3sJAM97DwDgewIA5HsQAPZ7BQD9exEAEHwDABV8CgAhfBMANnwFAD18EwBTfA0AY3w4AJ18HwC+fHwAPH0QAE99YgCzfQMAuH1DAP19sACvfhkAyn4dAOl+SQA0f3sAsX+lAFiAhgDggB0A/4AIAAmBBQAQgRQAJoEcAESBpgDsgQ8A/YGUAJOCNgDLgjUAAoNKAE6DJwB3g6gAIYQBACSEIQBHhAsAVIQSAGiEIQCLhNMAYIVVALeFBAC9hSQA44V8AGGGDwByhhAAhIYZAJ+GRgDnhhsABIdJAE+HGQBqhxgAhIcJAI+HOQDKhxYA4oc1ABmIDQAoiAQALogbAEuIcAC9iA0AzIgYAOaIEgD6iCoAJokaAEKJawKvizkA6ouLAHeMJQCejFIA8owGAPqMFAAQjRIAJI0MADKNFgBKjQEATY0IAFiNFwBxjQoAfY0EAIONYQDmjQAA6I06ACSOKgFQj8YAGJAzAE2QFQBkkHQA2pA7ABeRPwBYkQUAX5FdAL6RQwADkhYAG5IMACmSfgCpkhQAv5JlACaTEAA4k5wA1pMzAAuUBgATlEoAX5ROAa+VTQD+lRMAE5YzAEiWRACOlmwA/JYOAAyXAAAOlw8AH5cHACiXAAArlwkANpcBADmXBQBAlxYAWJcxAIuXEwCglxUAt5ccANWXAADXlxoA85cIAP2XMQAwmIAAsphyACaZdACdmU4A7ZkXAAaaVABcmhcAdZocAJOaFgCrmhYAw5osAPGaGgANmwEAEJsRACObBwAsmxwASpsDAE+bBQBWmw0AZZtmAM2bOQAInFIAXJwCAGCcOgCcnMkAZ50FAG6dGgCKnRQAoJ08AN6dAADgnQ0A750hABKeUABknhIAeJ42ALCebAAenzEAUZ8AAFOfCABdn4UA5J8AAOafQwAroCMAUKAEAFagQACYoBUAsKAxAOOgIgAHoQQADaEkADOhCQA+oQQARKEJAE+hPQCOoZ4ALqKMALyiKAHmo7oAoqQgAMSkUQAXpUEAWqW/ABumNgBTphkAbqZXAMemMwH8pwkAB6gMABWoTQBkqCgAjqg6AMqoHwDrqGwAWalEAJ+pEgCzqRIAx6kmAO+pPwAwqioAXKoSAHCqLQCfqkYA56pBACqrEgA+qyYAZqsrAJOrKAC9qwAAv6sdAN6rBwDnqxIA+6sCAP+rBQAGrBMAG6wRAC6sAAAwrA8AQawSAFWsEwBqrAQAcKwTAIWsJwCurBAAwKwMAM6sAADQrAMA1awLAOKsEwD3rAgAAa0oACutCwA5rQgAQ60qAG+tBAB1rQIAea0JAIStJQCrrQgAta0hANitCgDlrQsA8q0fABOuJgA8rhgAV64NAGauHQCFrioAsa4UAMeuGQDirhoA/q4PAA+vBQAWryYAP68TAFSvAwBZrwQAX68AAGGvGgB9rxAAj68DAJSvMADGrxQA3K8uAA2wBwAWsAsAI7AAACWwKABPsBUAZrABAGmwDQB4sCAAm7AIAKWwBwCusAEAsbATAMewIADpsBMA/rADAAOxGQAesQAAILEUADaxAAA4sRUAT7EfAHCxBgB4sRUAj7EXAKixCgC0sQEAt7EqAOOxGwAAsiEAI7ITADiyFgBQsgEAU7IOAGOyEwB4sgQAfrIAAIGyGgCdsgMAorIMALCyAwC1sgEAuLITAM2yFwDmshQA/LIEAAKzAQAFsxQAG7MNACqzCAA0swgAPrMAAEGzAABDswAARbMBAEizGQBjswYAa7MEAHGzCwB+swEAgbMEAIezEwCcsw0Aq7MHALSzCAC+swMAw7MDAMizAwDNswYA1bMUAOuzCQD2swEA+bMAAPuzDAAJtAcAErQAABS0AQAYtAsAJbQEACy0DQA7tBAATbQZAGi0IACKtAQAkLQCAJS0AQCXtAQAnbQAAJ+0BQCmtBMAu7QOAMu0GgDntAkA8rQCAPa0JQAdtQAAH7UHACi1FgBAtQoATbUKAFm1AABbtRgAdbUTAIq1GwCntQMArLUCALC1OQDrtXAAXbYAAF+2KACJtjUAwLYgAOK2OgAetxAAMLcWAEi3AABKt0cAk7cVAKq3KQDVtxIA6bcSAP23AAD/twcACLg0AD64RgCGuDEAubgkAN+4CQDquBQAALkKAAy5DwAduQAAH7kIACu5CAA3uQgAQbkCAEW5AABIuQkAVbkKAGG5AQBkuQcAbrkBAHO5FACJuQIAjbkAAJC5AwCVuQMAmrkAAJy5AgChuQMAqLkHALG5AAC0uQIAuLkHAMO5JQDquQIA8LkXAAm6AAALugkAFroDABu6BQAiugIAKLoIADS6AQA3ugUAProKAEq6AQBNugAAULoJAFy6AQBfugUAZroKAHK6AgB6ugAAfLoUAJK6AgCYugcAoboAAKS6FAC6ugEAvboAAL+6BQDGugEAyboBAMy6BwDVug8A5roAAOi6CADyug0AAbsBAAS7DgAUuxcALbsAADC7BAA2uwIAO7sCAEC7GwBduykAiLsqALS7gwA5vFAAi7wEAJG8JAC3vEIA+7wGAAO9EAAVvQUAHL0SADC9CgA8vTIAcL0KAHy9AQB/vRcAmL0TAK29GwDKvVoAJr4iAEq+DABYvlcCscDiAJXBeAAPwh0ALsInAFfCEABpwgQAb8IJAHrCBwCDwgUAisIRAJ3CEgCxwgQAt8IYANHCEADjwgcA7cIAAPDCKwAdwx8APsMAAEDDSACKwwMAj8MWAKfDCgCzwzMA6MP8AObEcABYxQEAW8UEAGHFDABvxQUAdsUQAIjFDQCXxQ0ApsUYAMDFAADCxSEA5cUAAOfFCgDzxQkA/sUFAAXGBQAMxgcAFcYNACTGKwBRxjIAhcYEAIvGNQDCxmwAMMfSAATIXQBjyAMAaMgVAH/IFwCYyCYAwMgGAMjICwDVyA4A5cggAAfJCAARyRcAKskSAD7JAQBByQoATckXAGbJGgCCyQAAhMkLAJLJFQCpyRMAvskEAMTJWAEeywAAIMsnAEnLAQBMyw8AXcsUAHPLLQCiyw8As8sAALXLAAC4yxoA1MsmAP3LAgABzCsAL8x8AK3MGADHzAMAzMwLANnMCwDnzBcAAM0QABLNGQAtzQoAOc0GAEHNEQBUzQkAX80TAHXNFQCMzQoAmc1JAOXNDADzzScAHM4qAEjOiwDVzgQA284NAOrOdwJj0Q0ActEBAHXRTQDE0QcAzdFQAB/SEAAx0joBbdOhABDUJwA51HMArtSSAELV6gAu1gcAN9YYAFHWIwB21gMAe9YAAH3WAwCC1hsAn9YKAKvWAQCu1gcAt9YBALrWBwDD1gEAxtYJANLWGwDv1gIA89YAAPXWFwAO1wAAENcCABTXFgAs1zoAaNdBAKvXnwBM2AEAT9gGAFfYJwCA2HkA+9idAJrZGgC22QEBudoVANDaOQAL22wAedu8ADfcLABl3CYAjdwcAKvcFgDD3EwAEd1fAHLdTQDB3R8A4t0fAAPenACh3jEA1N4SAOjehQBv3wAAcd9AALPfAQC23xsA098zAAjgEgAc4AIAIOADACXgBQAs4AAAL+ADADTgBAA64AAAPOAKAEjgCQBT4AcAXOAHAGXgHQCE4AAAhuAKAJLgFQCp4A0AuOAkAN7gAwDk4A4A9OAlABvhGQA24RcAT+ECAFPhGABt4QAAb+EbAIzhCwCZ4QUAoOEGAKjhFwDB4QAAw+EBAMbhDgDW4QsA4+EdAALiAwAH4gsAFOIDABniIgA94gEAQOIhAGPiEAB14i0ApOISALjiFADO4gwA3OITAPHiAQD04gYA/OIZABfjAQAa4wIAHuMBACHjBgAp4wQAL+MKADvjDABJ4wwAV+MOAGfjBQBu4wEAceMAAHPjBQB64woAhuMBAInjBwCT4w4Ao+MIAK3jAgCx4wcAuuMDAL/jCgDL4wAAzeMAAM/jBADW4wMA2+MEAOHjBADn4woA8+MCAPfjBQD+4wIAA+QEAArkEAAc5AAAIuQEACjkCgA05AAAOOQDAD7kDABM5AAATuQAAFDkAwBW5AMAW+QEAGHkBQBo5AoAdOQAAHjkAwB+5AwAjOQAAJDkAwCV5AQAnOQGAKTkAQCn5AQAreQDALTkCgDA5AkAy+QEANHkBQDY5AcA4eQHAOrkAgDu5AAA8OQCAPTkBgD85A4ADOUDABHlDQAg5TMAVeUdAHTlBAB65QIAfuUQAJDlFgCo5RAAuuUIAMTlCQDP5SsA/OUdABvmCQAm5hoAQuYSAFbmHAB05ikAn+YSALTmLgDl5g0A9OYxACfnAQAq5wIALuc+AG7nDgF+6BQAlOguAMToqQBv6QwAfekaAJnphwAj6rEA1uoeAPbqTwBH64YAz+sIANnrPgAZ7CYAQewnAGrsBABw7BwAjuwCAJLsCwCf7AIAo+xGAOvsNAAh7QAAI+07AGDtBQBn7S0Alu0GAJ7tLwDP7RYA5+0MAPXtJgAd7iIAQe4BAETuEQBY7g0AZ+4NAHbuLACk7jIA2O4UAO7uJgAW7xIAKu8zAF/vcQDS7yUA+e8RAA3wAgAR8BIAJfAqAFHwBABX8BAAafAfAIrwAQCN8BIAofALAK7wIwDT8A0A4vAHAOvwEgD/8AUABvETABvxCwAp8TsAZvEwAJjxHgC48QAAuvEiAN7xAwDj8Q0A8vEDAPfxBwAA8hsAHfISADHyBAA38hMATfIGAFXyEgBp8j4AqfICAK3yTgD98hsAGvNqAIbzCgCS8xMAp/MAAKrzAwCv8wkAuvMBAL7zAADA8wEAw/MBAMbzBQDN8wAA0fMAANTzAgDY8wEA2/MIAOXzAADn8wYA7/MAAPLzAwD38wMA/PMEAAT0AQAH9A0AGPQGACD0BgAo9AAALPQBAC/0AwA09AcAQPQDAEj0BgBQ9AEAU/QGAFv0CABn9AAAafQEAG/0AQB09AUAe/QEAIH0AQCF9AIAifQCAI/0AACS9AQAmPQCAJz0DgCt9AIAsfQFALj0AAC69AQAwvQEAMj0AgDM9AMA0fQCANb0AQDZ9AQA3/QBAOT0BQDr9AcA9PQHAP70AgAD9QEABvUCAAr1EQAf9Q8AMPUDADf1BAA99QUARPUGAE31AgBR9QYAWfULAGb1AQBq9RIAfvUNAI31BACV9Q8ApvUDAKz1AwCx9QYAufUGAMH1DADP9QkA2vUBAN31EADw9QMA9fUCAPn1AQD99QkACPYAAAr2BwAT9gYAG/YGACP2AAAl9gQAK/YCADD2AAAy9gcAO/YGAET2AABG9gMAS/YAAE32AwBS9gMAV/YIAGL2AABk9hEAd/YDAHz2AAB+9gMAg/YFAIr2BgCS9gEAlvYAAJj2EQCr9gEArvYHALj2AAC69gYAwvYNANH2DADg9gsA7fYBAPD2AgD09gAA9vYBAPn2AQD89goACPcDAA33CgAZ9wEAHPcBAB/3AQAi9wsAL/cCADP3AAA29wwARPcBAEf3AQBK9wwAWPcBAFv3AQBe9wkAafcAAGv3BABy9wkAffcAAH/3DACN9wEAkPcEAJb3CQCh9wAApPcDAKn3DAC39xAAyfcBAMz3EQDf9xIA9PcYAA74AAAQ+AsAHvgGACf4EQA8+AQAQvgOAFL4AABU+BYAbfgBAHD4DgCA+AsAjfgRAKD4AwCm+BEAuvgmAOL4FAD4+BQADvkJABr5CgAm+UIAavmEAPD5CwD9+TYANfoJAEH6LQBw+i0An/oLAKz6PwDt+hoACft4AIP7BgCL+xMBoPwYALr8UwAP/RIAI/0KAC/9BwA4/QkAQ/0kAGn9HgCJ/RsApv2yAFr+AQBd/gIAYf4IAGv+CgB3/gAAef5oAOP+EAD1/mIAWf+CAN3/BwDm/xkA"

func TestRoaring_OrThenAnd(t *testing.T) {
	bm1 := BitmapOf(bm1Arr...)
	require.NoError(t, bm1.Validate())

	bm2 := New()
	_, err := bm2.FromBase64(bm2Bytes)
	require.NoError(t, err)
	require.NoError(t, bm2.Validate())

	orBm := Or(bm1, bm2) // this can be FastOr, bm1.Or(bm2)
	require.NoError(t, orBm.Validate())

	mask := New()
	mask.AddRange(279_900_001, 280_000_001)
	mask.Or(orBm) // this can be roaring.And(mask, orBm)

	require.NoError(t, mask.Validate()) // <-- fails here
}

func TestRoaring_OrThenAnd_RunOptimize(t *testing.T) {
	bm1 := BitmapOf(bm1Arr...)
	require.NoError(t, bm1.Validate())

	fmt.Printf("%v\n", bm1)
	bm2 := New()
	bm2.FromBase64(bm2Bytes) // this shows that data is not corrupted
	bm2 = BitmapOf(bm2.ToArray()...)
	require.NoError(t, bm2.Validate())

	bm2.RunOptimize()
	require.NoError(t, bm2.Validate())

	orBm := Or(bm1, bm2)
	require.NoError(t, orBm.Validate())

	mask := New()
	mask.AddRange(279_900_001, 280_000_001)
	require.NoError(t, mask.Validate())

	mask.And(orBm)

	require.NoError(t, mask.Validate())
}

func TestSplitter_BrokeBm(t *testing.T) {
	bm1 := NewBitmap()
	bm2 := NewBitmap()
	bm3 := NewBitmap()

	for i := 0; i < 2000; i++ {
		bm1.Add(uint32(i))
		bm2.Add(uint32(i + 2000))
		bm3.Add(uint32(i * 4000))
	}
	res := FastOr(bm1, bm2, bm3)

	require.NoError(t, res.Validate())

	return
}

func TestRoaring_AndMask(t *testing.T) {
	r := randv2.New(randv2.NewPCG(13, 22)) // reproducible random

	rb := NewBitmap()
	for j := 0; j < 1_000_000; j++ {
		rb.Add(r.Uint32N(10_000_000) + 5_000_000)
	}

	mask := New()
	mask.AddRange(1, 10_000_001)
	mask.And(rb)

	err := mask.Validate()
	require.NoError(t, err) // this fails
}

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) {
	// Expected checksums for reproducible testing
	expectedChecksums := map[uint64]map[uint64]map[int]uint64{
		15: {
			1:     {0: 10756319042591085143, 1: 8628356015285516814},
			2:     {0: 9098333059944862327, 1: 8643661217147186334},
			4:     {0: 6958029410146852663, 1: 8552786581093523559},
			8:     {0: 1468016395925628727, 1: 17120221891265014711},
			16:    {0: 10544680338284849079, 1: 10276365928919663543},
			32:    {0: 16946816020221683671, 1: 15774941559772765735},
			64:    {0: 6805685596090222999, 1: 14027082878079462903},
			128:   {0: 10938873449103961751, 1: 15444148319012625847},
			256:   {0: 11309310771509366551, 1: 7069335405671456567},
			512:   {0: 12541562025061152055, 1: 16261505930335083639},
			1024:  {0: 2339435738231874871, 1: 10952176602620091831},
			2048:  {0: 3316768049318457015, 1: 17316440206395307191},
			4096:  {0: 7701764264875653559, 1: 14832271157678859191},
			8192:  {0: 16988454899365713580, 1: 10726883116002431148},
			16384: {0: 2090028183478809173, 1: 9796457766245620565},
			32768: {0: 7760976824469153733, 1: 12282386713985239749},
			65536: {0: 981896277892437765, 1: 11087826385241811525},
		},
		100: {
			1:     {0: 9066279125779985483, 1: 8577657534118736529},
			2:     {0: 4369425401968277239, 1: 8664705869706981924},
			4:     {0: 11010263968690220268, 1: 8747926805318181728},
			8:     {0: 10633650503763838178, 1: 7914439743116618412},
			16:    {0: 2103672447757413801, 1: 17045885344622844731},
			32:    {0: 12393679577414425883, 1: 6955536801820872561},
			64:    {0: 8197316132833680708, 1: 8636063068238530422},
			128:   {0: 7231439595719530925, 1: 15483402246458171763},
			256:   {0: 16279390471979224259, 1: 10865940656713619409},
			512:   {0: 18178650019838088967, 1: 3561060448163512986},
			1024:  {0: 14129223433416501692, 1: 7566389309386577368},
			2048:  {0: 7894714367708308029, 1: 14322377208770974283},
			4096:  {0: 6808097750982305134, 1: 15258365281783128036},
			8192:  {0: 5220938908514583451, 1: 7907615236815205617},
			16384: {0: 7801599049027983452, 1: 15366568190157828206},
			32768: {0: 12138675384054307626, 1: 1639002974230284776},
			65536: {0: 14890641509296776915, 1: 4669671005208206569},
		},
		512: {
			1:     {0: 827073066654895541, 1: 8612092039284236527},
			2:     {0: 12579948327828555139, 1: 8611133265144625760},
			4:     {0: 13237566687897418215, 1: 8610189884167809947},
			8:     {0: 1963122788668779039, 1: 11510392801384632065},
			16:    {0: 16746247274296044527, 1: 13465507099452589101},
			32:    {0: 825734909322010511, 1: 12319660855737761317},
			64:    {0: 9549528494128535247, 1: 14223792047697043957},
			128:   {0: 4041381740454103948, 1: 6750203723185038846},
			256:   {0: 7479480802351225402, 1: 15120562265861553528},
			512:   {0: 10226096245326616211, 1: 2123185684866484358},
			1024:  {0: 11147571132137264071, 1: 1491568024944778791},
			2048:  {0: 13981076381879476127, 1: 9988660227473270361},
			4096:  {0: 11371001616995089391, 1: 6746885678345436557},
			8192:  {0: 13391729850604800783, 1: 8278994428803645669},
			16384: {0: 16904558478699170767, 1: 18317580384194851125},
			32768: {0: 9632691026248850622, 1: 7001884646453199196},
			65536: {0: 5681615685697371437, 1: 9355850228005660679},
		},
		1023: {
			1:     {0: 8631198422780375735, 1: 8613055211470360138},
			2:     {0: 5320069948751931063, 1: 8613042017330821606},
			4:     {0: 17410506490660662967, 1: 8613989796354150263},
			8:     {0: 5518796129031940535, 1: 746402130471049399},
			16:    {0: 14798031165738763703, 1: 12612339809927874231},
			32:    {0: 15315673636708793783, 1: 9532837701920862135},
			64:    {0: 7522839260639306167, 1: 2823706096559924663},
			128:   {0: 9587520344641008812, 1: 7726041297071629484},
			256:   {0: 17155103986506795605, 1: 6313321014394915413},
			512:   {0: 12175764683182123845, 1: 15506743299236676933},
			1024:  {0: 3571090491137291397, 1: 10578105683313814149},
			2048:  {0: 2237728790313941541, 1: 1717755092268207653},
			4096:  {0: 9686908407091041829, 1: 11237119237887424037},
			8192:  {0: 1820574113220693541, 1: 6255563087371431461},
			16384: {0: 4282238745751428901, 1: 16052809024863665957},
			32768: {0: 4757895643122848293, 1: 11441606648169673253},
			65536: {0: 13049746141697269285, 1: 16352630024729701925},
		},
		1025: {
			1:     {0: 16082706216882239750, 1: 8611133265144625760},
			2:     {0: 12372593145282835221, 1: 8609215716865404226},
			4:     {0: 16585165836803014019, 1: 8606372379795418255},
			8:     {0: 10608955794586209375, 1: 56703568294819583},
			16:    {0: 8276728750771033399, 1: 8063557333063131655},
			32:    {0: 10794409826319712711, 1: 10503624278129685111},
			64:    {0: 18176085198269729708, 1: 8204216864690730060},
			128:   {0: 17952727548789690314, 1: 12359753801590897482},
			256:   {0: 14990418481054615768, 1: 17958305146627430476},
			512:   {0: 4875534555349427013, 1: 17195640123067758377},
			1024:  {0: 5974583595409151659, 1: 8978053391731676363},
			2048:  {0: 3044574169068517039, 1: 14966468005696446975},
			4096:  {0: 691405335039223607, 1: 639128391183175735},
			8192:  {0: 4038113400756120263, 1: 12825785820597459191},
			16384: {0: 1707028181932787630, 1: 12526547269329962670},
			32768: {0: 5628393221510929589, 1: 6322935199976410277},
			65536: {0: 14552713712975952780, 1: 14116387162697418672},
		},
		4095: {
			1:     {0: 16949218234402177463, 1: 8613068405609898670},
			2:     {0: 6830997255050832823, 1: 8613085997795950046},
			4:     {0: 3431046584319368119, 1: 8614077757284407143},
			8:     {0: 10577784705589702583, 1: 11227064421971279799},
			16:    {0: 13582283525559942071, 1: 8280698677262929847},
			32:    {0: 15930731229079543980, 1: 14540819050448025772},
			64:    {0: 15074197189812092501, 1: 8183429771446961749},
			128:   {0: 16353918313334514501, 1: 8211290591646809413},
			256:   {0: 17541269277318240901, 1: 15870350090812465285},
			512:   {0: 2886944576023397925, 1: 836005010297672229},
			1024:  {0: 2513825157712442917, 1: 4097762838503421477},
			2048:  {0: 7990320838034419237, 1: 2629680369156025893},
			4096:  {0: 15715908757492956965, 1: 5113759417806159653},
			8192:  {0: 8124527689922589221, 1: 9297845031996404261},
			16384: {0: 4269569377294204453, 1: 4817984819978255909},
			32768: {0: 6778708389721242917, 1: 6948029477167889701},
			65536: {0: 7213964021817199397, 1: 1491414404504750885},
		},
		4096: {
			1:     {0: 11204821770578667958, 1: 8612076646121441573},
			2:     {0: 4002267072615482294, 1: 8611102478819035852},
			4:     {0: 4410347288001337270, 1: 8610110719330578755},
			8:     {0: 8603373155648831414, 1: 2315836927982075848},
			16:    {0: 16944482119189024652, 1: 4822482652523786870},
			32:    {0: 6928244183881028666, 1: 10404343182114103400},
			64:    {0: 3024916132362050707, 1: 18344738716466403161},
			128:   {0: 3834944388080394183, 1: 11965577797857582925},
			256:   {0: 12578054101381780383, 1: 6432236967053365413},
			512:   {0: 8964060272711867887, 1: 4932377867961823298},
			1024:  {0: 10128075423705193231, 1: 13478118364967442607},
			2048:  {0: 10873419466579909583, 1: 2115085958593098761},
			4096:  {0: 4070443640866143422, 1: 4961060556868877236},
			8192:  {0: 18035946153837538605, 1: 2745127392817860183},
			16384: {0: 10440079310404823051, 1: 17449655376855997137},
			32768: {0: 3643662661208167111, 1: 8040054815272426829},
			65536: {0: 10935678078244034623, 1: 9483227545069674309},
		},
		4097: {
			1:     {0: 12502862512299620788, 1: 8611155255377189980},
			2:     {0: 9181307251578323890, 1: 8609189328586327162},
			4:     {0: 2746848181595101094, 1: 8606425156353572383},
			8:     {0: 16463913002427077937, 1: 4531009983748580157},
			16:    {0: 5620696034248496124, 1: 1681598425519654588},
			32:    {0: 14741226801656710698, 1: 15129443590117138858},
			64:    {0: 6054465815016208075, 1: 17167720527236979867},
			128:   {0: 16740558302224955231, 1: 6094338199568812847},
			256:   {0: 16186283226139238340, 1: 9873750830371717112},
			512:   {0: 17128678634972789677, 1: 17686674735082264593},
			1024:  {0: 4584566501618899867, 1: 1571778330094025403},
			2048:  {0: 14362076614095467407, 1: 18052295794438597855},
			4096:  {0: 14068496717840570686, 1: 15528345011722562094},
			8192:  {0: 11973549300238445781, 1: 4445961311069353765},
			16384: {0: 17875326558828238723, 1: 2623816128707679187},
			32768: {0: 16383141035864297567, 1: 6192384169366743215},
			65536: {0: 9434099907678191244, 1: 12315506264659309232},
		},
	}

	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))
		}

		checksum := rb1.Checksum()
		expected := expectedChecksums[N][gap][0]
		assert.EqualValues(t, expected, checksum, "N=%d, gap=%d, part 1", N, gap)

		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(x, x+3+gap/2)
			rb2.AddRange(x, x+3+gap/2)
		}

		rb1.RunOptimize()
		rb2.RunOptimize()

		checksum = rb1.Checksum()
		expected = expectedChecksums[N][gap][1]
		assert.EqualValues(t, expected, checksum, "N=%d, gap=%d, part 2", N, gap)

		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)
}

// TestCardinalityInRangeEquivalence verifies that CardinalityInRange(start, end) == Rank(end-1) - Rank(start-1)
// for many inputs, across all container types.
func TestCardinalityInRangeEquivalence(t *testing.T) {
	for N := uint32(1); N <= 1048576; N *= 2 {
		t.Run("N="+strconv.Itoa(int(N)), func(t *testing.T) {
			for gap := uint32(1); gap <= 65536; gap *= 2 {
				rb := NewBitmap()
				for x := uint32(0); x <= N; x += gap {
					rb.Add(x)
				}
				// Test various [start, end) ranges
				testPoints := []uint64{0, 1, 63, 64, 65, 100, 1000, uint64(N / 2), uint64(N), uint64(N + 1), 1 << 16, (1 << 16) + 1}
				for _, s := range testPoints {
					for _, e := range testPoints {
						if s >= e {
							continue
						}
						got := rb.CardinalityInRange(s, e)
						// Compute expected via two Rank calls.
						var expected uint64
						if s == 0 {
							expected = rb.Rank(uint32(e - 1))
						} else {
							expected = rb.Rank(uint32(e-1)) - rb.Rank(uint32(s-1))
						}
						if got != expected {
							t.Errorf("CardinalityInRange(%d, %d) = %d, want %d (N=%d, gap=%d)",
								s, e, got, expected, N, gap)
						}
					}
				}
			}
		})
	}
}

// TestCardinalityInRangeEmpty tests that empty ranges return 0.
func TestCardinalityInRangeEmpty(t *testing.T) {
	rb := NewBitmap()
	rb.AddRange(100, 200)
	assert.EqualValues(t, 0, rb.CardinalityInRange(50, 50))   // empty range
	assert.EqualValues(t, 0, rb.CardinalityInRange(100, 100)) // empty range
	assert.EqualValues(t, 0, rb.CardinalityInRange(200, 100)) // inverted range
	assert.EqualValues(t, 0, rb.CardinalityInRange(300, 400)) // no values in range
	assert.EqualValues(t, 0, rb.CardinalityInRange(0, 100))   // no values before the range
}

// TestCardinalityInRangeSingleContainer tests ranges within a single container.
func TestCardinalityInRangeSingleContainer(t *testing.T) {
	rb := NewBitmap()
	for i := uint32(0); i < 100; i++ {
		rb.Add(i * 3) // values: 0, 3, 6, 9, ..., 297
	}
	// All within container 0 (high bits = 0)
	assert.EqualValues(t, 100, rb.CardinalityInRange(0, 300)) // all values
	assert.EqualValues(t, 1, rb.CardinalityInRange(0, 1))     // just 0
	assert.EqualValues(t, 1, rb.CardinalityInRange(0, 3))     // just 0
	assert.EqualValues(t, 2, rb.CardinalityInRange(0, 4))     // 0 and 3
	assert.EqualValues(t, 1, rb.CardinalityInRange(3, 4))     // just 3
	assert.EqualValues(t, 1, rb.CardinalityInRange(3, 6))     // just 3
	assert.EqualValues(t, 2, rb.CardinalityInRange(3, 7))     // 3 and 6
}

// TestCardinalityInRangeMultiContainer tests ranges spanning multiple containers (high 16 bits).
func TestCardinalityInRangeMultiContainer(t *testing.T) {
	rb := NewBitmap()
	// Put values in 3 different containers:
	// Container 0 (key=0): values 0..99
	for i := uint32(0); i < 100; i++ {
		rb.Add(i)
	}
	// Container 1 (key=1): values 65536..65635
	for i := uint32(0); i < 100; i++ {
		rb.Add(65536 + i)
	}
	// Container 3 (key=3): values 196608..196707 (skip container 2)
	for i := uint32(0); i < 100; i++ {
		rb.Add(196608 + i)
	}

	// Entire range
	assert.EqualValues(t, 300, rb.CardinalityInRange(0, 200000))
	// Just container 0
	assert.EqualValues(t, 100, rb.CardinalityInRange(0, 65536))
	// Just container 1
	assert.EqualValues(t, 100, rb.CardinalityInRange(65536, 131072))
	// Containers 0 and 1
	assert.EqualValues(t, 200, rb.CardinalityInRange(0, 131072))
	// Partial container 0 + full container 1 + partial container 3
	assert.EqualValues(t, 50+100+50, rb.CardinalityInRange(50, 196658))
	// Range in the gap (container 2 doesn't exist)
	assert.EqualValues(t, 0, rb.CardinalityInRange(131072, 196608))
	// Range spanning the gap
	assert.EqualValues(t, 100+100, rb.CardinalityInRange(65536, 196708))
}

// TestCardinalityInRangeRunOptimized tests CardinalityInRange with run-compressed containers.
func TestCardinalityInRangeRunOptimized(t *testing.T) {
	rb := NewBitmap()
	// Create a large consecutive range which will be run-optimized.
	rb.AddRange(1000, 5000)
	rb.AddRange(70000, 80000) // second container (key=1)
	rb.RunOptimize()

	assert.EqualValues(t, 4000, rb.CardinalityInRange(1000, 5000))
	assert.EqualValues(t, 10000, rb.CardinalityInRange(70000, 80000))
	assert.EqualValues(t, 100, rb.CardinalityInRange(1000, 1100))
	assert.EqualValues(t, 4000+10000, rb.CardinalityInRange(0, 100000))
	assert.EqualValues(t, 0, rb.CardinalityInRange(5000, 70000)) // gap between runs
	assert.EqualValues(t, 4000+10000, rb.CardinalityInRange(1000, 80000))
	// Partial into both
	assert.EqualValues(t, 3000+5000, rb.CardinalityInRange(2000, 75000))
}

// TestCardinalityInRangeBitmapContainer tests CardinalityInRange with bitmap containers (>4096 values in one container).
func TestCardinalityInRangeBitmapContainer(t *testing.T) {
	rb := NewBitmap()
	// Add enough values to trigger bitmap container: every other value in [0, 16384).
	for i := uint32(0); i < 16384; i += 2 {
		rb.Add(i)
	}
	// 8192 values: 0, 2, 4, ..., 16382

	assert.EqualValues(t, 8192, rb.CardinalityInRange(0, 16384))
	assert.EqualValues(t, 1, rb.CardinalityInRange(0, 1))      // just 0
	assert.EqualValues(t, 1, rb.CardinalityInRange(0, 2))      // just 0
	assert.EqualValues(t, 2, rb.CardinalityInRange(0, 3))      // 0, 2
	assert.EqualValues(t, 50, rb.CardinalityInRange(0, 100))   // 0, 2, 4, ..., 98
	assert.EqualValues(t, 50, rb.CardinalityInRange(100, 200)) // 100, 102, ..., 198
	assert.EqualValues(t, 0, rb.CardinalityInRange(1, 2))      // no even values in [1, 2)
	assert.EqualValues(t, 1, rb.CardinalityInRange(1, 3))      // just 2
}

// TestCardinalityInRangeFullUint32Range tests CardinalityInRange with end = 1<<32 (full uint32 range).
func TestCardinalityInRangeFullUint32Range(t *testing.T) {
	rb := NewBitmap()
	rb.Add(0)
	rb.Add(0xFFFFFFFF) // MaxUint32
	rb.Add(0x80000000) // mid-point

	assert.EqualValues(t, 3, rb.CardinalityInRange(0, 1<<32))
	assert.EqualValues(t, 1, rb.CardinalityInRange(0, 1))
	assert.EqualValues(t, 1, rb.CardinalityInRange(0xFFFFFFFF, 1<<32))
	assert.EqualValues(t, 2, rb.CardinalityInRange(0x80000000, 1<<32))
}

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)
	})

	t.Run("ToExistingArray-Test", func(t *testing.T) {
		values := make([]uint32, 0, 110)
		rb := NewBitmap()

		for i := 10; i < 120; i++ {
			values = append(values, uint32(i))
		}
		rb.AddMany(values)
		assert.Equal(t, values, rb.ToArray())
		existing := make([]uint32, len(values))
		buf := rb.ToExistingArray(&existing)
		assert.Equal(t, values, *buf)
	})
}

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))
			// Check that Validate() returns nil if and only if tt.err is nil
			validateErr := corruptedDeserializedBitMap.Validate()
			if tt.err == nil {
				assert.NoError(t, validateErr, "expected validation to succeed when tt.err is nil")
			} else {
				assert.Error(t, validateErr, "expected validation to fail when tt.err is not nil")
			}

			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())
}