Author: Armin Rigo <[email protected]>
Branch: bitstring
Changeset: r83892:227dd39eb692
Date: 2016-04-25 18:38 +0200
http://bitbucket.org/pypy/pypy/changeset/227dd39eb692/
Log: The basic implementation
diff --git a/rpython/tool/algo/bitstring.py b/rpython/tool/algo/bitstring.py
new file mode 100644
--- /dev/null
+++ b/rpython/tool/algo/bitstring.py
@@ -0,0 +1,20 @@
+
+
+def make_bitstring(lst):
+ "NOT_RPYTHON"
+ if not lst:
+ return ''
+ num_bits = max(lst) + 1
+ num_bytes = (num_bits + 7) // 8
+ entries = [0] * num_bytes
+ for x in lst:
+ assert x >= 0
+ entries[x >> 3] |= 1 << (x & 7)
+ return ''.join(map(chr, entries))
+
+def bitcheck(bitstring, n):
+ assert n >= 0
+ byte_number = n >> 3
+ if byte_number >= len(bitstring):
+ return False
+ return (ord(bitstring[byte_number]) & (1 << (n & 7))) != 0
diff --git a/rpython/tool/algo/test/test_bitstring.py
b/rpython/tool/algo/test/test_bitstring.py
new file mode 100644
--- /dev/null
+++ b/rpython/tool/algo/test/test_bitstring.py
@@ -0,0 +1,20 @@
+from rpython.tool.algo.bitstring import *
+from hypothesis import given, strategies
+
+def test_make():
+ assert make_bitstring([]) == ''
+ assert make_bitstring([0]) == '\x01'
+ assert make_bitstring([7]) == '\x80'
+ assert make_bitstring([8]) == '\x00\x01'
+ assert make_bitstring([2, 4, 20]) == '\x14\x00\x10'
+
+def test_bitcheck():
+ assert bitcheck('\x01', 0) is True
+ assert bitcheck('\x01', 1) is False
+ assert bitcheck('\x01', 10) is False
+ assert [n for n in range(32) if bitcheck('\x14\x00\x10', n)] == [2, 4, 20]
+
+@given(strategies.lists(strategies.integers(min_value=0, max_value=299)))
+def test_random(lst):
+ bitstring = make_bitstring(lst)
+ assert set([n for n in range(300) if bitcheck(bitstring, n)]) == set(lst)
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
