diff options
Diffstat (limited to 'lib/std/bitset.myr')
-rw-r--r-- | lib/std/bitset.myr | 155 |
1 files changed, 155 insertions, 0 deletions
diff --git a/lib/std/bitset.myr b/lib/std/bitset.myr new file mode 100644 index 0000000..7843c7d --- /dev/null +++ b/lib/std/bitset.myr @@ -0,0 +1,155 @@ +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) +} + |