bitset.gno

  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/moul/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}