shithub: mc

Download patch

ref: 52ec5d6f05690494ee1a43452a0305ea697f0165
parent: cb2a50f6b3ada53a03cd211c79f920979edc0a25
author: Ori Bernstein <ori@eigenstate.org>
date: Sat Oct 22 18:52:56 EDT 2016 

Add bitset counting.

	Now we can know how many items are in a bitset.


--- a/lib/std/bitset.myr
+++ b/lib/std/bitset.myr
@@ -18,6 +18,7 @@
 	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 @@
 	-> 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 @@
 		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
 	}
 
--- a/lib/std/test/bitset.myr
+++ b/lib/std/test/bitset.myr
@@ -4,10 +4,7 @@
 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 @@
 			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 @@
 			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 @@
 			;;
 			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
 }