+++ /dev/null
-// Copyright 2014 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package intsets_test
-
-import (
- "fmt"
- "log"
- "math/rand"
- "sort"
- "strings"
- "testing"
-
- "golang.org/x/tools/container/intsets"
-)
-
-func TestBasics(t *testing.T) {
- var s intsets.Sparse
- if len := s.Len(); len != 0 {
- t.Errorf("Len({}): got %d, want 0", len)
- }
- if s := s.String(); s != "{}" {
- t.Errorf("String({}): got %q, want \"{}\"", s)
- }
- if s.Has(3) {
- t.Errorf("Has(3): got true, want false")
- }
- if err := s.Check(); err != nil {
- t.Error(err)
- }
-
- if !s.Insert(3) {
- t.Errorf("Insert(3): got false, want true")
- }
- if max := s.Max(); max != 3 {
- t.Errorf("Max: got %d, want 3", max)
- }
-
- if !s.Insert(435) {
- t.Errorf("Insert(435): got false, want true")
- }
- if s := s.String(); s != "{3 435}" {
- t.Errorf("String({3 435}): got %q, want \"{3 435}\"", s)
- }
- if max := s.Max(); max != 435 {
- t.Errorf("Max: got %d, want 435", max)
- }
- if len := s.Len(); len != 2 {
- t.Errorf("Len: got %d, want 2", len)
- }
-
- if !s.Remove(435) {
- t.Errorf("Remove(435): got false, want true")
- }
- if s := s.String(); s != "{3}" {
- t.Errorf("String({3}): got %q, want \"{3}\"", s)
- }
-}
-
-// Insert, Len, IsEmpty, Hash, Clear, AppendTo.
-func TestMoreBasics(t *testing.T) {
- set := new(intsets.Sparse)
- set.Insert(456)
- set.Insert(123)
- set.Insert(789)
- if set.Len() != 3 {
- t.Errorf("%s.Len: got %d, want 3", set, set.Len())
- }
- if set.IsEmpty() {
- t.Errorf("%s.IsEmpty: got true", set)
- }
- if !set.Has(123) {
- t.Errorf("%s.Has(123): got false", set)
- }
- if set.Has(1234) {
- t.Errorf("%s.Has(1234): got true", set)
- }
- got := set.AppendTo([]int{-1})
- if want := []int{-1, 123, 456, 789}; fmt.Sprint(got) != fmt.Sprint(want) {
- t.Errorf("%s.AppendTo: got %v, want %v", set, got, want)
- }
-
- set.Clear()
-
- if set.Len() != 0 {
- t.Errorf("Clear: got %d, want 0", set.Len())
- }
- if !set.IsEmpty() {
- t.Errorf("IsEmpty: got false")
- }
- if set.Has(123) {
- t.Errorf("%s.Has: got false", set)
- }
-}
-
-func TestTakeMin(t *testing.T) {
- var set intsets.Sparse
- set.Insert(456)
- set.Insert(123)
- set.Insert(789)
- set.Insert(-123)
- var got int
- for i, want := range []int{-123, 123, 456, 789} {
- if !set.TakeMin(&got) || got != want {
- t.Errorf("TakeMin #%d: got %d, want %d", i, got, want)
- }
- }
- if set.TakeMin(&got) {
- t.Errorf("%s.TakeMin returned true", &set)
- }
- if err := set.Check(); err != nil {
- t.Fatalf("check: %s: %#v", err, &set)
- }
-}
-
-func TestMinAndMax(t *testing.T) {
- values := []int{0, 456, 123, 789, -123} // elt 0 => empty set
- wantMax := []int{intsets.MinInt, 456, 456, 789, 789}
- wantMin := []int{intsets.MaxInt, 456, 123, 123, -123}
-
- var set intsets.Sparse
- for i, x := range values {
- if i != 0 {
- set.Insert(x)
- }
- if got, want := set.Min(), wantMin[i]; got != want {
- t.Errorf("Min #%d: got %d, want %d", i, got, want)
- }
- if got, want := set.Max(), wantMax[i]; got != want {
- t.Errorf("Max #%d: got %d, want %d", i, got, want)
- }
- }
-
- set.Insert(intsets.MinInt)
- if got, want := set.Min(), intsets.MinInt; got != want {
- t.Errorf("Min: got %d, want %d", got, want)
- }
-
- set.Insert(intsets.MaxInt)
- if got, want := set.Max(), intsets.MaxInt; got != want {
- t.Errorf("Max: got %d, want %d", got, want)
- }
-}
-
-func TestEquals(t *testing.T) {
- var setX intsets.Sparse
- setX.Insert(456)
- setX.Insert(123)
- setX.Insert(789)
-
- if !setX.Equals(&setX) {
- t.Errorf("Equals(%s, %s): got false", &setX, &setX)
- }
-
- var setY intsets.Sparse
- setY.Insert(789)
- setY.Insert(456)
- setY.Insert(123)
-
- if !setX.Equals(&setY) {
- t.Errorf("Equals(%s, %s): got false", &setX, &setY)
- }
-
- setY.Insert(1)
- if setX.Equals(&setY) {
- t.Errorf("Equals(%s, %s): got true", &setX, &setY)
- }
-
- var empty intsets.Sparse
- if setX.Equals(&empty) {
- t.Errorf("Equals(%s, %s): got true", &setX, &empty)
- }
-
- // Edge case: some block (with offset=0) appears in X but not Y.
- setY.Remove(123)
- if setX.Equals(&setY) {
- t.Errorf("Equals(%s, %s): got true", &setX, &setY)
- }
-}
-
-// A pset is a parallel implementation of a set using both an intsets.Sparse
-// and a built-in hash map.
-type pset struct {
- hash map[int]bool
- bits intsets.Sparse
-}
-
-func makePset() *pset {
- return &pset{hash: make(map[int]bool)}
-}
-
-func (set *pset) add(n int) {
- prev := len(set.hash)
- set.hash[n] = true
- grewA := len(set.hash) > prev
-
- grewB := set.bits.Insert(n)
-
- if grewA != grewB {
- panic(fmt.Sprintf("add(%d): grewA=%t grewB=%t", n, grewA, grewB))
- }
-}
-
-func (set *pset) remove(n int) {
- prev := len(set.hash)
- delete(set.hash, n)
- shrankA := len(set.hash) < prev
-
- shrankB := set.bits.Remove(n)
-
- if shrankA != shrankB {
- panic(fmt.Sprintf("remove(%d): shrankA=%t shrankB=%t", n, shrankA, shrankB))
- }
-}
-
-func (set *pset) check(t *testing.T, msg string) {
- var eltsA []int
- for elt := range set.hash {
- eltsA = append(eltsA, int(elt))
- }
- sort.Ints(eltsA)
-
- eltsB := set.bits.AppendTo(nil)
-
- if a, b := fmt.Sprint(eltsA), fmt.Sprint(eltsB); a != b {
- t.Errorf("check(%s): hash=%s bits=%s (%s)", msg, a, b, &set.bits)
- }
-
- if err := set.bits.Check(); err != nil {
- t.Fatalf("Check(%s): %s: %#v", msg, err, &set.bits)
- }
-}
-
-// randomPset returns a parallel set of random size and elements.
-func randomPset(prng *rand.Rand, maxSize int) *pset {
- set := makePset()
- size := int(prng.Int()) % maxSize
- for i := 0; i < size; i++ {
- // TODO(adonovan): benchmark how performance varies
- // with this sparsity parameter.
- n := int(prng.Int()) % 10000
- set.add(n)
- }
- return set
-}
-
-// TestRandomMutations performs the same random adds/removes on two
-// set implementations and ensures that they compute the same result.
-func TestRandomMutations(t *testing.T) {
- const debug = false
-
- set := makePset()
- prng := rand.New(rand.NewSource(0))
- for i := 0; i < 10000; i++ {
- n := int(prng.Int())%2000 - 1000
- if i%2 == 0 {
- if debug {
- log.Printf("add %d", n)
- }
- set.add(n)
- } else {
- if debug {
- log.Printf("remove %d", n)
- }
- set.remove(n)
- }
- if debug {
- set.check(t, "post mutation")
- }
- }
- set.check(t, "final")
- if debug {
- log.Print(&set.bits)
- }
-}
-
-func TestLowerBound(t *testing.T) {
- // Use random sets of sizes from 0 to about 4000.
- prng := rand.New(rand.NewSource(0))
- for i := uint(0); i < 12; i++ {
- x := randomPset(prng, 1<<i)
- for j := 0; j < 10000; j++ {
- found := intsets.MaxInt
- for e := range x.hash {
- if e >= j && e < found {
- found = e
- }
- }
- if res := x.bits.LowerBound(j); res != found {
- t.Errorf("%s: LowerBound(%d)=%d, expected %d", &x.bits, j, res, found)
- }
- }
- }
-}
-
-// TestSetOperations exercises classic set operations: ∩ , ∪, \.
-func TestSetOperations(t *testing.T) {
- prng := rand.New(rand.NewSource(0))
-
- // Use random sets of sizes from 0 to about 4000.
- // For each operator, we test variations such as
- // Z.op(X, Y), Z.op(X, Z) and Z.op(Z, Y) to exercise
- // the degenerate cases of each method implementation.
- for i := uint(0); i < 12; i++ {
- X := randomPset(prng, 1<<i)
- Y := randomPset(prng, 1<<i)
-
- // TODO(adonovan): minimise dependencies between stanzas below.
-
- // Copy(X)
- C := makePset()
- C.bits.Copy(&Y.bits) // no effect on result
- C.bits.Copy(&X.bits)
- C.hash = X.hash
- C.check(t, "C.Copy(X)")
- C.bits.Copy(&C.bits)
- C.check(t, "C.Copy(C)")
-
- // U.Union(X, Y)
- U := makePset()
- U.bits.Union(&X.bits, &Y.bits)
- for n := range X.hash {
- U.hash[n] = true
- }
- for n := range Y.hash {
- U.hash[n] = true
- }
- U.check(t, "U.Union(X, Y)")
-
- // U.Union(X, X)
- U.bits.Union(&X.bits, &X.bits)
- U.hash = X.hash
- U.check(t, "U.Union(X, X)")
-
- // U.Union(U, Y)
- U = makePset()
- U.bits.Copy(&X.bits)
- U.bits.Union(&U.bits, &Y.bits)
- for n := range X.hash {
- U.hash[n] = true
- }
- for n := range Y.hash {
- U.hash[n] = true
- }
- U.check(t, "U.Union(U, Y)")
-
- // U.Union(X, U)
- U.bits.Copy(&Y.bits)
- U.bits.Union(&X.bits, &U.bits)
- U.check(t, "U.Union(X, U)")
-
- // U.UnionWith(U)
- U.bits.UnionWith(&U.bits)
- U.check(t, "U.UnionWith(U)")
-
- // I.Intersection(X, Y)
- I := makePset()
- I.bits.Intersection(&X.bits, &Y.bits)
- for n := range X.hash {
- if Y.hash[n] {
- I.hash[n] = true
- }
- }
- I.check(t, "I.Intersection(X, Y)")
-
- // I.Intersection(X, X)
- I.bits.Intersection(&X.bits, &X.bits)
- I.hash = X.hash
- I.check(t, "I.Intersection(X, X)")
-
- // I.Intersection(I, X)
- I.bits.Intersection(&I.bits, &X.bits)
- I.check(t, "I.Intersection(I, X)")
-
- // I.Intersection(X, I)
- I.bits.Intersection(&X.bits, &I.bits)
- I.check(t, "I.Intersection(X, I)")
-
- // I.Intersection(I, I)
- I.bits.Intersection(&I.bits, &I.bits)
- I.check(t, "I.Intersection(I, I)")
-
- // D.Difference(X, Y)
- D := makePset()
- D.bits.Difference(&X.bits, &Y.bits)
- for n := range X.hash {
- if !Y.hash[n] {
- D.hash[n] = true
- }
- }
- D.check(t, "D.Difference(X, Y)")
-
- // D.Difference(D, Y)
- D.bits.Copy(&X.bits)
- D.bits.Difference(&D.bits, &Y.bits)
- D.check(t, "D.Difference(D, Y)")
-
- // D.Difference(Y, D)
- D.bits.Copy(&X.bits)
- D.bits.Difference(&Y.bits, &D.bits)
- D.hash = make(map[int]bool)
- for n := range Y.hash {
- if !X.hash[n] {
- D.hash[n] = true
- }
- }
- D.check(t, "D.Difference(Y, D)")
-
- // D.Difference(X, X)
- D.bits.Difference(&X.bits, &X.bits)
- D.hash = nil
- D.check(t, "D.Difference(X, X)")
-
- // D.DifferenceWith(D)
- D.bits.Copy(&X.bits)
- D.bits.DifferenceWith(&D.bits)
- D.check(t, "D.DifferenceWith(D)")
-
- // SD.SymmetricDifference(X, Y)
- SD := makePset()
- SD.bits.SymmetricDifference(&X.bits, &Y.bits)
- for n := range X.hash {
- if !Y.hash[n] {
- SD.hash[n] = true
- }
- }
- for n := range Y.hash {
- if !X.hash[n] {
- SD.hash[n] = true
- }
- }
- SD.check(t, "SD.SymmetricDifference(X, Y)")
-
- // X.SymmetricDifferenceWith(Y)
- SD.bits.Copy(&X.bits)
- SD.bits.SymmetricDifferenceWith(&Y.bits)
- SD.check(t, "X.SymmetricDifference(Y)")
-
- // Y.SymmetricDifferenceWith(X)
- SD.bits.Copy(&Y.bits)
- SD.bits.SymmetricDifferenceWith(&X.bits)
- SD.check(t, "Y.SymmetricDifference(X)")
-
- // SD.SymmetricDifference(X, X)
- SD.bits.SymmetricDifference(&X.bits, &X.bits)
- SD.hash = nil
- SD.check(t, "SD.SymmetricDifference(X, X)")
-
- // SD.SymmetricDifference(X, Copy(X))
- X2 := makePset()
- X2.bits.Copy(&X.bits)
- SD.bits.SymmetricDifference(&X.bits, &X2.bits)
- SD.check(t, "SD.SymmetricDifference(X, Copy(X))")
-
- // Copy(X).SymmetricDifferenceWith(X)
- SD.bits.Copy(&X.bits)
- SD.bits.SymmetricDifferenceWith(&X.bits)
- SD.check(t, "Copy(X).SymmetricDifferenceWith(X)")
- }
-}
-
-func TestIntersectionWith(t *testing.T) {
- // Edge cases: the pairs (1,1), (1000,2000), (8000,4000)
- // exercise the <, >, == cases in IntersectionWith that the
- // TestSetOperations data is too dense to cover.
- var X, Y intsets.Sparse
- X.Insert(1)
- X.Insert(1000)
- X.Insert(8000)
- Y.Insert(1)
- Y.Insert(2000)
- Y.Insert(4000)
- X.IntersectionWith(&Y)
- if got, want := X.String(), "{1}"; got != want {
- t.Errorf("IntersectionWith: got %s, want %s", got, want)
- }
-}
-
-func TestIntersects(t *testing.T) {
- prng := rand.New(rand.NewSource(0))
-
- for i := uint(0); i < 12; i++ {
- X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
- x, y := &X.bits, &Y.bits
-
- // test the slow way
- var z intsets.Sparse
- z.Copy(x)
- z.IntersectionWith(y)
-
- if got, want := x.Intersects(y), !z.IsEmpty(); got != want {
- t.Errorf("Intersects(%s, %s): got %v, want %v (%s)", x, y, got, want, &z)
- }
-
- // make it false
- a := x.AppendTo(nil)
- for _, v := range a {
- y.Remove(v)
- }
-
- if got, want := x.Intersects(y), false; got != want {
- t.Errorf("Intersects: got %v, want %v", got, want)
- }
-
- // make it true
- if x.IsEmpty() {
- continue
- }
- i := prng.Intn(len(a))
- y.Insert(a[i])
-
- if got, want := x.Intersects(y), true; got != want {
- t.Errorf("Intersects: got %v, want %v", got, want)
- }
- }
-}
-
-func TestSubsetOf(t *testing.T) {
- prng := rand.New(rand.NewSource(0))
-
- for i := uint(0); i < 12; i++ {
- X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
- x, y := &X.bits, &Y.bits
-
- // test the slow way
- var z intsets.Sparse
- z.Copy(x)
- z.DifferenceWith(y)
-
- if got, want := x.SubsetOf(y), z.IsEmpty(); got != want {
- t.Errorf("SubsetOf: got %v, want %v", got, want)
- }
-
- // make it true
- y.UnionWith(x)
-
- if got, want := x.SubsetOf(y), true; got != want {
- t.Errorf("SubsetOf: got %v, want %v", got, want)
- }
-
- // make it false
- if x.IsEmpty() {
- continue
- }
- a := x.AppendTo(nil)
- i := prng.Intn(len(a))
- y.Remove(a[i])
-
- if got, want := x.SubsetOf(y), false; got != want {
- t.Errorf("SubsetOf: got %v, want %v", got, want)
- }
- }
-}
-
-func TestBitString(t *testing.T) {
- for _, test := range []struct {
- input []int
- want string
- }{
- {nil, "0"},
- {[]int{0}, "1"},
- {[]int{0, 4, 5}, "110001"},
- {[]int{0, 7, 177}, "1" + strings.Repeat("0", 169) + "10000001"},
- {[]int{-3, 0, 4, 5}, "110001.001"},
- {[]int{-3}, "0.001"},
- } {
- var set intsets.Sparse
- for _, x := range test.input {
- set.Insert(x)
- }
- if got := set.BitString(); got != test.want {
- t.Errorf("BitString(%s) = %s, want %s", set.String(), got, test.want)
- }
- }
-}
-
-func TestFailFastOnShallowCopy(t *testing.T) {
- var x intsets.Sparse
- x.Insert(1)
-
- y := x // shallow copy (breaks representation invariants)
- defer func() {
- got := fmt.Sprint(recover())
- want := "interface conversion: interface {} is nil, not intsets.to_copy_a_sparse_you_must_call_its_Copy_method"
- if got != want {
- t.Errorf("shallow copy: recover() = %q, want %q", got, want)
- }
- }()
- _ = y.String() // panics
- t.Error("didn't panic as expected")
-}
-
-// -- Benchmarks -------------------------------------------------------
-
-// TODO(adonovan):
-// - Add benchmarks of each method.
-// - Gather set distributions from pointer analysis.
-// - Measure memory usage.
-
-func benchmarkInsertProbeSparse(b *testing.B, size, spread int) {
- prng := rand.New(rand.NewSource(0))
- // Generate our insertions and probes beforehand (we don't want to benchmark
- // the prng).
- insert := make([]int, size)
- probe := make([]int, size*2)
- for i := range insert {
- insert[i] = prng.Int() % spread
- }
- for i := range probe {
- probe[i] = prng.Int() % spread
- }
-
- b.ResetTimer()
- var x intsets.Sparse
- for tries := 0; tries < b.N; tries++ {
- x.Clear()
- for _, n := range insert {
- x.Insert(n)
- }
- hits := 0
- for _, n := range probe {
- if x.Has(n) {
- hits++
- }
- }
- // Use the variable so it doesn't get optimized away.
- if hits > len(probe) {
- b.Fatalf("%d hits, only %d probes", hits, len(probe))
- }
- }
-}
-
-func BenchmarkInsertProbeSparse_2_10(b *testing.B) {
- benchmarkInsertProbeSparse(b, 2, 10)
-}
-
-func BenchmarkInsertProbeSparse_10_10(b *testing.B) {
- benchmarkInsertProbeSparse(b, 10, 10)
-}
-
-func BenchmarkInsertProbeSparse_10_1000(b *testing.B) {
- benchmarkInsertProbeSparse(b, 10, 1000)
-}
-
-func BenchmarkInsertProbeSparse_100_100(b *testing.B) {
- benchmarkInsertProbeSparse(b, 100, 100)
-}
-
-func BenchmarkInsertProbeSparse_100_10000(b *testing.B) {
- benchmarkInsertProbeSparse(b, 100, 1000)
-}
-
-func BenchmarkUnionDifferenceSparse(b *testing.B) {
- prng := rand.New(rand.NewSource(0))
- for tries := 0; tries < b.N; tries++ {
- var x, y, z intsets.Sparse
- for i := 0; i < 1000; i++ {
- n := int(prng.Int()) % 100000
- if i%2 == 0 {
- x.Insert(n)
- } else {
- y.Insert(n)
- }
- }
- z.Union(&x, &y)
- z.Difference(&x, &y)
- }
-}
-
-func BenchmarkUnionDifferenceHashTable(b *testing.B) {
- prng := rand.New(rand.NewSource(0))
- for tries := 0; tries < b.N; tries++ {
- x, y, z := make(map[int]bool), make(map[int]bool), make(map[int]bool)
- for i := 0; i < 1000; i++ {
- n := int(prng.Int()) % 100000
- if i%2 == 0 {
- x[n] = true
- } else {
- y[n] = true
- }
- }
- // union
- for n := range x {
- z[n] = true
- }
- for n := range y {
- z[n] = true
- }
- // difference
- z = make(map[int]bool)
- for n := range y {
- if !x[n] {
- z[n] = true
- }
- }
- }
-}
-
-func BenchmarkAppendTo(b *testing.B) {
- prng := rand.New(rand.NewSource(0))
- var x intsets.Sparse
- for i := 0; i < 1000; i++ {
- x.Insert(int(prng.Int()) % 10000)
- }
- var space [1000]int
- for tries := 0; tries < b.N; tries++ {
- x.AppendTo(space[:0])
- }
-}
projects / dotfiles / .git / blobdiff