ref: 37382a5df854971f64bf07f9c6a7c94f2e7d058e
dir: /lib/std/bitset.myr/
use "alloc.use" use "die.use" use "extremum.use" use "mk.use" use "slcp.use" use "sldup.use" use "slfill.use" use "types.use" pkg std = type bitset = struct bits : size[:] ;; const mkbs : (-> bitset#) const bsdup : (bs : bitset# -> bitset#) const bsfree : (bs : bitset# -> void) const bsmax : (a : bitset# -> size) generic bsput : (bs : bitset#, v : @a::(integral,numeric) -> void) generic bsdel : (bs : bitset#, v : @a::(integral,numeric) -> void) generic bshas : (bs : bitset#, v : @a::(integral,numeric) -> bool) const bsdiff : (a : bitset#, b : bitset# -> void) const bsintersect : (a : bitset#, b : bitset# -> void) const bsunion : (a : bitset#, b : bitset# -> void) const bseq : (a : bitset#, b : bitset# -> bool) const bsissubset : (a : bitset#, b : bitset# -> bool) const bsclear : (bs : bitset# -> bitset#) ;; const mkbs = { -> zalloc() } const bsdup = {bs -> mk([.bits=sldup(bs.bits)]) } const bsfree = {bs slfree(bs.bits) free(bs) } const bsclear = {bs slfill(bs.bits, 0) -> bs } const bsmax = {bs -> bs.bits.len * sizeof(size) * 8 } generic bsput = {bs, v var idx var off idx = (v castto(size)) / (8*sizeof(size)) off = (v castto(size)) % (8*sizeof(size)) ensurelen(bs, idx) bs.bits[idx] |= (1 << off) } generic bsdel = {bs, v var idx var off idx = (v castto(size)) / (8*sizeof(size)) off = (v castto(size)) % (8*sizeof(size)) if idx >= bs.bits.len -> ;; bs.bits[idx] &= ~(1 << off) } generic bshas = {bs, v var idx var off idx = (v castto(size)) / (8*sizeof(size)) off = (v castto(size)) % (8*sizeof(size)) if idx >= bs.bits.len -> false ;; -> (bs.bits[idx] & (1 << off)) != 0 } const bsunion = {a, b var i eqsz(a, b) for i = 0; i < b.bits.len; i++ a.bits[i] |= b.bits[i] ;; } const bsintersect = {a, b var i, n n = min(a.bits.len, b.bits.len) for i = 0; i < n; i++ a.bits[i] &= b.bits[i] ;; } const bsdiff = {a, b var i, n n = min(b.bits.len, a.bits.len) for i = 0; i < n; i++ a.bits[i] &= ~b.bits[i] ;; } const bsissubset = {a, b var i eqsz(a, b); for i = 0; i < a.bits.len; i++ if (b.bits[i] & a.bits[i]) != b.bits[i] -> false ;; ;; -> true } const bseq = {a, b var i eqsz(a, b) for i = 0; i < a.bits.len; i++ if a.bits[i] != b.bits[i] -> false ;; ;; -> true } const ensurelen = {bs, len if bs.bits.len <= len bs.bits = slzgrow(bs.bits, len + 1) ;; } const eqsz = {a, b var sz sz = max(a.bits.len, b.bits.len) ensurelen(a, sz) ensurelen(b, sz) }