1
2
3
4
5
6
7
8
9
10
11
12
13 package intsets
14
15
16
17
18
19
20
21
22
23
24
25
26 import (
27 "bytes"
28 "fmt"
29 "math/bits"
30 )
31
32
33
34
35
36
37
38
39 type Sparse struct {
40
41
42
43
44
45
46
47 root block
48 }
49
50 type word uintptr
51
52 const (
53 _m = ^word(0)
54 bitsPerWord = 8 << (_m>>8&1 + _m>>16&1 + _m>>32&1)
55 bitsPerBlock = 256
56 wordsPerBlock = bitsPerBlock / bitsPerWord
57 )
58
59
60 const (
61 MaxInt = int(^uint(0) >> 1)
62 MinInt = -MaxInt - 1
63 )
64
65
66 func popcount(x word) int {
67
68 if bitsPerWord == 32 {
69 return bits.OnesCount32(uint32(x))
70 } else {
71 return bits.OnesCount64(uint64(x))
72 }
73 }
74
75
76 func nlz(x word) int {
77
78 if bitsPerWord == 32 {
79 return bits.LeadingZeros32(uint32(x))
80 } else {
81 return bits.LeadingZeros64(uint64(x))
82 }
83 }
84
85
86 func ntz(x word) int {
87
88 if bitsPerWord == 32 {
89 return bits.TrailingZeros32(uint32(x))
90 } else {
91 return bits.TrailingZeros64(uint64(x))
92 }
93 }
94
95
96
97
98
99
100
101
102
103
104
105
106 type block struct {
107 offset int
108 bits [wordsPerBlock]word
109 next, prev *block
110 }
111
112
113
114 func wordMask(i uint) (w uint, mask word) {
115 w = i / bitsPerWord
116 mask = 1 << (i % bitsPerWord)
117 return
118 }
119
120
121
122 func (b *block) insert(i uint) bool {
123 w, mask := wordMask(i)
124 if b.bits[w]&mask == 0 {
125 b.bits[w] |= mask
126 return true
127 }
128 return false
129 }
130
131
132
133
134 func (b *block) remove(i uint) bool {
135 w, mask := wordMask(i)
136 if b.bits[w]&mask != 0 {
137 b.bits[w] &^= mask
138 return true
139 }
140 return false
141 }
142
143
144 func (b *block) has(i uint) bool {
145 w, mask := wordMask(i)
146 return b.bits[w]&mask != 0
147 }
148
149
150 func (b *block) empty() bool {
151 for _, w := range b.bits {
152 if w != 0 {
153 return false
154 }
155 }
156 return true
157 }
158
159
160 func (b *block) len() int {
161 var l int
162 for _, w := range b.bits {
163 l += popcount(w)
164 }
165 return l
166 }
167
168
169
170 func (b *block) max() int {
171 bi := b.offset + bitsPerBlock
172
173 for i := len(b.bits) - 1; i >= 0; i-- {
174 if w := b.bits[i]; w != 0 {
175 return bi - nlz(w) - 1
176 }
177 bi -= bitsPerWord
178 }
179 panic("BUG: empty block")
180 }
181
182
183
184
185
186 func (b *block) min(take bool) int {
187 for i, w := range b.bits {
188 if w != 0 {
189 tz := ntz(w)
190 if take {
191 b.bits[i] = w &^ (1 << uint(tz))
192 }
193 return b.offset + i*bitsPerWord + tz
194 }
195 }
196 panic("BUG: empty block")
197 }
198
199
200
201
202 func (b *block) lowerBound(i uint) (int, bool) {
203 w := i / bitsPerWord
204 bit := i % bitsPerWord
205
206 if val := b.bits[w] >> bit; val != 0 {
207 return b.offset + int(i) + ntz(val), true
208 }
209
210 for w++; w < wordsPerBlock; w++ {
211 if val := b.bits[w]; val != 0 {
212 return b.offset + int(w*bitsPerWord) + ntz(val), true
213 }
214 }
215
216 return 0, false
217 }
218
219
220
221 func (b *block) forEach(f func(int)) {
222 for i, w := range b.bits {
223 offset := b.offset + i*bitsPerWord
224 for bi := 0; w != 0 && bi < bitsPerWord; bi++ {
225 if w&1 != 0 {
226 f(offset)
227 }
228 offset++
229 w >>= 1
230 }
231 }
232 }
233
234
235
236 func offsetAndBitIndex(x int) (int, uint) {
237 mod := x % bitsPerBlock
238 if mod < 0 {
239
240 mod += bitsPerBlock
241 }
242 return x - mod, uint(mod)
243 }
244
245
246
247
248
249 var none block
250
251
252
253
254 type to_copy_a_sparse_you_must_call_its_Copy_method struct{}
255
256
257 func (s *Sparse) init() {
258 root := &s.root
259 if root.next == nil {
260 root.offset = MaxInt
261 root.next = root
262 root.prev = root
263 } else if root.next.prev != root {
264
265
266
267
268
269
270 _ = (interface{}(nil)).(to_copy_a_sparse_you_must_call_its_Copy_method)
271 }
272 }
273
274 func (s *Sparse) first() *block {
275 s.init()
276 if s.root.offset == MaxInt {
277 return &none
278 }
279 return &s.root
280 }
281
282
283 func (s *Sparse) next(b *block) *block {
284 if b.next == &s.root {
285 return &none
286 }
287 return b.next
288 }
289
290
291 func (s *Sparse) prev(b *block) *block {
292 if b.prev == &s.root {
293 return &none
294 }
295 return b.prev
296 }
297
298
299 func (s *Sparse) IsEmpty() bool {
300 return s.root.next == nil || s.root.offset == MaxInt
301 }
302
303
304 func (s *Sparse) Len() int {
305 var l int
306 for b := s.first(); b != &none; b = s.next(b) {
307 l += b.len()
308 }
309 return l
310 }
311
312
313 func (s *Sparse) Max() int {
314 if s.IsEmpty() {
315 return MinInt
316 }
317 return s.root.prev.max()
318 }
319
320
321 func (s *Sparse) Min() int {
322 if s.IsEmpty() {
323 return MaxInt
324 }
325 return s.root.min(false)
326 }
327
328
329
330 func (s *Sparse) LowerBound(x int) int {
331 offset, i := offsetAndBitIndex(x)
332 for b := s.first(); b != &none; b = s.next(b) {
333 if b.offset > offset {
334 return b.min(false)
335 }
336 if b.offset == offset {
337 if y, ok := b.lowerBound(i); ok {
338 return y
339 }
340 }
341 }
342 return MaxInt
343 }
344
345
346
347
348 func (s *Sparse) block(offset int) *block {
349 for b := s.first(); b != &none && b.offset <= offset; b = s.next(b) {
350 if b.offset == offset {
351 return b
352 }
353 }
354 return nil
355 }
356
357
358 func (s *Sparse) Insert(x int) bool {
359 offset, i := offsetAndBitIndex(x)
360
361 b := s.first()
362 for ; b != &none && b.offset <= offset; b = s.next(b) {
363 if b.offset == offset {
364 return b.insert(i)
365 }
366 }
367
368
369 new := s.insertBlockBefore(b)
370 new.offset = offset
371 return new.insert(i)
372 }
373
374
375
376 func (s *Sparse) removeBlock(b *block) *block {
377 if b != &s.root {
378 b.prev.next = b.next
379 b.next.prev = b.prev
380 if b.next == &s.root {
381 return &none
382 }
383 return b.next
384 }
385
386 first := s.root.next
387 if first == &s.root {
388
389 s.Clear()
390 return &none
391 }
392 s.root.offset = first.offset
393 s.root.bits = first.bits
394 if first.next == &s.root {
395
396 s.root.next = &s.root
397 s.root.prev = &s.root
398 } else {
399 s.root.next = first.next
400 first.next.prev = &s.root
401 }
402 return &s.root
403 }
404
405
406 func (s *Sparse) Remove(x int) bool {
407 offset, i := offsetAndBitIndex(x)
408 if b := s.block(offset); b != nil {
409 if !b.remove(i) {
410 return false
411 }
412 if b.empty() {
413 s.removeBlock(b)
414 }
415 return true
416 }
417 return false
418 }
419
420
421 func (s *Sparse) Clear() {
422 s.root = block{
423 offset: MaxInt,
424 next: &s.root,
425 prev: &s.root,
426 }
427 }
428
429
430
431
432
433
434
435
436
437 func (s *Sparse) TakeMin(p *int) bool {
438 if s.IsEmpty() {
439 return false
440 }
441 *p = s.root.min(true)
442 if s.root.empty() {
443 s.removeBlock(&s.root)
444 }
445 return true
446 }
447
448
449 func (s *Sparse) Has(x int) bool {
450 offset, i := offsetAndBitIndex(x)
451 if b := s.block(offset); b != nil {
452 return b.has(i)
453 }
454 return false
455 }
456
457
458
459
460
461
462 func (s *Sparse) forEach(f func(int)) {
463 for b := s.first(); b != &none; b = s.next(b) {
464 b.forEach(f)
465 }
466 }
467
468
469 func (s *Sparse) Copy(x *Sparse) {
470 if s == x {
471 return
472 }
473
474 xb := x.first()
475 sb := s.first()
476 for xb != &none {
477 if sb == &none {
478 sb = s.insertBlockBefore(sb)
479 }
480 sb.offset = xb.offset
481 sb.bits = xb.bits
482 xb = x.next(xb)
483 sb = s.next(sb)
484 }
485 s.discardTail(sb)
486 }
487
488
489
490
491 func (s *Sparse) insertBlockBefore(next *block) *block {
492 if s.IsEmpty() {
493 if next != &none {
494 panic("BUG: passed block with empty set")
495 }
496 return &s.root
497 }
498
499 if next == &s.root {
500
501
502 second := s.root
503 s.root = block{
504 next: &second,
505 }
506 if second.next == &s.root {
507 s.root.prev = &second
508 } else {
509 s.root.prev = second.prev
510 second.next.prev = &second
511 second.prev = &s.root
512 }
513 return &s.root
514 }
515 if next == &none {
516
517 next = &s.root
518 }
519 b := new(block)
520 b.next = next
521 b.prev = next.prev
522 b.prev.next = b
523 next.prev = b
524 return b
525 }
526
527
528 func (s *Sparse) discardTail(b *block) {
529 if b != &none {
530 if b == &s.root {
531 s.Clear()
532 } else {
533 b.prev.next = &s.root
534 s.root.prev = b.prev
535 }
536 }
537 }
538
539
540 func (s *Sparse) IntersectionWith(x *Sparse) {
541 if s == x {
542 return
543 }
544
545 xb := x.first()
546 sb := s.first()
547 for xb != &none && sb != &none {
548 switch {
549 case xb.offset < sb.offset:
550 xb = x.next(xb)
551
552 case xb.offset > sb.offset:
553 sb = s.removeBlock(sb)
554
555 default:
556 var sum word
557 for i := range sb.bits {
558 r := xb.bits[i] & sb.bits[i]
559 sb.bits[i] = r
560 sum |= r
561 }
562 if sum != 0 {
563 sb = s.next(sb)
564 } else {
565
566 }
567
568 xb = x.next(xb)
569 }
570 }
571
572 s.discardTail(sb)
573 }
574
575
576 func (s *Sparse) Intersection(x, y *Sparse) {
577 switch {
578 case s == x:
579 s.IntersectionWith(y)
580 return
581 case s == y:
582 s.IntersectionWith(x)
583 return
584 case x == y:
585 s.Copy(x)
586 return
587 }
588
589 xb := x.first()
590 yb := y.first()
591 sb := s.first()
592 for xb != &none && yb != &none {
593 switch {
594 case xb.offset < yb.offset:
595 xb = x.next(xb)
596 continue
597 case xb.offset > yb.offset:
598 yb = y.next(yb)
599 continue
600 }
601
602 if sb == &none {
603 sb = s.insertBlockBefore(sb)
604 }
605 sb.offset = xb.offset
606
607 var sum word
608 for i := range sb.bits {
609 r := xb.bits[i] & yb.bits[i]
610 sb.bits[i] = r
611 sum |= r
612 }
613 if sum != 0 {
614 sb = s.next(sb)
615 } else {
616
617 }
618
619 xb = x.next(xb)
620 yb = y.next(yb)
621 }
622
623 s.discardTail(sb)
624 }
625
626
627 func (s *Sparse) Intersects(x *Sparse) bool {
628 sb := s.first()
629 xb := x.first()
630 for sb != &none && xb != &none {
631 switch {
632 case xb.offset < sb.offset:
633 xb = x.next(xb)
634 case xb.offset > sb.offset:
635 sb = s.next(sb)
636 default:
637 for i := range sb.bits {
638 if sb.bits[i]&xb.bits[i] != 0 {
639 return true
640 }
641 }
642 sb = s.next(sb)
643 xb = x.next(xb)
644 }
645 }
646 return false
647 }
648
649
650 func (s *Sparse) UnionWith(x *Sparse) bool {
651 if s == x {
652 return false
653 }
654
655 var changed bool
656 xb := x.first()
657 sb := s.first()
658 for xb != &none {
659 if sb != &none && sb.offset == xb.offset {
660 for i := range xb.bits {
661 union := sb.bits[i] | xb.bits[i]
662 if sb.bits[i] != union {
663 sb.bits[i] = union
664 changed = true
665 }
666 }
667 xb = x.next(xb)
668 } else if sb == &none || sb.offset > xb.offset {
669 sb = s.insertBlockBefore(sb)
670 sb.offset = xb.offset
671 sb.bits = xb.bits
672 changed = true
673
674 xb = x.next(xb)
675 }
676 sb = s.next(sb)
677 }
678 return changed
679 }
680
681
682 func (s *Sparse) Union(x, y *Sparse) {
683 switch {
684 case x == y:
685 s.Copy(x)
686 return
687 case s == x:
688 s.UnionWith(y)
689 return
690 case s == y:
691 s.UnionWith(x)
692 return
693 }
694
695 xb := x.first()
696 yb := y.first()
697 sb := s.first()
698 for xb != &none || yb != &none {
699 if sb == &none {
700 sb = s.insertBlockBefore(sb)
701 }
702 switch {
703 case yb == &none || (xb != &none && xb.offset < yb.offset):
704 sb.offset = xb.offset
705 sb.bits = xb.bits
706 xb = x.next(xb)
707
708 case xb == &none || (yb != &none && yb.offset < xb.offset):
709 sb.offset = yb.offset
710 sb.bits = yb.bits
711 yb = y.next(yb)
712
713 default:
714 sb.offset = xb.offset
715 for i := range xb.bits {
716 sb.bits[i] = xb.bits[i] | yb.bits[i]
717 }
718 xb = x.next(xb)
719 yb = y.next(yb)
720 }
721 sb = s.next(sb)
722 }
723
724 s.discardTail(sb)
725 }
726
727
728 func (s *Sparse) DifferenceWith(x *Sparse) {
729 if s == x {
730 s.Clear()
731 return
732 }
733
734 xb := x.first()
735 sb := s.first()
736 for xb != &none && sb != &none {
737 switch {
738 case xb.offset > sb.offset:
739 sb = s.next(sb)
740
741 case xb.offset < sb.offset:
742 xb = x.next(xb)
743
744 default:
745 var sum word
746 for i := range sb.bits {
747 r := sb.bits[i] & ^xb.bits[i]
748 sb.bits[i] = r
749 sum |= r
750 }
751 if sum == 0 {
752 sb = s.removeBlock(sb)
753 } else {
754 sb = s.next(sb)
755 }
756 xb = x.next(xb)
757 }
758 }
759 }
760
761
762 func (s *Sparse) Difference(x, y *Sparse) {
763 switch {
764 case x == y:
765 s.Clear()
766 return
767 case s == x:
768 s.DifferenceWith(y)
769 return
770 case s == y:
771 var y2 Sparse
772 y2.Copy(y)
773 s.Difference(x, &y2)
774 return
775 }
776
777 xb := x.first()
778 yb := y.first()
779 sb := s.first()
780 for xb != &none && yb != &none {
781 if xb.offset > yb.offset {
782
783 yb = y.next(yb)
784 continue
785 }
786
787 if sb == &none {
788 sb = s.insertBlockBefore(sb)
789 }
790 sb.offset = xb.offset
791
792 switch {
793 case xb.offset < yb.offset:
794
795 sb.bits = xb.bits
796
797 sb = s.next(sb)
798
799 default:
800
801 var sum word
802 for i := range sb.bits {
803 r := xb.bits[i] & ^yb.bits[i]
804 sb.bits[i] = r
805 sum |= r
806 }
807 if sum != 0 {
808 sb = s.next(sb)
809 } else {
810
811 }
812
813 yb = y.next(yb)
814 }
815 xb = x.next(xb)
816 }
817
818 for xb != &none {
819 if sb == &none {
820 sb = s.insertBlockBefore(sb)
821 }
822 sb.offset = xb.offset
823 sb.bits = xb.bits
824 sb = s.next(sb)
825
826 xb = x.next(xb)
827 }
828
829 s.discardTail(sb)
830 }
831
832
833 func (s *Sparse) SymmetricDifferenceWith(x *Sparse) {
834 if s == x {
835 s.Clear()
836 return
837 }
838
839 sb := s.first()
840 xb := x.first()
841 for xb != &none && sb != &none {
842 switch {
843 case sb.offset < xb.offset:
844 sb = s.next(sb)
845 case xb.offset < sb.offset:
846 nb := s.insertBlockBefore(sb)
847 nb.offset = xb.offset
848 nb.bits = xb.bits
849 xb = x.next(xb)
850 default:
851 var sum word
852 for i := range sb.bits {
853 r := sb.bits[i] ^ xb.bits[i]
854 sb.bits[i] = r
855 sum |= r
856 }
857 if sum == 0 {
858 sb = s.removeBlock(sb)
859 } else {
860 sb = s.next(sb)
861 }
862 xb = x.next(xb)
863 }
864 }
865
866 for xb != &none {
867 sb = s.insertBlockBefore(sb)
868 sb.offset = xb.offset
869 sb.bits = xb.bits
870 sb = s.next(sb)
871 xb = x.next(xb)
872 }
873 }
874
875
876 func (s *Sparse) SymmetricDifference(x, y *Sparse) {
877 switch {
878 case x == y:
879 s.Clear()
880 return
881 case s == x:
882 s.SymmetricDifferenceWith(y)
883 return
884 case s == y:
885 s.SymmetricDifferenceWith(x)
886 return
887 }
888
889 sb := s.first()
890 xb := x.first()
891 yb := y.first()
892 for xb != &none && yb != &none {
893 if sb == &none {
894 sb = s.insertBlockBefore(sb)
895 }
896 switch {
897 case yb.offset < xb.offset:
898 sb.offset = yb.offset
899 sb.bits = yb.bits
900 sb = s.next(sb)
901 yb = y.next(yb)
902 case xb.offset < yb.offset:
903 sb.offset = xb.offset
904 sb.bits = xb.bits
905 sb = s.next(sb)
906 xb = x.next(xb)
907 default:
908 var sum word
909 for i := range sb.bits {
910 r := xb.bits[i] ^ yb.bits[i]
911 sb.bits[i] = r
912 sum |= r
913 }
914 if sum != 0 {
915 sb.offset = xb.offset
916 sb = s.next(sb)
917 }
918 xb = x.next(xb)
919 yb = y.next(yb)
920 }
921 }
922
923 for xb != &none {
924 if sb == &none {
925 sb = s.insertBlockBefore(sb)
926 }
927 sb.offset = xb.offset
928 sb.bits = xb.bits
929 sb = s.next(sb)
930 xb = x.next(xb)
931 }
932
933 for yb != &none {
934 if sb == &none {
935 sb = s.insertBlockBefore(sb)
936 }
937 sb.offset = yb.offset
938 sb.bits = yb.bits
939 sb = s.next(sb)
940 yb = y.next(yb)
941 }
942
943 s.discardTail(sb)
944 }
945
946
947 func (s *Sparse) SubsetOf(x *Sparse) bool {
948 if s == x {
949 return true
950 }
951
952 sb := s.first()
953 xb := x.first()
954 for sb != &none {
955 switch {
956 case xb == &none || xb.offset > sb.offset:
957 return false
958 case xb.offset < sb.offset:
959 xb = x.next(xb)
960 default:
961 for i := range sb.bits {
962 if sb.bits[i]&^xb.bits[i] != 0 {
963 return false
964 }
965 }
966 sb = s.next(sb)
967 xb = x.next(xb)
968 }
969 }
970 return true
971 }
972
973
974 func (s *Sparse) Equals(t *Sparse) bool {
975 if s == t {
976 return true
977 }
978 sb := s.first()
979 tb := t.first()
980 for {
981 switch {
982 case sb == &none && tb == &none:
983 return true
984 case sb == &none || tb == &none:
985 return false
986 case sb.offset != tb.offset:
987 return false
988 case sb.bits != tb.bits:
989 return false
990 }
991
992 sb = s.next(sb)
993 tb = t.next(tb)
994 }
995 }
996
997
998 func (s *Sparse) String() string {
999 var buf bytes.Buffer
1000 buf.WriteByte('{')
1001 s.forEach(func(x int) {
1002 if buf.Len() > 1 {
1003 buf.WriteByte(' ')
1004 }
1005 fmt.Fprintf(&buf, "%d", x)
1006 })
1007 buf.WriteByte('}')
1008 return buf.String()
1009 }
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021 func (s *Sparse) BitString() string {
1022 if s.IsEmpty() {
1023 return "0"
1024 }
1025
1026 min, max := s.Min(), s.Max()
1027 var nbytes int
1028 if max > 0 {
1029 nbytes = max
1030 }
1031 nbytes++
1032 radix := nbytes
1033 if min < 0 {
1034 nbytes += len(".") - min
1035 }
1036
1037 b := make([]byte, nbytes)
1038 for i := range b {
1039 b[i] = '0'
1040 }
1041 if radix < nbytes {
1042 b[radix] = '.'
1043 }
1044 s.forEach(func(x int) {
1045 if x >= 0 {
1046 x += len(".")
1047 }
1048 b[radix-x] = '1'
1049 })
1050 return string(b)
1051 }
1052
1053
1054
1055 func (s *Sparse) GoString() string {
1056 var buf bytes.Buffer
1057 for b := s.first(); b != &none; b = s.next(b) {
1058 fmt.Fprintf(&buf, "block %p {offset=%d next=%p prev=%p",
1059 b, b.offset, b.next, b.prev)
1060 for _, w := range b.bits {
1061 fmt.Fprintf(&buf, " 0%016x", w)
1062 }
1063 fmt.Fprintf(&buf, "}\n")
1064 }
1065 return buf.String()
1066 }
1067
1068
1069
1070 func (s *Sparse) AppendTo(slice []int) []int {
1071 s.forEach(func(x int) {
1072 slice = append(slice, x)
1073 })
1074 return slice
1075 }
1076
1077
1078
1079
1080 func (s *Sparse) check() error {
1081 s.init()
1082 if s.root.empty() {
1083
1084 if s.root.next != &s.root {
1085 return fmt.Errorf("multiple blocks with empty root block")
1086 }
1087 if s.root.offset != MaxInt {
1088 return fmt.Errorf("empty set has offset %d, should be MaxInt", s.root.offset)
1089 }
1090 return nil
1091 }
1092 for b := s.first(); ; b = s.next(b) {
1093 if b.offset%bitsPerBlock != 0 {
1094 return fmt.Errorf("bad offset modulo: %d", b.offset)
1095 }
1096 if b.empty() {
1097 return fmt.Errorf("empty block")
1098 }
1099 if b.prev.next != b {
1100 return fmt.Errorf("bad prev.next link")
1101 }
1102 if b.next.prev != b {
1103 return fmt.Errorf("bad next.prev link")
1104 }
1105 if b.next == &s.root {
1106 break
1107 }
1108 if b.offset >= b.next.offset {
1109 return fmt.Errorf("bad offset order: b.offset=%d, b.next.offset=%d",
1110 b.offset, b.next.offset)
1111 }
1112 }
1113 return nil
1114 }
1115
View as plain text