1 // Copyright 2014 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
15 "golang.org/x/tools/container/intsets"
18 func TestBasics(t *testing.T) {
20 if len := s.Len(); len != 0 {
21 t.Errorf("Len({}): got %d, want 0", len)
23 if s := s.String(); s != "{}" {
24 t.Errorf("String({}): got %q, want \"{}\"", s)
27 t.Errorf("Has(3): got true, want false")
29 if err := s.Check(); err != nil {
34 t.Errorf("Insert(3): got false, want true")
36 if max := s.Max(); max != 3 {
37 t.Errorf("Max: got %d, want 3", max)
41 t.Errorf("Insert(435): got false, want true")
43 if s := s.String(); s != "{3 435}" {
44 t.Errorf("String({3 435}): got %q, want \"{3 435}\"", s)
46 if max := s.Max(); max != 435 {
47 t.Errorf("Max: got %d, want 435", max)
49 if len := s.Len(); len != 2 {
50 t.Errorf("Len: got %d, want 2", len)
54 t.Errorf("Remove(435): got false, want true")
56 if s := s.String(); s != "{3}" {
57 t.Errorf("String({3}): got %q, want \"{3}\"", s)
61 // Insert, Len, IsEmpty, Hash, Clear, AppendTo.
62 func TestMoreBasics(t *testing.T) {
63 set := new(intsets.Sparse)
68 t.Errorf("%s.Len: got %d, want 3", set, set.Len())
71 t.Errorf("%s.IsEmpty: got true", set)
74 t.Errorf("%s.Has(123): got false", set)
77 t.Errorf("%s.Has(1234): got true", set)
79 got := set.AppendTo([]int{-1})
80 if want := []int{-1, 123, 456, 789}; fmt.Sprint(got) != fmt.Sprint(want) {
81 t.Errorf("%s.AppendTo: got %v, want %v", set, got, want)
87 t.Errorf("Clear: got %d, want 0", set.Len())
90 t.Errorf("IsEmpty: got false")
93 t.Errorf("%s.Has: got false", set)
97 func TestTakeMin(t *testing.T) {
98 var set intsets.Sparse
104 for i, want := range []int{-123, 123, 456, 789} {
105 if !set.TakeMin(&got) || got != want {
106 t.Errorf("TakeMin #%d: got %d, want %d", i, got, want)
109 if set.TakeMin(&got) {
110 t.Errorf("%s.TakeMin returned true", &set)
112 if err := set.Check(); err != nil {
113 t.Fatalf("check: %s: %#v", err, &set)
117 func TestMinAndMax(t *testing.T) {
118 values := []int{0, 456, 123, 789, -123} // elt 0 => empty set
119 wantMax := []int{intsets.MinInt, 456, 456, 789, 789}
120 wantMin := []int{intsets.MaxInt, 456, 123, 123, -123}
122 var set intsets.Sparse
123 for i, x := range values {
127 if got, want := set.Min(), wantMin[i]; got != want {
128 t.Errorf("Min #%d: got %d, want %d", i, got, want)
130 if got, want := set.Max(), wantMax[i]; got != want {
131 t.Errorf("Max #%d: got %d, want %d", i, got, want)
135 set.Insert(intsets.MinInt)
136 if got, want := set.Min(), intsets.MinInt; got != want {
137 t.Errorf("Min: got %d, want %d", got, want)
140 set.Insert(intsets.MaxInt)
141 if got, want := set.Max(), intsets.MaxInt; got != want {
142 t.Errorf("Max: got %d, want %d", got, want)
146 func TestEquals(t *testing.T) {
147 var setX intsets.Sparse
152 if !setX.Equals(&setX) {
153 t.Errorf("Equals(%s, %s): got false", &setX, &setX)
156 var setY intsets.Sparse
161 if !setX.Equals(&setY) {
162 t.Errorf("Equals(%s, %s): got false", &setX, &setY)
166 if setX.Equals(&setY) {
167 t.Errorf("Equals(%s, %s): got true", &setX, &setY)
170 var empty intsets.Sparse
171 if setX.Equals(&empty) {
172 t.Errorf("Equals(%s, %s): got true", &setX, &empty)
175 // Edge case: some block (with offset=0) appears in X but not Y.
177 if setX.Equals(&setY) {
178 t.Errorf("Equals(%s, %s): got true", &setX, &setY)
182 // A pset is a parallel implementation of a set using both an intsets.Sparse
183 // and a built-in hash map.
189 func makePset() *pset {
190 return &pset{hash: make(map[int]bool)}
193 func (set *pset) add(n int) {
194 prev := len(set.hash)
196 grewA := len(set.hash) > prev
198 grewB := set.bits.Insert(n)
201 panic(fmt.Sprintf("add(%d): grewA=%t grewB=%t", n, grewA, grewB))
205 func (set *pset) remove(n int) {
206 prev := len(set.hash)
208 shrankA := len(set.hash) < prev
210 shrankB := set.bits.Remove(n)
212 if shrankA != shrankB {
213 panic(fmt.Sprintf("remove(%d): shrankA=%t shrankB=%t", n, shrankA, shrankB))
217 func (set *pset) check(t *testing.T, msg string) {
219 for elt := range set.hash {
220 eltsA = append(eltsA, int(elt))
224 eltsB := set.bits.AppendTo(nil)
226 if a, b := fmt.Sprint(eltsA), fmt.Sprint(eltsB); a != b {
227 t.Errorf("check(%s): hash=%s bits=%s (%s)", msg, a, b, &set.bits)
230 if err := set.bits.Check(); err != nil {
231 t.Fatalf("Check(%s): %s: %#v", msg, err, &set.bits)
235 // randomPset returns a parallel set of random size and elements.
236 func randomPset(prng *rand.Rand, maxSize int) *pset {
238 size := int(prng.Int()) % maxSize
239 for i := 0; i < size; i++ {
240 // TODO(adonovan): benchmark how performance varies
241 // with this sparsity parameter.
242 n := int(prng.Int()) % 10000
248 // TestRandomMutations performs the same random adds/removes on two
249 // set implementations and ensures that they compute the same result.
250 func TestRandomMutations(t *testing.T) {
254 prng := rand.New(rand.NewSource(0))
255 for i := 0; i < 10000; i++ {
256 n := int(prng.Int())%2000 - 1000
259 log.Printf("add %d", n)
264 log.Printf("remove %d", n)
269 set.check(t, "post mutation")
272 set.check(t, "final")
278 func TestLowerBound(t *testing.T) {
279 // Use random sets of sizes from 0 to about 4000.
280 prng := rand.New(rand.NewSource(0))
281 for i := uint(0); i < 12; i++ {
282 x := randomPset(prng, 1<<i)
283 for j := 0; j < 10000; j++ {
284 found := intsets.MaxInt
285 for e := range x.hash {
286 if e >= j && e < found {
290 if res := x.bits.LowerBound(j); res != found {
291 t.Errorf("%s: LowerBound(%d)=%d, expected %d", &x.bits, j, res, found)
297 // TestSetOperations exercises classic set operations: ∩ , ∪, \.
298 func TestSetOperations(t *testing.T) {
299 prng := rand.New(rand.NewSource(0))
301 // Use random sets of sizes from 0 to about 4000.
302 // For each operator, we test variations such as
303 // Z.op(X, Y), Z.op(X, Z) and Z.op(Z, Y) to exercise
304 // the degenerate cases of each method implementation.
305 for i := uint(0); i < 12; i++ {
306 X := randomPset(prng, 1<<i)
307 Y := randomPset(prng, 1<<i)
309 // TODO(adonovan): minimise dependencies between stanzas below.
313 C.bits.Copy(&Y.bits) // no effect on result
316 C.check(t, "C.Copy(X)")
318 C.check(t, "C.Copy(C)")
322 U.bits.Union(&X.bits, &Y.bits)
323 for n := range X.hash {
326 for n := range Y.hash {
329 U.check(t, "U.Union(X, Y)")
332 U.bits.Union(&X.bits, &X.bits)
334 U.check(t, "U.Union(X, X)")
339 U.bits.Union(&U.bits, &Y.bits)
340 for n := range X.hash {
343 for n := range Y.hash {
346 U.check(t, "U.Union(U, Y)")
350 U.bits.Union(&X.bits, &U.bits)
351 U.check(t, "U.Union(X, U)")
354 U.bits.UnionWith(&U.bits)
355 U.check(t, "U.UnionWith(U)")
357 // I.Intersection(X, Y)
359 I.bits.Intersection(&X.bits, &Y.bits)
360 for n := range X.hash {
365 I.check(t, "I.Intersection(X, Y)")
367 // I.Intersection(X, X)
368 I.bits.Intersection(&X.bits, &X.bits)
370 I.check(t, "I.Intersection(X, X)")
372 // I.Intersection(I, X)
373 I.bits.Intersection(&I.bits, &X.bits)
374 I.check(t, "I.Intersection(I, X)")
376 // I.Intersection(X, I)
377 I.bits.Intersection(&X.bits, &I.bits)
378 I.check(t, "I.Intersection(X, I)")
380 // I.Intersection(I, I)
381 I.bits.Intersection(&I.bits, &I.bits)
382 I.check(t, "I.Intersection(I, I)")
384 // D.Difference(X, Y)
386 D.bits.Difference(&X.bits, &Y.bits)
387 for n := range X.hash {
392 D.check(t, "D.Difference(X, Y)")
394 // D.Difference(D, Y)
396 D.bits.Difference(&D.bits, &Y.bits)
397 D.check(t, "D.Difference(D, Y)")
399 // D.Difference(Y, D)
401 D.bits.Difference(&Y.bits, &D.bits)
402 D.hash = make(map[int]bool)
403 for n := range Y.hash {
408 D.check(t, "D.Difference(Y, D)")
410 // D.Difference(X, X)
411 D.bits.Difference(&X.bits, &X.bits)
413 D.check(t, "D.Difference(X, X)")
415 // D.DifferenceWith(D)
417 D.bits.DifferenceWith(&D.bits)
418 D.check(t, "D.DifferenceWith(D)")
420 // SD.SymmetricDifference(X, Y)
422 SD.bits.SymmetricDifference(&X.bits, &Y.bits)
423 for n := range X.hash {
428 for n := range Y.hash {
433 SD.check(t, "SD.SymmetricDifference(X, Y)")
435 // X.SymmetricDifferenceWith(Y)
436 SD.bits.Copy(&X.bits)
437 SD.bits.SymmetricDifferenceWith(&Y.bits)
438 SD.check(t, "X.SymmetricDifference(Y)")
440 // Y.SymmetricDifferenceWith(X)
441 SD.bits.Copy(&Y.bits)
442 SD.bits.SymmetricDifferenceWith(&X.bits)
443 SD.check(t, "Y.SymmetricDifference(X)")
445 // SD.SymmetricDifference(X, X)
446 SD.bits.SymmetricDifference(&X.bits, &X.bits)
448 SD.check(t, "SD.SymmetricDifference(X, X)")
450 // SD.SymmetricDifference(X, Copy(X))
452 X2.bits.Copy(&X.bits)
453 SD.bits.SymmetricDifference(&X.bits, &X2.bits)
454 SD.check(t, "SD.SymmetricDifference(X, Copy(X))")
456 // Copy(X).SymmetricDifferenceWith(X)
457 SD.bits.Copy(&X.bits)
458 SD.bits.SymmetricDifferenceWith(&X.bits)
459 SD.check(t, "Copy(X).SymmetricDifferenceWith(X)")
463 func TestIntersectionWith(t *testing.T) {
464 // Edge cases: the pairs (1,1), (1000,2000), (8000,4000)
465 // exercise the <, >, == cases in IntersectionWith that the
466 // TestSetOperations data is too dense to cover.
467 var X, Y intsets.Sparse
474 X.IntersectionWith(&Y)
475 if got, want := X.String(), "{1}"; got != want {
476 t.Errorf("IntersectionWith: got %s, want %s", got, want)
480 func TestIntersects(t *testing.T) {
481 prng := rand.New(rand.NewSource(0))
483 for i := uint(0); i < 12; i++ {
484 X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
485 x, y := &X.bits, &Y.bits
490 z.IntersectionWith(y)
492 if got, want := x.Intersects(y), !z.IsEmpty(); got != want {
493 t.Errorf("Intersects(%s, %s): got %v, want %v (%s)", x, y, got, want, &z)
498 for _, v := range a {
502 if got, want := x.Intersects(y), false; got != want {
503 t.Errorf("Intersects: got %v, want %v", got, want)
510 i := prng.Intn(len(a))
513 if got, want := x.Intersects(y), true; got != want {
514 t.Errorf("Intersects: got %v, want %v", got, want)
519 func TestSubsetOf(t *testing.T) {
520 prng := rand.New(rand.NewSource(0))
522 for i := uint(0); i < 12; i++ {
523 X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
524 x, y := &X.bits, &Y.bits
531 if got, want := x.SubsetOf(y), z.IsEmpty(); got != want {
532 t.Errorf("SubsetOf: got %v, want %v", got, want)
538 if got, want := x.SubsetOf(y), true; got != want {
539 t.Errorf("SubsetOf: got %v, want %v", got, want)
547 i := prng.Intn(len(a))
550 if got, want := x.SubsetOf(y), false; got != want {
551 t.Errorf("SubsetOf: got %v, want %v", got, want)
556 func TestBitString(t *testing.T) {
557 for _, test := range []struct {
563 {[]int{0, 4, 5}, "110001"},
564 {[]int{0, 7, 177}, "1" + strings.Repeat("0", 169) + "10000001"},
565 {[]int{-3, 0, 4, 5}, "110001.001"},
566 {[]int{-3}, "0.001"},
568 var set intsets.Sparse
569 for _, x := range test.input {
572 if got := set.BitString(); got != test.want {
573 t.Errorf("BitString(%s) = %s, want %s", set.String(), got, test.want)
578 func TestFailFastOnShallowCopy(t *testing.T) {
582 y := x // shallow copy (breaks representation invariants)
584 got := fmt.Sprint(recover())
585 want := "interface conversion: interface {} is nil, not intsets.to_copy_a_sparse_you_must_call_its_Copy_method"
587 t.Errorf("shallow copy: recover() = %q, want %q", got, want)
590 _ = y.String() // panics
591 t.Error("didn't panic as expected")
594 // -- Benchmarks -------------------------------------------------------
597 // - Add benchmarks of each method.
598 // - Gather set distributions from pointer analysis.
599 // - Measure memory usage.
601 func benchmarkInsertProbeSparse(b *testing.B, size, spread int) {
602 prng := rand.New(rand.NewSource(0))
603 // Generate our insertions and probes beforehand (we don't want to benchmark
605 insert := make([]int, size)
606 probe := make([]int, size*2)
607 for i := range insert {
608 insert[i] = prng.Int() % spread
610 for i := range probe {
611 probe[i] = prng.Int() % spread
616 for tries := 0; tries < b.N; tries++ {
618 for _, n := range insert {
622 for _, n := range probe {
627 // Use the variable so it doesn't get optimized away.
628 if hits > len(probe) {
629 b.Fatalf("%d hits, only %d probes", hits, len(probe))
634 func BenchmarkInsertProbeSparse_2_10(b *testing.B) {
635 benchmarkInsertProbeSparse(b, 2, 10)
638 func BenchmarkInsertProbeSparse_10_10(b *testing.B) {
639 benchmarkInsertProbeSparse(b, 10, 10)
642 func BenchmarkInsertProbeSparse_10_1000(b *testing.B) {
643 benchmarkInsertProbeSparse(b, 10, 1000)
646 func BenchmarkInsertProbeSparse_100_100(b *testing.B) {
647 benchmarkInsertProbeSparse(b, 100, 100)
650 func BenchmarkInsertProbeSparse_100_10000(b *testing.B) {
651 benchmarkInsertProbeSparse(b, 100, 1000)
654 func BenchmarkUnionDifferenceSparse(b *testing.B) {
655 prng := rand.New(rand.NewSource(0))
656 for tries := 0; tries < b.N; tries++ {
657 var x, y, z intsets.Sparse
658 for i := 0; i < 1000; i++ {
659 n := int(prng.Int()) % 100000
671 func BenchmarkUnionDifferenceHashTable(b *testing.B) {
672 prng := rand.New(rand.NewSource(0))
673 for tries := 0; tries < b.N; tries++ {
674 x, y, z := make(map[int]bool), make(map[int]bool), make(map[int]bool)
675 for i := 0; i < 1000; i++ {
676 n := int(prng.Int()) % 100000
691 z = make(map[int]bool)
700 func BenchmarkAppendTo(b *testing.B) {
701 prng := rand.New(rand.NewSource(0))
703 for i := 0; i < 1000; i++ {
704 x.Insert(int(prng.Int()) % 10000)
707 for tries := 0; tries < b.N; tries++ {
708 x.AppendTo(space[:0])