bitset.gno
4.71 Kb · 189 lines
1// Package bitset is a dense, fixed-capacity bit vector as a pure, reusable
2// package: a compact set of small non-negative integers with the usual
3// set algebra (union, intersection, difference).
4//
5// Storage is a []uint64 of ceil(n/64) words, so 1024 bits cost 16 words rather
6// than 1024 booleans — the reason to reach for this on chain, where every byte
7// is paid for.
8//
9// Capacity is fixed at construction and every operation is bounds-checked
10// rather than growing: an out-of-range index is a caller bug, and silently
11// growing would make gas unpredictable.
12//
13// A live demo of this package is at
14// [r/moul/x/daily/bitsetdemo](/r/nym-moultest123/x/daily/bitsetdemo/v0).
15package bitset
16
17import "strings"
18
19// MaxBits bounds a BitSet so allocation and iteration stay predictable.
20const MaxBits = 1 << 16 // 65536 bits = 1024 words = 8 KiB
21
22// BitSet is a fixed-capacity set of integers in [0, n).
23type BitSet struct {
24 n int
25 words []uint64
26}
27
28// New returns a BitSet holding bits [0, n). n is clamped to [0, MaxBits].
29func New(n int) *BitSet {
30 if n < 0 {
31 n = 0
32 }
33 if n > MaxBits {
34 n = MaxBits
35 }
36 return &BitSet{n: n, words: make([]uint64, (n+63)/64)}
37}
38
39// Cap returns the capacity in bits.
40func (b *BitSet) Cap() int { return b.n }
41
42// InRange reports whether i is a valid index.
43func (b *BitSet) InRange(i int) bool { return i >= 0 && i < b.n }
44
45// Set turns bit i on and reports whether i was in range.
46func (b *BitSet) Set(i int) bool {
47 if !b.InRange(i) {
48 return false
49 }
50 b.words[i/64] |= 1 << uint(i%64)
51 return true
52}
53
54// Clear turns bit i off and reports whether i was in range.
55func (b *BitSet) Clear(i int) bool {
56 if !b.InRange(i) {
57 return false
58 }
59 b.words[i/64] &^= 1 << uint(i%64)
60 return true
61}
62
63// Flip inverts bit i and reports whether i was in range.
64func (b *BitSet) Flip(i int) bool {
65 if !b.InRange(i) {
66 return false
67 }
68 b.words[i/64] ^= 1 << uint(i%64)
69 return true
70}
71
72// Has reports whether bit i is set. Out of range is false, never a panic:
73// membership of something that cannot be a member is simply false.
74func (b *BitSet) Has(i int) bool {
75 if !b.InRange(i) {
76 return false
77 }
78 return b.words[i/64]&(1<<uint(i%64)) != 0
79}
80
81// Count returns the number of set bits (popcount).
82func (b *BitSet) Count() int {
83 total := 0
84 for _, w := range b.words {
85 total += popcount(w)
86 }
87 return total
88}
89
90// popcount counts set bits with the classic SWAR trick — no math/bits on gno.
91func popcount(x uint64) int {
92 n := 0
93 for x != 0 {
94 x &= x - 1 // clear the lowest set bit
95 n++
96 }
97 return n
98}
99
100// Slice returns the set bits in ascending order.
101func (b *BitSet) Slice() []int {
102 out := []int{}
103 for i := 0; i < b.n; i++ {
104 if b.Has(i) {
105 out = append(out, i)
106 }
107 }
108 return out
109}
110
111// Clone returns an independent copy.
112func (b *BitSet) Clone() *BitSet {
113 c := New(b.n)
114 copy(c.words, b.words)
115 return c
116}
117
118// sameCap reports whether two sets can be combined word-wise.
119func sameCap(a, b *BitSet) bool { return a != nil && b != nil && a.n == b.n }
120
121// Union returns a ∪ b, or nil when the capacities differ. Mismatched capacities
122// are a caller error rather than something to silently pad.
123func Union(a, b *BitSet) *BitSet { return combine(a, b, "or") }
124
125// Intersect returns a ∩ b, or nil when the capacities differ.
126func Intersect(a, b *BitSet) *BitSet { return combine(a, b, "and") }
127
128// Difference returns a \ b, or nil when the capacities differ.
129func Difference(a, b *BitSet) *BitSet { return combine(a, b, "andnot") }
130
131// SymmetricDifference returns a △ b, or nil when the capacities differ.
132func SymmetricDifference(a, b *BitSet) *BitSet { return combine(a, b, "xor") }
133
134func combine(a, b *BitSet, op string) *BitSet {
135 if !sameCap(a, b) {
136 return nil
137 }
138 out := New(a.n)
139 for i := range a.words {
140 switch op {
141 case "or":
142 out.words[i] = a.words[i] | b.words[i]
143 case "and":
144 out.words[i] = a.words[i] & b.words[i]
145 case "andnot":
146 out.words[i] = a.words[i] &^ b.words[i]
147 case "xor":
148 out.words[i] = a.words[i] ^ b.words[i]
149 }
150 }
151 return out
152}
153
154// Equal reports whether two sets have the same capacity and the same bits.
155func Equal(a, b *BitSet) bool {
156 if !sameCap(a, b) {
157 return false
158 }
159 for i := range a.words {
160 if a.words[i] != b.words[i] {
161 return false
162 }
163 }
164 return true
165}
166
167// String renders the set as '0'/'1' from bit 0 upward, which reads left-to-right
168// in index order (note this is the reverse of binary notation).
169func (b *BitSet) String() string {
170 var sb strings.Builder
171 for i := 0; i < b.n; i++ {
172 if b.Has(i) {
173 sb.WriteByte('1')
174 } else {
175 sb.WriteByte('0')
176 }
177 }
178 return sb.String()
179}
180
181// FromSlice builds a BitSet of capacity n containing the given indices.
182// Out-of-range indices are ignored.
183func FromSlice(n int, idx []int) *BitSet {
184 b := New(n)
185 for _, i := range idx {
186 b.Set(i)
187 }
188 return b
189}
