gopls/container/intsets/sparse

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.
4
5	package intsets_test
6
7	import (
8	"fmt"
9	"log"
10	"math/rand"
11	"sort"
12	"strings"
13	"testing"
14
15	"golang.org/x/tools/container/intsets"
16	)
17
18	func TestBasics(t *testing.T) {
19	var s intsets.Sparse
20	if len := s.Len(); len != 0 {
21	t.Errorf("Len({}): got %d, want 0", len)
22	}
23	if s := s.String(); s != "{}" {
24	t.Errorf("String({}): got %q, want \"{}\"", s)
25	}
26	if s.Has(3) {
27	t.Errorf("Has(3): got true, want false")
28	}
29	if err := s.Check(); err != nil {
30	t.Error(err)
31	}
32
33	if !s.Insert(3) {
34	t.Errorf("Insert(3): got false, want true")
35	}
36	if max := s.Max(); max != 3 {
37	t.Errorf("Max: got %d, want 3", max)
38	}
39
40	if !s.Insert(435) {
41	t.Errorf("Insert(435): got false, want true")
42	}
43	if s := s.String(); s != "{3 435}" {
44	t.Errorf("String({3 435}): got %q, want \"{3 435}\"", s)
45	}
46	if max := s.Max(); max != 435 {
47	t.Errorf("Max: got %d, want 435", max)
48	}
49	if len := s.Len(); len != 2 {
50	t.Errorf("Len: got %d, want 2", len)
51	}
52
53	if !s.Remove(435) {
54	t.Errorf("Remove(435): got false, want true")
55	}
56	if s := s.String(); s != "{3}" {
57	t.Errorf("String({3}): got %q, want \"{3}\"", s)
58	}
59	}
60
61	// Insert, Len, IsEmpty, Hash, Clear, AppendTo.
62	func TestMoreBasics(t *testing.T) {
63	set := new(intsets.Sparse)
64	set.Insert(456)
65	set.Insert(123)
66	set.Insert(789)
67	if set.Len() != 3 {
68	t.Errorf("%s.Len: got %d, want 3", set, set.Len())
69	}
70	if set.IsEmpty() {
71	t.Errorf("%s.IsEmpty: got true", set)
72	}
73	if !set.Has(123) {
74	t.Errorf("%s.Has(123): got false", set)
75	}
76	if set.Has(1234) {
77	t.Errorf("%s.Has(1234): got true", set)
78	}
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)
82	}
83
84	set.Clear()
85
86	if set.Len() != 0 {
87	t.Errorf("Clear: got %d, want 0", set.Len())
88	}
89	if !set.IsEmpty() {
90	t.Errorf("IsEmpty: got false")
91	}
92	if set.Has(123) {
93	t.Errorf("%s.Has: got false", set)
94	}
95	}
96
97	func TestTakeMin(t *testing.T) {
98	var set intsets.Sparse
99	set.Insert(456)
100	set.Insert(123)
101	set.Insert(789)
102	set.Insert(-123)
103	var got int
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)
107	}
108	}
109	if set.TakeMin(&got) {
110	t.Errorf("%s.TakeMin returned true", &set)
111	}
112	if err := set.Check(); err != nil {
113	t.Fatalf("check: %s: %#v", err, &set)
114	}
115	}
116
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}
121
122	var set intsets.Sparse
123	for i, x := range values {
124	if i != 0 {
125	set.Insert(x)
126	}
127	if got, want := set.Min(), wantMin[i]; got != want {
128	t.Errorf("Min #%d: got %d, want %d", i, got, want)
129	}
130	if got, want := set.Max(), wantMax[i]; got != want {
131	t.Errorf("Max #%d: got %d, want %d", i, got, want)
132	}
133	}
134
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)
138	}
139
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)
143	}
144	}
145
146	func TestEquals(t *testing.T) {
147	var setX intsets.Sparse
148	setX.Insert(456)
149	setX.Insert(123)
150	setX.Insert(789)
151
152	if !setX.Equals(&setX) {
153	t.Errorf("Equals(%s, %s): got false", &setX, &setX)
154	}
155
156	var setY intsets.Sparse
157	setY.Insert(789)
158	setY.Insert(456)
159	setY.Insert(123)
160
161	if !setX.Equals(&setY) {
162	t.Errorf("Equals(%s, %s): got false", &setX, &setY)
163	}
164
165	setY.Insert(1)
166	if setX.Equals(&setY) {
167	t.Errorf("Equals(%s, %s): got true", &setX, &setY)
168	}
169
170	var empty intsets.Sparse
171	if setX.Equals(&empty) {
172	t.Errorf("Equals(%s, %s): got true", &setX, &empty)
173	}
174
175	// Edge case: some block (with offset=0) appears in X but not Y.
176	setY.Remove(123)
177	if setX.Equals(&setY) {
178	t.Errorf("Equals(%s, %s): got true", &setX, &setY)
179	}
180	}
181
182	// A pset is a parallel implementation of a set using both an intsets.Sparse
183	// and a built-in hash map.
184	type pset struct {
185	hash map[int]bool
186	bits intsets.Sparse
187	}
188
189	func makePset() *pset {
190	return &pset{hash: make(map[int]bool)}
191	}
192
193	func (set *pset) add(n int) {
194	prev := len(set.hash)
195	set.hash[n] = true
196	grewA := len(set.hash) > prev
197
198	grewB := set.bits.Insert(n)
199
200	if grewA != grewB {
201	panic(fmt.Sprintf("add(%d): grewA=%t grewB=%t", n, grewA, grewB))
202	}
203	}
204
205	func (set *pset) remove(n int) {
206	prev := len(set.hash)
207	delete(set.hash, n)
208	shrankA := len(set.hash) < prev
209
210	shrankB := set.bits.Remove(n)
211
212	if shrankA != shrankB {
213	panic(fmt.Sprintf("remove(%d): shrankA=%t shrankB=%t", n, shrankA, shrankB))
214	}
215	}
216
217	func (set pset) check(t testing.T, msg string) {
218	var eltsA []int
219	for elt := range set.hash {
220	eltsA = append(eltsA, int(elt))
221	}
222	sort.Ints(eltsA)
223
224	eltsB := set.bits.AppendTo(nil)
225
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)
228	}
229
230	if err := set.bits.Check(); err != nil {
231	t.Fatalf("Check(%s): %s: %#v", msg, err, &set.bits)
232	}
233	}
234
235	// randomPset returns a parallel set of random size and elements.
236	func randomPset(prng rand.Rand, maxSize int) pset {
237	set := makePset()
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
243	set.add(n)
244	}
245	return set
246	}
247
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) {
251	const debug = false
252
253	set := makePset()
254	prng := rand.New(rand.NewSource(0))
255	for i := 0; i < 10000; i++ {
256	n := int(prng.Int())%2000 - 1000
257	if i%2 == 0 {
258	if debug {
259	log.Printf("add %d", n)
260	}
261	set.add(n)
262	} else {
263	if debug {
264	log.Printf("remove %d", n)
265	}
266	set.remove(n)
267	}
268	if debug {
269	set.check(t, "post mutation")
270	}
271	}
272	set.check(t, "final")
273	if debug {
274	log.Print(&set.bits)
275	}
276	}
277
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 {
287	found = e
288	}
289	}
290	if res := x.bits.LowerBound(j); res != found {
291	t.Errorf("%s: LowerBound(%d)=%d, expected %d", &x.bits, j, res, found)
292	}
293	}
294	}
295	}
296
297	// TestSetOperations exercises classic set operations: ∩ , ∪, \.
298	func TestSetOperations(t *testing.T) {
299	prng := rand.New(rand.NewSource(0))
300
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)
308
309	// TODO(adonovan): minimise dependencies between stanzas below.
310
311	// Copy(X)
312	C := makePset()
313	C.bits.Copy(&Y.bits) // no effect on result
314	C.bits.Copy(&X.bits)
315	C.hash = X.hash
316	C.check(t, "C.Copy(X)")
317	C.bits.Copy(&C.bits)
318	C.check(t, "C.Copy(C)")
319
320	// U.Union(X, Y)
321	U := makePset()
322	U.bits.Union(&X.bits, &Y.bits)
323	for n := range X.hash {
324	U.hash[n] = true
325	}
326	for n := range Y.hash {
327	U.hash[n] = true
328	}
329	U.check(t, "U.Union(X, Y)")
330
331	// U.Union(X, X)
332	U.bits.Union(&X.bits, &X.bits)
333	U.hash = X.hash
334	U.check(t, "U.Union(X, X)")
335
336	// U.Union(U, Y)
337	U = makePset()
338	U.bits.Copy(&X.bits)
339	U.bits.Union(&U.bits, &Y.bits)
340	for n := range X.hash {
341	U.hash[n] = true
342	}
343	for n := range Y.hash {
344	U.hash[n] = true
345	}
346	U.check(t, "U.Union(U, Y)")
347
348	// U.Union(X, U)
349	U.bits.Copy(&Y.bits)
350	U.bits.Union(&X.bits, &U.bits)
351	U.check(t, "U.Union(X, U)")
352
353	// U.UnionWith(U)
354	U.bits.UnionWith(&U.bits)
355	U.check(t, "U.UnionWith(U)")
356
357	// I.Intersection(X, Y)
358	I := makePset()
359	I.bits.Intersection(&X.bits, &Y.bits)
360	for n := range X.hash {
361	if Y.hash[n] {
362	I.hash[n] = true
363	}
364	}
365	I.check(t, "I.Intersection(X, Y)")
366
367	// I.Intersection(X, X)
368	I.bits.Intersection(&X.bits, &X.bits)
369	I.hash = X.hash
370	I.check(t, "I.Intersection(X, X)")
371
372	// I.Intersection(I, X)
373	I.bits.Intersection(&I.bits, &X.bits)
374	I.check(t, "I.Intersection(I, X)")
375
376	// I.Intersection(X, I)
377	I.bits.Intersection(&X.bits, &I.bits)
378	I.check(t, "I.Intersection(X, I)")
379
380	// I.Intersection(I, I)
381	I.bits.Intersection(&I.bits, &I.bits)
382	I.check(t, "I.Intersection(I, I)")
383
384	// D.Difference(X, Y)
385	D := makePset()
386	D.bits.Difference(&X.bits, &Y.bits)
387	for n := range X.hash {
388	if !Y.hash[n] {
389	D.hash[n] = true
390	}
391	}
392	D.check(t, "D.Difference(X, Y)")
393
394	// D.Difference(D, Y)
395	D.bits.Copy(&X.bits)
396	D.bits.Difference(&D.bits, &Y.bits)
397	D.check(t, "D.Difference(D, Y)")
398
399	// D.Difference(Y, D)
400	D.bits.Copy(&X.bits)
401	D.bits.Difference(&Y.bits, &D.bits)
402	D.hash = make(map[int]bool)
403	for n := range Y.hash {
404	if !X.hash[n] {
405	D.hash[n] = true
406	}
407	}
408	D.check(t, "D.Difference(Y, D)")
409
410	// D.Difference(X, X)
411	D.bits.Difference(&X.bits, &X.bits)
412	D.hash = nil
413	D.check(t, "D.Difference(X, X)")
414
415	// D.DifferenceWith(D)
416	D.bits.Copy(&X.bits)
417	D.bits.DifferenceWith(&D.bits)
418	D.check(t, "D.DifferenceWith(D)")
419
420	// SD.SymmetricDifference(X, Y)
421	SD := makePset()
422	SD.bits.SymmetricDifference(&X.bits, &Y.bits)
423	for n := range X.hash {
424	if !Y.hash[n] {
425	SD.hash[n] = true
426	}
427	}
428	for n := range Y.hash {
429	if !X.hash[n] {
430	SD.hash[n] = true
431	}
432	}
433	SD.check(t, "SD.SymmetricDifference(X, Y)")
434
435	// X.SymmetricDifferenceWith(Y)
436	SD.bits.Copy(&X.bits)
437	SD.bits.SymmetricDifferenceWith(&Y.bits)
438	SD.check(t, "X.SymmetricDifference(Y)")
439
440	// Y.SymmetricDifferenceWith(X)
441	SD.bits.Copy(&Y.bits)
442	SD.bits.SymmetricDifferenceWith(&X.bits)
443	SD.check(t, "Y.SymmetricDifference(X)")
444
445	// SD.SymmetricDifference(X, X)
446	SD.bits.SymmetricDifference(&X.bits, &X.bits)
447	SD.hash = nil
448	SD.check(t, "SD.SymmetricDifference(X, X)")
449
450	// SD.SymmetricDifference(X, Copy(X))
451	X2 := makePset()
452	X2.bits.Copy(&X.bits)
453	SD.bits.SymmetricDifference(&X.bits, &X2.bits)
454	SD.check(t, "SD.SymmetricDifference(X, Copy(X))")
455
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)")
460	}
461	}
462
463	// TestUnionWithChanged checks the 'changed' result of UnionWith.
464	func TestUnionWithChanged(t *testing.T) {
465	setOf := func(elems ...int) *intsets.Sparse {
466	s := new(intsets.Sparse)
467	for _, elem := range elems {
468	s.Insert(elem)
469	}
470	return s
471	}
472
473	checkUnionWith := func(x, y *intsets.Sparse) {
474	xstr := x.String()
475	prelen := x.Len()
476	changed := x.UnionWith(y)
477	if (x.Len() > prelen) != changed {
478	t.Errorf("%s.UnionWith(%s) => %s, changed=%t", xstr, y, x, changed)
479	}
480	}
481
482	// The case marked "!" is a regression test for Issue 50352,
483	// which spuriously returned true when y ⊂ x.
484
485	// same block
486	checkUnionWith(setOf(1, 2), setOf(1, 2))
487	checkUnionWith(setOf(1, 2, 3), setOf(1, 2)) // !
488	checkUnionWith(setOf(1, 2), setOf(1, 2, 3))
489	checkUnionWith(setOf(1, 2), setOf())
490
491	// different blocks
492	checkUnionWith(setOf(1, 1000000), setOf(1, 1000000))
493	checkUnionWith(setOf(1, 2, 1000000), setOf(1, 2))
494	checkUnionWith(setOf(1, 2), setOf(1, 2, 1000000))
495	checkUnionWith(setOf(1, 1000000), setOf())
496	}
497
498	func TestIntersectionWith(t *testing.T) {
499	// Edge cases: the pairs (1,1), (1000,2000), (8000,4000)
500	// exercise the <, >, == cases in IntersectionWith that the
501	// TestSetOperations data is too dense to cover.
502	var X, Y intsets.Sparse
503	X.Insert(1)
504	X.Insert(1000)
505	X.Insert(8000)
506	Y.Insert(1)
507	Y.Insert(2000)
508	Y.Insert(4000)
509	X.IntersectionWith(&Y)
510	if got, want := X.String(), "{1}"; got != want {
511	t.Errorf("IntersectionWith: got %s, want %s", got, want)
512	}
513	}
514
515	func TestIntersects(t *testing.T) {
516	prng := rand.New(rand.NewSource(0))
517
518	for i := uint(0); i < 12; i++ {
519	X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
520	x, y := &X.bits, &Y.bits
521
522	// test the slow way
523	var z intsets.Sparse
524	z.Copy(x)
525	z.IntersectionWith(y)
526
527	if got, want := x.Intersects(y), !z.IsEmpty(); got != want {
528	t.Errorf("Intersects(%s, %s): got %v, want %v (%s)", x, y, got, want, &z)
529	}
530
531	// make it false
532	a := x.AppendTo(nil)
533	for _, v := range a {
534	y.Remove(v)
535	}
536
537	if got, want := x.Intersects(y), false; got != want {
538	t.Errorf("Intersects: got %v, want %v", got, want)
539	}
540
541	// make it true
542	if x.IsEmpty() {
543	continue
544	}
545	i := prng.Intn(len(a))
546	y.Insert(a[i])
547
548	if got, want := x.Intersects(y), true; got != want {
549	t.Errorf("Intersects: got %v, want %v", got, want)
550	}
551	}
552	}
553
554	func TestSubsetOf(t *testing.T) {
555	prng := rand.New(rand.NewSource(0))
556
557	for i := uint(0); i < 12; i++ {
558	X, Y := randomPset(prng, 1<<i), randomPset(prng, 1<<i)
559	x, y := &X.bits, &Y.bits
560
561	// test the slow way
562	var z intsets.Sparse
563	z.Copy(x)
564	z.DifferenceWith(y)
565
566	if got, want := x.SubsetOf(y), z.IsEmpty(); got != want {
567	t.Errorf("SubsetOf: got %v, want %v", got, want)
568	}
569
570	// make it true
571	y.UnionWith(x)
572
573	if got, want := x.SubsetOf(y), true; got != want {
574	t.Errorf("SubsetOf: got %v, want %v", got, want)
575	}
576
577	// make it false
578	if x.IsEmpty() {
579	continue
580	}
581	a := x.AppendTo(nil)
582	i := prng.Intn(len(a))
583	y.Remove(a[i])
584
585	if got, want := x.SubsetOf(y), false; got != want {
586	t.Errorf("SubsetOf: got %v, want %v", got, want)
587	}
588	}
589	}
590
591	func TestBitString(t *testing.T) {
592	for _, test := range []struct {
593	input []int
594	want string
595	}{
596	{nil, "0"},
597	{[]int{0}, "1"},
598	{[]int{0, 4, 5}, "110001"},
599	{[]int{0, 7, 177}, "1" + strings.Repeat("0", 169) + "10000001"},
600	{[]int{-3, 0, 4, 5}, "110001.001"},
601	{[]int{-3}, "0.001"},
602	} {
603	var set intsets.Sparse
604	for _, x := range test.input {
605	set.Insert(x)
606	}
607	if got := set.BitString(); got != test.want {
608	t.Errorf("BitString(%s) = %s, want %s", set.String(), got, test.want)
609	}
610	}
611	}
612
613	func TestFailFastOnShallowCopy(t *testing.T) {
614	var x intsets.Sparse
615	x.Insert(1)
616
617	y := x // shallow copy (breaks representation invariants)
618	defer func() {
619	got := fmt.Sprint(recover())
620	want := "interface conversion: interface {} is nil, not intsets.to_copy_a_sparse_you_must_call_its_Copy_method"
621	if got != want {
622	t.Errorf("shallow copy: recover() = %q, want %q", got, want)
623	}
624	}()
625	_ = y.String() // panics
626	t.Error("didn't panic as expected")
627	}
628
629	// -- Benchmarks -------------------------------------------------------
630
631	// TODO(adonovan):
632	// - Add benchmarks of each method.
633	// - Gather set distributions from pointer analysis.
634	// - Measure memory usage.
635
636	func benchmarkInsertProbeSparse(b *testing.B, size, spread int) {
637	prng := rand.New(rand.NewSource(0))
638	// Generate our insertions and probes beforehand (we don't want to benchmark
639	// the prng).
640	insert := make([]int, size)
641	probe := make([]int, size*2)
642	for i := range insert {
643	insert[i] = prng.Int() % spread
644	}
645	for i := range probe {
646	probe[i] = prng.Int() % spread
647	}
648
649	b.ResetTimer()
650	var x intsets.Sparse
651	for tries := 0; tries < b.N; tries++ {
652	x.Clear()
653	for _, n := range insert {
654	x.Insert(n)
655	}
656	hits := 0
657	for _, n := range probe {
658	if x.Has(n) {
659	hits++
660	}
661	}
662	// Use the variable so it doesn't get optimized away.
663	if hits > len(probe) {
664	b.Fatalf("%d hits, only %d probes", hits, len(probe))
665	}
666	}
667	}
668
669	func BenchmarkInsertProbeSparse_2_10(b *testing.B) {
670	benchmarkInsertProbeSparse(b, 2, 10)
671	}
672
673	func BenchmarkInsertProbeSparse_10_10(b *testing.B) {
674	benchmarkInsertProbeSparse(b, 10, 10)
675	}
676
677	func BenchmarkInsertProbeSparse_10_1000(b *testing.B) {
678	benchmarkInsertProbeSparse(b, 10, 1000)
679	}
680
681	func BenchmarkInsertProbeSparse_100_100(b *testing.B) {
682	benchmarkInsertProbeSparse(b, 100, 100)
683	}
684
685	func BenchmarkInsertProbeSparse_100_10000(b *testing.B) {
686	benchmarkInsertProbeSparse(b, 100, 1000)
687	}
688
689	func BenchmarkUnionDifferenceSparse(b *testing.B) {
690	prng := rand.New(rand.NewSource(0))
691	for tries := 0; tries < b.N; tries++ {
692	var x, y, z intsets.Sparse
693	for i := 0; i < 1000; i++ {
694	n := int(prng.Int()) % 100000
695	if i%2 == 0 {
696	x.Insert(n)
697	} else {
698	y.Insert(n)
699	}
700	}
701	z.Union(&x, &y)
702	z.Difference(&x, &y)
703	}
704	}
705
706	func BenchmarkUnionDifferenceHashTable(b *testing.B) {
707	prng := rand.New(rand.NewSource(0))
708	for tries := 0; tries < b.N; tries++ {
709	x, y, z := make(map[int]bool), make(map[int]bool), make(map[int]bool)
710	for i := 0; i < 1000; i++ {
711	n := int(prng.Int()) % 100000
712	if i%2 == 0 {
713	x[n] = true
714	} else {
715	y[n] = true
716	}
717	}
718	// union
719	for n := range x {
720	z[n] = true
721	}
722	for n := range y {
723	z[n] = true
724	}
725	// difference
726	z = make(map[int]bool)
727	for n := range y {
728	if !x[n] {
729	z[n] = true
730	}
731	}
732	}
733	}
734
735	func BenchmarkAppendTo(b *testing.B) {
736	prng := rand.New(rand.NewSource(0))
737	var x intsets.Sparse
738	for i := 0; i < 1000; i++ {
739	x.Insert(int(prng.Int()) % 10000)
740	}
741	var space [1000]int
742	for tries := 0; tries < b.N; tries++ {
743	x.AppendTo(space[:0])
744	}
745	}
746