mirror of
https://github.com/featurebasedb/featurebase.git
synced 2026-08-28 10:54:59 +00:00
7d1fde7438
The anti-entropy feature has never actually worked. We've been
talking about removing it or replacing it for ages, but haven't
had a concrete motivation.
But the anti-entropy interface is the sole user of several components
of the Tx interface, and now that we're trying to replace that
interface, being able to drop those components has some appeal, so
let's remove the one thing that used them, in the hopes that this
will simplify life.
This also lets us drop ForEach and ForEachRange, which were
barely used at all. The one surviving usage (CSV export) can be
handled by using the container iterator we already have, and
making ContainerCallback exported so we can use it to just call
things for every bit.
(cherry picked from commit fff9ddc1f5)
4828 lines
146 KiB
Go
4828 lines
146 KiB
Go
// 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")
|
|
}
|
|
}
|