summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2016-10-22 22:52:56 -0700
committerOri Bernstein <ori@eigenstate.org>2016-10-22 22:52:56 -0700
commit52ec5d6f05690494ee1a43452a0305ea697f0165 (patch)
tree552f7e495841e97088d22bcc9bdf1c34f212c57c
parentcb2a50f6b3ada53a03cd211c79f920979edc0a25 (diff)
downloadmc-52ec5d6f05690494ee1a43452a0305ea697f0165.tar.gz
Add bitset counting.
Now we can know how many items are in a bitset.
-rw-r--r--lib/std/bitset.myr15
-rw-r--r--lib/std/test/bitset.myr32
2 files changed, 32 insertions, 15 deletions
diff --git a/lib/std/bitset.myr b/lib/std/bitset.myr
index d914c67..5aa160d 100644
--- a/lib/std/bitset.myr
+++ b/lib/std/bitset.myr
@@ -18,6 +18,7 @@ pkg std =
const bsclear : (bs : bitset# -> bitset#)
const bsmax : (a : bitset# -> size)
+ const bscount : (a : bitset# -> size)
generic bsput : (bs : bitset#, v : @a::(integral,numeric) -> bool)
generic bsdel : (bs : bitset#, v : @a::(integral,numeric) -> bool)
@@ -60,6 +61,16 @@ const bsmax = {bs
-> bs.bits.len * sizeof(size) * 8
}
+const bscount = {bs
+ var n
+
+ n = 0
+ for v in bybsvalue(bs)
+ n++
+ ;;
+ -> n
+}
+
generic bsput = {bs, v
var idx, off, changed
@@ -166,14 +177,16 @@ impl iterable bsiter -> size =
var n = bsmax(bs)
for var i = itp.idx; i < n; i++
/* fast forward by whole chunks */
- while i < n && bs.bits[i >> 8*sizeof(size)] != 0
+ while i < n && bs.bits[i / (8*sizeof(size))] == 0
i = (i + 8*sizeof(size)) & ~(8*sizeof(size) - 1)
;;
if bshas(bs, i)
+ itp.idx = i + 1
valp# = i
-> true
;;
;;
+ itp.idx = n
-> false
}
diff --git a/lib/std/test/bitset.myr b/lib/std/test/bitset.myr
index 020e273..d6c8a8f 100644
--- a/lib/std/test/bitset.myr
+++ b/lib/std/test/bitset.myr
@@ -4,10 +4,7 @@ use testr
const main = {
testr.run([
[.name="basic", .fn={ctx
- var bs = std.mkbs()
- std.bsput(bs, 0)
- std.bsput(bs, 1)
- std.bsput(bs, 16)
+ var bs = mkset([0, 1, 16][:])
testr.check(ctx, std.bshas(bs, 0), "missing 0")
testr.check(ctx, std.bshas(bs, 1), "missing 1")
testr.check(ctx, std.bshas(bs, 16), "missing 16")
@@ -18,16 +15,8 @@ const main = {
std.bsfree(bs)
}],
[.name="bigsets", .fn={ctx
- var bs = std.mkbs()
/* multiple chunks */
- std.bsput(bs, 0)
- std.bsput(bs, 63)
- std.bsput(bs, 64)
- std.bsput(bs, 65)
- std.bsput(bs, 73)
- std.bsput(bs, 127)
- std.bsput(bs, 128)
- std.bsput(bs, 129)
+ var bs = mkset([0, 63, 64, 65, 73, 127, 128, 129][:])
testr.check(ctx, std.bshas(bs, 0), "missing 0")
testr.check(ctx, std.bshas(bs, 63), "missing 63")
testr.check(ctx, std.bshas(bs, 64), "missing 64")
@@ -38,8 +27,8 @@ const main = {
std.bsfree(bs)
}],
[.name="iter", .fn={ctx
- var bs = std.mkbs()
var expected = [0,1,3,7,16][:]
+ var bs = mkset(expected)
var i = 0
std.bsput(bs, 1)
@@ -53,5 +42,20 @@ const main = {
;;
std.bsfree(bs)
}],
+ [.name="count", .fn={ctx
+ var bs = mkset([0, 63, 64, 65, 73, 127, 128, 129][:])
+ testr.check(ctx, std.bscount(bs) == 8, "wrong element count, expected {}", std.bscount(bs))
+ std.bsfree(bs)
+ }]
][:])
}
+
+const mkset = {elts
+ var bs
+
+ bs = std.mkbs()
+ for e in elts
+ std.bsput(bs, e)
+ ;;
+ -> bs
+}