scriptoriumadmin/featurebase
1
0
Fork 0
mirror of https://github.com/featurebasedb/featurebase.git synced 2026-08-28 10:54:59 +00:00
Code Issues Projects Releases Packages Wiki Activity Actions
featurebase/roaring/roaring_internal_test.go

4828 lines
146 KiB
Go
Raw Permalink Blame History

// Copyright 2022 Molecula Corp. (DBA FeatureBase).
// SPDX-License-Identifier: Apache-2.0
package roaring
import (
"bytes"
"encoding/hex"
"fmt"
"math/rand"
"os"
"reflect"
"runtime"
"strings"
"testing"
"github.com/featurebasedb/featurebase/v3/generator"
"github.com/pkg/errors"
)
// String produces a human viewable string of the contents.
func (iv Interval16) String() string {
return fmt.Sprintf("[%d, %d]", iv.Start, iv.Last)
}
func GetRoaringIter(bitsToSet ...uint64) RoaringIterator {
b := NewBitmap()
changed := b.DirectAddN(bitsToSet...)
n := len(bitsToSet)
if changed != n {
e := fmt.Sprintf("changed=%v but bitsToSet len = %v", changed, n)
panic(e)
}
buf := bytes.NewBuffer(make([]byte, 0, 100000))
_, er := b.WriteTo(buf)
if er != nil {
if er != nil {
panic(er)
}
}
itr, err := NewRoaringIterator(buf.Bytes())
if err != nil {
panic(err)
}
return itr
}
func TestRunAppendInterval(t *testing.T) {
a := NewContainerRun(nil)
tests := []struct {
base []Interval16
app Interval16
exp int32
}{
{
base: []Interval16{},
app: Interval16{Start: 22, Last: 25},
exp: 4,
},
{
base: []Interval16{{Start: 20, Last: 23}},
app: Interval16{Start: 22, Last: 25},
exp: 2,
},
{
base: []Interval16{{Start: 20, Last: 23}},
app: Interval16{Start: 21, Last: 22},
exp: 0,
},
{
base: []Interval16{{Start: 20, Last: 23}},
app: Interval16{Start: 19, Last: 25},
exp: 2, // runAppendInterval explicitly does not support intervals whose start is < c.runs[-1].start
},
}
for i, test := range tests {
a.setRuns(test.base)
if n := a.runAppendInterval(test.app); n != test.exp {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, n)
}
}
}
func TestInterval16RunLen(t *testing.T) {
iv := Interval16{Start: 7, Last: 9}
if iv.runlen() != 3 {
t.Fatalf("should be 3")
}
iv = Interval16{Start: 7, Last: 7}
if iv.runlen() != 1 {
t.Fatalf("should be 1")
}
}
func TestContainerRunAdd(t *testing.T) {
c := NewContainerRun(nil)
tests := []struct {
op uint16
exp []Interval16
}{
{1, []Interval16{{Start: 1, Last: 1}}},
{2, []Interval16{{Start: 1, Last: 2}}},
{4, []Interval16{{Start: 1, Last: 2}, {Start: 4, Last: 4}}},
{3, []Interval16{{Start: 1, Last: 4}}},
{10, []Interval16{{Start: 1, Last: 4}, {Start: 10, Last: 10}}},
{7, []Interval16{{Start: 1, Last: 4}, {Start: 7, Last: 7}, {Start: 10, Last: 10}}},
{6, []Interval16{{Start: 1, Last: 4}, {Start: 6, Last: 7}, {Start: 10, Last: 10}}},
{0, []Interval16{{Start: 0, Last: 4}, {Start: 6, Last: 7}, {Start: 10, Last: 10}}},
{8, []Interval16{{Start: 0, Last: 4}, {Start: 6, Last: 8}, {Start: 10, Last: 10}}},
}
var changed bool
for _, test := range tests {
c.setMapped(true)
c, changed = c.add(test.op)
if !changed {
t.Fatalf("result of adding new bit should be true: %v", c.runs())
}
if !reflect.DeepEqual(c.runs(), test.exp) {
t.Fatalf("Should have %v, but got %v after adding %v", test.exp, c.runs(), test.op)
}
if c.Mapped() {
t.Fatalf("container should not be mapped after adding bit %v", test.op)
}
}
}
func TestContainerRunAdd2(t *testing.T) {
c := NewContainerRun(nil)
c, ret := c.add(0)
if !ret {
t.Fatalf("result of adding new bit should be true: %v", c.runs())
}
if !reflect.DeepEqual(c.runs(), []Interval16{{Start: 0, Last: 0}}) {
t.Fatalf("should have 1 run of length 1, but have %v", c.runs())
}
c, ret = c.add(0)
if ret {
t.Fatalf("result of adding existing bit should be false: %v", c.runs())
}
}
func TestRunCountRange(t *testing.T) {
c := NewContainerRun(nil)
cnt := RunCountRange(c.runs(), 2, 9)
if cnt != 0 {
t.Fatalf("should get 0 from empty container, but got: %v", cnt)
}
c, _ = c.add(5)
c, _ = c.add(6)
c, _ = c.add(7)
cnt = RunCountRange(c.runs(), 2, 9)
if cnt != 3 {
t.Fatalf("should get 3 from interval within range, but got: %v", cnt)
}
c, _ = c.add(8)
c, _ = c.add(9)
c, _ = c.add(10)
c, _ = c.add(11)
cnt = RunCountRange(c.runs(), 4, 8)
if cnt != 3 {
t.Fatalf("should get 3 from range overlaps front of interval, but got: %v", cnt)
}
cnt = RunCountRange(c.runs(), 5, 8)
if cnt != 3 {
t.Fatalf("should get 3 from range within interval, but got: %v", cnt)
}
cnt = RunCountRange(c.runs(), 6, 8)
if cnt != 2 {
t.Fatalf("should get 2 from range within interval, but got: %v", cnt)
}
cnt = RunCountRange(c.runs(), 3, 9)
if cnt != 4 {
t.Fatalf("should get 4 from range overlaps front of interval, but got: %v", cnt)
}
cnt = RunCountRange(c.runs(), 9, 14)
if cnt != 3 {
t.Fatalf("should get 3 from range overlaps back of interval, but got: %v", cnt)
}
cnt = RunCountRange(c.runs(), 8, 10)
if cnt != 2 {
t.Fatalf("should get 2 from range within interval, but got: %v", cnt)
}
cnt = RunCountRange(c.runs(), 8, 11)
if cnt != 3 {
t.Fatalf("should get 3 from range within interval, but got: %v", cnt)
}
cnt = RunCountRange(c.runs(), 8, 12)
if cnt != 4 {
t.Fatalf("should get 4 from range overlaps back of interval, but got: %v", cnt)
}
cnt = RunCountRange(c.runs(), 5, 12)
if cnt != 7 {
t.Fatalf("should get 7 from interval within range, but got: %v", cnt)
}
cnt = RunCountRange(c.runs(), 5, 11)
if cnt != 6 {
t.Fatalf("should get 6 from interval equal to range, but got: %v", cnt)
}
c, _ = c.add(17)
c, _ = c.add(19)
c, _ = c.add(18)
cnt = RunCountRange(c.runs(), 1, 22)
if cnt != 10 {
t.Fatalf("should get 10 from multiple ranges in interval, but got: %v", cnt)
}
c, _ = c.add(13)
c, _ = c.add(14)
cnt = RunCountRange(c.runs(), 6, 18)
if cnt != 9 {
t.Fatalf("should get 9 from multiple ranges overlapping both sides, but got: %v", cnt)
}
// verify that the disparate ops resulted in three separate runs
cnt = c.countRuns()
if cnt != 3 {
t.Fatalf("should get 3 total runs, but got: %v [%v]", cnt, c.runs())
}
}
func TestRunContains(t *testing.T) {
c := NewContainerRun(nil)
if c.runContains(5) {
t.Fatalf("empty run container should not contain 5")
}
c, _ = c.add(5)
if !c.runContains(5) {
t.Fatalf("run container with 5 should contain 5")
}
c, _ = c.add(6)
c, _ = c.add(7)
c, _ = c.add(9)
c, _ = c.add(10)
c, _ = c.add(11)
if !c.runContains(10) {
t.Fatalf("run container with 10 in second run should contain 10")
}
}
func TestBitmapCountRange(t *testing.T) {
c := NewContainerBitmap(0, nil)
tests := []struct {
start int32
end int32
bitmap [bitmapN]uint64
exp int32
}{
{start: 0, end: 1, bitmap: [bitmapN]uint64{1}, exp: 1},
{start: 2, end: 7, bitmap: [bitmapN]uint64{0xFFFFFFFFFFFFFF18}, exp: 2},
{start: 67, end: 68, bitmap: [bitmapN]uint64{0, 0x8}, exp: 1},
{start: 1, end: 68, bitmap: [bitmapN]uint64{0x3, 0x8, 0xF}, exp: 2},
{start: 1, end: 258, bitmap: [bitmapN]uint64{0xF, 0x8, 0xA, 0x4, 0xFFFFFFFFFFFFFFFF}, exp: 9},
{start: 66, end: 71, bitmap: [bitmapN]uint64{0xF, 0xFFFFFFFFFFFFFF18}, exp: 2},
{start: 63, end: 64, bitmap: [bitmapN]uint64{0x8000000000000000}, exp: 1},
}
for i, test := range tests {
c.setBitmap(test.bitmap[:])
if ret := BitmapCountRange(c.bitmap(), test.start, test.end); ret != test.exp {
t.Fatalf("test #%v count of %v from %v to %v should be %v but got %v", i, test.bitmap, test.start, test.end, test.exp, ret)
}
}
}
func TestIntersectionCountArrayBitmap3(t *testing.T) {
a, b := NewContainerBitmapN(getFullBitmap(), MaxContainerVal+1), NewContainerBitmapN(getFullBitmap(), MaxContainerVal+1)
res := intersectBitmapBitmap(a, b)
if res.N() != res.count() || res.N() != MaxContainerVal+1 {
t.Fatalf("test #1 intersectCountBitmapBitmap fail orig: %v new: %v exp: %v", res.N(), res.count(), MaxContainerVal+1)
}
a = a.bitmapToRun(0)
res = intersectBitmapRun(b, a)
if res.N() != res.count() || res.N() != MaxContainerVal+1 {
t.Fatalf("test #2 intersectCountBitmapRun fail orig: %v new: %v exp: %v", res.N(), res.count(), MaxContainerVal+1)
}
b = b.bitmapToRun(0)
res = intersectRunRun(a, b)
n := intersectionCountRunRun(a, b)
if res.N() != res.count() || res.N() != MaxContainerVal+1 || res.N() != int32(n) {
t.Fatalf("test #3 intersectCountRunRun fail orig: %v new: %v exp: %v", res.N(), res.count(), MaxContainerVal+1)
}
}
func TestIntersectionCountArrayBitmap2(t *testing.T) {
a, b := NewContainerArray(nil), NewContainerBitmap(0, nil)
tests := []struct {
array []uint16
bitmap [bitmapN]uint64
exp int32
}{
{
array: []uint16{0},
bitmap: [bitmapN]uint64{1},
exp: 1,
},
{
array: []uint16{0, 1},
bitmap: [bitmapN]uint64{3},
exp: 2,
},
{
array: []uint16{64, 128, 129, 2000},
bitmap: [bitmapN]uint64{932421, 2},
exp: 0,
},
{
array: []uint16{0, 65, 130, 195},
bitmap: [bitmapN]uint64{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
exp: 4,
},
{
array: []uint16{63, 120, 543, 639, 12000},
bitmap: [bitmapN]uint64{0x8000000000000000, 0, 0, 0, 0, 0, 0, 0, 0, 0x8000000000000000},
exp: 2,
},
}
for i, test := range tests {
a.setArray(test.array)
b.setBitmap(test.bitmap[:])
ret := intersectionCountArrayBitmap(a, b)
if ret != test.exp {
t.Fatalf("test #%v intersectCountArrayBitmap fail received: %v exp: %v", i, ret, test.exp)
}
}
}
func TestRunRemove(t *testing.T) {
c := NewContainerRun([]Interval16{{Start: 2, Last: 10}, {Start: 12, Last: 13}, {Start: 15, Last: 16}})
tests := []struct {
op uint16
exp []Interval16
expRet bool
}{
{2, []Interval16{{Start: 3, Last: 10}, {Start: 12, Last: 13}, {Start: 15, Last: 16}}, true},
{10, []Interval16{{Start: 3, Last: 9}, {Start: 12, Last: 13}, {Start: 15, Last: 16}}, true},
{12, []Interval16{{Start: 3, Last: 9}, {Start: 13, Last: 13}, {Start: 15, Last: 16}}, true},
{13, []Interval16{{Start: 3, Last: 9}, {Start: 15, Last: 16}}, true},
{16, []Interval16{{Start: 3, Last: 9}, {Start: 15, Last: 15}}, true},
{6, []Interval16{{Start: 3, Last: 5}, {Start: 7, Last: 9}, {Start: 15, Last: 15}}, true},
{8, []Interval16{{Start: 3, Last: 5}, {Start: 7, Last: 7}, {Start: 9, Last: 9}, {Start: 15, Last: 15}}, true},
{8, []Interval16{{Start: 3, Last: 5}, {Start: 7, Last: 7}, {Start: 9, Last: 9}, {Start: 15, Last: 15}}, false},
{1, []Interval16{{Start: 3, Last: 5}, {Start: 7, Last: 7}, {Start: 9, Last: 9}, {Start: 15, Last: 15}}, false},
{44, []Interval16{{Start: 3, Last: 5}, {Start: 7, Last: 7}, {Start: 9, Last: 9}, {Start: 15, Last: 15}}, false},
}
for i, test := range tests {
c = c.Freeze()
var ret bool
c, ret = c.remove(test.op)
if ret != test.expRet || !reflect.DeepEqual(c.runs(), test.exp) {
t.Fatalf("test #%v Unexpected result removing %v from runs. Expected %v, got %v. Expected %v, got %v", i, test.op, test.expRet, ret, test.exp, c.runs())
}
if ret && c.frozen() {
t.Fatalf("test #%v container was not unmapped although bit %v was removed", i, test.op)
}
if !ret && !c.frozen() {
t.Fatalf("test #%v container was unmapped although bit %v was not removed", i, test.op)
}
}
}
func TestRunMax(t *testing.T) {
c := NewContainerRun([]Interval16{{Start: 2, Last: 10}, {Start: 12, Last: 13}, {Start: 15, Last: 16}})
max := c.max()
if max != 16 {
t.Fatalf("max for %v should be 16", c.runs())
}
c = NewContainerRun(nil)
max = c.max()
if max != 0 {
t.Fatalf("max for %v should be 0", c.runs())
}
}
func TestIntersectionCountArrayRun(t *testing.T) {
a := NewContainerArray([]uint16{1, 5, 10, 11, 12})
b := NewContainerRun([]Interval16{{Start: 2, Last: 10}, {Start: 12, Last: 13}, {Start: 15, Last: 16}})
ret := intersectionCountArrayRun(a, b)
if ret != 3 {
t.Fatalf("count of %v with %v should be 3, but got %v", a.array(), b.runs(), ret)
}
}
func TestIntersectionCountBitmapRun(t *testing.T) {
ob := make([]uint64, bitmapN)
ob[0] = 1 << 63
a := NewContainerBitmap(1, ob)
b := NewContainerRun([]Interval16{{Start: 63, Last: 64}})
ret := intersectionCountBitmapRun(a, b)
if ret != 1 {
t.Fatalf("count of %v with %v should be 1, but got %v", a.bitmap(), b.runs(), ret)
}
a = NewContainerBitmap(-1, []uint64{0xF0000001, 0xFF00000000000000, 0xFF000000000000F0, 0x0F0000})
b = NewContainerRun([]Interval16{{Start: 29, Last: 31}, {Start: 125, Last: 134}, {Start: 191, Last: 197}, {Start: 200, Last: 300}})
ret = intersectionCountBitmapRun(a, b)
if ret != 14 {
t.Fatalf("count of %v with %v should be 14, but got %v", a.bitmap(), b.runs(), ret)
}
}
func TestIntersectionCountRunRun(t *testing.T) {
tests := []struct {
aruns []Interval16
bruns []Interval16
exp int32
}{
{
aruns: []Interval16{},
bruns: []Interval16{{Start: 3, Last: 8}}, exp: 0},
{
aruns: []Interval16{{Start: 2, Last: 10}},
bruns: []Interval16{{Start: 3, Last: 8}}, exp: 6},
{
aruns: []Interval16{{Start: 2, Last: 10}},
bruns: []Interval16{{Start: 1, Last: 11}}, exp: 9},
{
aruns: []Interval16{{Start: 2, Last: 10}},
bruns: []Interval16{{Start: 0, Last: 2}}, exp: 1},
{
aruns: []Interval16{{Start: 2, Last: 10}},
bruns: []Interval16{{Start: 1, Last: 10}}, exp: 9},
{
aruns: []Interval16{{Start: 2, Last: 10}},
bruns: []Interval16{{Start: 5, Last: 12}}, exp: 6},
{
aruns: []Interval16{{Start: 2, Last: 10}},
bruns: []Interval16{{Start: 10, Last: 99}}, exp: 1},
{
aruns: []Interval16{{Start: 2, Last: 10}, {Start: 44, Last: 99}},
bruns: []Interval16{{Start: 12, Last: 14}}, exp: 0},
{
aruns: []Interval16{{Start: 2, Last: 10}, {Start: 12, Last: 13}},
bruns: []Interval16{{Start: 2, Last: 10}, {Start: 12, Last: 13}}, exp: 11},
{
aruns: []Interval16{{Start: 8, Last: 12}, {Start: 15, Last: 19}},
bruns: []Interval16{{Start: 9, Last: 9}, {Start: 11, Last: 17}}, exp: 6},
}
for i, test := range tests {
a := NewContainerRun(test.aruns)
b := NewContainerRun(test.bruns)
ret := intersectionCountRunRun(a, b)
if ret != test.exp {
t.Fatalf("test #%v failed intersecting %v with %v should be %v, but got %v", i, test.aruns, test.bruns, test.exp, ret)
}
}
}
func TestIntersectArrayRun(t *testing.T) {
a := NewContainerArray(nil)
b := NewContainerRun(nil)
tests := []struct {
array []uint16
runs []Interval16
exp []uint16
}{
{
array: []uint16{1, 4, 5, 7, 10, 11, 12},
runs: []Interval16{{Start: 5, Last: 10}},
exp: []uint16{5, 7, 10},
},
{
array: []uint16{},
runs: []Interval16{{Start: 5, Last: 10}},
exp: []uint16(nil),
},
{
array: []uint16{1, 4, 5, 7, 10, 11, 12},
runs: []Interval16{},
exp: []uint16(nil),
},
{
array: []uint16{0, 1, 4, 5, 7, 10, 11, 12},
runs: []Interval16{{Start: 0, Last: 5}, {Start: 7, Last: 7}},
exp: []uint16{0, 1, 4, 5, 7},
},
}
for i, test := range tests {
a.setArray(test.array)
b.setRuns(test.runs)
ret := intersectArrayRun(a, b)
if test.exp == nil {
if len(ret.array()) != 0 {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.array())
}
} else if !reflect.DeepEqual(ret.array(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.array())
}
}
}
func TestIntersectRunRun(t *testing.T) {
a := NewContainerRun(nil)
b := NewContainerRun(nil)
tests := []struct {
aruns []Interval16
bruns []Interval16
exp []Interval16
expN int32
}{
{
aruns: []Interval16{},
bruns: []Interval16{{Start: 5, Last: 10}},
exp: []Interval16(nil),
expN: 0,
},
{
aruns: []Interval16{{Start: 5, Last: 12}},
bruns: []Interval16{{Start: 5, Last: 10}},
exp: []Interval16{{Start: 5, Last: 10}},
expN: 6,
},
{
aruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 8}, {Start: 9, Last: 12}},
bruns: []Interval16{{Start: 5, Last: 10}},
exp: []Interval16{{Start: 5, Last: 5}, {Start: 7, Last: 10}},
expN: 5,
},
{
aruns: []Interval16{{Start: 20, Last: 30}},
bruns: []Interval16{{Start: 5, Last: 10}, {Start: 19, Last: 21}},
exp: []Interval16{{Start: 20, Last: 21}},
expN: 2,
},
{
aruns: []Interval16{{Start: 5, Last: 10}},
bruns: []Interval16{{Start: 7, Last: 12}},
exp: []Interval16{{Start: 7, Last: 10}},
expN: 4,
},
{
aruns: []Interval16{{Start: 5, Last: 12}},
bruns: []Interval16{{Start: 7, Last: 10}},
exp: []Interval16{{Start: 7, Last: 10}},
expN: 4,
},
}
for i, test := range tests {
a.setRuns(test.aruns)
b.setRuns(test.bruns)
ret := intersectRunRun(a, b)
if ret.N() != test.expN {
t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.N())
}
if test.exp != nil {
if !reflect.DeepEqual(ret.runs(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
}
} else if len(ret.runs()) != 0 {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
}
}
}
func TestIntersectBitmapRunBitmap(t *testing.T) {
tests := []struct {
bitmap []uint64
runs []Interval16
exp []uint64
expN int32
}{
{
bitmap: []uint64{1},
runs: []Interval16{{Start: 0, Last: 0}, {Start: 2, Last: 5}, {Start: 62, Last: 71}, {Start: 77, Last: 4096}},
exp: []uint64{1},
expN: 1,
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 1, Last: 1}},
exp: []uint64{2},
expN: 1,
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 1, Last: 1}, {Start: 10, Last: 12}, {Start: 61, Last: 77}},
exp: []uint64{0xe000000000001C02},
expN: 7,
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 1, Last: 1}, {Start: 61, Last: 77}},
exp: []uint64{0xE000000000000002, 0x00000000000003FFF},
expN: 18,
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF, 1, 1, 1, 0xA, 1, 1, 0, 1},
runs: []Interval16{{Start: 63, Last: 10000}},
exp: []uint64{0x8000000000000000, 1, 1, 1, 0xA, 1, 1, 0, 1},
expN: 9,
},
}
for i, test := range tests {
exp := make([]uint64, bitmapN)
copy(exp, test.exp)
a := NewContainerBitmap(-1, test.bitmap)
b := NewContainerRun(test.runs)
b.setN(4097)
ret := intersectBitmapRun(a, b)
if ret.isArray() {
ret = ret.arrayToBitmap()
}
if !reflect.DeepEqual(ret.bitmap(), exp) {
t.Fatalf("test #%v expected %v, but got %v", i, exp, ret.bitmap())
}
if ret.N() != test.expN {
t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.N())
}
}
}
func TestIntersectBitmapRunArray(t *testing.T) {
a := NewContainerBitmap(0, nil)
b := NewContainerRun(nil)
tests := []struct {
bitmap []uint64
runs []Interval16
exp []uint16
expN int32
}{
{
bitmap: []uint64{1},
runs: []Interval16{{Start: 0, Last: 0}, {Start: 2, Last: 5}, {Start: 62, Last: 71}, {Start: 77, Last: 4096}},
exp: []uint16{0},
expN: 1,
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 1, Last: 1}},
exp: []uint16{1},
expN: 1,
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 1, Last: 1}, {Start: 10, Last: 12}, {Start: 61, Last: 77}},
exp: []uint16{1, 10, 11, 12, 61, 62, 63},
expN: 7,
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 1, Last: 1}, {Start: 61, Last: 68}},
exp: []uint16{1, 61, 62, 63, 64, 65, 66, 67, 68},
expN: 9,
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF, 1, 1, 1, 0xA, 1, 1, 0, 1},
runs: []Interval16{{Start: 63, Last: 10000}, {Start: 65000, Last: 65535}},
exp: []uint16{63, 64, 128, 192, 257, 259, 320, 384, 512},
expN: 9,
},
}
for i, test := range tests {
copy(a.bitmap(), test.bitmap)
b.setRuns(test.runs)
ret := intersectBitmapRun(a, b)
if !reflect.DeepEqual(ret.array(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.array())
}
if ret.N() != test.expN {
t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.N())
}
}
}
func TestUnionMixed(t *testing.T) {
// array container
a := NewContainerArray([]uint16{1, 4, 5, 7, 10, 11, 12})
// bitmap container
b := NewContainerBitmap(2, []uint64{0x3})
// run container
r := NewContainerRun([]Interval16{{Start: 5, Last: 10}})
t.Run("various container Unions", func(t *testing.T) {
tests := []struct {
name string
c1 *Container
c2 *Container
exp []uint16
}{
{name: "run-array", c1: r, c2: a, exp: []uint16{1, 4, 5, 6, 7, 8, 9, 10, 11, 12}},
{name: "array-run", c1: a, c2: r, exp: []uint16{1, 4, 5, 6, 7, 8, 9, 10, 11, 12}},
{name: "run-run", c1: r, c2: r, exp: []uint16{5, 6, 7, 8, 9, 10}},
{name: "bitmap-run", c1: b, c2: r, exp: []uint16{0, 1, 5, 6, 7, 8, 9, 10}},
{name: "run-bitmap", c1: r, c2: b, exp: []uint16{0, 1, 5, 6, 7, 8, 9, 10}},
{name: "array-bitmap", c1: a, c2: b, exp: []uint16{0, 1, 4, 5, 7, 10, 11, 12}},
{name: "bitmap-array", c1: a, c2: b, exp: []uint16{0, 1, 4, 5, 7, 10, 11, 12}},
}
for _, tt := range tests {
res := union(tt.c1, tt.c2)
// convert to array for comparison
if res.isBitmap() {
res = res.bitmapToArray()
} else if res.isRun() {
res = res.runToArray()
}
if !reflect.DeepEqual(res.array(), tt.exp) {
t.Fatalf("test %s expected %v, but got %v", tt.name, tt.exp, res.array())
}
}
})
}
func TestUnionInterval16InPlace(t *testing.T) {
tests := []struct {
name string
a []Interval16
b []Interval16
expected []Interval16
expectedN int32
}{
{
name: "firstBitUnset lastBitSet",
a: []Interval16{{1, 10}},
b: []Interval16{{10, 10}},
expected: []Interval16{{1, 10}},
expectedN: 10,
},
{
name: "single overlap",
a: []Interval16{{1, 10}, {21, 28}},
b: []Interval16{{8, 12}},
expected: []Interval16{{1, 12}, {21, 28}},
expectedN: 20,
},
{
name: "nested intervals",
a: []Interval16{{3, 13}, {17, 20}},
b: []Interval16{{1, 4}, {6, 7}, {8, 9}, {10, 11}, {14, 17}},
expected: []Interval16{{1, 20}},
expectedN: 20,
},
{
name: "no overlap",
a: []Interval16{{3, 4}, {7, 8}},
b: []Interval16{{1, 2}, {5, 6}, {9, 10}},
expected: []Interval16{{1, 10}},
expectedN: 10,
},
{
name: "b in a",
a: []Interval16{{1, 10}},
b: []Interval16{{5, 7}},
expected: []Interval16{{1, 10}},
expectedN: 10,
},
{
name: "a eq b",
a: []Interval16{{1, 10}},
b: []Interval16{{1, 10}},
expected: []Interval16{{1, 10}},
expectedN: 10,
},
{
name: "a in b",
a: []Interval16{{5, 7}},
b: []Interval16{{1, 10}},
expected: []Interval16{{1, 10}},
expectedN: 10,
},
{
name: "a ahead b",
a: []Interval16{{1, 2}, {3, 4}, {5, 7}},
b: []Interval16{{10, 11}, {12, 13}, {14, 15}},
expected: []Interval16{{1, 7}, {10, 15}},
expectedN: 13,
},
{
name: "b ahead a",
a: []Interval16{{10, 11}, {12, 13}, {14, 15}},
b: []Interval16{{1, 2}, {3, 4}, {5, 7}},
expected: []Interval16{{1, 7}, {10, 15}},
expectedN: 13,
},
{
name: "empty a and b",
a: []Interval16{},
b: []Interval16{},
expected: []Interval16{},
expectedN: 0,
},
{
name: "empty a",
a: []Interval16{},
b: []Interval16{{1, 2}, {3, 4}, {5, 7}},
expected: []Interval16{{1, 7}},
expectedN: 7,
},
{
name: "empty b",
a: []Interval16{{1, 2}, {3, 4}, {5, 7}},
b: []Interval16{},
expected: []Interval16{{1, 7}},
expectedN: 7,
},
{
name: "single a",
a: []Interval16{{1, 2}},
b: []Interval16{},
expected: []Interval16{{1, 2}},
expectedN: 2,
},
{
name: "single b",
a: []Interval16{},
b: []Interval16{{1, 2}},
expected: []Interval16{{1, 2}},
expectedN: 2,
},
{
name: "single a single b",
a: []Interval16{{3, 4}},
b: []Interval16{{1, 2}},
expected: []Interval16{{1, 4}},
expectedN: 4,
},
{
name: "oddBitsSet lastBitUnset",
a: []Interval16{{1, 1}, {3, 3}, {5, 5}},
b: []Interval16{{0, 4}},
expected: []Interval16{{0, 5}},
expectedN: 6,
},
{
name: "all bits",
a: []Interval16{{1, 1}, {3, 3}, {5, 5}},
b: []Interval16{{0, 0}, {2, 2}, {4, 4}},
expected: []Interval16{{0, 5}},
expectedN: 6,
},
{
name: "short a long b",
a: []Interval16{{5, 5}, {7, 7}, {9, 10}, {12, 12}, {15, 17}, {19, 20}},
b: []Interval16{{1, 10}, {12, 12}, {14, 18}},
expected: []Interval16{{1, 10}, {12, 12}, {14, 20}},
expectedN: 18,
},
{
name: "common endings",
a: []Interval16{{1, 5}, {15, 20}, {25, 35}},
b: []Interval16{{1, 10}, {15, 20}, {30, 35}},
expected: []Interval16{{1, 10}, {15, 20}, {25, 35}},
expectedN: 27,
},
{
name: "common endings and overlap",
a: []Interval16{{1, 5}, {10, 15}},
b: []Interval16{{5, 10}, {12, 17}},
expected: []Interval16{{1, 17}},
expectedN: 17,
},
{
name: "no common endings and overlap",
a: []Interval16{{5, 10}, {12, 17}},
b: []Interval16{{0, 11}, {15, 20}},
expected: []Interval16{{0, 20}},
expectedN: 21,
},
}
for _, tc := range tests {
t.Run(tc.name, func(t *testing.T) {
bb := make([]Interval16, len(tc.b))
copy(bb, tc.b)
runs, n := unionInterval16InPlace(tc.a, tc.b)
for i, v := range tc.expected {
if runs[i] != v {
t.Fatalf("runs expected: %+v, got: %+v", tc.expected, runs)
}
}
if n != tc.expectedN {
t.Fatalf("N expected: %d, got: %d", tc.expectedN, n)
}
for i, v := range bb {
if tc.b[i] != v {
t.Fatalf("b changed - runs expected: %+v, got: %+v", bb, tc.b)
}
}
})
}
}
func TestIntersectMixed(t *testing.T) {
a := NewContainerRun([]Interval16{{Start: 5, Last: 10}})
b := NewContainerArray([]uint16{1, 4, 5, 7, 10, 11, 12})
c := NewContainerBitmap(2, []uint64{0x60})
res := intersect(a, b)
if !reflect.DeepEqual(res.array(), []uint16{5, 7, 10}) {
t.Fatalf("test #1 expected %v, but got %v", []uint16{5, 7, 10}, res.array())
}
res = intersect(b, a)
if !reflect.DeepEqual(res.array(), []uint16{5, 7, 10}) {
t.Fatalf("test #1 expected %v, but got %v", []uint16{5, 7, 10}, res.array())
}
res = intersect(a, a)
if !reflect.DeepEqual(res.runs(), []Interval16{{Start: 5, Last: 10}}) {
t.Fatalf("test #3 expected %v, but got %v", []Interval16{{Start: 5, Last: 10}}, res.runs())
}
res = intersect(c, a)
if !reflect.DeepEqual(res.array(), []uint16{5, 6}) {
t.Fatalf("test #4 expected %v, but got %v", []uint16{6}, res.array())
}
res = intersect(a, c)
if !reflect.DeepEqual(res.array(), []uint16{5, 6}) {
t.Fatalf("test #5 expected %v, but got %v", []uint16{6}, res.array())
}
res = intersect(b, c)
if !reflect.DeepEqual(res.array(), []uint16{5}) {
t.Fatalf("test #6 expected %v, but got %v", []uint16{5}, res.array())
}
res = intersect(c, b)
if !reflect.DeepEqual(res.array(), []uint16{5}) {
t.Fatalf("test #7 expected %v, but got %v", []uint16{5}, res.array())
}
}
func TestDifferenceMixed(t *testing.T) {
a := NewContainerRun([]Interval16{{Start: 5, Last: 10}})
b := NewContainerArray([]uint16{0, 2, 4, 6, 8, 10, 12})
c := NewContainerBitmap(-1, MakeBitmap([]uint64{0x64}))
d := NewContainerArray([]uint16{1, 3, 5, 7, 9, 11, 12})
res := difference(a, b)
if !reflect.DeepEqual(res.array(), []uint16{5, 7, 9}) {
t.Fatalf("test #1 expected %v, but got %#v", []uint16{5, 7, 9}, res)
}
res = difference(b, a)
if !reflect.DeepEqual(res.array(), []uint16{0, 2, 4, 12}) {
t.Fatalf("test #2 expected %v, but got %v", []uint16{0, 2, 4, 12}, res.array())
}
res = difference(a, a)
if !reflect.DeepEqual(res.runs(), []Interval16{}) {
t.Fatalf("test #3 expected empty but got %v", res.runs())
}
res = difference(c, a)
if !reflect.DeepEqual(res.bitmap(), MakeBitmap([]uint64{0x4})) {
t.Fatalf("test #4 expected %v, but got %v", []uint16{4}, res.bitmap())
}
res = difference(a, c)
if !reflect.DeepEqual(res.runs(), []Interval16{{Start: 7, Last: 10}}) {
t.Fatalf("test #5 expected %v, but got %v", []Interval16{{Start: 7, Last: 10}}, res.runs())
}
res = difference(b, c)
if !reflect.DeepEqual(res.array(), []uint16{0, 4, 8, 10, 12}) {
t.Fatalf("test #6 expected %v, but got %v", []uint16{0, 4, 8, 10, 12}, res.array())
}
res = difference(c, b)
if !reflect.DeepEqual(res.array(), []uint16{5}) {
t.Fatalf("test #7 expected %v, but got %v", []uint16{5}, res.array())
}
res = difference(b, b)
if res.N() != 0 {
t.Fatalf("test #8 expected 0, but got %d", res.N())
}
res = difference(c, c)
if res.N() != 0 {
t.Fatalf("test #9 expected 0, but got %d", res.N())
}
res = difference(d, b)
if !reflect.DeepEqual(res.array(), []uint16{1, 3, 5, 7, 9, 11}) {
t.Fatalf("test #10 expected %v, but got %d", []uint16{1, 3, 5, 7, 9, 11}, res.array())
}
res = difference(b, d)
if !reflect.DeepEqual(res.array(), []uint16{0, 2, 4, 6, 8, 10}) {
t.Fatalf("test #11 expected %v, but got %d", []uint16{0, 2, 4, 6, 8, 10}, res.array())
}
}
func TestUnionRunRun(t *testing.T) {
a := NewContainerRun(nil)
b := NewContainerRun(nil)
tests := []struct {
aruns []Interval16
bruns []Interval16
exp []Interval16
}{
{
aruns: []Interval16{},
bruns: []Interval16{{Start: 5, Last: 10}},
exp: []Interval16{{Start: 5, Last: 10}},
},
{
aruns: []Interval16{{Start: 5, Last: 12}},
bruns: []Interval16{{Start: 5, Last: 10}},
exp: []Interval16{{Start: 5, Last: 12}},
},
{
aruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 8}, {Start: 9, Last: 12}},
bruns: []Interval16{{Start: 5, Last: 10}},
exp: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 12}},
},
{
aruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 8}, {Start: 9, Last: 12}},
bruns: []Interval16{{Start: 2, Last: 65535}},
exp: []Interval16{{Start: 1, Last: 65535}},
},
{
aruns: []Interval16{{Start: 2, Last: 65535}},
bruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 8}, {Start: 9, Last: 12}},
exp: []Interval16{{Start: 1, Last: 65535}},
},
{
aruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 8}, {Start: 9, Last: 12}},
bruns: []Interval16{{Start: 0, Last: 65535}},
exp: []Interval16{{Start: 0, Last: 65535}},
},
{
aruns: []Interval16{{Start: 0, Last: 65535}},
bruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 8}, {Start: 9, Last: 12}},
exp: []Interval16{{Start: 0, Last: 65535}},
},
{
aruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 9}, {Start: 12, Last: 22}},
bruns: []Interval16{{Start: 2, Last: 8}, {Start: 16, Last: 27}, {Start: 33, Last: 34}},
exp: []Interval16{{Start: 1, Last: 9}, {Start: 12, Last: 27}, {Start: 33, Last: 34}},
},
}
for i, test := range tests {
a.setRuns(test.aruns)
b.setRuns(test.bruns)
ret := unionRunRun(a, b)
if !reflect.DeepEqual(ret.runs(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
}
}
}
func TestUnionArrayRun(t *testing.T) {
a := NewContainerArray(nil)
b := NewContainerRun(nil)
tests := []struct {
array []uint16
runs []Interval16
exp []uint16
}{
{
array: []uint16{1, 4, 5, 7, 10, 11, 12},
runs: []Interval16{{Start: 5, Last: 10}},
exp: []uint16{1, 4, 5, 6, 7, 8, 9, 10, 11, 12},
},
{
array: []uint16{},
runs: []Interval16{{Start: 5, Last: 10}},
exp: []uint16{5, 6, 7, 8, 9, 10},
},
{
array: []uint16{1, 4, 5, 7, 10, 11, 12},
runs: []Interval16{},
exp: []uint16{1, 4, 5, 7, 10, 11, 12},
},
{
array: []uint16{0, 1, 4, 5, 7, 10, 11, 12},
runs: []Interval16{{Start: 0, Last: 5}, {Start: 7, Last: 7}},
exp: []uint16{0, 1, 2, 3, 4, 5, 7, 10, 11, 12},
},
}
for i, test := range tests {
a.setArray(test.array)
b.setRuns(test.runs)
ret := unionArrayRun(a, b)
if !reflect.DeepEqual(ret.array(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.array())
}
}
}
func TestBitmapSetRange(t *testing.T) {
tests := []struct {
bitmap []uint64
start uint64
last uint64
exp []uint64
expN int32
}{
{
bitmap: []uint64{0x0000000000FFF900},
start: 9,
last: 10,
exp: []uint64{0x0000000000FFFF00},
expN: 16,
},
{
bitmap: []uint64{0xFF0, 0xFF, 0xFF},
start: 60,
last: 130,
exp: []uint64{0xF000000000000FF0, 0xFFFFFFFFFFFFFFFF, 0xFF},
expN: 84,
},
}
for i, test := range tests {
c := NewContainerBitmap(-1, test.bitmap)
c.bitmapSetRange(test.start, test.last+1)
if !reflect.DeepEqual(c.bitmap()[:len(test.exp)], test.exp) {
t.Fatalf("test %#v expected %x, got %x", i, test.exp, c.bitmap()[:len(test.bitmap)])
}
if test.expN != c.N() {
t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, c.N())
}
}
}
func TestArrayToBitmap(t *testing.T) {
tests := []struct {
array []uint16
exp []uint64
}{
{
array: []uint16{},
exp: []uint64{},
},
{
array: []uint16{0, 1, 2, 3},
exp: []uint64{0xF},
},
}
for i, test := range tests {
exp := make([]uint64, bitmapN)
copy(exp, test.exp)
a := NewContainerArray(test.array)
a = a.arrayToBitmap()
if !reflect.DeepEqual(a.bitmap(), exp) {
t.Fatalf("test #%v expected %v, but got %v", i, exp, a.bitmap())
}
}
}
func TestBitmapToArray(t *testing.T) {
tests := []struct {
bitmap []uint64
exp []uint16
}{
{
bitmap: []uint64{},
exp: []uint16{},
},
{
bitmap: []uint64{0xF},
exp: []uint16{0, 1, 2, 3},
},
}
for i, test := range tests {
a := NewContainerBitmap(-1, test.bitmap)
a = a.bitmapToArray()
if !reflect.DeepEqual(a.array(), test.exp) {
t.Fatalf("test #%v expected %#v, but got %#v", i, test.exp, a.array())
}
}
}
func TestRunToBitmap(t *testing.T) {
tests := []struct {
runs []Interval16
exp []uint64
}{
{
runs: []Interval16{},
exp: []uint64{},
},
{
runs: []Interval16{{Start: 0, Last: 0}},
exp: []uint64{1},
},
{
runs: []Interval16{{Start: 0, Last: 4}},
exp: []uint64{31},
},
{
runs: []Interval16{{Start: 2, Last: 2}, {Start: 5, Last: 7}, {Start: 13, Last: 14}, {Start: 17, Last: 17}},
exp: []uint64{155876},
},
{
runs: []Interval16{{Start: 0, Last: 3}, {Start: 60, Last: 67}},
exp: []uint64{0xF00000000000000F, 0x000000000000000F},
},
}
for i, test := range tests {
exp := make([]uint64, bitmapN)
n := 0
for i, v := range test.exp {
exp[i] = v
n += int(popcount(v))
}
a := NewContainerRun(test.runs)
a = a.runToBitmap()
if !reflect.DeepEqual(a.bitmap(), exp) {
t.Fatalf("test #%v expected %v, but got %v", i, exp, a.bitmap())
}
}
}
func getFullBitmap() []uint64 {
x := make([]uint64, 1024)
for i := range x {
x[i] = uint64(0xFFFFFFFFFFFFFFFF)
}
return x
}
func TestBitmapToRun(t *testing.T) {
tests := []struct {
bitmap []uint64
exp []Interval16
}{
{
// empty run
bitmap: []uint64{},
exp: []Interval16{},
},
{
// single-bit run
bitmap: []uint64{1},
exp: []Interval16{{Start: 0, Last: 0}},
},
{
// single multi-bit run in one word
bitmap: []uint64{31},
exp: []Interval16{{Start: 0, Last: 4}},
},
{
// multiple runs in one word
bitmap: []uint64{155876},
exp: []Interval16{{Start: 2, Last: 2}, {Start: 5, Last: 7}, {Start: 13, Last: 14}, {Start: 17, Last: 17}},
},
{
// span two words, both mixed
bitmap: []uint64{0xF00000000000000F, 0x000000000000000F},
exp: []Interval16{{Start: 0, Last: 3}, {Start: 60, Last: 67}},
},
{
// span two words, first = maxBitmap
bitmap: []uint64{0xFFFFFFFFFFFFFFFF, 0xF},
exp: []Interval16{{Start: 0, Last: 67}},
},
{
// span two words, second = maxBitmap
bitmap: []uint64{0xF000000000000000, 0xFFFFFFFFFFFFFFFF},
exp: []Interval16{{Start: 60, Last: 127}},
},
{
// span three words
bitmap: []uint64{0xF000000000000000, 0xFFFFFFFFFFFFFFFF, 0xF},
exp: []Interval16{{Start: 60, Last: 131}},
},
{
bitmap: make([]uint64, bitmapN),
exp: []Interval16{{Start: 65408, Last: 65535}},
},
{
bitmap: getFullBitmap(),
exp: []Interval16{{Start: 0, Last: 65535}},
},
}
tests[8].bitmap[1022] = 0xFFFFFFFFFFFFFFFF
tests[8].bitmap[1023] = 0xFFFFFFFFFFFFFFFF
for i, test := range tests {
a := NewContainerBitmap(-1, test.bitmap)
x := a.bitmap()
a = a.bitmapToRun(0)
if !reflect.DeepEqual(a.runs(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, a.runs())
}
a = a.runToBitmap()
if !reflect.DeepEqual(a.bitmap(), x) {
t.Fatalf("test #%v expected %v, but got %v", i, a.bitmap(), x)
}
}
}
func TestArrayToRun(t *testing.T) {
tests := []struct {
array []uint16
exp []Interval16
}{
{
array: []uint16{},
exp: []Interval16{},
},
{
array: []uint16{0},
exp: []Interval16{{Start: 0, Last: 0}},
},
{
array: []uint16{0, 1, 2, 3, 4},
exp: []Interval16{{Start: 0, Last: 4}},
},
{
array: []uint16{2, 5, 6, 7, 13, 14, 17},
exp: []Interval16{{Start: 2, Last: 2}, {Start: 5, Last: 7}, {Start: 13, Last: 14}, {Start: 17, Last: 17}},
},
}
for i, test := range tests {
a := NewContainerArray(test.array)
a = a.arrayToRun(0)
if !reflect.DeepEqual(a.runs(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, a.runs())
}
}
}
func TestRunToArray(t *testing.T) {
tests := []struct {
runs []Interval16
exp []uint16
}{
{
runs: []Interval16{},
exp: []uint16{},
},
{
runs: []Interval16{{Start: 0, Last: 0}},
exp: []uint16{0},
},
{
runs: []Interval16{{Start: 0, Last: 4}},
exp: []uint16{0, 1, 2, 3, 4},
},
{
runs: []Interval16{{Start: 2, Last: 2}, {Start: 5, Last: 7}, {Start: 13, Last: 14}, {Start: 17, Last: 17}},
exp: []uint16{2, 5, 6, 7, 13, 14, 17},
},
}
for i, test := range tests {
a := NewContainerRun(test.runs)
a = a.runToArray()
if !reflect.DeepEqual(a.array(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, a.array())
}
}
}
func TestBitmapZeroRange(t *testing.T) {
tests := []struct {
bitmap []uint64
start uint64
last uint64
exp []uint64
expN int32
}{
{
bitmap: []uint64{0x0000000000FFFF00},
start: 9,
last: 10,
exp: []uint64{0x0000000000FFF900},
expN: 14,
},
{
bitmap: []uint64{0xFF0, 0xFF, 0xFF},
start: 60,
last: 130,
exp: []uint64{0xFF0, 0, 0xF8},
expN: 13,
},
}
for i, test := range tests {
c := NewContainerBitmap(-1, test.bitmap)
bitmap := c.bitmap()
c.bitmapZeroRange(test.start, test.last+1)
if !reflect.DeepEqual(bitmap[:len(test.exp)], test.exp) {
t.Fatalf("test %#v expected %x, got %x", i, test.exp, bitmap[:len(test.bitmap)])
}
if test.expN != c.N() {
t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, c.N())
}
for i := range test.bitmap {
bitmap[i] = 0
}
}
}
func TestUnionBitmapRun(t *testing.T) {
tests := []struct {
bitmap []uint64
runs []Interval16
exp []uint64
expN int32
}{
{
bitmap: []uint64{2},
runs: []Interval16{{Start: 0, Last: 0}, {Start: 2, Last: 5}, {Start: 62, Last: 71}, {Start: 77, Last: 78}},
exp: []uint64{0xC00000000000003F, 0x60FF},
expN: 18,
},
}
for i, test := range tests {
a := NewContainerBitmap(-1, test.bitmap)
b := NewContainerRun(test.runs)
ret := unionBitmapRun(a, b)
if ret.isArray() {
ret = ret.arrayToBitmap()
}
bitmap := ret.bitmap()
if !reflect.DeepEqual(bitmap[:len(test.exp)], test.exp) {
t.Fatalf("test #%v expected %x, but got %x", i, test.exp, bitmap[:len(test.exp)])
}
if ret.N() != test.expN {
t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.N())
}
for i := range test.bitmap {
a.bitmap()[i] = 0
}
}
}
func TestBitmapCountRuns(t *testing.T) {
tests := []struct {
bitmap []uint64
exp int32
}{
{
bitmap: []uint64{0xFF00FF00},
exp: 2,
},
{
bitmap: []uint64{0xFF00FF0000000000, 0x1},
exp: 2,
},
{
bitmap: []uint64{0xFF00FF0000000000, 0x2, 0x100},
exp: 4,
},
{
bitmap: []uint64{0xFF00FF0000000000, 0x1010101FF0101010, 0x100},
exp: 10,
},
}
var c *Container
for i, test := range tests {
c = NewContainerBitmap(-1, test.bitmap)
ret := c.bitmapCountRuns()
if ret != test.exp {
t.Fatalf("test #%v expected %v but got %v", i, test.exp, ret)
}
for j := range test.bitmap {
c.bitmap()[j] = 0
}
}
test := tests[3]
for j, v := range test.bitmap {
c.bitmap()[1024-len(test.bitmap)+j] = v
}
ret := c.bitmapCountRuns()
if ret != test.exp {
t.Fatalf("test at end expected %v but got %v", test.exp, ret)
}
}
func TestArrayCountRuns(t *testing.T) {
c := NewContainerArray(nil)
tests := []struct {
array []uint16
exp int32
}{
{
array: []uint16{},
exp: 0,
},
{
array: []uint16{0},
exp: 1,
},
{
array: []uint16{1},
exp: 1,
},
{
array: []uint16{1, 2, 3, 5},
exp: 2,
},
{
array: []uint16{0, 1, 3, 9, 2048, 4096, 4097, 65534, 65535},
exp: 6,
},
{
array: []uint16{0, 10, 11, 12},
exp: 2,
},
}
for i, test := range tests {
c.setArray(test.array)
ret := c.arrayCountRuns()
if ret != test.exp {
t.Fatalf("test #%v expected %v but got %v", i, test.exp, ret)
}
}
}
func TestDifferenceArrayRun(t *testing.T) {
tests := []struct {
array []uint16
runs []Interval16
exp []uint16
}{
{
array: []uint16{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12},
runs: []Interval16{{Start: 5, Last: 10}},
exp: []uint16{0, 1, 2, 3, 4, 11, 12},
},
}
for i, test := range tests {
a := NewContainerArray(test.array)
b := NewContainerRun(test.runs)
ret := differenceArrayRun(a, b)
if !reflect.DeepEqual(ret.array(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.array())
}
}
}
func TestDifferenceRunArray(t *testing.T) {
tests := []struct {
runs []Interval16
array []uint16
exp []Interval16
}{
{
runs: []Interval16{{Start: 0, Last: 12}},
array: []uint16{5, 6, 7, 8, 9, 10},
exp: []Interval16{{Start: 0, Last: 4}, {Start: 11, Last: 12}},
},
{
runs: []Interval16{{Start: 0, Last: 12}},
array: []uint16{0, 1, 2, 3},
exp: []Interval16{{Start: 4, Last: 12}},
},
{
runs: []Interval16{{Start: 0, Last: 12}},
array: []uint16{9, 10, 11, 12, 13},
exp: []Interval16{{Start: 0, Last: 8}},
},
{
runs: []Interval16{{Start: 1, Last: 12}},
array: []uint16{0, 9, 10, 11, 12, 13},
exp: []Interval16{{Start: 1, Last: 8}},
},
{
runs: []Interval16{{Start: 1, Last: 12}, {Start: 14, Last: 14}, {Start: 18, Last: 18}},
array: []uint16{0, 9, 10, 11, 12, 13, 14, 17},
exp: []Interval16{{Start: 1, Last: 8}, {Start: 18, Last: 18}},
},
{
runs: []Interval16{{Start: 1, Last: 12}, {Start: 14, Last: 14}, {Start: 18, Last: 18}},
array: []uint16{0, 9, 10, 11, 12, 13, 14, 17, 19},
exp: []Interval16{{Start: 1, Last: 8}, {Start: 18, Last: 18}},
},
{
runs: []Interval16{{Start: 1, Last: 12}, {Start: 14, Last: 17}, {Start: 19, Last: 28}},
array: []uint16{0, 9, 10, 11, 12, 13, 14, 17, 19, 25, 27},
exp: []Interval16{{Start: 1, Last: 8}, {Start: 15, Last: 16}, {Start: 20, Last: 24}, {Start: 26, Last: 26}, {Start: 28, Last: 28}},
},
{
runs: []Interval16{{Start: 0, Last: 20}, {Start: 65533, Last: 65535}},
array: []uint16{65533, 65534, 65535},
exp: []Interval16{{Start: 0, Last: 20}},
},
{
runs: []Interval16{{Start: 0, Last: 20}, {Start: 65530, Last: 65535}},
array: []uint16{37, 65535},
exp: []Interval16{{Start: 0, Last: 20}, {Start: 65530, Last: 65534}},
},
}
for i, test := range tests {
a := NewContainerRun(test.runs)
b := NewContainerArray(test.array)
ret := differenceRunArray(a, b)
if !reflect.DeepEqual(ret.runs(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
}
}
}
func MakeBitmap(start []uint64) []uint64 {
b := make([]uint64, bitmapN)
copy(b, start)
return b
}
func MakeLastBitSet() []uint64 {
obj := NewFileBitmap(65535)
c := obj.container(0)
c = c.arrayToBitmap()
return c.bitmap()
}
func TestDifferenceRunBitmap(t *testing.T) {
tests := []struct {
runs []Interval16
bitmap []uint64
exp []Interval16
}{
{
runs: []Interval16{{Start: 0, Last: 63}},
bitmap: MakeBitmap([]uint64{0x0000FFFF000000F0}),
exp: []Interval16{{Start: 0, Last: 3}, {Start: 8, Last: 31}, {Start: 48, Last: 63}},
},
{
runs: []Interval16{{Start: 0, Last: 63}},
bitmap: MakeBitmap([]uint64{0x8000000000000000}),
exp: []Interval16{{Start: 0, Last: 62}},
},
{
runs: []Interval16{{Start: 0, Last: 63}},
bitmap: MakeBitmap([]uint64{0x0000000000000001}),
exp: []Interval16{{Start: 1, Last: 63}},
},
{
runs: []Interval16{{Start: 0, Last: 63}},
bitmap: MakeBitmap([]uint64{0x0, 0x0000000000000001}),
exp: []Interval16{{Start: 0, Last: 63}},
},
{
runs: []Interval16{{Start: 0, Last: 65}},
bitmap: MakeBitmap([]uint64{0x0, 0x0000000000000001}),
exp: []Interval16{{Start: 0, Last: 63}, {Start: 65, Last: 65}},
},
{
runs: []Interval16{{Start: 0, Last: 65}},
bitmap: MakeBitmap([]uint64{0x0, 0x8000000000000000}),
exp: []Interval16{{Start: 0, Last: 65}},
},
{
runs: []Interval16{{Start: 1, Last: 65535}},
bitmap: MakeBitmap([]uint64{0x0000000000000001}),
exp: []Interval16{{Start: 1, Last: 65535}},
},
{
runs: []Interval16{{Start: 0, Last: 65533}, {Start: 65535, Last: 65535}},
bitmap: MakeLastBitSet(),
exp: []Interval16{{Start: 0, Last: 65533}},
},
}
for i, test := range tests {
a := NewContainerRun(test.runs)
b := NewContainerBitmap(-1, test.bitmap)
ret := differenceRunBitmap(a, b)
if !reflect.DeepEqual(ret.runs(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
}
}
}
func TestDifferenceBitmapRun(t *testing.T) {
tests := []struct {
bitmap []uint64
runs []Interval16
exp []uint64
}{
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 4, Last: 7}, {Start: 32, Last: 47}},
exp: []uint64{0xFFFF0000FFFFFF0F},
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFBF},
runs: []Interval16{{Start: 0, Last: 5}, {Start: 7, Last: 63}},
exp: []uint64{0x0000000000000000},
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFBF},
runs: []Interval16{{Start: 0, Last: 5}},
exp: []uint64{0xFFFFFFFFFFFFFF80},
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 60, Last: 63}},
exp: []uint64{0x0FFFFFFFFFFFFFFF},
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 60, Last: 65}},
exp: []uint64{0x0FFFFFFFFFFFFFFF},
},
{
bitmap: []uint64{0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF},
runs: []Interval16{{Start: 60, Last: 65}, {Start: 67, Last: 72}, {Start: 126, Last: 130}},
exp: []uint64{0x0FFFFFFFFFFFFFFF, 0x3FFFFFFFFFFFFE04, 0xFFFFFFFFFFFFFFF8},
},
{
bitmap: []uint64{0x0000000000000001},
runs: []Interval16{{Start: 0, Last: 0}},
exp: []uint64{0x0000000000000000},
},
{
bitmap: []uint64{0x8000000000000000},
runs: []Interval16{{Start: 63, Last: 63}},
exp: []uint64{0x0000000000000000},
},
{
bitmap: []uint64{0xC000000000000000, 0x0000000000000003},
runs: []Interval16{{Start: 63, Last: 64}},
exp: []uint64{0x4000000000000000, 0x0000000000000002},
},
{
bitmap: []uint64{0x0000000000000000},
runs: []Interval16{{Start: 5, Last: 7}},
exp: []uint64{0x0000000000000000},
}, {
bitmap: bitmapLastBitSet(),
runs: []Interval16{{Start: 65535, Last: 65535}},
exp: bitmapEmpty(),
},
{
bitmap: bitmapFull(),
runs: []Interval16{{Start: 0, Last: 65535}},
exp: bitmapEmpty(),
},
}
for i, test := range tests {
a := NewContainerBitmap(-1, test.bitmap)
b := NewContainerRun(test.runs)
ret := differenceBitmapRun(a, b)
if !reflect.DeepEqual(ret.bitmap()[:len(test.exp)], test.exp) {
t.Fatalf("test #%v expected \n%X, but got \n%X", i, test.exp, ret.bitmap()[:len(test.exp)])
}
}
}
func TestDifferenceBitmapArray(t *testing.T) {
tests := []struct {
bitmap []uint64
array []uint16
exp []uint16
}{
{
bitmap: MakeBitmap([]uint64{0xFF0F}),
array: []uint16{0, 1, 2, 3, 4, 5, 6, 7, 10},
exp: []uint16{8, 9, 11, 12, 13, 14, 15},
},
{
bitmap: []uint64{0x0000},
array: []uint16{0, 1, 2, 3, 4, 5, 6, 7, 10},
exp: []uint16{},
},
{
bitmap: []uint64{0xFFFF},
array: []uint16{0, 1, 2, 3, 4, 5, 6, 7, 10},
exp: []uint16{8, 9, 11, 12, 13, 14, 15},
},
{
bitmap: bitmapOddBitsSet(),
array: []uint16{0, 1, 2, 3, 4, 5, 6, 7, 10},
exp: []uint16{9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63},
},
{
bitmap: bitmapOddBitsSet(),
array: []uint16{63},
exp: []uint16{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61},
},
{
bitmap: MakeBitmap([]uint64{0x0000FFFF000000F0}),
array: []uint16{4, 5, 6, 7, 20, 21, 22, 23, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47},
exp: []uint16{},
},
}
for i, test := range tests {
b := NewContainerBitmap(-1, test.bitmap[:1])
a := NewContainerArray(test.array)
ret := differenceBitmapArray(b, a)
if !reflect.DeepEqual(ret.array(), test.exp) {
t.Fatalf("test #%v expected %#v, but got %#v", i, test.exp, ret.array())
}
}
}
func TestDifferenceBitmapBitmap(t *testing.T) {
tests := []struct {
abitmap []uint64
bbitmap []uint64
exp []uint16
}{
{
abitmap: []uint64{0xFF00FFFFFFFFFFFF},
bbitmap: []uint64{0xFFFFFFFFFFFFF000},
exp: []uint16{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11},
},
{
abitmap: []uint64{0xF},
bbitmap: []uint64{0},
exp: []uint16{0, 1, 2, 3},
},
}
for i, test := range tests {
a := NewContainerBitmap(-1, test.abitmap)
b := NewContainerBitmap(-1, test.bbitmap)
ret := differenceBitmapBitmap(a, b)
if !reflect.DeepEqual(ret.array(), test.exp) {
t.Fatalf("test #%v expected \n%X, but got \n%X", i, test.exp, ret.array())
}
}
}
func TestDifferenceRunRun(t *testing.T) {
tests := []struct {
aruns []Interval16
bruns []Interval16
exp []Interval16
expn int32
}{
{
// this tests all six overlap combinations
// A [ ] [ ] [ ] [ ] [ ] [ ]
// B [ ] [ ] [ ] [ ] [ ] [ ]
aruns: []Interval16{{Start: 3, Last: 6}, {Start: 13, Last: 16}, {Start: 24, Last: 26}, {Start: 33, Last: 38}, {Start: 43, Last: 46}, {Start: 53, Last: 56}},
bruns: []Interval16{{Start: 1, Last: 8}, {Start: 11, Last: 14}, {Start: 21, Last: 23}, {Start: 35, Last: 37}, {Start: 44, Last: 48}, {Start: 57, Last: 59}},
exp: []Interval16{{Start: 15, Last: 16}, {Start: 24, Last: 26}, {Start: 33, Last: 34}, {Start: 38, Last: 38}, {Start: 43, Last: 43}, {Start: 53, Last: 56}},
expn: 13,
},
}
for i, test := range tests {
a := NewContainerRun(test.aruns)
b := NewContainerRun(test.bruns)
ret := differenceRunRun(a, b)
if !reflect.DeepEqual(ret.runs(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
}
if ret.N() != test.expn {
t.Fatalf("test #%v expected n=%v, but got n=%v", i, test.expn, ret.N())
}
}
}
func TestWriteReadArray(t *testing.T) {
ca := NewContainerArray([]uint16{1, 10, 100, 1000})
ba := NewFileBitmap()
ba.Containers.Put(0, ca)
ba2 := NewFileBitmap()
var buf bytes.Buffer
_, err := ba.WriteTo(&buf)
if err != nil {
t.Fatalf("error writing: %v", err)
}
err = ba2.UnmarshalBinary(buf.Bytes())
if err != nil {
t.Fatalf("error unmarshaling: %v", err)
}
if !reflect.DeepEqual(ba2.Containers.Get(0).array(), ca.array()) {
t.Fatalf("array test expected %x, but got %x", ca.array(), ba2.Containers.Get(0).array())
}
}
func TestWriteReadBitmap(t *testing.T) {
// create bitmap containing > 4096 bits
cb := NewContainerBitmapN(nil, 0)
for i := 0; i < 129; i++ {
cb.bitmap()[i] = 0x5555555555555555
cb.n += 32
}
bb := NewFileBitmap()
bb.Containers.Put(0, cb)
bb2 := NewFileBitmap()
var buf bytes.Buffer
_, err := bb.WriteTo(&buf)
if err != nil {
t.Fatalf("error writing: %v", err)
}
err = bb2.UnmarshalBinary(buf.Bytes())
if err != nil {
t.Fatalf("error unmarshaling: %v", err)
}
if !reflect.DeepEqual(bb2.Containers.Get(0).bitmap(), cb.bitmap()) {
t.Fatalf("bitmap test expected %x, but got %x", cb.bitmap(), bb2.Containers.Get(0).bitmap())
}
}
func TestWriteReadFullBitmap(t *testing.T) {
// create bitmap containing > 4096 bits
cb := NewContainerBitmapN(nil, 0)
for i := 0; i < bitmapN; i++ {
cb.bitmap()[i] = 0xffffffffffffffff
cb.n += 64
}
bb := NewFileBitmap()
bb.Containers.Put(0, cb)
bb2 := NewFileBitmap()
var buf bytes.Buffer
_, err := bb.writeToUnoptimized(&buf)
if err != nil {
t.Fatalf("error writing: %v", err)
}
if !cb.isBitmap() {
t.Fatalf("how can i test a bitmap if it's not a bitmap")
}
err = bb2.UnmarshalBinary(buf.Bytes())
if err != nil {
t.Fatalf("error unmarshaling: %v", err)
}
if !reflect.DeepEqual(bb2.Containers.Get(0).bitmap(), cb.bitmap()) {
t.Fatalf("bitmap test expected %x, but got %x", cb.bitmap(), bb2.Containers.Get(0).bitmap())
}
if bb2.Containers.Get(0).N() != cb.N() {
t.Fatalf("bitmap test expected count %x, but got %x", cb.N(), bb2.Containers.Get(0).N())
}
if bb2.Containers.Get(0).count() != cb.count() {
t.Fatalf("bitmap test expected count %x, but got %x", cb.N(), bb2.Containers.Get(0).N())
}
}
func TestWriteReadRun(t *testing.T) {
cr := NewContainerRun([]Interval16{{Start: 3, Last: 13}, {Start: 100, Last: 109}})
br := NewFileBitmap()
br.Containers.Put(0, cr)
br2 := NewFileBitmap()
var buf bytes.Buffer
_, err := br.WriteTo(&buf)
if err != nil {
t.Fatalf("error writing: %v", err)
}
err = br2.UnmarshalBinary(buf.Bytes())
if err != nil {
t.Fatalf("error unmarshaling: %v", err)
}
if !reflect.DeepEqual(br2.Containers.Get(0).runs(), cr.runs()) {
t.Fatalf("run test expected %x, but got %x", cr.runs(), br2.Containers.Get(0).runs())
}
}
func TestXorArrayRun(t *testing.T) {
tests := []struct {
a *Container
b *Container
exp *Container
}{
{
a: NewContainerArray([]uint16{1, 5, 10, 11, 12}),
b: NewContainerRun([]Interval16{{Start: 2, Last: 10}, {Start: 12, Last: 13}, {Start: 15, Last: 16}}),
exp: NewContainerArray([]uint16{1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 15, 16}),
}, {
a: NewContainerArray([]uint16{1, 5, 10, 11, 12, 13, 14}),
b: NewContainerRun([]Interval16{{Start: 2, Last: 10}, {Start: 12, Last: 13}, {Start: 15, Last: 16}}),
exp: NewContainerArray([]uint16{1, 2, 3, 4, 6, 7, 8, 9, 11, 14, 15, 16}),
}, {
a: NewContainerArray([]uint16{65535}),
b: NewContainerRun([]Interval16{{Start: 65534, Last: 65535}}),
exp: NewContainerArray([]uint16{65534}),
}, {
a: NewContainerArray([]uint16{65535}),
b: NewContainerRun([]Interval16{{Start: 65535, Last: 65535}}),
exp: NewContainerArray([]uint16{}),
},
}
for i, test := range tests {
test.a.setN(test.a.count())
test.b.setN(test.b.count())
ret := xor(test.a, test.b)
if !reflect.DeepEqual(ret.array(), test.exp.array()) {
t.Fatalf("test #%v expected %#v, but got %#v", i, test.exp, ret)
}
ret = xor(test.b, test.a)
if !reflect.DeepEqual(ret.array(), test.exp.array()) {
t.Fatalf("test #%v.1 expected %#v, but got %#v", i, test.exp, ret)
}
}
}
// special case that didn't fit the xorrunrun table testing below.
func TestXorRunRun1(t *testing.T) {
a := NewContainerRun([]Interval16{{Start: 4, Last: 10}})
b := NewContainerRun([]Interval16{{Start: 5, Last: 10}})
ret := xorRunRun(a, b)
if !reflect.DeepEqual(ret.array(), []uint16{4}) {
t.Fatalf("test #1 expected %v, but got %v", []uint16{4}, ret.array())
}
ret = xorRunRun(b, a)
if !reflect.DeepEqual(ret.array(), []uint16{4}) {
t.Fatalf("test #1 expected %v, but got %v", []uint16{4}, ret.array())
}
}
func TestXorRunRun(t *testing.T) {
a := NewContainerRun(nil)
b := NewContainerRun(nil)
tests := []struct {
aruns []Interval16
bruns []Interval16
exp []Interval16
}{
{
aruns: []Interval16{},
bruns: []Interval16{{Start: 5, Last: 10}},
exp: []Interval16{{Start: 5, Last: 10}},
},
{
aruns: []Interval16{{Start: 0, Last: 4}},
bruns: []Interval16{{Start: 6, Last: 10}},
exp: []Interval16{{Start: 0, Last: 4}, {Start: 6, Last: 10}},
},
{
aruns: []Interval16{{Start: 0, Last: 6}},
bruns: []Interval16{{Start: 4, Last: 10}},
exp: []Interval16{{Start: 0, Last: 3}, {Start: 7, Last: 10}},
},
{
aruns: []Interval16{{Start: 4, Last: 10}},
bruns: []Interval16{{Start: 0, Last: 6}},
exp: []Interval16{{Start: 0, Last: 3}, {Start: 7, Last: 10}},
},
{
aruns: []Interval16{{Start: 0, Last: 10}},
bruns: []Interval16{{Start: 0, Last: 6}},
exp: []Interval16{{Start: 7, Last: 10}},
},
{
aruns: []Interval16{{Start: 0, Last: 6}},
bruns: []Interval16{{Start: 0, Last: 10}},
exp: []Interval16{{Start: 7, Last: 10}},
},
{
aruns: []Interval16{{Start: 0, Last: 6}},
bruns: []Interval16{{Start: 0, Last: 10}},
exp: []Interval16{{Start: 7, Last: 10}},
},
{
aruns: []Interval16{{Start: 5, Last: 12}},
bruns: []Interval16{{Start: 5, Last: 10}},
exp: []Interval16{{Start: 11, Last: 12}},
},
{
aruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 12}},
bruns: []Interval16{{Start: 5, Last: 10}},
exp: []Interval16{{Start: 1, Last: 3}, {Start: 6, Last: 6}, {Start: 11, Last: 12}},
},
{
aruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 12}},
bruns: []Interval16{{Start: 2, Last: 65535}},
exp: []Interval16{{Start: 1, Last: 1}, {Start: 4, Last: 4}, {Start: 6, Last: 6}, {Start: 13, Last: 65535}},
},
{
aruns: []Interval16{{Start: 2, Last: 65535}},
bruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 12}},
exp: []Interval16{{Start: 1, Last: 1}, {Start: 4, Last: 4}, {Start: 6, Last: 6}, {Start: 13, Last: 65535}},
},
{
aruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 12}},
bruns: []Interval16{{Start: 0, Last: 65535}},
exp: []Interval16{{Start: 0, Last: 0}, {Start: 4, Last: 4}, {Start: 6, Last: 6}, {Start: 13, Last: 65535}},
},
{
aruns: []Interval16{{Start: 0, Last: 65535}},
bruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 12}},
exp: []Interval16{{Start: 0, Last: 0}, {Start: 4, Last: 4}, {Start: 6, Last: 6}, {Start: 13, Last: 65535}},
},
{
aruns: []Interval16{{Start: 1, Last: 3}, {Start: 5, Last: 5}, {Start: 7, Last: 9}, {Start: 12, Last: 22}},
bruns: []Interval16{{Start: 2, Last: 8}, {Start: 16, Last: 27}, {Start: 33, Last: 34}},
exp: []Interval16{{Start: 1, Last: 1}, {Start: 4, Last: 4}, {Start: 6, Last: 6}, {Start: 9, Last: 9}, {Start: 12, Last: 15}, {Start: 23, Last: 27}, {Start: 33, Last: 34}},
},
{
aruns: []Interval16{{Start: 65530, Last: 65535}},
bruns: []Interval16{{Start: 65532, Last: 65535}},
exp: []Interval16{{Start: 65530, Last: 65531}},
},
}
for i, test := range tests {
a.setRuns(test.aruns)
b.setRuns(test.bruns)
ret := xorRunRun(a, b)
if !reflect.DeepEqual(ret.runs(), test.exp) {
t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
}
ret = xorRunRun(b, a)
if !reflect.DeepEqual(ret.runs(), test.exp) {
t.Fatalf("test #%v.1 expected %v, but got %v", i, test.exp, ret.runs())
}
}
}
func TestBitmapXorRange(t *testing.T) {
tests := []struct {
bitmap []uint64
start uint64
last uint64
exp []uint64
expN int32
}{
{
bitmap: []uint64{0x0000000000000000},
start: 0,
last: 2,
exp: []uint64{0x0000000000000007},
expN: 3,
},
{
bitmap: []uint64{0xF1},
start: 4,
last: 8,
exp: []uint64{0x101},
expN: 2,
},
{
bitmap: []uint64{0xAA},
start: 0,
last: 7,
exp: []uint64{0x55},
expN: 4,
},
{
bitmap: []uint64{0x0, 0x0000000000000000, 0x0000000000000000},
start: 63,
last: 128,
exp: []uint64{0x8000000000000000, 0xFFFFFFFFFFFFFFFF, 0x000000000000001},
expN: 66,
},
{
bitmap: []uint64{0x0, 0x00000000000000FF, 0x0000000000000000},
start: 63,
last: 128,
exp: []uint64{0x8000000000000000, 0xFFFFFFFFFFFFFF00, 0x000000000000001},
expN: 58,
},
{
bitmap: []uint64{0x0, 0x0, 0x0},
start: 129,
last: 131,
exp: []uint64{0x0000000000000000, 0x0000000000000000, 0x00000000000000E},
expN: 3,
},
}
for i, test := range tests {
c := NewContainerBitmap(-1, test.bitmap)
c.bitmapXorRange(test.start, test.last+1)
if !reflect.DeepEqual(c.bitmap()[:len(test.exp)], test.exp) {
t.Fatalf("test %#v expected %x, got %x", i, test.exp, c.bitmap()[:len(test.bitmap)])
}
if test.expN != c.N() {
t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, c.N())
}
}
}
func TestXorBitmapRun(t *testing.T) {
tests := []struct {
bitmap []uint64
runs []Interval16
exp []uint64
}{
{
bitmap: []uint64{0x0, 0x0, 0x0},
runs: []Interval16{{Start: 129, Last: 131}},
exp: []uint64{0x0, 0x0, 0x00000000000000E},
},
}
for i, test := range tests {
a := NewContainerBitmap(-1, test.bitmap)
e := NewContainerBitmap(-1, test.exp)
b := NewContainerRun(test.runs)
//xorBitmapRun
ret := xor(a, b)
if ret.isRun() {
ret = ret.runToBitmap()
}
if !reflect.DeepEqual(ret.bitmap(), e.bitmap()) {
t.Fatalf("test #%v expected %v, but got %v", i, e.bitmap(), ret.bitmap())
}
ret = xor(b, a)
if ret.isRun() {
ret = ret.runToBitmap()
}
if !reflect.DeepEqual(ret.bitmap(), e.bitmap()) {
t.Fatalf("test #%v.1 expected %v, but got %v", i, e.bitmap(), ret.bitmap())
}
}
}
func TestIteratorArray(t *testing.T) {
// use values that span two containers
b := NewFileBitmap(0, 1, 10, 100, 1000, 10000, 90000, 100000)
if !b.Containers.Get(0).isArray() {
t.Fatalf("wrong container type")
}
itr := b.Iterator()
if !(itr.key == 0 && itr.j == -1) {
t.Fatalf("iterator did not zero correctly: %v\n", itr)
}
itr.Seek(1000)
if !(itr.key == 0 && itr.j == 3) {
t.Fatalf("iterator did not seek correctly: %#v\n", itr)
}
itr.Seek(10000)
itr.Next()
val, eof := itr.Next()
if !(itr.key == 1 && itr.j == 0 && val == 90000 && !eof) {
t.Fatalf("iterator did not next correctly across containers: %v\n", itr)
}
itr.Seek(65535)
if !(itr.key == 1 && itr.j == -1) {
t.Fatalf("iterator did not seek missing value in previous container correctly: %v\n", itr)
}
val, eof = itr.Next()
if !(val == 90000 && !eof) {
t.Fatalf("iterator did not next from missing value in previous container correctly: %d, %v\n", val, eof)
}
itr.Seek(80000)
if !(itr.key == 1 && itr.j == -1) {
t.Fatalf("iterator did not seek missing value correctly: %v\n", itr)
}
itr.Seek(100000)
if !(itr.key == 1 && itr.j == 0) {
t.Fatalf("iterator did not seek correctly in multiple containers: %v\n", itr)
}
val, eof = itr.Next()
if !(val == 100000 && !eof) {
t.Fatalf("iterator did not next correctly: %d, %v\n", val, eof)
}
val, eof = itr.Next()
if !(val == 0 && eof) {
t.Fatalf("iterator did not eof correctly: %d, %v\n", val, eof)
}
// Test for seeking value not in bitmap, where next container that the iterator should
// go to has values with low bits smaller than the low bits of seek.
b = NewBitmap(65537, 65538, 65539, 65541, 65542)
itr = b.Iterator()
// Both 65536+5-1 and 5 are not in b.
itr.Seek(5)
if !(itr.key == 1 && itr.j == -1) {
t.Fatalf("iterator did not seek correctly in next container: %v\n", itr)
}
val, eof = itr.Next()
if !(val == 65537 && !eof) {
t.Fatalf("iterator did not next corrrectly to next container: %d, %v\n", val, eof)
}
val, eof = itr.Next()
if !(val == 65538 && !eof) {
t.Fatalf("iterator did not next correctly: %d, %v\n", val, eof)
}
}
func TestIteratorBitmap(t *testing.T) {
// use values that span two containers
// this dataset will update to bitmap after enough Adds,
// but won't update to RLE until Optimize() is called
b := NewFileBitmap()
for i := uint64(61000); i < 71000; i++ {
if _, err := b.Add(i); err != nil {
t.Fatalf("adding bit: %v", err)
}
}
for i := uint64(75000); i < 75100; i++ {
if _, err := b.Add(i); err != nil {
t.Fatalf("adding bit: %v", err)
}
}
if !b.Containers.Get(0).isBitmap() {
t.Fatalf("wrong container type")
}
itr := b.Iterator()
if !(itr.key == 0 && itr.j == -1) {
t.Fatalf("iterator did not zero correctly: %v\n", itr)
}
itr.Seek(65000)
if !(itr.key == 0 && itr.j == 64999) {
t.Fatalf("iterator did not seek correctly: %v\n", itr)
}
itr.Seek(65535)
itr.Next()
val, eof := itr.Next()
if !(itr.key == 1 && itr.j == 0 && val == 65536 && !eof) {
t.Fatalf("iterator did not next correctly across containers: %v\n", itr)
}
itr.Seek(74000)
if !(itr.key == 1 && itr.j == 8463) {
t.Fatalf("iterator did not seek missing value correctly: %v\n", itr)
}
itr.Seek(70999)
if !(itr.key == 1 && itr.j == 5462) {
t.Fatalf("iterator did not seek correctly in multiple containers: %v\n", itr)
}
val, eof = itr.Next()
if !(val == 70999 && !eof) {
t.Fatalf("iterator did not next correctly: %d, %v\n", val, eof)
}
itr.Seek(75100)
val, eof = itr.Next()
if !(val == 0 && eof) {
t.Fatalf("iterator did not eof correctly: %d, %v\n", val, eof)
}
// Test for seeking value not in bitmap, where next container that the iterator should
// go to has values with low bits smaller than the low bits of seek.
for i := uint64(65536*3 + 2); i < 65536*3+4110; i++ {
if i != 65536*3+5 && i != 65536*3+7 {
if _, err := b.Add(i); err != nil {
t.Fatalf("adding bit: %v", err)
}
}
}
// We expect this to be a bitmap container because more than
// 4096 bits have been set, but Optimize() has not been called.
if !b.Containers.Get(3).isBitmap() {
t.Fatalf("wrong container type")
}
// Both 65536*2+5 and 65536*3+5 are not in b.
itr.Seek(65536*2 + 5)
if !(itr.key == 3 && itr.j == -1) {
t.Fatalf("iterator did not seek correctly in next container: %v\n", itr)
}
val, eof = itr.Next()
if !((val == 65536*3+2) && !eof) {
t.Fatalf("iterator did not next correctly to next container: %d, %v\n", val, eof)
}
val, eof = itr.Next()
if !((val == 65536*3+3) && !eof) {
t.Fatalf("iterator did not next correctly to next container: %d, %v\n", val, eof)
}
}
func TestIteratorRuns(t *testing.T) {
b := NewFileBitmap(0, 1, 2, 3, 4, 5, 1000, 1001, 1002, 1003, 1004, 1005, 100000, 100001, 100002, 100003, 100004, 100005)
b.Optimize()
if !b.Containers.Get(0).isRun() {
t.Fatalf("wrong container type")
}
itr := b.Iterator()
if !(itr.key == 0 && itr.j == 0 && itr.k == -1) {
t.Fatalf("iterator did not zero correctly: %v\n", itr)
}
itr.Seek(4)
if !(itr.key == 0 && itr.j == 0 && itr.k == 3) {
t.Fatalf("iterator did not seek correctly: %v\n", itr)
}
itr.Next()
itr.Next()
val, eof := itr.Next()
if !(val == 1000 && !eof) {
t.Fatalf("iterator did not next correctly across runs: %v, %v", val, itr)
}
itr.Next()
val, eof = itr.Next()
if !(val == 1002 && !eof) {
t.Fatalf("iterator did not next correctly within a run: %v, %v", val, itr)
}
itr.Next()
itr.Next()
itr.Next()
val, eof = itr.Next()
if !(val == 100000 && !eof) {
t.Fatalf("iterator did not next correctly across containers: %v, %v", val, itr)
}
itr.Seek(500)
if !(itr.key == 0 && itr.j == 1 && itr.k == -1) {
t.Fatalf("iterator did not seek missing value correctly: %v\n", itr)
}
itr.Seek(1004)
if !(itr.key == 0 && itr.j == 1 && itr.k == 3) {
t.Fatalf("iterator did not seek correctly in multiple runs: %v\n", itr)
}
itr.Seek(1005)
if !(itr.key == 0 && itr.j == 1 && itr.k == 4) {
t.Fatalf("iterator did not seek correctly to end of run: %v\n", itr)
}
itr.Seek(1007)
if !(itr.key == 1 && itr.j == -1 && itr.k == -1) {
t.Fatalf("iterator did not seek correctly to end of run: %v\n", itr)
}
val, eof = itr.Next()
if !(val == 100000 && !eof) {
t.Fatalf("iterator did not next correctly across containers: %v, %v", val, itr)
}
itr.Seek(100005)
if !(itr.key == 1 && itr.j == 0 && itr.k == 4) {
t.Fatalf("iterator did not seek correctly in multiple containers: %v\n", itr)
}
itr.Next()
val, eof = itr.Next()
if !(val == 0 && eof) {
t.Fatalf("iterator did not eof correctly: %d, %v\n", val, eof)
}
// Test for seeking value not in bitmap, where next container that the iterator should
// go to has values with low bits smaller than the low bits of seek.
for i := uint64(65536*3 + 1); i <= 65536*3+8; i++ {
if _, err := b.Add(i); err != nil {
t.Fatalf("adding bit: %v", err)
}
}
for i := uint64(65536*3 + 10); i <= 65536*3+20; i++ {
if _, err := b.Add(i); err != nil {
t.Fatalf("adding bit: %v", err)
}
}
b.Optimize()
if !b.Containers.Get(3).isRun() {
t.Fatalf("wrong container type")
}
// Both 65536*2+9 and 65536*3+9 are not in b.
itr.Seek(65536*2 + 9)
if !(itr.key == 3 && itr.j == 0 && itr.k == -1) {
t.Fatalf("iterator did not seek correctly in next container: %v\n", itr)
}
val, eof = itr.Next()
if !((val == 65536*3+1) && !eof) {
t.Fatalf("iterator did not next correctly to next container: %d, %v\n", val, eof)
}
val, eof = itr.Next()
if !((val == 65536*3+2) && !eof) {
t.Fatalf("iterator did not next correctly to next container: %d, %v\n", val, eof)
}
}
func TestIteratorVarious(t *testing.T) {
tests := []struct {
bm *Bitmap
exp uint64
}{
{
bm: NewFileBitmap(3, 4, 5),
exp: 3,
},
{
bm: bitmapVariousContainers(),
exp: 61221,
},
{
bm: NewFileBitmap(2, 66000, 70000, 70001, 70002, 70003, 70004),
exp: 7,
},
}
for i, test := range tests {
test.bm.Optimize()
t.Run(fmt.Sprintf("#%d:", i), func(t *testing.T) {
if cnt := test.bm.Count(); cnt != test.exp {
t.Fatalf("merged count %d is not %d", cnt, test.exp)
}
iter := test.bm.Iterator()
bits := make([]uint64, 0, test.bm.Count())
for v, eof := iter.Next(); !eof; v, eof = iter.Next() {
bits = append(bits, v)
}
if length := len(bits); uint64(length) != test.exp {
t.Fatalf("length %d is not %d", length, test.exp)
}
})
}
}
func TestRunBinSearchContains(t *testing.T) {
tests := []struct {
runs []Interval16
index uint16
exp struct {
index int32
found bool
}
}{
{
runs: []Interval16{{Start: 0, Last: 10}},
index: uint16(3),
exp: struct {
index int32
found bool
}{index: 0, found: true},
},
{
runs: []Interval16{{Start: 0, Last: 10}},
index: uint16(13),
exp: struct {
index int32
found bool
}{index: 0, found: false},
},
{
runs: []Interval16{{Start: 0, Last: 10}, {Start: 20, Last: 30}},
index: uint16(13),
exp: struct {
index int32
found bool
}{index: 0, found: false},
},
{
runs: []Interval16{{Start: 0, Last: 10}, {Start: 20, Last: 30}},
index: uint16(36),
exp: struct {
index int32
found bool
}{index: 1, found: false},
},
}
for i, test := range tests {
index := test.index
runs := test.runs
idx, found := BinSearchRuns(index, runs)
if test.exp.index != idx && test.exp.found != found {
t.Fatalf("test #%v expected %v , but got %v %v", i, test.exp, idx, found)
}
}
}
func TestRunBinSearch(t *testing.T) {
tests := []struct {
runs []Interval16
search uint16
exp bool
expi int32
}{
{
runs: []Interval16{{2, 10}, {50, 60}, {80, 90}},
search: 1,
exp: false,
expi: 0,
},
{
runs: []Interval16{{2, 10}, {50, 60}, {80, 90}},
search: 2,
exp: true,
expi: 0,
},
{
runs: []Interval16{{2, 10}, {50, 60}, {80, 90}},
search: 5,
exp: true,
expi: 0,
},
{
runs: []Interval16{{2, 10}, {50, 60}, {80, 90}},
search: 10,
exp: true,
expi: 0,
},
{
runs: []Interval16{{2, 10}, {50, 60}, {80, 90}},
search: 20,
exp: false,
expi: 1,
},
{
runs: []Interval16{{2, 10}, {50, 60}, {80, 90}},
search: 55,
exp: true,
expi: 1,
},
{
runs: []Interval16{{2, 10}, {50, 60}, {80, 90}},
search: 70,
exp: false,
expi: 2,
},
{
runs: []Interval16{{2, 10}, {50, 60}, {80, 90}},
search: 100,
exp: false,
expi: 3,
},
}
for i, test := range tests {
idx, contains := BinSearchRuns(test.search, test.runs)
if !(test.exp == contains && test.expi == idx) {
t.Fatalf("test #%v expected (%v, %v) but got (%v, %v)", i, test.exp, test.expi, contains, idx)
}
}
}
func TestBitmap_RemoveEmptyContainers(t *testing.T) {
bm1 := NewFileBitmap(1<<16, 2<<16, 3<<16)
bm2 := NewFileBitmap(1<<16, 2<<16+1, 3<<16)
bm3 := bm1.Intersect(bm2)
if bm3.countNonEmptyContainers() != 2 {
t.Fatalf("Should be 1 empty container ")
}
bm3.removeEmptyContainers()
if bm3.countNonEmptyContainers() != bm3.Containers.Size() {
t.Fatalf("Should be no empty containers ")
}
}
func TestBitmap_BitmapWriteToWithEmpty(t *testing.T) {
bm1 := NewFileBitmap(1<<16, 2<<16, 3<<16)
if _, err := bm1.Remove(2 << 16); err != nil {
t.Fatalf("removing a bit: %v", err)
}
var buf bytes.Buffer
if _, err := bm1.WriteTo(&buf); err != nil {
t.Fatalf("Failure to write to bitmap buffer. ")
}
bm0 := NewFileBitmap()
if err := bm0.UnmarshalBinary(buf.Bytes()); err != nil {
t.Fatalf("unmarshalling: %v", err)
}
if bm0.countNonEmptyContainers() != bm0.Containers.Size() {
t.Fatalf("Should be no empty containers ")
}
if bm0.Count() != bm1.Count() {
t.Fatalf("Counts do not match after a marshal %d %d", bm0.Count(), bm1.Count())
}
}
func TestSearch64(t *testing.T) {
tests := []struct {
a []uint64
value uint64
exp int
}{
{
a: []uint64{1, 5, 10, 12},
value: 5,
exp: 1,
},
{
a: []uint64{1, 5, 10, 12},
value: 1,
exp: 0,
},
{
a: []uint64{1, 5, 10, 12},
value: 0,
exp: -1,
},
{
a: []uint64{1, 5, 10, 12},
value: 2,
exp: -2,
},
{
a: []uint64{1, 5, 10, 12},
value: 7,
exp: -3,
},
{
a: []uint64{1, 5, 10, 12},
value: 11,
exp: -4,
},
{
a: []uint64{1, 5, 10, 12},
value: 13,
exp: -5,
},
{
a: []uint64{1, 5, 10, 12},
value: 3843534,
exp: -5,
},
{
a: []uint64{},
value: 3843534,
exp: -1,
},
{
a: []uint64{},
value: 0,
exp: -1,
},
{
a: []uint64{0},
value: 0,
exp: 0,
},
{
a: []uint64{0},
value: 1,
exp: -2,
},
}
for _, test := range tests {
t.Run(fmt.Sprintf("%d in %v", test.value, test.a), func(t *testing.T) {
actual := search64(test.a, test.value)
if actual != test.exp {
t.Errorf("got: %d, exp: %d", actual, test.exp)
}
})
}
}
func TestIntersectArrayBitmap(t *testing.T) {
tests := []struct {
array []uint16
bitmap []uint64
exp []uint16
}{
{
array: []uint16{0},
bitmap: []uint64{1},
exp: []uint16{0},
},
{
array: []uint16{0, 1},
bitmap: []uint64{3},
exp: []uint16{0, 1},
},
{
array: []uint16{64, 128, 129, 2000},
bitmap: []uint64{932421, 2},
exp: []uint16{},
},
{
array: []uint16{0, 65, 130, 195},
bitmap: []uint64{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
exp: []uint16{0, 65, 130, 195},
},
{
array: []uint16{63, 120, 543, 639, 12000},
bitmap: []uint64{0x8000000000000000, 0, 0, 0, 0, 0, 0, 0, 0, 0x8000000000000000},
exp: []uint16{63, 639},
},
{
array: []uint16{0, 1, 63, 120, 543, 639, 12000, 65534, 65535},
bitmap: bitmapOddBitsSet(),
exp: []uint16{1, 63, 543, 639, 65535},
},
{
array: []uint16{0, 1, 63, 120, 543, 639, 12000, 65534, 65535},
bitmap: bitmapEvenBitsSet(),
exp: []uint16{0, 120, 12000, 65534},
},
}
for i, test := range tests {
a := NewContainerArray(test.array)
b := NewContainerBitmap(-1, test.bitmap)
ret := intersectArrayBitmap(a, b).array()
if len(ret) == 0 && len(test.exp) == 0 {
continue
}
if !reflect.DeepEqual(ret, test.exp) {
t.Fatalf("test #%v intersectArrayBitmap received: %v exp: %v", i, ret, test.exp)
}
}
}
func TestBitmapClone(t *testing.T) {
b := NewFileBitmap()
for i := uint64(61000); i < 71000; i++ {
if _, err := b.Add(i); err != nil {
t.Fatalf("adding bit: %v", err)
}
}
c := b.Clone()
if _, err := b.BitwiseEqual(c); err != nil {
t.Fatalf("Clone Objects not equal: %v\n", err)
}
d := func() *Bitmap { //anybody know how to declare a nil value?
return nil
}()
e := d.Clone()
if e != nil {
t.Fatalf("Clone nil Objects not equal\n")
}
}
// rleCont returns a slice of numbers all in the range starting from
// container_width*num, and ending at container_width*(num+1)-1. If left is
// true, then the first 100 bits will be set, if mid is true, 100 bits in the
// middle will be set, if right is true, the last 100 bits will be set.
// sets 100 bits per true
func rleCont(num int, left, mid, right bool) []uint64 {
ret := make([]uint64, 0)
base := uint64(containerWidth * uint64(num))
if left {
for i := uint64(0); i < 100; i++ {
ret = append(ret, base+i)
}
}
if mid {
for i := uint64(containerWidth / 2); i < containerWidth/2+100; i++ {
ret = append(ret, base+i)
}
}
if right {
for i := uint64(containerWidth - 100); i < containerWidth; i++ {
ret = append(ret, base+i)
}
}
return ret
}
// sets 2 bits per true.
func arrCont(num int, left, mid, right bool) []uint64 {
ret := make([]uint64, 0)
base := containerWidth * uint64(num)
if left {
ret = append(ret, base+0, base+2)
}
if mid {
half := uint64(containerWidth / 2)
ret = append(ret, base+half, base+half+2)
}
if right {
ret = append(ret, base+containerWidth-3, base+containerWidth-1)
}
return ret
}
// sets 6667 bits per true.
func bitCont(num int, left, mid, right bool) []uint64 {
ret := make([]uint64, 0)
base := containerWidth * uint64(num)
if left {
for i := uint64(0); i < 20001; i += 3 {
ret = append(ret, base+i)
}
}
if mid {
for i := uint64(21000); i < 41001; i += 3 {
ret = append(ret, base+i)
}
}
if right {
for i := uint64(45537); i <= 65535; i += 3 {
ret = append(ret, base+i)
}
}
return ret
}
func bitmapVariousContainers() *Bitmap {
bits := make([]uint64, 0)
bits = append(bits, rleCont(0, true, true, true)...)
bits = append(bits, rleCont(1, true, true, true)...)
bits = append(bits, arrCont(2, true, true, true)...)
bits = append(bits, arrCont(3, true, true, true)...)
bits = append(bits, bitCont(4, true, true, true)...)
bits = append(bits, bitCont(5, true, true, true)...)
bits = append(bits, rleCont(6, true, true, true)...)
bits = append(bits, bitCont(7, true, true, true)...)
bits = append(bits, arrCont(8, true, true, true)...)
bits = append(bits, rleCont(9, true, true, true)...)
bm := NewFileBitmap(bits...)
bm.Optimize()
return bm
}
///////////////////////////////////////////////////////////////////////////
func getFunctionName(i interface{}) string {
x := runtime.FuncForPC(reflect.ValueOf(i).Pointer()).Name()
y := strings.Split(x, ".")
y = y[len(y)-1:]
return y[0]
}
func unionInPlaceWrapper(a, b *Container) *Container {
ret := a.Clone().unionInPlace(b)
ret.Repair()
return ret
}
func differenceInPlaceWrapper(a, b *Container) *Container {
a = a.Clone()
a = a.DifferenceInPlace(b)
return a
}
func intersectInPlaceWrapper(a, b *Container) *Container {
return a.Clone().intersectInPlace(b)
}
func TestContainerBitwiseCompare(t *testing.T) {
cts := setupContainerTests()
for t1, containers := range cts {
for name, c := range containers {
for t2, other := range cts {
for otherName, otherC := range other {
err := c.BitwiseCompare(otherC)
if err != nil {
if otherName == name {
t.Fatalf("container types %d/%d, contents %s: unexpected error %v",
t1, t2, name, err)
}
} else {
if name != otherName {
t.Fatalf("container types %d/%d, unexpected %s == %s",
t1, t2, name, otherName)
}
}
}
}
}
}
}
func TestContainerCombinations(t *testing.T) {
cts := setupContainerTests()
containerTypes := []byte{ContainerArray, ContainerBitmap, ContainerRun}
testOps := []testOp{
// intersect
{intersect, "empty", "empty", "empty"},
{intersect, "empty", "full", "empty"},
{intersect, "empty", "firstBitSet", "empty"},
{intersect, "empty", "lastBitSet", "empty"},
{intersect, "empty", "firstBitUnset", "empty"},
{intersect, "empty", "lastBitUnset", "empty"},
{intersect, "empty", "innerBitsSet", "empty"},
{intersect, "empty", "outerBitsSet", "empty"},
{intersect, "empty", "oddBitsSet", "empty"},
{intersect, "empty", "evenBitsSet", "empty"},
//
{intersect, "full", "empty", "empty"},
{intersect, "full", "full", "full"},
{intersect, "full", "firstBitSet", "firstBitSet"},
{intersect, "full", "lastBitSet", "lastBitSet"},
{intersect, "full", "firstBitUnset", "firstBitUnset"},
{intersect, "full", "lastBitUnset", "lastBitUnset"},
{intersect, "full", "innerBitsSet", "innerBitsSet"},
{intersect, "full", "outerBitsSet", "outerBitsSet"},
{intersect, "full", "oddBitsSet", "oddBitsSet"},
{intersect, "full", "evenBitsSet", "evenBitsSet"},
//
{intersect, "firstBitSet", "empty", "empty"},
{intersect, "firstBitSet", "full", "firstBitSet"},
{intersect, "firstBitSet", "firstBitSet", "firstBitSet"},
{intersect, "firstBitSet", "lastBitSet", "empty"},
{intersect, "firstBitSet", "firstBitUnset", "empty"},
{intersect, "firstBitSet", "lastBitUnset", "firstBitSet"},
{intersect, "firstBitSet", "innerBitsSet", "empty"},
{intersect, "firstBitSet", "outerBitsSet", "firstBitSet"},
{intersect, "firstBitSet", "oddBitsSet", "empty"},
{intersect, "firstBitSet", "evenBitsSet", "firstBitSet"},
//
{intersect, "lastBitSet", "empty", "empty"},
{intersect, "lastBitSet", "full", "lastBitSet"},
{intersect, "lastBitSet", "firstBitSet", "empty"},
{intersect, "lastBitSet", "lastBitSet", "lastBitSet"},
{intersect, "lastBitSet", "firstBitUnset", "lastBitSet"},
{intersect, "lastBitSet", "lastBitUnset", "empty"},
{intersect, "lastBitSet", "innerBitsSet", "empty"},
{intersect, "lastBitSet", "outerBitsSet", "lastBitSet"},
{intersect, "lastBitSet", "oddBitsSet", "lastBitSet"},
{intersect, "lastBitSet", "evenBitsSet", "empty"},
//
{intersect, "firstBitUnset", "empty", "empty"},
{intersect, "firstBitUnset", "full", "firstBitUnset"},
{intersect, "firstBitUnset", "firstBitSet", "empty"},
{intersect, "firstBitUnset", "lastBitSet", "lastBitSet"},
{intersect, "firstBitUnset", "firstBitUnset", "firstBitUnset"},
{intersect, "firstBitUnset", "lastBitUnset", "innerBitsSet"},
{intersect, "firstBitUnset", "innerBitsSet", "innerBitsSet"},
{intersect, "firstBitUnset", "outerBitsSet", "lastBitSet"},
{intersect, "firstBitUnset", "oddBitsSet", "oddBitsSet"},
//{intersect, "firstBitUnset", "evenBitsSet", ""},
//
{intersect, "lastBitUnset", "empty", "empty"},
{intersect, "lastBitUnset", "full", "lastBitUnset"},
{intersect, "lastBitUnset", "firstBitSet", "firstBitSet"},
{intersect, "lastBitUnset", "lastBitSet", "empty"},
{intersect, "lastBitUnset", "firstBitUnset", "innerBitsSet"},
{intersect, "lastBitUnset", "lastBitUnset", "lastBitUnset"},
{intersect, "lastBitUnset", "innerBitsSet", "innerBitsSet"},
{intersect, "lastBitUnset", "outerBitsSet", "firstBitSet"},
//{intersect, "lastBitUnset", "oddBitsSet", ""},
{intersect, "lastBitUnset", "evenBitsSet", "evenBitsSet"},
//
{intersect, "innerBitsSet", "empty", "empty"},
{intersect, "innerBitsSet", "full", "innerBitsSet"},
{intersect, "innerBitsSet", "firstBitSet", "empty"},
{intersect, "innerBitsSet", "lastBitSet", "empty"},
{intersect, "innerBitsSet", "firstBitUnset", "innerBitsSet"},
{intersect, "innerBitsSet", "lastBitUnset", "innerBitsSet"},
{intersect, "innerBitsSet", "innerBitsSet", "innerBitsSet"},
{intersect, "innerBitsSet", "outerBitsSet", "empty"},
//{intersect, "innerBitsSet", "oddBitsSet", ""},
//{intersect, "innerBitsSet", "evenBitsSet", ""},
//
{intersect, "outerBitsSet", "empty", "empty"},
{intersect, "outerBitsSet", "full", "outerBitsSet"},
{intersect, "outerBitsSet", "firstBitSet", "firstBitSet"},
{intersect, "outerBitsSet", "lastBitSet", "lastBitSet"},
{intersect, "outerBitsSet", "firstBitUnset", "lastBitSet"},
{intersect, "outerBitsSet", "lastBitUnset", "firstBitSet"},
{intersect, "outerBitsSet", "innerBitsSet", "empty"},
{intersect, "outerBitsSet", "outerBitsSet", "outerBitsSet"},
{intersect, "outerBitsSet", "oddBitsSet", "lastBitSet"},
{intersect, "outerBitsSet", "evenBitsSet", "firstBitSet"},
//
{intersect, "oddBitsSet", "empty", "empty"},
{intersect, "oddBitsSet", "full", "oddBitsSet"},
{intersect, "oddBitsSet", "firstBitSet", "empty"},
{intersect, "oddBitsSet", "lastBitSet", "lastBitSet"},
{intersect, "oddBitsSet", "firstBitUnset", "oddBitsSet"},
//{intersect, "oddBitsSet", "lastBitUnset", ""},
//{intersect, "oddBitsSet", "innerBitsSet", ""},
{intersect, "oddBitsSet", "outerBitsSet", "lastBitSet"},
{intersect, "oddBitsSet", "oddBitsSet", "oddBitsSet"},
{intersect, "oddBitsSet", "evenBitsSet", "empty"},
//
{intersect, "evenBitsSet", "empty", "empty"},
{intersect, "evenBitsSet", "full", "evenBitsSet"},
{intersect, "evenBitsSet", "firstBitSet", "firstBitSet"},
{intersect, "evenBitsSet", "lastBitSet", "empty"},
//{intersect, "evenBitsSet", "firstBitUnset", ""},
{intersect, "evenBitsSet", "lastBitUnset", "evenBitsSet"},
//{intersect, "evenBitsSet", "innerBitsSet", ""},
{intersect, "evenBitsSet", "outerBitsSet", "firstBitSet"},
{intersect, "evenBitsSet", "oddBitsSet", "empty"},
{intersect, "evenBitsSet", "evenBitsSet", "evenBitsSet"},
// intersect in place
{intersectInPlaceWrapper, "empty", "empty", "empty"},
{intersectInPlaceWrapper, "empty", "full", "empty"},
{intersectInPlaceWrapper, "empty", "firstBitSet", "empty"},
{intersectInPlaceWrapper, "empty", "lastBitSet", "empty"},
{intersectInPlaceWrapper, "empty", "firstBitUnset", "empty"},
{intersectInPlaceWrapper, "empty", "lastBitUnset", "empty"},
{intersectInPlaceWrapper, "empty", "innerBitsSet", "empty"},
{intersectInPlaceWrapper, "empty", "outerBitsSet", "empty"},
{intersectInPlaceWrapper, "empty", "oddBitsSet", "empty"},
{intersectInPlaceWrapper, "empty", "evenBitsSet", "empty"},
//
{intersectInPlaceWrapper, "full", "empty", "empty"},
{intersectInPlaceWrapper, "full", "full", "full"},
{intersectInPlaceWrapper, "full", "firstBitSet", "firstBitSet"},
{intersectInPlaceWrapper, "full", "lastBitSet", "lastBitSet"},
{intersectInPlaceWrapper, "full", "firstBitUnset", "firstBitUnset"},
{intersectInPlaceWrapper, "full", "lastBitUnset", "lastBitUnset"},
{intersectInPlaceWrapper, "full", "innerBitsSet", "innerBitsSet"},
{intersectInPlaceWrapper, "full", "outerBitsSet", "outerBitsSet"},
{intersectInPlaceWrapper, "full", "oddBitsSet", "oddBitsSet"},
{intersectInPlaceWrapper, "full", "evenBitsSet", "evenBitsSet"},
//
{intersectInPlaceWrapper, "firstBitSet", "empty", "empty"},
{intersectInPlaceWrapper, "firstBitSet", "full", "firstBitSet"},
{intersectInPlaceWrapper, "firstBitSet", "firstBitSet", "firstBitSet"},
{intersectInPlaceWrapper, "firstBitSet", "lastBitSet", "empty"},
{intersectInPlaceWrapper, "firstBitSet", "firstBitUnset", "empty"},
{intersectInPlaceWrapper, "firstBitSet", "lastBitUnset", "firstBitSet"},
{intersectInPlaceWrapper, "firstBitSet", "innerBitsSet", "empty"},
{intersectInPlaceWrapper, "firstBitSet", "outerBitsSet", "firstBitSet"},
{intersectInPlaceWrapper, "firstBitSet", "oddBitsSet", "empty"},
{intersectInPlaceWrapper, "firstBitSet", "evenBitsSet", "firstBitSet"},
//
{intersectInPlaceWrapper, "lastBitSet", "empty", "empty"},
{intersectInPlaceWrapper, "lastBitSet", "full", "lastBitSet"},
{intersectInPlaceWrapper, "lastBitSet", "firstBitSet", "empty"},
{intersectInPlaceWrapper, "lastBitSet", "lastBitSet", "lastBitSet"},
{intersectInPlaceWrapper, "lastBitSet", "firstBitUnset", "lastBitSet"},
{intersectInPlaceWrapper, "lastBitSet", "lastBitUnset", "empty"},
{intersectInPlaceWrapper, "lastBitSet", "innerBitsSet", "empty"},
{intersectInPlaceWrapper, "lastBitSet", "outerBitsSet", "lastBitSet"},
{intersectInPlaceWrapper, "lastBitSet", "oddBitsSet", "lastBitSet"},
{intersectInPlaceWrapper, "lastBitSet", "evenBitsSet", "empty"},
//
{intersectInPlaceWrapper, "firstBitUnset", "empty", "empty"},
{intersectInPlaceWrapper, "firstBitUnset", "full", "firstBitUnset"},
{intersectInPlaceWrapper, "firstBitUnset", "firstBitSet", "empty"},
{intersectInPlaceWrapper, "firstBitUnset", "lastBitSet", "lastBitSet"},
{intersectInPlaceWrapper, "firstBitUnset", "firstBitUnset", "firstBitUnset"},
{intersectInPlaceWrapper, "firstBitUnset", "lastBitUnset", "innerBitsSet"},
{intersectInPlaceWrapper, "firstBitUnset", "innerBitsSet", "innerBitsSet"},
{intersectInPlaceWrapper, "firstBitUnset", "outerBitsSet", "lastBitSet"},
{intersectInPlaceWrapper, "firstBitUnset", "oddBitsSet", "oddBitsSet"},
//
{intersectInPlaceWrapper, "lastBitUnset", "empty", "empty"},
{intersectInPlaceWrapper, "lastBitUnset", "full", "lastBitUnset"},
{intersectInPlaceWrapper, "lastBitUnset", "firstBitSet", "firstBitSet"},
{intersectInPlaceWrapper, "lastBitUnset", "lastBitSet", "empty"},
{intersectInPlaceWrapper, "lastBitUnset", "firstBitUnset", "innerBitsSet"},
{intersectInPlaceWrapper, "lastBitUnset", "lastBitUnset", "lastBitUnset"},
{intersectInPlaceWrapper, "lastBitUnset", "innerBitsSet", "innerBitsSet"},
{intersectInPlaceWrapper, "lastBitUnset", "outerBitsSet", "firstBitSet"},
{intersectInPlaceWrapper, "lastBitUnset", "evenBitsSet", "evenBitsSet"},
//
{intersectInPlaceWrapper, "innerBitsSet", "empty", "empty"},
{intersectInPlaceWrapper, "innerBitsSet", "full", "innerBitsSet"},
{intersectInPlaceWrapper, "innerBitsSet", "firstBitSet", "empty"},
{intersectInPlaceWrapper, "innerBitsSet", "lastBitSet", "empty"},
{intersectInPlaceWrapper, "innerBitsSet", "firstBitUnset", "innerBitsSet"},
{intersectInPlaceWrapper, "innerBitsSet", "lastBitUnset", "innerBitsSet"},
{intersectInPlaceWrapper, "innerBitsSet", "innerBitsSet", "innerBitsSet"},
{intersectInPlaceWrapper, "innerBitsSet", "outerBitsSet", "empty"},
//
{intersectInPlaceWrapper, "outerBitsSet", "empty", "empty"},
{intersectInPlaceWrapper, "outerBitsSet", "full", "outerBitsSet"},
{intersectInPlaceWrapper, "outerBitsSet", "firstBitSet", "firstBitSet"},
{intersectInPlaceWrapper, "outerBitsSet", "lastBitSet", "lastBitSet"},
{intersectInPlaceWrapper, "outerBitsSet", "firstBitUnset", "lastBitSet"},
{intersectInPlaceWrapper, "outerBitsSet", "lastBitUnset", "firstBitSet"},
{intersectInPlaceWrapper, "outerBitsSet", "innerBitsSet", "empty"},
{intersectInPlaceWrapper, "outerBitsSet", "outerBitsSet", "outerBitsSet"},
{intersectInPlaceWrapper, "outerBitsSet", "oddBitsSet", "lastBitSet"},
{intersectInPlaceWrapper, "outerBitsSet", "evenBitsSet", "firstBitSet"},
//
{intersectInPlaceWrapper, "oddBitsSet", "empty", "empty"},
{intersectInPlaceWrapper, "oddBitsSet", "full", "oddBitsSet"},
{intersectInPlaceWrapper, "oddBitsSet", "firstBitSet", "empty"},
{intersectInPlaceWrapper, "oddBitsSet", "lastBitSet", "lastBitSet"},
{intersectInPlaceWrapper, "oddBitsSet", "firstBitUnset", "oddBitsSet"},
{intersectInPlaceWrapper, "oddBitsSet", "outerBitsSet", "lastBitSet"},
{intersectInPlaceWrapper, "oddBitsSet", "oddBitsSet", "oddBitsSet"},
{intersectInPlaceWrapper, "oddBitsSet", "evenBitsSet", "empty"},
//
{intersectInPlaceWrapper, "evenBitsSet", "empty", "empty"},
{intersectInPlaceWrapper, "evenBitsSet", "full", "evenBitsSet"},
{intersectInPlaceWrapper, "evenBitsSet", "firstBitSet", "firstBitSet"},
{intersectInPlaceWrapper, "evenBitsSet", "lastBitSet", "empty"},
{intersectInPlaceWrapper, "evenBitsSet", "lastBitUnset", "evenBitsSet"},
{intersectInPlaceWrapper, "evenBitsSet", "outerBitsSet", "firstBitSet"},
{intersectInPlaceWrapper, "evenBitsSet", "oddBitsSet", "empty"},
{intersectInPlaceWrapper, "evenBitsSet", "evenBitsSet", "evenBitsSet"},
// union
{union, "empty", "empty", "empty"},
{union, "empty", "full", "full"},
{union, "empty", "firstBitSet", "firstBitSet"},
{union, "empty", "lastBitSet", "lastBitSet"},
{union, "empty", "firstBitUnset", "firstBitUnset"},
{union, "empty", "lastBitUnset", "lastBitUnset"},
{union, "empty", "innerBitsSet", "innerBitsSet"},
{union, "empty", "outerBitsSet", "outerBitsSet"},
{union, "empty", "oddBitsSet", "oddBitsSet"},
{union, "empty", "evenBitsSet", "evenBitsSet"},
//
{union, "full", "empty", "full"},
{union, "full", "full", "full"},
{union, "full", "firstBitSet", "full"},
{union, "full", "lastBitSet", "full"},
{union, "full", "firstBitUnset", "full"},
{union, "full", "lastBitUnset", "full"},
{union, "full", "innerBitsSet", "full"},
{union, "full", "outerBitsSet", "full"},
{union, "full", "oddBitsSet", "full"},
{union, "full", "evenBitsSet", "full"},
//
{union, "firstBitSet", "empty", "firstBitSet"},
{union, "firstBitSet", "full", "full"},
{union, "firstBitSet", "firstBitSet", "firstBitSet"},
{union, "firstBitSet", "lastBitSet", "outerBitsSet"},
{union, "firstBitSet", "firstBitUnset", "full"},
{union, "firstBitSet", "lastBitUnset", "lastBitUnset"},
{union, "firstBitSet", "innerBitsSet", "lastBitUnset"},
{union, "firstBitSet", "outerBitsSet", "outerBitsSet"},
//{union, "firstBitSet", "oddBitsSet", ""},
{union, "firstBitSet", "evenBitsSet", "evenBitsSet"},
//
{union, "lastBitSet", "empty", "lastBitSet"},
{union, "lastBitSet", "full", "full"},
{union, "lastBitSet", "firstBitSet", "outerBitsSet"},
{union, "lastBitSet", "lastBitSet", "lastBitSet"},
{union, "lastBitSet", "firstBitUnset", "firstBitUnset"},
{union, "lastBitSet", "lastBitUnset", "full"},
{union, "lastBitSet", "innerBitsSet", "firstBitUnset"},
{union, "lastBitSet", "outerBitsSet", "outerBitsSet"},
{union, "lastBitSet", "oddBitsSet", "oddBitsSet"},
//{union, "lastBitSet", "evenBitsSet", ""},
//
{union, "firstBitUnset", "empty", "firstBitUnset"},
{union, "firstBitUnset", "full", "full"},
{union, "firstBitUnset", "firstBitSet", "full"},
{union, "firstBitUnset", "lastBitSet", "firstBitUnset"},
{union, "firstBitUnset", "firstBitUnset", "firstBitUnset"},
{union, "firstBitUnset", "lastBitUnset", "full"},
{union, "firstBitUnset", "innerBitsSet", "firstBitUnset"},
{union, "firstBitUnset", "outerBitsSet", "full"},
{union, "firstBitUnset", "oddBitsSet", "firstBitUnset"},
{union, "firstBitUnset", "evenBitsSet", "full"},
//
{union, "lastBitUnset", "empty", "lastBitUnset"},
{union, "lastBitUnset", "full", "full"},
{union, "lastBitUnset", "firstBitSet", "lastBitUnset"},
{union, "lastBitUnset", "lastBitSet", "full"},
{union, "lastBitUnset", "firstBitUnset", "full"},
{union, "lastBitUnset", "lastBitUnset", "lastBitUnset"},
{union, "lastBitUnset", "innerBitsSet", "lastBitUnset"},
{union, "lastBitUnset", "outerBitsSet", "full"},
{union, "lastBitUnset", "oddBitsSet", "full"},
{union, "lastBitUnset", "evenBitsSet", "lastBitUnset"},
//
{union, "innerBitsSet", "empty", "innerBitsSet"},
{union, "innerBitsSet", "full", "full"},
{union, "innerBitsSet", "firstBitSet", "lastBitUnset"},
{union, "innerBitsSet", "lastBitSet", "firstBitUnset"},
{union, "innerBitsSet", "firstBitUnset", "firstBitUnset"},
{union, "innerBitsSet", "lastBitUnset", "lastBitUnset"},
{union, "innerBitsSet", "innerBitsSet", "innerBitsSet"},
{union, "innerBitsSet", "outerBitsSet", "full"},
{union, "innerBitsSet", "oddBitsSet", "firstBitUnset"},
{union, "innerBitsSet", "evenBitsSet", "lastBitUnset"},
//
{union, "outerBitsSet", "empty", "outerBitsSet"},
{union, "outerBitsSet", "full", "full"},
{union, "outerBitsSet", "firstBitSet", "outerBitsSet"},
{union, "outerBitsSet", "lastBitSet", "outerBitsSet"},
{union, "outerBitsSet", "firstBitUnset", "full"},
{union, "outerBitsSet", "lastBitUnset", "full"},
{union, "outerBitsSet", "innerBitsSet", "full"},
{union, "outerBitsSet", "outerBitsSet", "outerBitsSet"},
//{union, "outerBitsSet", "oddBitsSet", ""},
//{union, "outerBitsSet", "evenBitsSet", ""},
//
{union, "oddBitsSet", "empty", "oddBitsSet"},
{union, "oddBitsSet", "full", "full"},
//{union, "oddBitsSet", "firstBitSet", ""},
{union, "oddBitsSet", "lastBitSet", "oddBitsSet"},
{union, "oddBitsSet", "firstBitUnset", "firstBitUnset"},
{union, "oddBitsSet", "lastBitUnset", "full"},
{union, "oddBitsSet", "innerBitsSet", "firstBitUnset"},
//{union, "oddBitsSet", "outerBitsSet", ""},
{union, "oddBitsSet", "oddBitsSet", "oddBitsSet"},
{union, "oddBitsSet", "evenBitsSet", "full"},
//
{union, "evenBitsSet", "empty", "evenBitsSet"},
{union, "evenBitsSet", "full", "full"},
{union, "evenBitsSet", "firstBitSet", "evenBitsSet"},
//{union, "evenBitsSet", "lastBitSet", ""},
{union, "evenBitsSet", "firstBitUnset", "full"},
{union, "evenBitsSet", "lastBitUnset", "lastBitUnset"},
{union, "evenBitsSet", "innerBitsSet", "lastBitUnset"},
//{union, "evenBitsSet", "outerBitsSet", ""},
{union, "evenBitsSet", "oddBitsSet", "full"},
{union, "evenBitsSet", "evenBitsSet", "evenBitsSet"},
// unionInPlaceWrapper
{unionInPlaceWrapper, "empty", "empty", "empty"},
{unionInPlaceWrapper, "empty", "full", "full"},
{unionInPlaceWrapper, "empty", "firstBitSet", "firstBitSet"},
{unionInPlaceWrapper, "empty", "lastBitSet", "lastBitSet"},
{unionInPlaceWrapper, "empty", "firstBitUnset", "firstBitUnset"},
{unionInPlaceWrapper, "empty", "lastBitUnset", "lastBitUnset"},
{unionInPlaceWrapper, "empty", "innerBitsSet", "innerBitsSet"},
{unionInPlaceWrapper, "empty", "outerBitsSet", "outerBitsSet"},
{unionInPlaceWrapper, "empty", "oddBitsSet", "oddBitsSet"},
{unionInPlaceWrapper, "empty", "evenBitsSet", "evenBitsSet"},
//
{unionInPlaceWrapper, "full", "empty", "full"},
{unionInPlaceWrapper, "full", "full", "full"},
{unionInPlaceWrapper, "full", "firstBitSet", "full"},
{unionInPlaceWrapper, "full", "lastBitSet", "full"},
{unionInPlaceWrapper, "full", "firstBitUnset", "full"},
{unionInPlaceWrapper, "full", "lastBitUnset", "full"},
{unionInPlaceWrapper, "full", "innerBitsSet", "full"},
{unionInPlaceWrapper, "full", "outerBitsSet", "full"},
{unionInPlaceWrapper, "full", "oddBitsSet", "full"},
{unionInPlaceWrapper, "full", "evenBitsSet", "full"},
//
{unionInPlaceWrapper, "firstBitSet", "empty", "firstBitSet"},
{unionInPlaceWrapper, "firstBitSet", "full", "full"},
{unionInPlaceWrapper, "firstBitSet", "firstBitSet", "firstBitSet"},
{unionInPlaceWrapper, "firstBitSet", "lastBitSet", "outerBitsSet"},
{unionInPlaceWrapper, "firstBitSet", "firstBitUnset", "full"},
{unionInPlaceWrapper, "firstBitSet", "lastBitUnset", "lastBitUnset"},
{unionInPlaceWrapper, "firstBitSet", "innerBitsSet", "lastBitUnset"},
{unionInPlaceWrapper, "firstBitSet", "outerBitsSet", "outerBitsSet"},
//{unionInPlaceWrapper, "firstBitSet", "oddBitsSet", ""},
{unionInPlaceWrapper, "firstBitSet", "evenBitsSet", "evenBitsSet"},
//
{unionInPlaceWrapper, "lastBitSet", "empty", "lastBitSet"},
{unionInPlaceWrapper, "lastBitSet", "full", "full"},
{unionInPlaceWrapper, "lastBitSet", "firstBitSet", "outerBitsSet"},
{unionInPlaceWrapper, "lastBitSet", "lastBitSet", "lastBitSet"},
{unionInPlaceWrapper, "lastBitSet", "firstBitUnset", "firstBitUnset"},
{unionInPlaceWrapper, "lastBitSet", "lastBitUnset", "full"},
{unionInPlaceWrapper, "lastBitSet", "innerBitsSet", "firstBitUnset"},
{unionInPlaceWrapper, "lastBitSet", "outerBitsSet", "outerBitsSet"},
{unionInPlaceWrapper, "lastBitSet", "oddBitsSet", "oddBitsSet"},
//{unionInPlaceWrapper, "lastBitSet", "evenBitsSet", ""},
//
{unionInPlaceWrapper, "firstBitUnset", "empty", "firstBitUnset"},
{unionInPlaceWrapper, "firstBitUnset", "full", "full"},
{unionInPlaceWrapper, "firstBitUnset", "firstBitSet", "full"},
{unionInPlaceWrapper, "firstBitUnset", "lastBitSet", "firstBitUnset"},
{unionInPlaceWrapper, "firstBitUnset", "firstBitUnset", "firstBitUnset"},
{unionInPlaceWrapper, "firstBitUnset", "lastBitUnset", "full"},
{unionInPlaceWrapper, "firstBitUnset", "innerBitsSet", "firstBitUnset"},
{unionInPlaceWrapper, "firstBitUnset", "outerBitsSet", "full"},
{unionInPlaceWrapper, "firstBitUnset", "oddBitsSet", "firstBitUnset"},
{unionInPlaceWrapper, "firstBitUnset", "evenBitsSet", "full"},
//
{unionInPlaceWrapper, "lastBitUnset", "empty", "lastBitUnset"},
{unionInPlaceWrapper, "lastBitUnset", "full", "full"},
{unionInPlaceWrapper, "lastBitUnset", "firstBitSet", "lastBitUnset"},
{unionInPlaceWrapper, "lastBitUnset", "lastBitSet", "full"},
{unionInPlaceWrapper, "lastBitUnset", "firstBitUnset", "full"},
{unionInPlaceWrapper, "lastBitUnset", "lastBitUnset", "lastBitUnset"},
{unionInPlaceWrapper, "lastBitUnset", "innerBitsSet", "lastBitUnset"},
{unionInPlaceWrapper, "lastBitUnset", "outerBitsSet", "full"},
{unionInPlaceWrapper, "lastBitUnset", "oddBitsSet", "full"},
{unionInPlaceWrapper, "lastBitUnset", "evenBitsSet", "lastBitUnset"},
//
{unionInPlaceWrapper, "innerBitsSet", "empty", "innerBitsSet"},
{unionInPlaceWrapper, "innerBitsSet", "full", "full"},
{unionInPlaceWrapper, "innerBitsSet", "firstBitSet", "lastBitUnset"},
{unionInPlaceWrapper, "innerBitsSet", "lastBitSet", "firstBitUnset"},
{unionInPlaceWrapper, "innerBitsSet", "firstBitUnset", "firstBitUnset"},
{unionInPlaceWrapper, "innerBitsSet", "lastBitUnset", "lastBitUnset"},
{unionInPlaceWrapper, "innerBitsSet", "innerBitsSet", "innerBitsSet"},
{unionInPlaceWrapper, "innerBitsSet", "outerBitsSet", "full"},
{unionInPlaceWrapper, "innerBitsSet", "oddBitsSet", "firstBitUnset"},
{unionInPlaceWrapper, "innerBitsSet", "evenBitsSet", "lastBitUnset"},
//
{unionInPlaceWrapper, "outerBitsSet", "empty", "outerBitsSet"},
{unionInPlaceWrapper, "outerBitsSet", "full", "full"},
{unionInPlaceWrapper, "outerBitsSet", "firstBitSet", "outerBitsSet"},
{unionInPlaceWrapper, "outerBitsSet", "lastBitSet", "outerBitsSet"},
{unionInPlaceWrapper, "outerBitsSet", "firstBitUnset", "full"},
{unionInPlaceWrapper, "outerBitsSet", "lastBitUnset", "full"},
{unionInPlaceWrapper, "outerBitsSet", "innerBitsSet", "full"},
{unionInPlaceWrapper, "outerBitsSet", "outerBitsSet", "outerBitsSet"},
//{unionInPlaceWrapper, "outerBitsSet", "oddBitsSet", ""},
//{unionInPlaceWrapper, "outerBitsSet", "evenBitsSet", ""},
//
{unionInPlaceWrapper, "oddBitsSet", "empty", "oddBitsSet"},
{unionInPlaceWrapper, "oddBitsSet", "full", "full"},
//{unionInPlaceWrapper, "oddBitsSet", "firstBitSet", ""},
{unionInPlaceWrapper, "oddBitsSet", "lastBitSet", "oddBitsSet"},
{unionInPlaceWrapper, "oddBitsSet", "firstBitUnset", "firstBitUnset"},
{unionInPlaceWrapper, "oddBitsSet", "lastBitUnset", "full"},
{unionInPlaceWrapper, "oddBitsSet", "innerBitsSet", "firstBitUnset"},
//{unionInPlaceWrapper, "oddBitsSet", "outerBitsSet", ""},
{unionInPlaceWrapper, "oddBitsSet", "oddBitsSet", "oddBitsSet"},
{unionInPlaceWrapper, "oddBitsSet", "evenBitsSet", "full"},
//
{unionInPlaceWrapper, "evenBitsSet", "empty", "evenBitsSet"},
{unionInPlaceWrapper, "evenBitsSet", "full", "full"},
{unionInPlaceWrapper, "evenBitsSet", "firstBitSet", "evenBitsSet"},
//{unionInPlaceWrapper, "evenBitsSet", "lastBitSet", ""},
{unionInPlaceWrapper, "evenBitsSet", "firstBitUnset", "full"},
{unionInPlaceWrapper, "evenBitsSet", "lastBitUnset", "lastBitUnset"},
{unionInPlaceWrapper, "evenBitsSet", "innerBitsSet", "lastBitUnset"},
//{unionInPlaceWrapper, "evenBitsSet", "outerBitsSet", ""},
{unionInPlaceWrapper, "evenBitsSet", "oddBitsSet", "full"},
{unionInPlaceWrapper, "evenBitsSet", "evenBitsSet", "evenBitsSet"},
// difference
{difference, "empty", "empty", "empty"},
{difference, "empty", "full", "empty"},
{difference, "empty", "firstBitSet", "empty"},
{difference, "empty", "lastBitSet", "empty"},
{difference, "empty", "firstBitUnset", "empty"},
{difference, "empty", "lastBitUnset", "empty"},
{difference, "empty", "innerBitsSet", "empty"},
{difference, "empty", "outerBitsSet", "empty"},
{difference, "empty", "oddBitsSet", "empty"},
{difference, "empty", "evenBitsSet", "empty"},
//
{difference, "full", "empty", "full"},
{difference, "full", "full", "empty"},
{difference, "full", "firstBitSet", "firstBitUnset"},
{difference, "full", "lastBitSet", "lastBitUnset"},
{difference, "full", "firstBitUnset", "firstBitSet"},
{difference, "full", "lastBitUnset", "lastBitSet"},
{difference, "full", "innerBitsSet", "outerBitsSet"},
{difference, "full", "outerBitsSet", "innerBitsSet"},
{difference, "full", "oddBitsSet", "evenBitsSet"},
{difference, "full", "evenBitsSet", "oddBitsSet"},
//
{difference, "firstBitSet", "empty", "firstBitSet"},
{difference, "firstBitSet", "full", "empty"},
{difference, "firstBitSet", "firstBitSet", "empty"},
{difference, "firstBitSet", "lastBitSet", "firstBitSet"},
{difference, "firstBitSet", "firstBitUnset", "firstBitSet"},
{difference, "firstBitSet", "lastBitUnset", "empty"},
{difference, "firstBitSet", "innerBitsSet", "firstBitSet"},
{difference, "firstBitSet", "outerBitsSet", "empty"},
{difference, "firstBitSet", "oddBitsSet", "firstBitSet"},
{difference, "firstBitSet", "evenBitsSet", "empty"},
//
{difference, "lastBitSet", "empty", "lastBitSet"},
{difference, "lastBitSet", "full", "empty"},
{difference, "lastBitSet", "firstBitSet", "lastBitSet"},
{difference, "lastBitSet", "lastBitSet", "empty"},
{difference, "lastBitSet", "firstBitUnset", "empty"},
{difference, "lastBitSet", "lastBitUnset", "lastBitSet"},
{difference, "lastBitSet", "innerBitsSet", "lastBitSet"},
{difference, "lastBitSet", "outerBitsSet", "empty"},
{difference, "lastBitSet", "oddBitsSet", "empty"},
{difference, "lastBitSet", "evenBitsSet", "lastBitSet"},
//
{difference, "firstBitUnset", "empty", "firstBitUnset"},
{difference, "firstBitUnset", "full", "empty"},
{difference, "firstBitUnset", "firstBitSet", "firstBitUnset"},
{difference, "firstBitUnset", "lastBitSet", "innerBitsSet"},
{difference, "firstBitUnset", "firstBitUnset", "empty"},
{difference, "firstBitUnset", "lastBitUnset", "lastBitSet"},
{difference, "firstBitUnset", "innerBitsSet", "lastBitSet"},
{difference, "firstBitUnset", "outerBitsSet", "innerBitsSet"},
//{difference, "firstBitUnset", "oddBitsSet", ""},
{difference, "firstBitUnset", "evenBitsSet", "oddBitsSet"},
//
{difference, "lastBitUnset", "empty", "lastBitUnset"},
{difference, "lastBitUnset", "full", "empty"},
{difference, "lastBitUnset", "firstBitSet", "innerBitsSet"},
{difference, "lastBitUnset", "lastBitSet", "lastBitUnset"},
{difference, "lastBitUnset", "firstBitUnset", "firstBitSet"},
{difference, "lastBitUnset", "lastBitUnset", "empty"},
{difference, "lastBitUnset", "innerBitsSet", "firstBitSet"},
{difference, "lastBitUnset", "outerBitsSet", "innerBitsSet"},
{difference, "lastBitUnset", "oddBitsSet", "evenBitsSet"},
//{difference, "lastBitUnset", "evenBitsSet", ""},
//
{difference, "innerBitsSet", "empty", "innerBitsSet"},
{difference, "innerBitsSet", "full", "empty"},
{difference, "innerBitsSet", "firstBitSet", "innerBitsSet"},
{difference, "innerBitsSet", "lastBitSet", "innerBitsSet"},
{difference, "innerBitsSet", "firstBitUnset", "empty"},
{difference, "innerBitsSet", "lastBitUnset", "empty"},
{difference, "innerBitsSet", "innerBitsSet", "empty"},
{difference, "innerBitsSet", "outerBitsSet", "innerBitsSet"},
//{difference, "innerBitsSet", "oddBitsSet", ""},
//{difference, "innerBitsSet", "evenBitsSet", ""},
//
{difference, "outerBitsSet", "empty", "outerBitsSet"},
{difference, "outerBitsSet", "full", "empty"},
{difference, "outerBitsSet", "firstBitSet", "lastBitSet"},
{difference, "outerBitsSet", "lastBitSet", "firstBitSet"},
{difference, "outerBitsSet", "firstBitUnset", "firstBitSet"},
{difference, "outerBitsSet", "lastBitUnset", "lastBitSet"},
{difference, "outerBitsSet", "innerBitsSet", "outerBitsSet"},
{difference, "outerBitsSet", "outerBitsSet", "empty"},
{difference, "outerBitsSet", "oddBitsSet", "firstBitSet"},
{difference, "outerBitsSet", "evenBitsSet", "lastBitSet"},
//
{difference, "oddBitsSet", "empty", "oddBitsSet"},
{difference, "oddBitsSet", "full", "empty"},
{difference, "oddBitsSet", "firstBitSet", "oddBitsSet"},
//{difference, "oddBitsSet", "lastBitSet", ""},
{difference, "oddBitsSet", "firstBitUnset", "empty"},
{difference, "oddBitsSet", "lastBitUnset", "lastBitSet"},
{difference, "oddBitsSet", "innerBitsSet", "lastBitSet"},
//{difference, "oddBitsSet", "outerBitsSet", ""},
{difference, "oddBitsSet", "oddBitsSet", "empty"},
{difference, "oddBitsSet", "evenBitsSet", "oddBitsSet"},
//
{difference, "evenBitsSet", "empty", "evenBitsSet"},
{difference, "evenBitsSet", "full", "empty"},
//{difference, "evenBitsSet", "firstBitSet", ""},
{difference, "evenBitsSet", "lastBitSet", "evenBitsSet"},
{difference, "evenBitsSet", "firstBitUnset", "firstBitSet"},
{difference, "evenBitsSet", "lastBitUnset", "empty"},
{difference, "evenBitsSet", "innerBitsSet", "firstBitSet"},
//{difference, "evenBitsSet", "outerBitsSet", ""},
{difference, "evenBitsSet", "oddBitsSet", "evenBitsSet"},
{difference, "evenBitsSet", "evenBitsSet", "empty"},
// xor
{xor, "empty", "empty", "empty"},
{xor, "empty", "full", "full"},
{xor, "empty", "firstBitSet", "firstBitSet"},
{xor, "empty", "lastBitSet", "lastBitSet"},
{xor, "empty", "firstBitUnset", "firstBitUnset"},
{xor, "empty", "lastBitUnset", "lastBitUnset"},
{xor, "empty", "innerBitsSet", "innerBitsSet"},
{xor, "empty", "outerBitsSet", "outerBitsSet"},
{xor, "empty", "oddBitsSet", "oddBitsSet"},
{xor, "empty", "evenBitsSet", "evenBitsSet"},
//
{xor, "full", "empty", "full"},
{xor, "full", "full", "empty"},
{xor, "full", "firstBitSet", "firstBitUnset"},
{xor, "full", "lastBitSet", "lastBitUnset"},
{xor, "full", "firstBitUnset", "firstBitSet"},
{xor, "full", "lastBitUnset", "lastBitSet"},
{xor, "full", "innerBitsSet", "outerBitsSet"},
{xor, "full", "outerBitsSet", "innerBitsSet"},
{xor, "full", "oddBitsSet", "evenBitsSet"},
{xor, "full", "evenBitsSet", "oddBitsSet"},
//
{xor, "firstBitSet", "empty", "firstBitSet"},
{xor, "firstBitSet", "full", "firstBitUnset"},
{xor, "firstBitSet", "firstBitSet", "empty"},
{xor, "firstBitSet", "lastBitSet", "outerBitsSet"},
{xor, "firstBitSet", "firstBitUnset", "full"},
{xor, "firstBitSet", "lastBitUnset", "innerBitsSet"},
{xor, "firstBitSet", "innerBitsSet", "lastBitUnset"},
{xor, "firstBitSet", "outerBitsSet", "lastBitSet"},
//{xor, "firstBitSet", "oddBitsSet", ""},
//{xor, "firstBitSet", "evenBitsSet", ""},
//
{xor, "lastBitSet", "empty", "lastBitSet"},
{xor, "lastBitSet", "full", "lastBitUnset"},
{xor, "lastBitSet", "firstBitSet", "outerBitsSet"},
{xor, "lastBitSet", "lastBitSet", "empty"},
{xor, "lastBitSet", "firstBitUnset", "innerBitsSet"},
{xor, "lastBitSet", "lastBitUnset", "full"},
{xor, "lastBitSet", "innerBitsSet", "firstBitUnset"},
{xor, "lastBitSet", "outerBitsSet", "firstBitSet"},
//{xor, "lastBitSet", "oddBitsSet", ""},
//{xor, "lastBitSet", "evenBitsSet", ""},
//
{xor, "firstBitUnset", "empty", "firstBitUnset"},
{xor, "firstBitUnset", "full", "firstBitSet"},
{xor, "firstBitUnset", "firstBitSet", "full"},
{xor, "firstBitUnset", "lastBitSet", "innerBitsSet"},
{xor, "firstBitUnset", "firstBitUnset", "empty"},
{xor, "firstBitUnset", "lastBitUnset", "outerBitsSet"},
{xor, "firstBitUnset", "innerBitsSet", "lastBitSet"},
{xor, "firstBitUnset", "outerBitsSet", "lastBitUnset"},
//{xor, "firstBitUnset", "oddBitsSet", ""},
//{xor, "firstBitUnset", "evenBitsSet", ""},
//
{xor, "lastBitUnset", "empty", "lastBitUnset"},
{xor, "lastBitUnset", "full", "lastBitSet"},
{xor, "lastBitUnset", "firstBitSet", "innerBitsSet"},
{xor, "lastBitUnset", "lastBitSet", "full"},
{xor, "lastBitUnset", "firstBitUnset", "outerBitsSet"},
{xor, "lastBitUnset", "lastBitUnset", "empty"},
{xor, "lastBitUnset", "innerBitsSet", "firstBitSet"},
{xor, "lastBitUnset", "outerBitsSet", "firstBitUnset"},
//{xor, "lastBitUnset", "oddBitsSet", ""},
//{xor, "lastBitUnset", "evenBitsSet", ""},
//
{xor, "innerBitsSet", "empty", "innerBitsSet"},
{xor, "innerBitsSet", "full", "outerBitsSet"},
{xor, "innerBitsSet", "firstBitSet", "lastBitUnset"},
{xor, "innerBitsSet", "lastBitSet", "firstBitUnset"},
{xor, "innerBitsSet", "firstBitUnset", "lastBitSet"},
{xor, "innerBitsSet", "lastBitUnset", "firstBitSet"},
{xor, "innerBitsSet", "innerBitsSet", "empty"},
{xor, "innerBitsSet", "outerBitsSet", "full"},
//{xor, "innerBitsSet", "oddBitsSet", ""},
//{xor, "innerBitsSet", "evenBitsSet", ""},
//
{xor, "outerBitsSet", "empty", "outerBitsSet"},
{xor, "outerBitsSet", "full", "innerBitsSet"},
{xor, "outerBitsSet", "firstBitSet", "lastBitSet"},
{xor, "outerBitsSet", "lastBitSet", "firstBitSet"},
{xor, "outerBitsSet", "firstBitUnset", "lastBitUnset"},
{xor, "outerBitsSet", "lastBitUnset", "firstBitUnset"},
{xor, "outerBitsSet", "innerBitsSet", "full"},
{xor, "outerBitsSet", "outerBitsSet", "empty"},
//{xor, "outerBitsSet", "oddBitsSet", ""},
//{xor, "outerBitsSet", "evenBitsSet", ""},
//
{xor, "oddBitsSet", "empty", "oddBitsSet"},
{xor, "oddBitsSet", "full", "evenBitsSet"},
//{xor, "oddBitsSet", "firstBitSet", ""},
//{xor, "oddBitsSet", "lastBitSet", ""},
//{xor, "oddBitsSet", "firstBitUnset", ""},
//{xor, "oddBitsSet", "lastBitUnset", ""},
//{xor, "oddBitsSet", "innerBitsSet", ""},
//{xor, "oddBitsSet", "outerBitsSet", ""},
{xor, "oddBitsSet", "oddBitsSet", "empty"},
{xor, "oddBitsSet", "evenBitsSet", "full"},
//
{xor, "evenBitsSet", "empty", "evenBitsSet"},
{xor, "evenBitsSet", "full", "oddBitsSet"},
//{xor, "evenBitsSet", "firstBitSet", ""},
//{xor, "evenBitsSet", "lastBitSet", ""},
//{xor, "evenBitsSet", "firstBitUnset", ""},
//{xor, "evenBitsSet", "lastBitUnset", ""},
//{xor, "evenBitsSet", "innerBitsSet", ""},
//{xor, "evenBitsSet", "outerBitsSet", ""},
{xor, "evenBitsSet", "oddBitsSet", "full"},
{xor, "evenBitsSet", "evenBitsSet", "empty"},
// flip
{flip, "empty", "", "full"},
{flip, "full", "", "empty"},
{flip, "firstBitSet", "", "firstBitUnset"},
{flip, "lastBitSet", "", "lastBitUnset"},
{flip, "firstBitUnset", "", "firstBitSet"},
{flip, "lastBitUnset", "", "lastBitSet"},
{flip, "innerBitsSet", "", "outerBitsSet"},
{flip, "outerBitsSet", "", "innerBitsSet"},
{flip, "oddBitsSet", "", "evenBitsSet"},
{flip, "evenBitsSet", "", "oddBitsSet"},
// differenceInPlace
{differenceInPlaceWrapper, "empty", "empty", "empty"},
{differenceInPlaceWrapper, "empty", "full", "empty"},
{differenceInPlaceWrapper, "empty", "firstBitSet", "empty"},
{differenceInPlaceWrapper, "empty", "lastBitSet", "empty"},
{differenceInPlaceWrapper, "empty", "firstBitUnset", "empty"},
{differenceInPlaceWrapper, "empty", "lastBitUnset", "empty"},
{differenceInPlaceWrapper, "empty", "innerBitsSet", "empty"},
{differenceInPlaceWrapper, "empty", "outerBitsSet", "empty"},
{differenceInPlaceWrapper, "empty", "oddBitsSet", "empty"},
{differenceInPlaceWrapper, "empty", "evenBitsSet", "empty"},
//
{differenceInPlaceWrapper, "full", "empty", "full"},
{differenceInPlaceWrapper, "full", "full", "empty"},
{differenceInPlaceWrapper, "full", "firstBitSet", "firstBitUnset"},
{differenceInPlaceWrapper, "full", "lastBitSet", "lastBitUnset"},
{differenceInPlaceWrapper, "full", "firstBitUnset", "firstBitSet"},
{differenceInPlaceWrapper, "full", "lastBitUnset", "lastBitSet"},
{differenceInPlaceWrapper, "full", "innerBitsSet", "outerBitsSet"},
{differenceInPlaceWrapper, "full", "outerBitsSet", "innerBitsSet"},
{differenceInPlaceWrapper, "full", "oddBitsSet", "evenBitsSet"},
{differenceInPlaceWrapper, "full", "evenBitsSet", "oddBitsSet"},
//
{differenceInPlaceWrapper, "firstBitSet", "empty", "firstBitSet"},
{differenceInPlaceWrapper, "firstBitSet", "full", "empty"},
{differenceInPlaceWrapper, "firstBitSet", "firstBitSet", "empty"},
{differenceInPlaceWrapper, "firstBitSet", "lastBitSet", "firstBitSet"},
{differenceInPlaceWrapper, "firstBitSet", "firstBitUnset", "firstBitSet"},
{differenceInPlaceWrapper, "firstBitSet", "lastBitUnset", "empty"},
{differenceInPlaceWrapper, "firstBitSet", "innerBitsSet", "firstBitSet"},
{differenceInPlaceWrapper, "firstBitSet", "outerBitsSet", "empty"},
{differenceInPlaceWrapper, "firstBitSet", "oddBitsSet", "firstBitSet"},
{differenceInPlaceWrapper, "firstBitSet", "evenBitsSet", "empty"},
//
{differenceInPlaceWrapper, "lastBitSet", "empty", "lastBitSet"},
{differenceInPlaceWrapper, "lastBitSet", "full", "empty"},
{differenceInPlaceWrapper, "lastBitSet", "firstBitSet", "lastBitSet"},
{differenceInPlaceWrapper, "lastBitSet", "lastBitSet", "empty"},
{differenceInPlaceWrapper, "lastBitSet", "firstBitUnset", "empty"},
{differenceInPlaceWrapper, "lastBitSet", "lastBitUnset", "lastBitSet"},
{differenceInPlaceWrapper, "lastBitSet", "innerBitsSet", "lastBitSet"},
{differenceInPlaceWrapper, "lastBitSet", "outerBitsSet", "empty"},
{differenceInPlaceWrapper, "lastBitSet", "oddBitsSet", "empty"},
{differenceInPlaceWrapper, "lastBitSet", "evenBitsSet", "lastBitSet"},
//
{differenceInPlaceWrapper, "firstBitUnset", "empty", "firstBitUnset"},
{differenceInPlaceWrapper, "firstBitUnset", "full", "empty"},
{differenceInPlaceWrapper, "firstBitUnset", "firstBitSet", "firstBitUnset"},
{differenceInPlaceWrapper, "firstBitUnset", "lastBitSet", "innerBitsSet"},
{differenceInPlaceWrapper, "firstBitUnset", "firstBitUnset", "empty"},
{differenceInPlaceWrapper, "firstBitUnset", "lastBitUnset", "lastBitSet"},
{differenceInPlaceWrapper, "firstBitUnset", "innerBitsSet", "lastBitSet"},
{differenceInPlaceWrapper, "firstBitUnset", "outerBitsSet", "innerBitsSet"},
//{differenceInPlaceWrapper, "firstBitUnset", "oddBitsSet", ""},
{differenceInPlaceWrapper, "firstBitUnset", "evenBitsSet", "oddBitsSet"},
//
{differenceInPlaceWrapper, "lastBitUnset", "empty", "lastBitUnset"},
{differenceInPlaceWrapper, "lastBitUnset", "full", "empty"},
{differenceInPlaceWrapper, "lastBitUnset", "firstBitSet", "innerBitsSet"},
{differenceInPlaceWrapper, "lastBitUnset", "lastBitSet", "lastBitUnset"},
{differenceInPlaceWrapper, "lastBitUnset", "firstBitUnset", "firstBitSet"},
{differenceInPlaceWrapper, "lastBitUnset", "lastBitUnset", "empty"},
{differenceInPlaceWrapper, "lastBitUnset", "innerBitsSet", "firstBitSet"},
{differenceInPlaceWrapper, "lastBitUnset", "outerBitsSet", "innerBitsSet"},
{differenceInPlaceWrapper, "lastBitUnset", "oddBitsSet", "evenBitsSet"},
//{differenceInPlaceWrapper, "lastBitUnset", "evenBitsSet", ""},
//
{differenceInPlaceWrapper, "innerBitsSet", "empty", "innerBitsSet"},
{differenceInPlaceWrapper, "innerBitsSet", "full", "empty"},
{differenceInPlaceWrapper, "innerBitsSet", "firstBitSet", "innerBitsSet"},
{differenceInPlaceWrapper, "innerBitsSet", "lastBitSet", "innerBitsSet"},
{differenceInPlaceWrapper, "innerBitsSet", "firstBitUnset", "empty"},
{differenceInPlaceWrapper, "innerBitsSet", "lastBitUnset", "empty"},
{differenceInPlaceWrapper, "innerBitsSet", "innerBitsSet", "empty"},
{differenceInPlaceWrapper, "innerBitsSet", "outerBitsSet", "innerBitsSet"},
//{differenceInPlaceWrapper, "innerBitsSet", "oddBitsSet", ""},
//{differenceInPlaceWrapper, "innerBitsSet", "evenBitsSet", ""},
//
{differenceInPlaceWrapper, "outerBitsSet", "empty", "outerBitsSet"},
{differenceInPlaceWrapper, "outerBitsSet", "full", "empty"},
{differenceInPlaceWrapper, "outerBitsSet", "firstBitSet", "lastBitSet"},
{differenceInPlaceWrapper, "outerBitsSet", "lastBitSet", "firstBitSet"},
{differenceInPlaceWrapper, "outerBitsSet", "firstBitUnset", "firstBitSet"},
{differenceInPlaceWrapper, "outerBitsSet", "lastBitUnset", "lastBitSet"},
{differenceInPlaceWrapper, "outerBitsSet", "innerBitsSet", "outerBitsSet"},
{differenceInPlaceWrapper, "outerBitsSet", "outerBitsSet", "empty"},
{differenceInPlaceWrapper, "outerBitsSet", "oddBitsSet", "firstBitSet"},
{differenceInPlaceWrapper, "outerBitsSet", "evenBitsSet", "lastBitSet"},
//
{differenceInPlaceWrapper, "oddBitsSet", "empty", "oddBitsSet"},
{differenceInPlaceWrapper, "oddBitsSet", "full", "empty"},
{differenceInPlaceWrapper, "oddBitsSet", "firstBitSet", "oddBitsSet"},
//{differenceInPlaceWrapper, "oddBitsSet", "lastBitSet", ""},
{differenceInPlaceWrapper, "oddBitsSet", "firstBitUnset", "empty"},
{differenceInPlaceWrapper, "oddBitsSet", "lastBitUnset", "lastBitSet"},
{differenceInPlaceWrapper, "oddBitsSet", "innerBitsSet", "lastBitSet"},
//{differenceInPlaceWrapper, "oddBitsSet", "outerBitsSet", ""},
{differenceInPlaceWrapper, "oddBitsSet", "oddBitsSet", "empty"},
{differenceInPlaceWrapper, "oddBitsSet", "evenBitsSet", "oddBitsSet"},
//
{differenceInPlaceWrapper, "evenBitsSet", "empty", "evenBitsSet"},
{differenceInPlaceWrapper, "evenBitsSet", "full", "empty"},
//{differenceInPlaceWrapper, "evenBitsSet", "firstBitSet", ""},
{differenceInPlaceWrapper, "evenBitsSet", "lastBitSet", "evenBitsSet"},
{differenceInPlaceWrapper, "evenBitsSet", "firstBitUnset", "firstBitSet"},
{differenceInPlaceWrapper, "evenBitsSet", "lastBitUnset", "empty"},
{differenceInPlaceWrapper, "evenBitsSet", "innerBitsSet", "firstBitSet"},
//{differenceInPlaceWrapper, "evenBitsSet", "outerBitsSet", ""},
{differenceInPlaceWrapper, "evenBitsSet", "oddBitsSet", "evenBitsSet"},
{differenceInPlaceWrapper, "evenBitsSet", "evenBitsSet", "empty"},
}
for _, testOp := range testOps {
for _, x := range containerTypes {
for _, y := range containerTypes {
desc := fmt.Sprintf("%s(%s/%s, %s/%s)", getFunctionName(testOp.f), containerTypeNames[x], testOp.x, containerTypeNames[y], testOp.y)
t.Run(desc, func(t *testing.T) {
ret := runContainerFunc(testOp.f, cts[x][testOp.x], cts[y][testOp.y])
exp := testOp.exp
// Compare to the same-type container, which is usually the cheapest
// to compare with.
ct := ret.typ()
if err := ret.BitwiseCompare(cts[ct][exp]); err != nil {
t.Error(err)
}
})
}
}
}
}
// func getFunc(func(a, b *container) *container, m, n *container) *container {
func runContainerFunc(f interface{}, c ...*Container) *Container {
switch f := f.(type) {
case func(*Container) *Container:
return f(c[0])
case func(*Container, *Container) *Container:
return f(c[0], c[1])
}
return nil
}
func TestUnmarshalRoaringWithNoErrors(t *testing.T) {
testCases := []struct {
roaringData string
roaringFileName string
count uint64
expectedBits string
}{
{ // generated serialize image from java(clojure) with arrays
roaringData: "3A300000020000000000020001000000180000001E0000000100020003000100",
count: 4,
expectedBits: "[1 2 3 65537]",
},
{ // generated serialize image from java(clojure) with a run and array
roaringData: "3B3001000100000900010000000100010009000100",
count: 11,
expectedBits: "[1 2 3 4 5 6 7 8 9 10 65537]",
},
{ // had to use an external file because emacs was barfing on the long line :()
roaringFileName: "testdata/bitmapcontainer.roaringbitmap",
count: 10000,
expectedBits: "X",
},
}
var testContainer []byte
var err error
for _, testCase := range testCases {
if testCase.roaringFileName == "" {
testContainer, err = hex.DecodeString(testCase.roaringData)
if err != nil {
t.Fatalf("hex decode %s", err)
}
} else {
testContainer, _ = os.ReadFile(testCase.roaringFileName)
}
bm := NewBitmap()
err = bm.UnmarshalBinary(testContainer)
if err != nil {
t.Fatalf("UnmarshalOfficialRoaring %s", err)
}
if bm.Count() != testCase.count {
t.Fatalf("expecting %s got %d", testCase.expectedBits, bm.Count())
}
}
}
func TestUnmarshalRoaringWithErrors(t *testing.T) {
//testing bitmaps with no containers
noContainers := []struct {
hexString string
expectedError string
}{
{ // Runs a bitmap without runs and no containers through the official roaring
hexString: "3A30000000000000",
expectedError: "header: malformed bitmap, key-cardinality slice overruns buffer at 8",
},
{ // Runs a bitmap with runs and no containers through the official roaring
hexString: "3B30000000000000",
expectedError: "header: malformed bitmap, key-cardinality slice overruns buffer at 9",
},
{ // Runs a bitmap in the Pilosa format through the Pilosa roaring
hexString: "3C30000000000000",
},
}
for _, loopContainers := range noContainers {
zeroContainers, err := hex.DecodeString(loopContainers.hexString)
if err != nil {
t.Fatalf("hex decode %s", err)
}
bm := NewBitmap()
err = bm.UnmarshalBinary(zeroContainers)
if err != nil {
if !strings.Contains(err.Error(), loopContainers.expectedError) {
t.Fatalf("Expected: %s, Got: %s", loopContainers.expectedError, err)
}
}
}
}
func BenchmarkUnionBitmapBitmapInPlace(b *testing.B) {
b1 := newTestBitmapContainer()
b2 := newTestBitmapContainer()
for n := 0; n < b.N; n++ {
b1 = unionBitmapBitmapInPlace(b1, b2)
}
}
func BenchmarkBitmapRepair(b *testing.B) {
b1 := newTestBitmapContainer()
for n := 0; n < b.N; n++ {
b1.bitmapRepair()
}
}
func newTestBitmapContainer() *Container {
return NewContainerBitmap(0, nil)
}
func TestShiftArray(t *testing.T) {
tests := []struct {
array []uint16
exp []uint16
}{
{
array: []uint16{1},
exp: []uint16{2},
},
{
array: []uint16{},
exp: []uint16{},
},
{
array: []uint16{1, 2, 3, 4, 5, 11, 12},
exp: []uint16{2, 3, 4, 5, 6, 12, 13},
},
{
array: []uint16{65535},
exp: []uint16{},
},
}
for i, test := range tests {
a := NewContainerArray(test.array)
ret1, _ := shift(a) // test generic shift function
ret2, _ := shiftArray(a) // test array-specific shift function
// accept nil *Container as valid substitute for empty array
if ret1 == nil {
ret1 = NewContainerArray(nil)
}
if ret2 == nil {
ret2 = NewContainerArray(nil)
}
if !reflect.DeepEqual(ret1.array(), test.exp) {
t.Fatalf("test #%v shift() expected %v, but got %v", i, test.exp, ret1.array())
} else if !reflect.DeepEqual(ret2.array(), test.exp) {
t.Fatalf("test #%v shiftArray() expected %v, but got %v", i, test.exp, ret2.array())
}
}
}
func TestShiftBitmap(t *testing.T) {
// note, bitmaps are provided for us by the ensuing tests
tests := []struct {
bitmap []uint64
exp []uint64
}{
{
bitmap: bitmapFirstBitSet(),
exp: bitmapSecondBitSet(),
},
{
bitmap: bitmapLastBitSet(),
exp: bitmapEmpty(),
},
{
bitmap: bitmapLastBitFirstRowSet(),
exp: bitmapFirstBitSecoundRowSet(),
},
}
for i, test := range tests {
a := NewContainerBitmap(-1, test.bitmap)
ret1, _ := shift(a) // test generic shift function
ret2, _ := shiftBitmap(a) // test bitmap-specific shift function
e := NewContainerBitmap(-1, test.exp)
if !reflect.DeepEqual(ret1.bitmap(), e.bitmap()) {
t.Fatalf("test #%v shift() expected %v, but got %v", i, e.bitmap(), ret1.bitmap())
} else if !reflect.DeepEqual(ret2.bitmap(), test.exp) {
t.Fatalf("test #%v shiftBitmap() expected %v, but got %v", i, e.bitmap(), ret2.bitmap())
}
}
}
func TestShiftRun(t *testing.T) {
tests := []struct {
runs []Interval16
n int32
en int32
exp []Interval16
carry bool
}{
{
runs: []Interval16{{Start: 5, Last: 10}},
n: 5,
en: 5,
exp: []Interval16{{Start: 6, Last: 11}},
carry: false,
},
{
runs: []Interval16{{Start: 5, Last: 65535}},
n: 65530,
en: 65529,
exp: []Interval16{{Start: 6, Last: 65535}},
carry: true,
},
{
runs: []Interval16{{Start: 65535, Last: 65535}},
n: 1,
en: 0,
exp: []Interval16{},
carry: true,
},
}
for i, test := range tests {
a := NewContainerRun(test.runs)
ret1, c1 := shift(a) // test generic shift function
ret2, c2 := shiftRun(a) // test run-specific shift function
if !reflect.DeepEqual(ret1.runs(), test.exp) && c1 == test.carry && ret1.N() == test.en {
t.Fatalf("test #%v shift() expected %v, but got %v %d", i, test.exp, ret1.runs(), ret1.N())
} else if !reflect.DeepEqual(ret2.runs(), test.exp) && c2 == test.carry && ret2.N() == test.en {
t.Fatalf("test #%v shiftRun() expected %v, but got %v %d", i, test.exp, ret2.runs(), ret2.N())
}
}
}
func TestOpLogWriteUnmarshal(t *testing.T) {
tests := []*op{
{
typ: opTypeAdd,
value: 27,
},
{
typ: opTypeRemove,
value: 28,
},
{
typ: opTypeAddBatch,
values: []uint64{1, 2, 6, 19},
},
{
typ: opTypeRemoveBatch,
values: []uint64{1, 2, 6, 19, 22, 44},
},
{
typ: opTypeAddBatch,
values: []uint64{51234567890},
},
{
typ: opTypeRemoveBatch,
values: []uint64{51234567890},
},
{
typ: opTypeAdd,
value: 0,
},
{
typ: opTypeRemove,
value: 0,
},
{
typ: opTypeAddBatch,
values: []uint64{0},
},
{
typ: opTypeRemoveBatch,
values: []uint64{0},
},
{
typ: opTypeAddBatch,
values: []uint64{},
},
{
typ: opTypeRemoveBatch,
values: []uint64{},
},
}
// test each one separately
for i, test := range tests {
t.Run(fmt.Sprintf("%d", i), func(t *testing.T) {
buf := &bytes.Buffer{}
if _, err := test.WriteTo(buf); err != nil {
t.Errorf("writing op %v to buffer: %v", test, err)
}
op := &op{}
if err := op.UnmarshalBinary(buf.Bytes()); err != nil {
t.Fatalf("unmarshling op: %v", err)
}
if err := compareOps(test, op); err != nil {
t.Errorf("mismatch: %v", err)
}
})
}
// now write them all to the same buffer and unmarshal one by one
t.Run("writeAllOps", func(t *testing.T) {
buf := &bytes.Buffer{}
for _, test := range tests {
_, err := test.WriteTo(buf)
if err != nil {
t.Fatalf("writing op to buffer: %v", err)
}
}
data := buf.Bytes()
offset := 0
for i, test := range tests {
op := &op{}
if err := op.UnmarshalBinary(data[offset:]); err != nil {
t.Fatalf("unmarshling op: %v", err)
}
if err := compareOps(test, op); err != nil {
t.Errorf("mismatch at %d: %v", i, err)
}
offset += op.size()
}
})
}
func compareOps(op1, op2 *op) error {
if op1.typ != op2.typ || op1.value != op2.value || len(op1.values) != len(op2.values) {
return errors.Errorf("mismatched type, value, or length: %v, %v", op1, op2)
}
for i := 0; i < len(op1.values); i++ {
if op1.values[i] != op2.values[i] {
return errors.Errorf("mismatched values at %d: %d and %d", i, op1.values[i], op2.values[i])
}
}
return nil
}
func TestDirectAddN(t *testing.T) {
tests := []struct {
call1 []uint64
expn1 int
call2 []uint64
expn2 int
exp []uint64
expcall2n []uint64
}{
{
call1: []uint64{0},
expn1: 1,
call2: []uint64{0, 1},
expn2: 1,
exp: []uint64{0, 1},
expcall2n: []uint64{1},
},
{
call1: []uint64{0, 22, 55},
expn1: 3,
call2: []uint64{0, 14, 22, 99, 55},
expn2: 2,
exp: []uint64{0, 14, 22, 55, 99},
expcall2n: []uint64{14, 99},
},
}
for i, test := range tests {
t.Run(fmt.Sprintf("%d", i), func(t *testing.T) {
b := NewBitmap()
n1 := b.DirectAddN(test.call1...)
if n1 != test.expn1 {
t.Errorf("mismatched n1 exp:%d got:%d", test.expn1, n1)
}
n2 := b.DirectAddN(test.call2...)
if n2 != test.expn2 {
t.Errorf("mismatched n2 exp:%d got:%d", test.expn2, n2)
}
if !reflect.DeepEqual(test.exp, b.Slice()) {
t.Errorf("misatched results \n%v\n%v", test.exp, b.Slice())
}
if !reflect.DeepEqual(test.expcall2n, test.call2[:n2]) {
t.Errorf("unexpected arg change \n%v\n%v", test.expcall2n, test.call2[:n2])
}
})
}
}
func TestDirectAddNVsAdd(t *testing.T) {
tests := [][]uint64{
{},
{0},
{0, 1, 2, 3},
{0, 1, 2, 101000, 9384932},
{9384932, 101000, 2, 1, 0},
{3489, 19230, 394, 0, 893982, 890283, 14, 7},
}
// Add some randomly created tests.
rand := rand.New(rand.NewSource(1))
for i := 0; i < 100; i++ {
tests = append(tests, generator.Uint64Slice(1+rand.Intn(1000), 0, 10000000, i%2 == 0, rand))
}
testsCopy := make([][]uint64, len(tests))
copy(testsCopy, tests)
for i, test := range testsCopy {
t.Run(fmt.Sprintf("Fresh%d", i), func(t *testing.T) {
ba := NewBitmap()
bd := NewBitmap()
na, err := ba.Add(test...)
if err != nil {
t.Fatalf("adding bits: %v", err)
}
nd := bd.DirectAddN(test...)
if na != (nd > 0) {
t.Errorf("differing changed numbers %v, %d", na, nd)
}
if ba.Count() != bd.Count() {
t.Errorf("different counts")
}
if !reflect.DeepEqual(ba.Slice(), bd.Slice()) {
t.Errorf("unequal values\n%v\n%v", ba.Slice(), bd.Slice())
}
})
}
ba := NewBitmap()
bd := NewBitmap()
for i, test := range tests {
t.Run(fmt.Sprintf("ContinuousAdd%d", i), func(t *testing.T) {
na, err := ba.Add(test...)
if err != nil {
t.Fatalf("adding bits: %v", err)
}
nd := bd.DirectAddN(test...)
if na != (nd > 0) {
t.Errorf("differing changed numbers %v, %d", na, nd)
}
if ba.Count() != bd.Count() {
t.Errorf("different counts")
}
if !reflect.DeepEqual(ba.Slice(), bd.Slice()) {
t.Errorf("unequal values\n%v\n%v", ba.Slice(), bd.Slice())
}
})
}
}
func BenchmarkUnionInPlaceRegression(b *testing.B) {
initial := make([]uint64, 0, 10100)
a1 := make([]uint64, 0, 10000)
a2 := make([]uint64, 0, 10000)
for i := uint64(0); i < 1<<30; i += 100000 {
initial = append(initial, i)
a1 = append(a1, i+67000)
a2 = append(a2, i/2)
}
a1BM := NewBTreeBitmap(a1...)
a2BM := NewBTreeBitmap(a2...)
b.Run("Union1", func(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
bm := NewBTreeBitmap(initial...)
_ = bm.Union(a1BM)
}
})
b.Run("UnionInPlace1", func(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
bm := NewBTreeBitmap(initial...)
bm.UnionInPlace(a1BM)
}
})
b.Run("Union2", func(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
bm := NewBTreeBitmap(initial...)
_ = bm.Union(a1BM, a2BM)
}
})
b.Run("UnionInPlace2", func(b *testing.B) {
b.ReportAllocs()
for i := 0; i < b.N; i++ {
bm := NewBTreeBitmap(initial...)
bm.UnionInPlace(a1BM, a2BM)
}
})
}
func TestBitmapAny(t *testing.T) {
bm := NewBTreeBitmap()
if bm.Any() {
t.Error("empty bitmap should have Any()==false")
}
_, err := bm.Add(1)
if err != nil {
t.Errorf("couldn't add a bit: %v", err)
}
if !bm.Any() {
t.Error("bitmap with 1 bit should have Any()==true")
}
_, err = bm.Add(100000)
if err != nil {
t.Errorf("couldn't add a bit: %v", err)
}
if !bm.Any() {
t.Error("bitmap with 2 bits should have Any()==true")
}
changed, err := bm.Remove(1)
if err != nil {
t.Errorf("couldn't remove a bit: %v", err)
}
if changed != true {
t.Error("removing a set bit should have been a change")
}
if !bm.Any() {
t.Error("bitmap with 1 bit left after removing 1 should have Any()==true")
}
_, err = bm.Add(1)
if err != nil {
t.Errorf("couldn't remove a bit: %v", err)
}
if changed != true {
t.Error("re-addintg a previously set bit should have been a change")
}
bm = bm.Difference(NewBTreeBitmap(1))
if !bm.Any() {
t.Error("bitmap with 1 bit left after differencing 1 should have Any()==true")
}
_, err = bm.Remove(100000)
if err != nil {
t.Errorf("couldn't remove a bit: %v", err)
}
if bm.Any() {
t.Error("shouldn't be any left")
}
}
func TestDifferenceInPlace_N(t *testing.T) {
a := doContainer(ContainerRun, runFull())
b := doContainer(ContainerBitmap, bitmapFull())
r := differenceInPlaceWrapper(a, b)
if r.N() != 0 {
t.Error("expected difference of containers to have n=0")
}
}
func BenchmarkUnionRunRunInPlace(bm *testing.B) {
bm.Skip("Skipping long running BenchmarkUnionRunRunInPlace")
runs := []struct {
name string
fn func() []Interval16
}{
{"FirstBitSet", runFirstBitSet},
{"LastBitSet", runLastBitSet},
{"FirstBitUnset", runFirstBitUnset},
{"LastBitUnset", runLastBitUnset},
{"InnerBitsSet", runInnerBitsSet},
{"OuterBitsSet", runOuterBitsSet},
{"OddBitsSet", runOddBitsSet},
{"EvenBitsSet", runEvenBitsSet},
}
for _, ar := range runs {
for _, br := range runs {
bm.Run("RunToBitmapRun-"+ar.name+"_"+br.name, func(bm *testing.B) {
for i := 0; i < bm.N; i++ {
arun := doContainer(ContainerRun, ar.fn())
brun := doContainer(ContainerRun, br.fn())
abmp := arun.runToBitmap()
_ = unionBitmapRunInPlace(abmp, brun)
}
})
bm.Run("RunRun-"+ar.name+"_"+br.name, func(bm *testing.B) {
for i := 0; i < bm.N; i++ {
arun := doContainer(ContainerRun, ar.fn())
brun := doContainer(ContainerRun, br.fn())
_ = unionRunRunInPlace(arun, brun)
}
})
}
}
}
func TestUnionRunRunInPlaceBitwiseCompare(t *testing.T) {
runs := []struct {
name string
fn func() []Interval16
}{
{name: "FirstBitSet", fn: runFirstBitSet},
{name: "LastBitSet", fn: runLastBitSet},
{name: "FirstBitUnset", fn: runFirstBitUnset},
{name: "LastBitUnset", fn: runLastBitUnset},
{name: "InnerBitsSet", fn: runInnerBitsSet},
{name: "OuterBitsSet", fn: runOuterBitsSet},
{name: "OddBitsSet", fn: runOddBitsSet},
{name: "EvenBitsSet", fn: runEvenBitsSet},
}
for _, a := range runs {
for _, b := range runs {
t.Run(a.name+"-"+b.name, func(t *testing.T) {
arun := doContainer(ContainerRun, a.fn())
abm := doContainer(ContainerRun, a.fn()).runToBitmap()
brun := doContainer(ContainerRun, b.fn())
out1 := unionBitmapRunInPlace(abm, brun)
out2 := unionRunRunInPlace(arun, brun)
out1.Repair()
// out2 may no longer be a run container, so don't assume that.
err := out1.BitwiseCompare(out2)
if err != nil {
t.Fatal(err)
}
})
}
}
}
func TestCloneRoaringIterator(t *testing.T) {
ca := NewContainerArray([]uint16{1, 10, 100, 1000})
ba := NewFileBitmap()
ba.Containers.Put(0, ca)
ba.Containers.Put(10, ca)
ba.Containers.Put(101, ca)
ba.Containers.Put(10001, ca)
var buf bytes.Buffer
_, err := ba.WriteTo(&buf)
if err != nil {
t.Fatalf("error writing: %v", err)
}
itr, err := NewRoaringIterator(buf.Bytes())
if err != nil {
t.Fatalf("error NewRoaringIterator(buf.Bytes()): %v", err)
}
itr2 := itr.Clone()
ikeys := itr2.ContainerKeys()
if len(ikeys) == 0 {
t.Fatalf("should not be empty")
}
if ikeys[0] != 0 {
t.Fatalf("first ikeys should be 0")
}
if ikeys[len(ikeys)-1] != 10001 {
t.Fatalf("last ikeys should be 10001")
}
var keys []uint64
for itrKey, synthC := itr.NextContainer(); synthC != nil; itrKey, synthC = itr.NextContainer() {
keys = append(keys, itrKey)
_ = synthC
}
var keys2 []uint64
for itrKey, synthC := itr2.NextContainer(); synthC != nil; itrKey, synthC = itr2.NextContainer() {
keys2 = append(keys2, itrKey)
_ = synthC
}
if !reflect.DeepEqual(keys, keys2) {
t.Fatalf("keys != keys2. keys='%#v'; keys2='%#v'", keys, keys2)
}
}
func TestRoaringIteratorContainerKeys(t *testing.T) {
ca := NewContainerArray([]uint16{1, 10, 100, 1000})
ba := NewFileBitmap()
ba.Containers.Put(101, ca)
ba.Containers.Put(10, ca)
ba.Containers.Put(10001, ca)
var buf bytes.Buffer
_, err := ba.WriteTo(&buf)
if err != nil {
t.Fatalf("error writing: %v", err)
}
itr, err := NewRoaringIterator(buf.Bytes())
if err != nil {
t.Fatalf("error NewRoaringIterator(buf.Bytes()): %v", err)
}
ikeys := itr.ContainerKeys()
if len(ikeys) == 0 {
t.Fatalf("should not be empty")
}
if ikeys[0] != 10 {
t.Fatalf("first ikeys should be 10")
}
if ikeys[len(ikeys)-1] != 10001 {
t.Fatalf("last ikeys should be 10001")
}
// make and check empty bitmap
baEmpty := NewFileBitmap()
var bufEmpty bytes.Buffer
_, err = baEmpty.WriteTo(&bufEmpty)
if err != nil {
t.Fatalf("error writing: %v", err)
}
itrEmpty, err := NewRoaringIterator(bufEmpty.Bytes())
if err != nil {
t.Fatalf("error NewRoaringIterator(bufEmpty.Bytes()): %v", err)
}
ikeys = itrEmpty.ContainerKeys()
if len(ikeys) != 0 {
t.Fatalf("should be empty")
}
}
func TestRoaringIteratorSkip(t *testing.T) {
ca := NewContainerArray([]uint16{1, 10, 100, 1000})
ba := NewFileBitmap()
ba.Containers.Put(101, ca)
ba.Containers.Put(10, ca)
ba.Containers.Put(10001, ca)
var buf bytes.Buffer
_, err := ba.WriteTo(&buf)
if err != nil {
t.Fatalf("error writing: %v", err)
}
itr, err := NewRoaringIterator(buf.Bytes())
if err != nil {
t.Fatalf("error NewRoaringIterator(buf.Bytes()): %v", err)
}
itr.Skip()
ckey1, ct := itr.NextContainer()
_ = ct
if ckey1 != 101 {
t.Fatalf("expected to skip 10 and get 101 but got: %v", ckey1)
}
// make and check empty bitmap
baEmpty := NewFileBitmap()
var bufEmpty bytes.Buffer
_, err = baEmpty.WriteTo(&bufEmpty)
if err != nil {
t.Fatalf("error writing: %v", err)
}
itrEmpty, err := NewRoaringIterator(bufEmpty.Bytes())
if err != nil {
t.Fatalf("error NewRoaringIterator(bufEmpty.Bytes()): %v", err)
}
itrEmpty.Skip()
// should not have panic-ed.
}
// we were seeing unionInterval16InPlace() returning too
// large an run container, which was causing problems when
// we write to the transactional backends. Verify that
// unionRunRunInPlace() converts to bitmap if its too large.
func TestContainer_unionRunRunInPlace_TwoBigRunArrays(t *testing.T) {
a := NewContainerRun(nil)
b := NewContainerRun(nil)
for i := uint16(0); i < 8192; i++ {
if i%3 == 0 {
a, _ = a.runAdd(i)
}
}
for i := uint16(0); i < 8192; i++ {
if i%3 == 1 {
b, _ = b.runAdd(i)
}
}
c := unionRunRunInPlace(a, b)
typ := ContainerType(c)
if typ == ContainerRun {
nr := len(c.runs())
if nr > runMaxSize {
panic(fmt.Sprintf("runs is over runMaxSize: %v", nr))
}
}
}
// we were seeing unionInterval16InPlace() returning too
// large an array container, which was causing problems when
// we write to the transactional backends. Verify that
// unionArrayArrayInPlace() converts to bitmap if its too large.
// Confirms that optimize() is done at the end of unionArrayArrayInPlace().
func TestContainer_unionArrayArrayInPlace_TwoBigArrayArrays(t *testing.T) {
a := NewContainerArray(nil)
b := NewContainerArray(nil)
for i := uint16(0); i < 4096; i++ {
a, _ = a.arrayAdd(i)
}
for i := uint16(4096); i < 8192; i++ {
b, _ = b.arrayAdd(i)
}
c := unionArrayArrayInPlace(a, b)
typ := ContainerType(c)
if typ == ContainerArray {
nr := len(c.array())
if nr > ArrayMaxSize {
panic(fmt.Sprintf("arrays is over arrayMaxSize: %v", nr))
}
}
}
// the love child of the above two tests.
func TestContainer_unionInPlace_ArrayUnionRun(t *testing.T) {
for k := 0; k < 2; k++ {
a := NewContainerArray(nil)
for i := uint16(0); i < 8192; i += 2 {
a, _ = a.arrayAdd(i)
}
b := NewContainerRun(nil)
for i := uint16(8192); i < 8192*2; i++ {
if i%3 == 1 {
b, _ = b.runAdd(i)
}
}
var c *Container
if k == 0 {
c = a.unionInPlace(b)
} else {
c = b.unionInPlace(a)
}
typ := ContainerType(c)
if typ == ContainerArray {
panic("should be impossible to have an array")
}
}
}
func TestContainerCallback(t *testing.T) {
containers, err := InitContainerArchetypes()
if err != nil {
t.Fatalf("creating containers: %v", err)
}
got := make([]uint16, 65536)
hit := func(u uint16) {
got = append(got, u)
}
var expected []uint16
// complain() wraps up some pretty-printing logic for this,
// but note also the closure trapping expected/got so we can
// just refer to them without passing them in.
complain := func(t *testing.T, msg string, args ...interface{}) {
l1 := len(expected)
l2 := len(got)
dotdot1 := ""
dotdot2 := ""
if l1 > 8 {
expected = expected[:8]
dotdot1 = "..."
}
if l2 > 8 {
got = got[:8]
dotdot2 = "..."
}
t.Fatalf("%s: expected %d%s, got %d%s", fmt.Sprintf(msg, args...), expected, dotdot1, got, dotdot2)
}
for t1, ci := range containers {
t.Run(ContainerArchetypeNames[t1], func(t *testing.T) {
for _, c1 := range ci {
got = got[:0]
expected = c1.Slice()
containerCallback(c1, hit)
if len(got) != len(expected) {
complain(t, "wrong length (%d vs %d)", len(expected), len(got))
}
for i := range got {
if got[i] != expected[i] {
complain(t, "element %d differs: expected %d, got %d", i, expected[i], got[i])
}
}
}
})
}
}
func TestIntersectionCallback(t *testing.T) {
containers, err := InitContainerArchetypes()
if err != nil {
t.Fatalf("creating containers: %v", err)
}
got := make([]uint16, 65536)
hit := func(u uint16) {
got = append(got, u)
}
var expected []uint16
// complain() wraps up some pretty-printing logic for this,
// but note also the closure trapping expected/got so we can
// just refer to them without passing them in.
complain := func(t *testing.T, msg string, args ...interface{}) {
l1 := len(expected)
l2 := len(got)
dotdot1 := ""
dotdot2 := ""
if l1 > 8 {
expected = expected[:8]
dotdot1 = "..."
}
if l2 > 8 {
got = got[:8]
dotdot2 = "..."
}
t.Fatalf("%s: expected %d%s, got %d%s", fmt.Sprintf(msg, args...), expected, dotdot1, got, dotdot2)
}
for t1, ci := range containers {
for t2, cj := range containers {
t.Run(fmt.Sprintf("%s-%s", ContainerArchetypeNames[t1], ContainerArchetypeNames[t2]), func(t *testing.T) {
for _, c1 := range ci {
for _, c2 := range cj {
got = got[:0]
expectedContainer := intersect(c1, c2)
expected = expectedContainer.Slice()
intersectionCallback(c1, c2, hit)
if len(got) != len(expected) {
complain(t, "wrong length (%d vs %d)", len(expected), len(got))
}
for i := range got {
if got[i] != expected[i] {
complain(t, "element %d differs: expected %d, got %d", i, expected[i], got[i])
}
}
}
}
})
}
}
}
func TestImportBitmap(t *testing.T) {
b := NewBitmap()
i := GetRoaringIter(1, 3, 5)
changed, _, err := b.ImportRoaringRawIterator(i, false, true, 16)
if err != nil {
t.Fatal("no error should happen changed")
}
if changed != 3 {
t.Fatal("Should have changed")
}
i = GetRoaringIter(1, 3, 5)
changed, _, err = b.ImportRoaringRawIterator(i, true, true, 16)
if err != nil {
t.Fatal("no error should happen changed")
}
if changed != 3 {
t.Fatalf("Should have changed %v", changed)
}
}
func TestVariousBitmap(t *testing.T) {
b := NewBitmap(3)
c, e := b.Add(8)
if e != nil {
t.Fatal("add:", e)
}
if c == false {
t.Fatal("add: should have changed")
}
c, _ = b.Add(8)
if c == true {
t.Fatal("add: should not changed")
}
z, _ := b.AddN(9)
if z != 1 {
t.Fatal("add: should changed 1")
}
z, _ = b.RemoveN(9)
if z != 1 {
t.Fatal("add: should changed 1")
}
if b.Contains(100) {
t.Fatal("should not contain 100")
}
if !b.Any() {
t.Fatal("should have bits ")
}
if b.Size() == 0 {
t.Fatal("should have storage")
}
if b.Count() == 0 {
t.Fatal("should have bits")
}
if b.Max() == 0 {
t.Fatal("should max >0")
}
if m, e := b.Min(); !(m == 3 && e) {
t.Fatal("min should be 3 and containers exist", m, e)
}
b = nil
x := b.Clone()
if x != nil {
t.Fatal("nil clone should be nil")
}
n := b.Freeze()
if n != nil {
t.Fatal("nil freeze should be nil")
}
r, _ := b.AddN()
if r != 0 {
t.Fatal("nil AddN should be 0")
}
}
func TestBitmapHash(t *testing.T) {
a, b := NewContainerBitmapN(getFullBitmap(), MaxContainerVal+1), NewContainerBitmapN(getFullBitmap(), MaxContainerVal+1)
arr := NewContainerArray([]uint16{1, 2, 3, 5, 8})
run := NewContainerRun([]Interval16{{Start: 0, Last: 32}})
ba := NewBitmap()
bb := NewBitmap()
ba.Containers.Put(1, arr)
ba.Containers.Put(2, run)
ba.Containers.Put(101, a)
ba.Containers.Put(102, a)
bb.Containers.Put(1, arr)
bb.Containers.Put(2, run)
bb.Containers.Put(101, b)
bb.Containers.Put(102, b)
if ba.Hash(0) != bb.Hash(0) {
t.Fatal("hash should be equal")
}
bb.Containers.Put(103, b)
if ba.Hash(0) == bb.Hash(0) {
t.Fatal("hash should be different")
}
}
Reference in a new issue View git blame Copy permalink