1
2
3
4
5
6
7 package bitset
8
9 import (
10 "encoding"
11 "encoding/json"
12 "fmt"
13 "math"
14 "strconv"
15 "testing"
16 )
17
18 func TestStringer(t *testing.T) {
19 v := New(0)
20 for i := uint(0); i < 10; i++ {
21 v.Set(i)
22 }
23 if v.String() != "{0,1,2,3,4,5,6,7,8,9}" {
24 t.Error("bad string output")
25 }
26 }
27
28 func TestStringLong(t *testing.T) {
29 v := New(0)
30 for i := uint(0); i < 262145; i++ {
31 v.Set(i)
32 }
33 str := v.String()
34 if len(str) != 1723903 {
35 t.Error("Unexpected string length: ", len(str))
36 }
37 }
38
39 func TestEmptyBitSet(t *testing.T) {
40 defer func() {
41 if r := recover(); r != nil {
42 t.Error("A zero-length bitset should be fine")
43 }
44 }()
45 b := New(0)
46 if b.Len() != 0 {
47 t.Errorf("Empty set should have capacity 0, not %d", b.Len())
48 }
49 }
50
51 func TestZeroValueBitSet(t *testing.T) {
52 defer func() {
53 if r := recover(); r != nil {
54 t.Error("A zero-length bitset should be fine")
55 }
56 }()
57 var b BitSet
58 if b.Len() != 0 {
59 t.Errorf("Empty set should have capacity 0, not %d", b.Len())
60 }
61 }
62
63 func TestBitSetNew(t *testing.T) {
64 v := New(16)
65 if v.Test(0) {
66 t.Errorf("Unable to make a bit set and read its 0th value.")
67 }
68 }
69
70 func TestBitSetHuge(t *testing.T) {
71 v := New(uint(math.MaxUint32))
72 if v.Test(0) {
73 t.Errorf("Unable to make a huge bit set and read its 0th value.")
74 }
75 }
76
77 func TestLen(t *testing.T) {
78 v := New(1000)
79 if v.Len() != 1000 {
80 t.Errorf("Len should be 1000, but is %d.", v.Len())
81 }
82 }
83
84 func TestLenIsNumberOfBitsNotBytes(t *testing.T) {
85 var b BitSet
86 if b.Len() != 0 {
87 t.Errorf("empty bitset should have Len 0, got %v", b.Len())
88 }
89
90 b.Set(0)
91 if b.Len() != 1 {
92 t.Errorf("bitset with first bit set should have Len 1, got %v", b.Len())
93 }
94
95 b.Set(8)
96 if b.Len() != 9 {
97 t.Errorf("bitset with 0th and 8th bit set should have Len 9, got %v", b.Len())
98 }
99
100 b.Set(1)
101 if b.Len() != 9 {
102 t.Errorf("bitset with 0th, 1st and 8th bit set should have Len 9, got %v", b.Len())
103 }
104 }
105
106 func ExampleBitSet_Len() {
107 var b BitSet
108 b.Set(8)
109 fmt.Println("len", b.Len())
110 fmt.Println("count", b.Count())
111
112
113
114 }
115
116 func TestBitSetIsClear(t *testing.T) {
117 v := New(1000)
118 for i := uint(0); i < 1000; i++ {
119 if v.Test(i) {
120 t.Errorf("Bit %d is set, and it shouldn't be.", i)
121 }
122 }
123 }
124
125 func TestExendOnBoundary(t *testing.T) {
126 v := New(32)
127 defer func() {
128 if r := recover(); r != nil {
129 t.Error("Border out of index error should not have caused a panic")
130 }
131 }()
132 v.Set(32)
133 }
134
135 func TestExceedCap(t *testing.T) {
136 defer func() {
137 if r := recover(); r == nil {
138 t.Error("Set to capacity should have caused a panic")
139 }
140 }()
141 NumHosts := uint(32768)
142 bmp := New(NumHosts)
143 bmp.ClearAll()
144 d := Cap()
145 bmp.Set(d)
146
147 }
148
149 func TestExpand(t *testing.T) {
150 v := New(0)
151 defer func() {
152 if r := recover(); r != nil {
153 t.Error("Expansion should not have caused a panic")
154 }
155 }()
156 for i := uint(0); i < 1000; i++ {
157 v.Set(i)
158 }
159 }
160
161 func TestBitSetAndGet(t *testing.T) {
162 v := New(1000)
163 v.Set(100)
164 if !v.Test(100) {
165 t.Errorf("Bit %d is clear, and it shouldn't be.", 100)
166 }
167 }
168
169 func TestNextClear(t *testing.T) {
170 v := New(1000)
171 v.Set(0).Set(1)
172 next, found := v.NextClear(0)
173 if !found || next != 2 {
174 t.Errorf("Found next clear bit as %d, it should have been 2", next)
175 }
176
177 v = New(1000)
178 for i := uint(0); i < 66; i++ {
179 v.Set(i)
180 }
181 next, found = v.NextClear(0)
182 if !found || next != 66 {
183 t.Errorf("Found next clear bit as %d, it should have been 66", next)
184 }
185
186 v = New(1000)
187 for i := uint(0); i < 64; i++ {
188 v.Set(i)
189 }
190 v.Clear(45)
191 v.Clear(52)
192 next, found = v.NextClear(10)
193 if !found || next != 45 {
194 t.Errorf("Found next clear bit as %d, it should have been 45", next)
195 }
196
197 v = New(1000)
198 for i := uint(0); i < 128; i++ {
199 v.Set(i)
200 }
201 v.Clear(73)
202 v.Clear(99)
203 next, found = v.NextClear(10)
204 if !found || next != 73 {
205 t.Errorf("Found next clear bit as %d, it should have been 73", next)
206 }
207
208 next, found = v.NextClear(72)
209 if !found || next != 73 {
210 t.Errorf("Found next clear bit as %d, it should have been 73", next)
211 }
212 next, found = v.NextClear(73)
213 if !found || next != 73 {
214 t.Errorf("Found next clear bit as %d, it should have been 73", next)
215 }
216 next, found = v.NextClear(74)
217 if !found || next != 99 {
218 t.Errorf("Found next clear bit as %d, it should have been 73", next)
219 }
220
221 v = New(128)
222 next, found = v.NextClear(0)
223 if !found || next != 0 {
224 t.Errorf("Found next clear bit as %d, it should have been 0", next)
225 }
226
227 for i := uint(0); i < 128; i++ {
228 v.Set(i)
229 }
230 _, found = v.NextClear(0)
231 if found {
232 t.Errorf("There are not clear bits")
233 }
234
235 b := new(BitSet)
236 c, d := b.NextClear(1)
237 if c != 0 || d {
238 t.Error("Unexpected values")
239 return
240 }
241
242 v = New(100)
243 for i := uint(0); i != 100; i++ {
244 v.Set(i)
245 }
246 next, found = v.NextClear(0)
247 if found || next != 0 {
248 t.Errorf("Found next clear bit as %d, it should have return (0, false)", next)
249
250 }
251 }
252
253 func TestIterate(t *testing.T) {
254 v := New(10000)
255 v.Set(0)
256 v.Set(1)
257 v.Set(2)
258 data := make([]uint, 3)
259 c := 0
260 for i, e := v.NextSet(0); e; i, e = v.NextSet(i + 1) {
261 data[c] = i
262 c++
263 }
264 if data[0] != 0 {
265 t.Errorf("bug 0")
266 }
267 if data[1] != 1 {
268 t.Errorf("bug 1")
269 }
270 if data[2] != 2 {
271 t.Errorf("bug 2")
272 }
273 v.Set(10)
274 v.Set(2000)
275 data = make([]uint, 5)
276 c = 0
277 for i, e := v.NextSet(0); e; i, e = v.NextSet(i + 1) {
278 data[c] = i
279 c++
280 }
281 if data[0] != 0 {
282 t.Errorf("bug 0")
283 }
284 if data[1] != 1 {
285 t.Errorf("bug 1")
286 }
287 if data[2] != 2 {
288 t.Errorf("bug 2")
289 }
290 if data[3] != 10 {
291 t.Errorf("bug 3")
292 }
293 if data[4] != 2000 {
294 t.Errorf("bug 4")
295 }
296
297 }
298
299 func TestSetTo(t *testing.T) {
300 v := New(1000)
301 v.SetTo(100, true)
302 if !v.Test(100) {
303 t.Errorf("Bit %d is clear, and it shouldn't be.", 100)
304 }
305 v.SetTo(100, false)
306 if v.Test(100) {
307 t.Errorf("Bit %d is set, and it shouldn't be.", 100)
308 }
309 }
310
311 func TestChain(t *testing.T) {
312 if !New(1000).Set(100).Set(99).Clear(99).Test(100) {
313 t.Errorf("Bit %d is clear, and it shouldn't be.", 100)
314 }
315 }
316
317 func TestOutOfBoundsLong(t *testing.T) {
318 v := New(64)
319 defer func() {
320 if r := recover(); r != nil {
321 t.Error("Long distance out of index error should not have caused a panic")
322 }
323 }()
324 v.Set(1000)
325 }
326
327 func TestOutOfBoundsClose(t *testing.T) {
328 v := New(65)
329 defer func() {
330 if r := recover(); r != nil {
331 t.Error("Local out of index error should not have caused a panic")
332 }
333 }()
334 v.Set(66)
335 }
336
337 func TestCount(t *testing.T) {
338 tot := uint(64*4 + 11)
339 v := New(tot)
340 checkLast := true
341 for i := uint(0); i < tot; i++ {
342 sz := uint(v.Count())
343 if sz != i {
344 t.Errorf("Count reported as %d, but it should be %d", sz, i)
345 checkLast = false
346 break
347 }
348 v.Set(i)
349 }
350 if checkLast {
351 sz := uint(v.Count())
352 if sz != tot {
353 t.Errorf("After all bits set, size reported as %d, but it should be %d", sz, tot)
354 }
355 }
356 }
357
358
359 func TestCount2(t *testing.T) {
360 tot := uint(64*4 + 11)
361 v := New(tot)
362 for i := uint(0); i < tot; i += 3 {
363 sz := uint(v.Count())
364 if sz != i/3 {
365 t.Errorf("Count reported as %d, but it should be %d", sz, i)
366 break
367 }
368 v.Set(i)
369 }
370 }
371
372
373 func TestNullTest(t *testing.T) {
374 var v *BitSet
375 defer func() {
376 if r := recover(); r == nil {
377 t.Error("Checking bit of null reference should have caused a panic")
378 }
379 }()
380 v.Test(66)
381 }
382
383 func TestNullSet(t *testing.T) {
384 var v *BitSet
385 defer func() {
386 if r := recover(); r == nil {
387 t.Error("Setting bit of null reference should have caused a panic")
388 }
389 }()
390 v.Set(66)
391 }
392
393 func TestNullClear(t *testing.T) {
394 var v *BitSet
395 defer func() {
396 if r := recover(); r == nil {
397 t.Error("Clearning bit of null reference should have caused a panic")
398 }
399 }()
400 v.Clear(66)
401 }
402
403 func TestNullCount(t *testing.T) {
404 var v *BitSet
405 defer func() {
406 if r := recover(); r != nil {
407 t.Error("Counting null reference should not have caused a panic")
408 }
409 }()
410 cnt := v.Count()
411 if cnt != 0 {
412 t.Errorf("Count reported as %d, but it should be 0", cnt)
413 }
414 }
415
416 func TestPanicDifferenceBNil(t *testing.T) {
417 var b *BitSet
418 var compare = New(10)
419 defer func() {
420 if r := recover(); r == nil {
421 t.Error("Nil First should should have caused a panic")
422 }
423 }()
424 b.Difference(compare)
425 }
426
427 func TestPanicDifferenceCompareNil(t *testing.T) {
428 var compare *BitSet
429 var b = New(10)
430 defer func() {
431 if r := recover(); r == nil {
432 t.Error("Nil Second should should have caused a panic")
433 }
434 }()
435 b.Difference(compare)
436 }
437
438 func TestPanicUnionBNil(t *testing.T) {
439 var b *BitSet
440 var compare = New(10)
441 defer func() {
442 if r := recover(); r == nil {
443 t.Error("Nil First should should have caused a panic")
444 }
445 }()
446 b.Union(compare)
447 }
448
449 func TestPanicUnionCompareNil(t *testing.T) {
450 var compare *BitSet
451 var b = New(10)
452 defer func() {
453 if r := recover(); r == nil {
454 t.Error("Nil Second should should have caused a panic")
455 }
456 }()
457 b.Union(compare)
458 }
459
460 func TestPanicIntersectionBNil(t *testing.T) {
461 var b *BitSet
462 var compare = New(10)
463 defer func() {
464 if r := recover(); r == nil {
465 t.Error("Nil First should should have caused a panic")
466 }
467 }()
468 b.Intersection(compare)
469 }
470
471 func TestPanicIntersectionCompareNil(t *testing.T) {
472 var compare *BitSet
473 var b = New(10)
474 defer func() {
475 if r := recover(); r == nil {
476 t.Error("Nil Second should should have caused a panic")
477 }
478 }()
479 b.Intersection(compare)
480 }
481
482 func TestPanicSymmetricDifferenceBNil(t *testing.T) {
483 var b *BitSet
484 var compare = New(10)
485 defer func() {
486 if r := recover(); r == nil {
487 t.Error("Nil First should should have caused a panic")
488 }
489 }()
490 b.SymmetricDifference(compare)
491 }
492
493 func TestPanicSymmetricDifferenceCompareNil(t *testing.T) {
494 var compare *BitSet
495 var b = New(10)
496 defer func() {
497 if r := recover(); r == nil {
498 t.Error("Nil Second should should have caused a panic")
499 }
500 }()
501 b.SymmetricDifference(compare)
502 }
503
504 func TestPanicComplementBNil(t *testing.T) {
505 var b *BitSet
506 defer func() {
507 if r := recover(); r == nil {
508 t.Error("Nil should should have caused a panic")
509 }
510 }()
511 b.Complement()
512 }
513
514 func TestPanicAnytBNil(t *testing.T) {
515 var b *BitSet
516 defer func() {
517 if r := recover(); r == nil {
518 t.Error("Nil should should have caused a panic")
519 }
520 }()
521 b.Any()
522 }
523
524 func TestPanicNonetBNil(t *testing.T) {
525 var b *BitSet
526 defer func() {
527 if r := recover(); r == nil {
528 t.Error("Nil should should have caused a panic")
529 }
530 }()
531 b.None()
532 }
533
534 func TestPanicAlltBNil(t *testing.T) {
535 var b *BitSet
536 defer func() {
537 if r := recover(); r == nil {
538 t.Error("Nil should should have caused a panic")
539 }
540 }()
541 b.All()
542 }
543
544 func TestAll(t *testing.T) {
545 v := New(0)
546 if !v.All() {
547 t.Error("Empty sets should return true on All()")
548 }
549 v = New(2)
550 v.SetTo(0, true)
551 v.SetTo(1, true)
552 if !v.All() {
553 t.Error("Non-empty sets with all bits set should return true on All()")
554 }
555 v = New(2)
556 if v.All() {
557 t.Error("Non-empty sets with no bits set should return false on All()")
558 }
559 v = New(2)
560 v.SetTo(0, true)
561 if v.All() {
562 t.Error("Non-empty sets with some bits set should return false on All()")
563 }
564 }
565
566 func TestShrink(t *testing.T) {
567 b := New(0)
568
569 b.Set(0)
570 b.Set(1)
571 b.Set(2)
572 b.Set(3)
573 b.Set(64)
574 b.Compact()
575 if !b.Test(0) {
576 t.Error("0 should be set")
577 return
578 }
579 if !b.Test(1) {
580 t.Error("1 should be set")
581 return
582 }
583 if !b.Test(2) {
584 t.Error("2 should be set")
585 return
586 }
587 if !b.Test(3) {
588 t.Error("3 should be set")
589 return
590 }
591 if !b.Test(64) {
592 t.Error("64 should be set")
593 return
594 }
595
596 b.Shrink(2)
597 if !b.Test(0) {
598 t.Error("0 should be set")
599 return
600 }
601 if !b.Test(1) {
602 t.Error("1 should be set")
603 return
604 }
605 if !b.Test(2) {
606 t.Error("2 should be set")
607 return
608 }
609 if b.Test(3) {
610 t.Error("3 should not be set")
611 return
612 }
613 if b.Test(64) {
614 t.Error("64 should not be set")
615 return
616 }
617
618 b.Set(24)
619 b.Shrink(100)
620 if !b.Test(24) {
621 t.Error("24 should be set")
622 return
623 }
624
625 b.Set(127)
626 b.Set(128)
627 b.Set(129)
628 b.Compact()
629 if !b.Test(127) {
630 t.Error("127 should be set")
631 return
632 }
633 if !b.Test(128) {
634 t.Error("128 should be set")
635 return
636 }
637 if !b.Test(129) {
638 t.Error("129 be set")
639 return
640 }
641
642 b.Shrink(128)
643 if !b.Test(127) {
644 t.Error("127 should be set")
645 return
646 }
647 if !b.Test(128) {
648 t.Error("128 should be set")
649 return
650 }
651 if b.Test(129) {
652 t.Error("129 should not be set")
653 return
654 }
655
656 b.Set(129)
657 b.Shrink(129)
658 if !b.Test(129) {
659 t.Error("129 should be set")
660 return
661 }
662
663 b.Set(1000)
664 b.Set(2000)
665 b.Set(3000)
666 b.Shrink(3000)
667 if len(b.set) != 3000/64+1 {
668 t.Error("Wrong length of BitSet.set")
669 return
670 }
671 if !b.Test(3000) {
672 t.Error("3000 should be set")
673 return
674 }
675
676 b.Shrink(2000)
677 if len(b.set) != 2000/64+1 {
678 t.Error("Wrong length of BitSet.set")
679 return
680 }
681 if b.Test(3000) {
682 t.Error("3000 should not be set")
683 return
684 }
685 if !b.Test(2000) {
686 t.Error("2000 should be set")
687 return
688 }
689 if !b.Test(1000) {
690 t.Error("1000 should be set")
691 return
692 }
693 if !b.Test(24) {
694 t.Error("24 should be set")
695 return
696 }
697 }
698
699 func TestInsertAtWithSet(t *testing.T) {
700 b := New(0)
701 b.Set(0)
702 b.Set(1)
703 b.Set(63)
704 b.Set(64)
705 b.Set(65)
706
707 b.InsertAt(3)
708 if !b.Test(0) {
709 t.Error("0 should be set")
710 return
711 }
712 if !b.Test(1) {
713 t.Error("1 should be set")
714 return
715 }
716 if b.Test(3) {
717 t.Error("3 should not be set")
718 return
719 }
720 if !b.Test(64) {
721 t.Error("64 should be set")
722 return
723 }
724 if !b.Test(65) {
725 t.Error("65 should be set")
726 return
727 }
728 if !b.Test(66) {
729 t.Error("66 should be set")
730 return
731 }
732
733 }
734
735 func TestInsertAt(t *testing.T) {
736 type testCase struct {
737 input []string
738 insertIdx uint
739 expected []string
740 }
741
742 testCases := []testCase{
743 {
744 input: []string{
745 "1111111111111111111111111111111111111111111111111111111111111111",
746 },
747 insertIdx: uint(62),
748 expected: []string{
749 "1011111111111111111111111111111111111111111111111111111111111111",
750 "0000000000000000000000000000000000000000000000000000000000000001",
751 },
752 },
753 {
754 input: []string{
755 "1111111111111111111111111111111111111111111111111111111111111111",
756 },
757 insertIdx: uint(63),
758 expected: []string{
759 "0111111111111111111111111111111111111111111111111111111111111111",
760 "0000000000000000000000000000000000000000000000000000000000000001",
761 },
762 },
763 {
764 input: []string{
765 "1111111111111111111111111111111111111111111111111111111111111111",
766 },
767 insertIdx: uint(0),
768 expected: []string{
769 "1111111111111111111111111111111111111111111111111111111111111110",
770 "0000000000000000000000000000000000000000000000000000000000000001",
771 },
772 },
773 {
774 input: []string{
775 "1111111111111111111111111111111111111111111111111111111111111111",
776 "1111111111111111111111111111111111111111111111111111111111111111",
777 "1111111111111111111111111111111111111111111111111111111111111111",
778 },
779 insertIdx: uint(70),
780 expected: []string{
781 "1111111111111111111111111111111111111111111111111111111111111111",
782 "1111111111111111111111111111111111111111111111111111111110111111",
783 "1111111111111111111111111111111111111111111111111111111111111111",
784 "0000000000000000000000000000000000000000000000000000000000000001",
785 },
786 },
787 {
788 input: []string{
789 "1111111111111111111111111111111111111111111111111111111111111111",
790 "1111111111111111111111111111111111111111111111111111111111111111",
791 "1111111111111111111111111111111111111111111111111111111111110000",
792 },
793 insertIdx: uint(70),
794 expected: []string{
795 "1111111111111111111111111111111111111111111111111111111111111111",
796 "1111111111111111111111111111111111111111111111111111111110111111",
797 "1111111111111111111111111111111111111111111111111111111111100001",
798 "0000000000000000000000000000000000000000000000000000000000000001",
799 },
800 },
801 {
802 input: []string{
803 "1111111111111111111111111111111111111111111111111111111111110000",
804 },
805 insertIdx: uint(10),
806 expected: []string{
807 "1111111111111111111111111111111111111111111111111111101111110000",
808 "0000000000000000000000000000000000000000000000000000000000000001",
809 },
810 },
811 }
812
813 for _, tc := range testCases {
814 var input []uint64
815 for _, inputElement := range tc.input {
816 parsed, _ := strconv.ParseUint(inputElement, 2, 64)
817 input = append(input, parsed)
818 }
819
820 var expected []uint64
821 for _, expectedElement := range tc.expected {
822 parsed, _ := strconv.ParseUint(expectedElement, 2, 64)
823 expected = append(expected, parsed)
824 }
825
826 b := From(input)
827 b.InsertAt(tc.insertIdx)
828 if len(b.set) != len(expected) {
829 t.Error("Length of sets should be equal")
830 return
831 }
832 for i := range b.set {
833 if b.set[i] != expected[i] {
834 t.Error("Unexpected results found in set")
835 return
836 }
837 }
838 }
839 }
840
841 func TestNone(t *testing.T) {
842 v := New(0)
843 if !v.None() {
844 t.Error("Empty sets should return true on None()")
845 }
846 v = New(2)
847 v.SetTo(0, true)
848 v.SetTo(1, true)
849 if v.None() {
850 t.Error("Non-empty sets with all bits set should return false on None()")
851 }
852 v = New(2)
853 if !v.None() {
854 t.Error("Non-empty sets with no bits set should return true on None()")
855 }
856 v = New(2)
857 v.SetTo(0, true)
858 if v.None() {
859 t.Error("Non-empty sets with some bits set should return false on None()")
860 }
861 v = new(BitSet)
862 if !v.None() {
863 t.Error("Empty sets should return true on None()")
864 }
865 }
866
867 func TestEqual(t *testing.T) {
868 a := New(100)
869 b := New(99)
870 c := New(100)
871 if a.Equal(b) {
872 t.Error("Sets of different sizes should be not be equal")
873 }
874 if !a.Equal(c) {
875 t.Error("Two empty sets of the same size should be equal")
876 }
877 a.Set(99)
878 c.Set(0)
879 if a.Equal(c) {
880 t.Error("Two sets with differences should not be equal")
881 }
882 c.Set(99)
883 a.Set(0)
884 if !a.Equal(c) {
885 t.Error("Two sets with the same bits set should be equal")
886 }
887 if a.Equal(nil) {
888 t.Error("The sets should be different")
889 }
890 a = New(0)
891 b = New(0)
892 if !a.Equal(b) {
893 t.Error("Two empty set should be equal")
894 }
895 var x *BitSet
896 var y *BitSet
897 z := New(0)
898 if !x.Equal(y) {
899 t.Error("Two nil bitsets should be equal")
900 }
901 if x.Equal(z) {
902 t.Error("Nil receiver bitset should not be equal to non-nil bitset")
903 }
904 }
905
906 func TestUnion(t *testing.T) {
907 a := New(100)
908 b := New(200)
909 for i := uint(1); i < 100; i += 2 {
910 a.Set(i)
911 b.Set(i - 1)
912 }
913 for i := uint(100); i < 200; i++ {
914 b.Set(i)
915 }
916 if a.UnionCardinality(b) != 200 {
917 t.Errorf("Union should have 200 bits set, but had %d", a.UnionCardinality(b))
918 }
919 if a.UnionCardinality(b) != b.UnionCardinality(a) {
920 t.Errorf("Union should be symmetric")
921 }
922
923 c := a.Union(b)
924 d := b.Union(a)
925 if c.Count() != 200 {
926 t.Errorf("Union should have 200 bits set, but had %d", c.Count())
927 }
928 if !c.Equal(d) {
929 t.Errorf("Union should be symmetric")
930 }
931 }
932
933 func TestInPlaceUnion(t *testing.T) {
934 a := New(100)
935 b := New(200)
936 for i := uint(1); i < 100; i += 2 {
937 a.Set(i)
938 b.Set(i - 1)
939 }
940 for i := uint(100); i < 200; i++ {
941 b.Set(i)
942 }
943 c := a.Clone()
944 c.InPlaceUnion(b)
945 d := b.Clone()
946 d.InPlaceUnion(a)
947 if c.Count() != 200 {
948 t.Errorf("Union should have 200 bits set, but had %d", c.Count())
949 }
950 if d.Count() != 200 {
951 t.Errorf("Union should have 200 bits set, but had %d", d.Count())
952 }
953 if !c.Equal(d) {
954 t.Errorf("Union should be symmetric")
955 }
956 }
957
958 func TestIntersection(t *testing.T) {
959 a := New(100)
960 b := New(200)
961 for i := uint(1); i < 100; i += 2 {
962 a.Set(i)
963 b.Set(i - 1).Set(i)
964 }
965 for i := uint(100); i < 200; i++ {
966 b.Set(i)
967 }
968 if a.IntersectionCardinality(b) != 50 {
969 t.Errorf("Intersection should have 50 bits set, but had %d", a.IntersectionCardinality(b))
970 }
971 if a.IntersectionCardinality(b) != b.IntersectionCardinality(a) {
972 t.Errorf("Intersection should be symmetric")
973 }
974 c := a.Intersection(b)
975 d := b.Intersection(a)
976 if c.Count() != 50 {
977 t.Errorf("Intersection should have 50 bits set, but had %d", c.Count())
978 }
979 if !c.Equal(d) {
980 t.Errorf("Intersection should be symmetric")
981 }
982 }
983
984 func TestInplaceIntersection(t *testing.T) {
985 a := New(100)
986 b := New(200)
987 for i := uint(1); i < 100; i += 2 {
988 a.Set(i)
989 b.Set(i - 1).Set(i)
990 }
991 for i := uint(100); i < 200; i++ {
992 b.Set(i)
993 }
994 c := a.Clone()
995 c.InPlaceIntersection(b)
996 d := b.Clone()
997 d.InPlaceIntersection(a)
998 if c.Count() != 50 {
999 t.Errorf("Intersection should have 50 bits set, but had %d", c.Count())
1000 }
1001 if d.Count() != 50 {
1002 t.Errorf("Intersection should have 50 bits set, but had %d", d.Count())
1003 }
1004 if !c.Equal(d) {
1005 t.Errorf("Intersection should be symmetric")
1006 }
1007 }
1008
1009 func TestDifference(t *testing.T) {
1010 a := New(100)
1011 b := New(200)
1012 for i := uint(1); i < 100; i += 2 {
1013 a.Set(i)
1014 b.Set(i - 1)
1015 }
1016 for i := uint(100); i < 200; i++ {
1017 b.Set(i)
1018 }
1019 if a.DifferenceCardinality(b) != 50 {
1020 t.Errorf("a-b Difference should have 50 bits set, but had %d", a.DifferenceCardinality(b))
1021 }
1022 if b.DifferenceCardinality(a) != 150 {
1023 t.Errorf("b-a Difference should have 150 bits set, but had %d", b.DifferenceCardinality(a))
1024 }
1025
1026 c := a.Difference(b)
1027 d := b.Difference(a)
1028 if c.Count() != 50 {
1029 t.Errorf("a-b Difference should have 50 bits set, but had %d", c.Count())
1030 }
1031 if d.Count() != 150 {
1032 t.Errorf("b-a Difference should have 150 bits set, but had %d", d.Count())
1033 }
1034 if c.Equal(d) {
1035 t.Errorf("Difference, here, should not be symmetric")
1036 }
1037 }
1038
1039 func TestInPlaceDifference(t *testing.T) {
1040 a := New(100)
1041 b := New(200)
1042 for i := uint(1); i < 100; i += 2 {
1043 a.Set(i)
1044 b.Set(i - 1)
1045 }
1046 for i := uint(100); i < 200; i++ {
1047 b.Set(i)
1048 }
1049 c := a.Clone()
1050 c.InPlaceDifference(b)
1051 d := b.Clone()
1052 d.InPlaceDifference(a)
1053 if c.Count() != 50 {
1054 t.Errorf("a-b Difference should have 50 bits set, but had %d", c.Count())
1055 }
1056 if d.Count() != 150 {
1057 t.Errorf("b-a Difference should have 150 bits set, but had %d", d.Count())
1058 }
1059 if c.Equal(d) {
1060 t.Errorf("Difference, here, should not be symmetric")
1061 }
1062 }
1063
1064 func TestSymmetricDifference(t *testing.T) {
1065 a := New(100)
1066 b := New(200)
1067 for i := uint(1); i < 100; i += 2 {
1068 a.Set(i)
1069 b.Set(i - 1).Set(i)
1070 }
1071 for i := uint(100); i < 200; i++ {
1072 b.Set(i)
1073 }
1074 if a.SymmetricDifferenceCardinality(b) != 150 {
1075 t.Errorf("a^b Difference should have 150 bits set, but had %d", a.SymmetricDifferenceCardinality(b))
1076 }
1077 if b.SymmetricDifferenceCardinality(a) != 150 {
1078 t.Errorf("b^a Difference should have 150 bits set, but had %d", b.SymmetricDifferenceCardinality(a))
1079 }
1080
1081 c := a.SymmetricDifference(b)
1082 d := b.SymmetricDifference(a)
1083 if c.Count() != 150 {
1084 t.Errorf("a^b Difference should have 150 bits set, but had %d", c.Count())
1085 }
1086 if d.Count() != 150 {
1087 t.Errorf("b^a Difference should have 150 bits set, but had %d", d.Count())
1088 }
1089 if !c.Equal(d) {
1090 t.Errorf("SymmetricDifference should be symmetric")
1091 }
1092 }
1093
1094 func TestInPlaceSymmetricDifference(t *testing.T) {
1095 a := New(100)
1096 b := New(200)
1097 for i := uint(1); i < 100; i += 2 {
1098 a.Set(i)
1099 b.Set(i - 1).Set(i)
1100 }
1101 for i := uint(100); i < 200; i++ {
1102 b.Set(i)
1103 }
1104 c := a.Clone()
1105 c.InPlaceSymmetricDifference(b)
1106 d := b.Clone()
1107 d.InPlaceSymmetricDifference(a)
1108 if c.Count() != 150 {
1109 t.Errorf("a^b Difference should have 150 bits set, but had %d", c.Count())
1110 }
1111 if d.Count() != 150 {
1112 t.Errorf("b^a Difference should have 150 bits set, but had %d", d.Count())
1113 }
1114 if !c.Equal(d) {
1115 t.Errorf("SymmetricDifference should be symmetric")
1116 }
1117 }
1118
1119 func TestComplement(t *testing.T) {
1120 a := New(50)
1121 b := a.Complement()
1122 if b.Count() != 50 {
1123 t.Errorf("Complement failed, size should be 50, but was %d", b.Count())
1124 }
1125 a = New(50)
1126 a.Set(10).Set(20).Set(42)
1127 b = a.Complement()
1128 if b.Count() != 47 {
1129 t.Errorf("Complement failed, size should be 47, but was %d", b.Count())
1130 }
1131 }
1132
1133 func TestIsSuperSet(t *testing.T) {
1134 a := New(500)
1135 b := New(300)
1136 c := New(200)
1137
1138
1139
1140
1141 for i := uint(0); i < 100; i++ {
1142 a.Set(i)
1143 }
1144 for i := uint(50); i < 150; i++ {
1145 b.Set(i)
1146 }
1147 for i := uint(0); i < 200; i++ {
1148 c.Set(i)
1149 }
1150
1151 if a.IsSuperSet(b) {
1152 t.Errorf("IsSuperSet fails")
1153 }
1154 if a.IsSuperSet(c) {
1155 t.Errorf("IsSuperSet fails")
1156 }
1157 if b.IsSuperSet(a) {
1158 t.Errorf("IsSuperSet fails")
1159 }
1160 if b.IsSuperSet(c) {
1161 t.Errorf("IsSuperSet fails")
1162 }
1163 if !c.IsSuperSet(a) {
1164 t.Errorf("IsSuperSet fails")
1165 }
1166 if !c.IsSuperSet(b) {
1167 t.Errorf("IsSuperSet fails")
1168 }
1169
1170 if a.IsStrictSuperSet(b) {
1171 t.Errorf("IsStrictSuperSet fails")
1172 }
1173 if a.IsStrictSuperSet(c) {
1174 t.Errorf("IsStrictSuperSet fails")
1175 }
1176 if b.IsStrictSuperSet(a) {
1177 t.Errorf("IsStrictSuperSet fails")
1178 }
1179 if b.IsStrictSuperSet(c) {
1180 t.Errorf("IsStrictSuperSet fails")
1181 }
1182 if !c.IsStrictSuperSet(a) {
1183 t.Errorf("IsStrictSuperSet fails")
1184 }
1185 if !c.IsStrictSuperSet(b) {
1186 t.Errorf("IsStrictSuperSet fails")
1187 }
1188 }
1189
1190 func TestDumpAsBits(t *testing.T) {
1191 a := New(10).Set(10)
1192 astr := "0000000000000000000000000000000000000000000000000000010000000000."
1193 if a.DumpAsBits() != astr {
1194 t.Errorf("DumpAsBits failed, output should be \"%s\" but was \"%s\"", astr, a.DumpAsBits())
1195 }
1196 var b BitSet
1197 bstr := "."
1198 if b.DumpAsBits() != bstr {
1199 t.Errorf("DumpAsBits failed, output should be \"%s\" but was \"%s\"", bstr, b.DumpAsBits())
1200 }
1201 }
1202
1203 func TestMarshalUnmarshalBinary(t *testing.T) {
1204 a := New(1010).Set(10).Set(1001)
1205 b := new(BitSet)
1206
1207 copyBinary(t, a, b)
1208
1209
1210 if !a.Equal(b) {
1211 t.Error("Bitsets are not equal:\n\t", a.DumpAsBits(), "\n\t", b.DumpAsBits())
1212 return
1213 }
1214 }
1215
1216 func TestMarshalUnmarshalBinaryByLittleEndian(t *testing.T) {
1217 LittleEndian()
1218 a := New(1010).Set(10).Set(1001)
1219 b := new(BitSet)
1220
1221 copyBinary(t, a, b)
1222
1223
1224 if !a.Equal(b) {
1225 t.Error("Bitsets are not equal:\n\t", a.DumpAsBits(), "\n\t", b.DumpAsBits())
1226 return
1227 }
1228 }
1229
1230 func copyBinary(t *testing.T, from encoding.BinaryMarshaler, to encoding.BinaryUnmarshaler) {
1231 data, err := from.MarshalBinary()
1232 if err != nil {
1233 t.Errorf(err.Error())
1234 return
1235 }
1236
1237 err = to.UnmarshalBinary(data)
1238 if err != nil {
1239 t.Errorf(err.Error())
1240 return
1241 }
1242 }
1243
1244 func TestMarshalUnmarshalJSON(t *testing.T) {
1245 a := New(1010).Set(10).Set(1001)
1246 data, err := json.Marshal(a)
1247 if err != nil {
1248 t.Errorf(err.Error())
1249 return
1250 }
1251
1252 b := new(BitSet)
1253 err = json.Unmarshal(data, b)
1254 if err != nil {
1255 t.Errorf(err.Error())
1256 return
1257 }
1258
1259
1260 if !a.Equal(b) {
1261 t.Error("Bitsets are not equal:\n\t", a.DumpAsBits(), "\n\t", b.DumpAsBits())
1262 return
1263 }
1264 }
1265
1266 func TestMarshalUnmarshalJSONByStdEncoding(t *testing.T) {
1267 Base64StdEncoding()
1268 a := New(1010).Set(10).Set(1001)
1269 data, err := json.Marshal(a)
1270 if err != nil {
1271 t.Errorf(err.Error())
1272 return
1273 }
1274
1275 b := new(BitSet)
1276 err = json.Unmarshal(data, b)
1277 if err != nil {
1278 t.Errorf(err.Error())
1279 return
1280 }
1281
1282
1283 if !a.Equal(b) {
1284 t.Error("Bitsets are not equal:\n\t", a.DumpAsBits(), "\n\t", b.DumpAsBits())
1285 return
1286 }
1287 }
1288
1289 func TestSafeSet(t *testing.T) {
1290 b := new(BitSet)
1291 c := b.safeSet()
1292 outType := fmt.Sprintf("%T", c)
1293 expType := "[]uint64"
1294 if outType != expType {
1295 t.Error("Expecting type: ", expType, ", gotf:", outType)
1296 return
1297 }
1298 if len(c) != 0 {
1299 t.Error("The slice should be empty")
1300 return
1301 }
1302 }
1303
1304 func TestFrom(t *testing.T) {
1305 u := []uint64{2, 3, 5, 7, 11}
1306 b := From(u)
1307 outType := fmt.Sprintf("%T", b)
1308 expType := "*bitset.BitSet"
1309 if outType != expType {
1310 t.Error("Expecting type: ", expType, ", gotf:", outType)
1311 return
1312 }
1313 }
1314
1315 func TestBytes(t *testing.T) {
1316 b := new(BitSet)
1317 c := b.Bytes()
1318 outType := fmt.Sprintf("%T", c)
1319 expType := "[]uint64"
1320 if outType != expType {
1321 t.Error("Expecting type: ", expType, ", gotf:", outType)
1322 return
1323 }
1324 if len(c) != 0 {
1325 t.Error("The slice should be empty")
1326 return
1327 }
1328 }
1329
1330 func TestCap(t *testing.T) {
1331 c := Cap()
1332 if c <= 0 {
1333 t.Error("The uint capacity should be >= 0")
1334 return
1335 }
1336 }
1337
1338 func TestWordsNeededLong(t *testing.T) {
1339 i := Cap()
1340 out := wordsNeeded(i)
1341 if out <= 0 {
1342 t.Error("Unexpected value: ", out)
1343 return
1344 }
1345 }
1346
1347 func TestTestTooLong(t *testing.T) {
1348 b := new(BitSet)
1349 if b.Test(1) {
1350 t.Error("Unexpected value: true")
1351 return
1352 }
1353 }
1354
1355 func TestClearTooLong(t *testing.T) {
1356 b := new(BitSet)
1357 c := b.Clear(1)
1358 if b != c {
1359 t.Error("Unexpected value")
1360 return
1361 }
1362 }
1363
1364 func TestClearAll(t *testing.T) {
1365 u := []uint64{2, 3, 5, 7, 11}
1366 b := From(u)
1367 c := b.ClearAll()
1368 if c.length != 320 {
1369 t.Error("Unexpected length: ", b.length)
1370 return
1371 }
1372 if c.Test(0) || c.Test(1) || c.Test(2) || c.Test(3) || c.Test(4) || c.Test(5) {
1373 t.Error("All bits should be unset")
1374 return
1375 }
1376 }
1377
1378 func TestFlip(t *testing.T) {
1379 b := new(BitSet)
1380 c := b.Flip(11)
1381 if c.length != 12 {
1382 t.Error("Unexpected value: ", c.length)
1383 return
1384 }
1385 d := c.Flip(7)
1386 if d.length != 12 {
1387 t.Error("Unexpected value: ", d.length)
1388 return
1389 }
1390 }
1391
1392 func TestFlipRange(t *testing.T) {
1393 b := new(BitSet)
1394 b.Set(1).Set(3).Set(5).Set(7).Set(9).Set(11).Set(13).Set(15)
1395 c := b.FlipRange(4, 25)
1396 if c.length != 25 {
1397 t.Error("Unexpected value: ", c.length)
1398 return
1399 }
1400 d := c.FlipRange(8, 24)
1401 if d.length != 25 {
1402 t.Error("Unexpected value: ", d.length)
1403 return
1404 }
1405 }
1406
1407 func TestCopy(t *testing.T) {
1408 a := New(10)
1409 if a.Copy(nil) != 0 {
1410 t.Error("No values should be copied")
1411 return
1412 }
1413 a = New(10)
1414 b := New(20)
1415 if a.Copy(b) != 10 {
1416 t.Error("Unexpected value")
1417 return
1418 }
1419 }
1420
1421 func TestNextSetError(t *testing.T) {
1422 b := new(BitSet)
1423 c, d := b.NextSet(1)
1424 if c != 0 || d {
1425 t.Error("Unexpected values")
1426 return
1427 }
1428 }
1429
1430 func TestDeleteWithBitStrings(t *testing.T) {
1431 type testCase struct {
1432 input []string
1433 deleteIdx uint
1434 expected []string
1435 }
1436
1437 testCases := []testCase{
1438 {
1439 input: []string{
1440 "1110000000000000000000000000000000000000000000000000000000000001",
1441 },
1442 deleteIdx: uint(63),
1443 expected: []string{
1444 "0110000000000000000000000000000000000000000000000000000000000001",
1445 },
1446 },
1447 {
1448 input: []string{
1449 "1000000000000000000000000000000000000000000000000000000000010101",
1450 },
1451 deleteIdx: uint(0),
1452 expected: []string{
1453 "0100000000000000000000000000000000000000000000000000000000001010",
1454 },
1455 },
1456 {
1457 input: []string{
1458 "0000000000000000000000000000000000000000000000000000000000111000",
1459 },
1460 deleteIdx: uint(4),
1461 expected: []string{
1462 "0000000000000000000000000000000000000000000000000000000000011000",
1463 },
1464 },
1465 {
1466 input: []string{
1467 "1000000000000000000000000000000000000000000000000000000000000001",
1468 "1010000000000000000000000000000000000000000000000000000000000001",
1469 },
1470 deleteIdx: uint(63),
1471 expected: []string{
1472 "1000000000000000000000000000000000000000000000000000000000000001",
1473 "0101000000000000000000000000000000000000000000000000000000000000",
1474 },
1475 },
1476 {
1477 input: []string{
1478 "1000000000000000000000000000000000000000000000000000000000000000",
1479 "1000000000000000000000000000000000000000000000000000000000000001",
1480 "1000000000000000000000000000000000000000000000000000000000000001",
1481 },
1482 deleteIdx: uint(64),
1483 expected: []string{
1484 "1000000000000000000000000000000000000000000000000000000000000000",
1485 "1100000000000000000000000000000000000000000000000000000000000000",
1486 "0100000000000000000000000000000000000000000000000000000000000000",
1487 },
1488 },
1489 {
1490 input: []string{
1491 "0000000000000000000000000000000000000000000000000000000000000001",
1492 "0000000000000000000000000000000000000000000000000000000000000001",
1493 "0000000000000000000000000000000000000000000000000000000000000001",
1494 "0000000000000000000000000000000000000000000000000000000000000001",
1495 "0000000000000000000000000000000000000000000000000000000000000001",
1496 },
1497 deleteIdx: uint(256),
1498 expected: []string{
1499 "0000000000000000000000000000000000000000000000000000000000000001",
1500 "0000000000000000000000000000000000000000000000000000000000000001",
1501 "0000000000000000000000000000000000000000000000000000000000000001",
1502 "0000000000000000000000000000000000000000000000000000000000000001",
1503 "0000000000000000000000000000000000000000000000000000000000000000",
1504 },
1505 },
1506 }
1507
1508 for _, tc := range testCases {
1509 var input []uint64
1510 for _, inputElement := range tc.input {
1511 parsed, _ := strconv.ParseUint(inputElement, 2, 64)
1512 input = append(input, parsed)
1513 }
1514
1515 var expected []uint64
1516 for _, expectedElement := range tc.expected {
1517 parsed, _ := strconv.ParseUint(expectedElement, 2, 64)
1518 expected = append(expected, parsed)
1519 }
1520
1521 b := From(input)
1522 b.DeleteAt(tc.deleteIdx)
1523 if len(b.set) != len(expected) {
1524 t.Errorf("Length of sets expected to be %d, but was %d", len(expected), len(b.set))
1525 return
1526 }
1527 for i := range b.set {
1528 if b.set[i] != expected[i] {
1529 t.Errorf("Unexpected output\nExpected: %b\nGot: %b", expected[i], b.set[i])
1530 return
1531 }
1532 }
1533 }
1534 }
1535
1536 func TestDeleteWithBitSetInstance(t *testing.T) {
1537 length := uint(256)
1538 bitSet := New(length)
1539
1540
1541 indexesToSet := []uint{0, 1, 126, 127, 128, 129, 170, 171, 200, 201, 202, 203, 255}
1542
1543
1544 deleteAt := uint(127)
1545
1546
1547 expectedToBeSet := []uint{0, 1, 126, 127, 128, 169, 170, 199, 200, 201, 202, 254}
1548
1549 expected := make(map[uint]struct{})
1550 for _, index := range expectedToBeSet {
1551 expected[index] = struct{}{}
1552 }
1553
1554 for _, index := range indexesToSet {
1555 bitSet.Set(index)
1556 }
1557
1558 bitSet.DeleteAt(deleteAt)
1559
1560 for i := uint(0); i < length; i++ {
1561 if _, ok := expected[i]; ok {
1562 if !bitSet.Test(i) {
1563 t.Errorf("Expected index %d to be set, but wasn't", i)
1564 }
1565 } else {
1566 if bitSet.Test(i) {
1567 t.Errorf("Expected index %d to not be set, but was", i)
1568 }
1569 }
1570
1571 }
1572 }
1573
View as plain text