1// Package bitset is a dense, fixed-capacity bit vector as a pure, reusable2// package: a compact set of small non-negative integers with the usual3// set algebra (union, intersection, difference).4//5// Storage is a []uint64 of ceil(n/64) words, so 1024 bits cost 16 words rather6// than 1024 booleans — the reason to reach for this on chain, where every byte7// is paid for.8//9// Capacity is fixed at construction and every operation is bounds-checked10// rather than growing: an out-of-range index is a caller bug, and silently11// growing would make gas unpredictable.12//13// A live demo of this package is at14// [r/moul/x/daily/bitsetdemo](/r/moul/x/daily/bitsetdemo/v0).15package bitset1617import "strings"1819// MaxBits bounds a BitSet so allocation and iteration stay predictable.20const MaxBits = 1 << 16 // 65536 bits = 1024 words = 8 KiB2122// BitSet is a fixed-capacity set of integers in [0, n).23type BitSet struct {24 n int25 words []uint6426}2728// 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 = 032 }33 if n > MaxBits {34 n = MaxBits35 }36 return &BitSet{n: n, words: make([]uint64, (n+63)/64)}37}3839// Cap returns the capacity in bits.40func (b *BitSet) Cap() int { return b.n }4142// InRange reports whether i is a valid index.43func (b *BitSet) InRange(i int) bool { return i >= 0 && i < b.n }4445// 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 false49 }50 b.words[i/64] |= 1 << uint(i%64)51 return true52}5354// 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 false58 }59 b.words[i/64] &^= 1 << uint(i%64)60 return true61}6263// 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 false67 }68 b.words[i/64] ^= 1 << uint(i%64)69 return true70}7172// 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 false77 }78 return b.words[i/64]&(1<<uint(i%64)) != 079}8081// Count returns the number of set bits (popcount).82func (b *BitSet) Count() int {83 total := 084 for _, w := range b.words {85 total += popcount(w)86 }87 return total88}8990// popcount counts set bits with the classic SWAR trick — no math/bits on gno.91func popcount(x uint64) int {92 n := 093 for x != 0 {94 x &= x - 1 // clear the lowest set bit95 n++96 }97 return n98}99100// 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 out109}110111// Clone returns an independent copy.112func (b *BitSet) Clone() *BitSet {113 c := New(b.n)114 copy(c.words, b.words)115 return c116}117118// 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 }120121// Union returns a ∪ b, or nil when the capacities differ. Mismatched capacities122// are a caller error rather than something to silently pad.123func Union(a, b *BitSet) *BitSet { return combine(a, b, "or") }124125// Intersect returns a ∩ b, or nil when the capacities differ.126func Intersect(a, b *BitSet) *BitSet { return combine(a, b, "and") }127128// Difference returns a \ b, or nil when the capacities differ.129func Difference(a, b *BitSet) *BitSet { return combine(a, b, "andnot") }130131// SymmetricDifference returns a △ b, or nil when the capacities differ.132func SymmetricDifference(a, b *BitSet) *BitSet { return combine(a, b, "xor") }133134func combine(a, b *BitSet, op string) *BitSet {135 if !sameCap(a, b) {136 return nil137 }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 out152}153154// 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 false158 }159 for i := range a.words {160 if a.words[i] != b.words[i] {161 return false162 }163 }164 return true165}166167// String renders the set as '0'/'1' from bit 0 upward, which reads left-to-right168// in index order (note this is the reverse of binary notation).169func (b *BitSet) String() string {170 var sb strings.Builder171 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}180181// 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 b189}190Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.