Viewing file:  test.py (45.45 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
# Tests for nybitset
# Note: uses assert statements for brevity,
# so wouldn't check so much with python -O.
from guppy.sets import *
import pickle
from time import process_time as clock
import gc
import random
import sys
try:
import numpy.random
except ImportError:
has_numpy = 0
else:
has_numpy = 1
if has_numpy:
def random_integers_list(low, high, length):
return list(map(int, numpy.random.random_integers(low, high, [length])))
else:
def random_integers_list(low, high, length):
return [random.randint(low, high) for i in range(length)]
Empty = immbitset()
Omega = ~Empty
bitsmut = mutbitset
bitset = immbitset
bitrange = immbitrange
bitsingle = immbit
def absorption(a, b):
assert a & (a | b) == a
assert a | (a & b) == a
def associative(a, b, c):
assert (a & b) & c == a & (b & c)
assert (a | b) | c == a | (b | c)
def commutative(a, b):
assert a & b == b & a
assert a | b == b | a
def deMorgan(a, b, c=None):
if c is None:
assert ~(a & b) == ~a | ~b
assert ~(a | b) == ~a & ~b
else:
assert c - (a & b) == (c - a) | (c - b)
assert c - (a | b) == (c - a) & (c - b)
def idempotence(a):
assert a & a == a
assert a | a == a
def inclusion(a, b):
assert a & b <= a
assert a & b <= b
assert a | b >= a
assert a | b >= b
def distributive(a, b, c):
assert a | (b & c) == (a | b) & (a | c)
assert a & (b | c) == (a & b) | (a & c)
assert (a & b) | (b & c) | (c & a) == (a | b) & (b | c) & (c | a)
assert not (a & b == a & c and a | b == a | c) or (b == c)
def test_set_operations(as_, bs, cs):
for a in as_:
idempotence(a)
for b in bs:
inclusion(a, b)
commutative(a, b)
absorption(a, b)
for c in cs:
associative(a, b, c)
distributive(a, b, c)
deMorgan(a, b, c)
def test_set_sub(as_, bs):
def imp(a, b):
assert not a or b
for a in as_:
for b in bs:
imp(len(a) != len(b), a != b)
imp(a < b, b > a and (not b < a))
imp(a <= b, b >= a and (a < b or a == b) and not a > b)
imp(a == b, a <= b and a >= b and not a != b and not b != a)
imp(a != b, not a == b and not b == a)
imp(a > b, b < a and not b > a)
imp(a >= b, b <= a and (b < a or a == b) and not a < b)
def test_set_len(as_, bs):
# If a set can provide a len(), it should be convertible to a list
for a in as_:
assert len(a) == len(list(a))
assert len(a & a) == len(a)
assert len(a | a) == len(a)
for b in bs:
# Test len of binary ops
assert len(a | b) == len(list(a | b))
assert len(a & b) == len(list(a & b))
assert len(a - b) == len(list(a - b))
assert len(a ^ b) == len(list(a ^ b))
def test_set_convert(as_, bs):
for a in as_:
for b in bs:
# Conversions
assert a | list(b) == a | b
assert a - tuple(b) == a - b
assert a & list(b) == a & b
assert a ^ tuple(b) == a ^ b
def eltime(f, args=(), N=1, retx=0):
r = list(range(N))
starttime = clock()
for i in r:
x = f(*args)
endtime = clock()
elapsed = endtime - starttime
if retx:
return elapsed, x
else:
return elapsed
'.nython on'
class IdSet(bitsmut):
def append(self, x):
bitsmut.append(self, id(x) // 12)
def remove(self, x):
bitsmut.remove(self, id(x) // 12)
def __contains__(self, x):
return bitsmut.__contains__(self, id(x) // 12)
'.nython off'
def add(a, b):
c = b
while c:
a, c = a ^ c, (a & c) << 1
print(a, c)
return a
def randint(lim=1 << 30):
# Return a random signed int
return int(random.randrange(-lim, lim))
def randlong():
a = randint()
b = randint()
ash = randint() & 255
c = randint()
d = randint()
bsh = randint() & 255
r = (a * b << ash) + (c * d << bsh)
return r
def dictset(l):
ds = {}
for e in l:
if e not in ds:
ds[e] = 1
return ds
def dslist(l):
ds = dictset(l)
ks = list(ds.keys())
ks.sort()
return ks
def randlist(n, amp):
' randlist(n, amp) -> list of n unique random ints in [-amp,amp]'
ds = {}
rng = [] # To become a non-sorted list of unique random ints
for i in range(10000):
while 1:
b = randint(50000)
if b not in ds:
rng.append(b)
ds[b] = 1
break
return rng
'.nython on'
def t_append(a, b):
ap = a.append
for bit in b:
ap(bit)
def t_append_id(a, b):
ap = a.append
for bit in b:
ap(id(bit) // 12)
'.nython off'
class Test:
# Set to 1 if test should be faster (less exhaustive) than normally
faster = 1
def test0(self):
pass
def test1(self):
import io
f = io.StringIO()
bitset([1, 3, 4]) | []
bitset([1, 3, 4]) & []
#bitset([1,3,4]) | {}
# bitset([1,3,4]) & {}
bitset([1, 3, 4]) | [5]
bitset([1, 3, 4]) | list(range(100))
bitset([1, 3, 4]) | list(range(100, -1, -1))
empties = (
bitset(),
bitset([]),
bitset(()),
bitset(0),
bitset(0),
bitset(bitset())
)
print(empties, file=f)
for e in empties:
assert e is Empty
bitset(0x1 << 30)
bitset(0x1 << 32)
print(bitset(0x8000), file=f)
print(bitset((4,)), file=f)
print(~bitset(0x8000), file=f)
print(bitset([1]) | bitset(3), file=f)
print(int(bitset([1])), file=f)
print(int(bitset([1])), file=f)
ms = bitset(0).mutcopy()
msa = ms
ms |= 1
print(list(ms), file=f)
ms |= 0x4000
print(list(ms), file=f)
ms |= [3, 4]
print(list(ms), file=f)
ms |= (6, 8)
print(list(ms), file=f)
ms |= bitset([7])
print(list(ms), ms, file=f)
ms |= bitset([37])
ts = bitset(ms)
print(ts, file=f)
ms &= ts
print(ms, file=f)
ms &= 1
print(ms, file=f)
ms |= ts
ms &= 0x4000
print(list(ms), file=f)
ms |= ts
ms &= [3, 4]
print(list(ms), file=f)
ms |= ts
ms &= (6, 8)
print(list(ms), file=f)
ms |= ts
ms &= bitset([7])
print(ms, file=f)
ms |= ts
ms &= ~bitset([6])
print(ms, 'ts&.', ts & ~bitset([6]), file=f)
ms ^= 1
print(ms, file=f)
ms ^= 0x4000
print(list(ms), file=f)
ms ^= [3, 4]
print(list(ms), file=f)
ms ^= (6, 8)
print(list(ms), file=f)
ms ^= bitset([7])
print(ms, file=f)
ms &= 0
ms |= ts
ms |= ~ts
print(ms, 'mt', ms | ~ ts, ts | ~ts, ~bitset([]) | ~ts, file=f)
xs = bitset(ms)
ms |= 1
print(ms, xs | 1, int(xs), int(xs), file=f)
ms ^= ms
print(ms, file=f)
ms &= ~ms
print(ms, int(ms), int(ms), file=f)
ms |= -1
print(ms, int(ms), file=f)
ms &= -2
print(ms, int(ms), file=f)
ms ^= -4
print(ms, int(ms), file=f)
ms |= -1
print(ms, int(ms), file=f)
ms &= -2
print(ms, int(ms), file=f)
ms ^= -4
print(ms, int(ms), file=f)
ms |= bitset(-1)
print(ms, int(ms), file=f)
ms &= bitset(-2)
print(ms, int(ms), file=f)
assert ms is msa
print(bitset(-1), file=f)
print(bitset([-1]), file=f)
print(bitset([-1]) | bitset([4]), file=f)
assert f.getvalue() == """\
(ImmBitSet([]), ImmBitSet([]), ImmBitSet([]), ImmBitSet([]), ImmBitSet([]), ImmBitSet([]))
ImmBitSet([15])
ImmBitSet([4])
(~ImmBitSet([15]))
ImmBitSet([0, 1])
2
2
[0]
[0, 14]
[0, 3, 4, 14]
[0, 3, 4, 6, 8, 14]
[0, 3, 4, 6, 7, 8, 14] MutBitSet([0, 3, 4, 6, 7, 8, 14])
ImmBitSet([0, 3, 4, 6, 7, 8, 14, 37])
MutBitSet([0, 3, 4, 6, 7, 8, 14, 37])
MutBitSet([0])
[14]
[3, 4]
[6, 8]
MutBitSet([7])
MutBitSet([0, 3, 4, 7, 8, 14, 37]) ts&. ImmBitSet([0, 3, 4, 7, 8, 14, 37])
MutBitSet([3, 4, 7, 8, 14, 37])
[3, 4, 7, 8, 37]
[7, 8, 37]
[6, 7, 37]
MutBitSet([6, 37])
MutBitSet(~ImmBitSet([])) mt (~ImmBitSet([])) (~ImmBitSet([])) (~ImmBitSet([]))
MutBitSet(~ImmBitSet([])) (~ImmBitSet([])) -1 -1
MutBitSet([])
MutBitSet([]) 0 0
MutBitSet(~ImmBitSet([])) -1
MutBitSet(~ImmBitSet([0])) -2
MutBitSet([1]) 2
MutBitSet(~ImmBitSet([])) -1
MutBitSet(~ImmBitSet([0])) -2
MutBitSet([1]) 2
MutBitSet(~ImmBitSet([])) -1
MutBitSet(~ImmBitSet([0])) -2
(~ImmBitSet([]))
ImmBitSet([-1])
ImmBitSet([-1, 4])
"""
def test2(self):
# Test standard operators (not-inplace)
for a in [randlong() for i in range(10)]:
for b in [randlong() for j in range(10)]:
ts = []
for ta in (a, bitset(a), bitsmut(a)):
for tb in (b, bitset(b), bitsmut(b)):
tr = []
tr.append(ta | tb)
tr.append(ta & tb)
tr.append(ta ^ tb)
tr.append(ta | ~tb)
tr.append(ta & ~tb)
tr.append(ta ^ ~tb)
tr.append(~ta | tb)
tr.append(~ta & tb)
tr.append(~ta ^ tb)
tr.append(~ta | ~tb)
tr.append(~ta & ~tb)
tr.append(~ta ^ ~tb)
ts.append(tr)
for tr in ts[1:]:
for r, x in zip(tr, ts[0]):
assert int(r) == x
def test3(self):
# Test in-place operators
p = randlong()
op = randint()
a = randlong()
b = randlong()
ts = []
for tp in (p, bitset(p), bitsmut(p)):
for ta in (a, bitset(a), bitsmut(a)):
if op & 1:
ta |= tp
elif op & 2:
ta &= tp
elif op & 4:
ta ^= tp
for tb in (b, bitset(b), bitsmut(b)):
tr = []
tb |= ta
tr.append(int(tb))
tb &= ta
tr.append(int(tb))
tb ^= ta
tr.append(int(tb))
tb |= ~ta
tr.append(int(tb))
tb &= ~ta
tr.append(int(tb))
tb ^= ~ta
tr.append(int(tb))
ts.append(tr)
for tr in ts[1:]:
for r, x in zip(tr, ts[0]):
assert int(r) == x
def test4(self):
# Some performance test
def f1(n, x, y):
while n > 0:
x |= y
x |= y
x |= y
x |= y
x |= y
n -= 1
x = 0
for exp in range(0, 1024*32, 16*32*(1+self.faster*31)):
y = 1 << exp
print(exp, eltime(f1, (1000, x, y)),
eltime(f1, (1000, bitset(x), y)),
eltime(f1, (1000, bitset(x), bitset(y))),
eltime(f1, (1000, bitsmut(x), y)),
eltime(f1, (1000, bitsmut(x), bitsmut(y))),
eltime(f1, (1000, bitsmut(x), bitset(y))))
def test5(self):
# Bitset from sequences in different ways
bits = {}
for i in range(50):
bit = randint()
bits[bit] = 1
bits[bit+randint() % 15] = 1
bits[bit+randint() % 15] = 1
bits[bit-randint() % 15] = 1
bits[bit-randint() % 15] = 1
bits = list(bits)
sbits = list(bits)
sbits.sort()
def dictset(bits):
return dict([(bit, 1) for bit in bits])
seqs = [bits, tuple(bits), dictset(bits)]
for seq in seqs:
assert list(bitset(seq)) == sbits
bs = Empty
bs = bs | seq
assert list(bs) == sbits
bs = Empty
bs = seq | bs
assert list(bs) == sbits
bs = Empty
bs |= seq
assert list(bs) == sbits
bs = bitsmut(Empty)
bs |= seq
assert list(bs) == sbits
bs = Empty
bs = bs ^ seq
assert list(bs) == sbits
bs = Empty
bs = seq ^ bs
assert list(bs) == sbits
bs = Empty
bs ^= seq
assert list(bs) == sbits
bs = bitsmut(Empty)
bs ^= seq
assert list(bs) == sbits
bs = Omega
bs = bs & seq
assert list(bs) == sbits
bs = Omega
bs = seq & bs
assert list(bs) == sbits
bs = Omega
bs &= seq
assert list(bs) == sbits
bs = bitsmut(Omega)
bs &= seq
assert list(bs) == sbits
bs = Omega
bs = bs ^ seq
bs = ~bs
assert list(bs) == sbits
bs = Omega
bs = seq ^ bs
bs = ~bs
assert list(bs) == sbits
bs = Omega
bs ^= seq
bs = ~bs
assert list(bs) == sbits
bs = bitsmut(Omega)
bs ^= seq
bs = ~bs
assert list(bs) == sbits
def test6(self):
# Comparisons
for a in (randlong(),):
for b in (a, ~a, randlong()):
assert ((bitset(a) == bitset(b)) == (a == b))
assert ((bitset(a) != bitset(b)) == (a != b))
assert ((bitset(a) == ~bitset(b)) == (a == ~b))
assert ((bitset(a) != ~bitset(b)) == (a != ~b))
assert ((~bitset(a) == bitset(b)) == (~a == b))
assert ((~bitset(a) != bitset(b)) == (~a != b))
assert ((~bitset(a) == ~bitset(b)) == (~a == ~b))
assert ((~bitset(a) != ~bitset(b)) == (~a != ~b))
assert ((bitsmut(a) == bitsmut(b)) == (a == b))
assert ((bitsmut(a) != bitsmut(b)) == (a != b))
assert ((bitsmut(a) == bitset(b)) == (a == b))
assert ((bitsmut(a) != bitset(b)) == (a != b))
assert ((bitset(a) == bitsmut(b)) == (a == b))
assert ((bitset(a) != bitsmut(b)) == (a != b))
def test7(self):
# Bitsmut gymnastics
import io
f = io.StringIO()
a = bitsmut(0)
print(str(a), file=f)
a.append(1)
print(str(a), a.pop(), str(a), file=f)
a.append(1)
print(str(a), a.pop(-1), str(a), file=f)
a.append(1)
print(str(a), a.pop(0), str(a), file=f)
a.append(1)
a.append(2)
a.append(3)
print(str(a), a.pop(), str(a), file=f)
print(str(a), a.pop(0), str(a), file=f)
a.remove(2)
print(str(a), file=f)
print(f.getvalue())
assert f.getvalue() == """\
MutBitSet([])
MutBitSet([1]) 1 MutBitSet([])
MutBitSet([1]) 1 MutBitSet([])
MutBitSet([1]) 1 MutBitSet([])
MutBitSet([1, 2, 3]) 3 MutBitSet([1, 2])
MutBitSet([1, 2]) 1 MutBitSet([2])
MutBitSet([])
"""
def f(a, b):
ap = a.append
for bit in b:
ap(bit)
def flu(a, b):
s = 0
for bit in b:
if bit in a:
s += 1
return s
def g(a, b):
for bit in b:
a[bit] = 1
def h(a, b):
for bit in b:
a |= bitsingle(bit)
def tms(rng, f=f):
ms = bitsmut(0)
t = eltime(f, (ms, rng))
srng = list(rng)
srng.sort()
assert ms == bitset(srng)
return t
def tmslu(rng, n=None):
if n is None:
n = len(rng)
ms = bitsmut(rng[:n])
elt, s = eltime(flu, (ms, rng), retx=1)
assert s == n
return elt
def tbslu(rng, n=None):
if n is None:
n = len(rng)
ms = bitset(rng[:n])
elt, s = eltime(flu, (ms, rng), retx=1)
assert s == n
return elt
def tlo(rng):
lo = 0
def f(a, b):
for bit in b:
a |= 1 << b
return eltime(h, (lo, rng))
def tbs(rng):
lo = bitset()
def f(a, b):
for bit in b:
a |= bitsingle(b)
return eltime(h, (lo, rng))
def tls(rng):
ls = []
return eltime(f, (ls, rng))
def tds(rng):
ds = {}
return eltime(g, (ds, rng))
def tdslu(rng, n=None):
if n is None:
n = len(rng)
ds = dict([(x, 1) for x in rng[:n]])
elt, s = eltime(flu, (ds, rng), retx=1)
assert s == n
return elt
step = (1 + self.faster*5)
for rng in (list(range(0, 10000, step)),
list(range(0, 100000, step)),
list(range(10000, -1, -1*step)),
randlist(10000, 50000-self.faster*40000)):
print(tms(rng), tds(rng), tls(rng), tms(rng, h),
tmslu(rng), tbslu(rng), tdslu(rng),
tmslu(rng, 100), tbslu(rng, 100), tdslu(rng, 100))
rng = list(range(10000))
print(tlo(rng), tbs(rng))
def test8(self):
# Subclassing a bitsmut
BS = IdSet
for bs in (BS(), BS([]), BS([0])):
os = ((), [], {})
for o in os:
bs.append(o)
for o in os:
assert o in bs
for o in os:
bs.remove(o)
for o in os:
assert o not in bs
def test9(self):
# Making bigger bitsmuts - testing the split
for i in (1000, 10000, 100000):
r = list(range(i))
m = bitsmut(r)
assert list(m) == r
la = random_integers_list(-i, i, i)
m = bitsmut(la)
las = dslist(la)
bs = bitset(m)
assert list(bs) == las
def test10(self):
# Performance test
def tests(la):
for i in (1000, 10000, 100000, 400000):
print('eltime(bitset, (la[:%d],))' % i)
print(eltime(bitset, (la[:i],)))
la = list(range(400000))
print('la = range(400000)')
tests(la)
la.reverse()
print('la.reverse()')
tests(la)
la = random_integers_list(-400000, 400000, 400000)
print('la=random_integers_list(-400000,400000,400000))')
tests(la)
def test11(self, n=1):
# A specific bug showed when setting splitting_size
la = random_integers_list(-400000, 400000, 400000)
while n > 0:
ms = bitsmut([])
ms._splitting_size = 100
ms |= la
print('test11', n, ms._indisize, ms._num_seg)
n -= 1
def test12(self):
# append should be able to reuse space that was pop()'d
# even for other bit ranges
# Due to allocation strategy, the size may differ an
# initial round but should then be stable.
for N in (32, 64, 128, 256, 31, 33, 63, 65, 255, 257):
ms = bitsmut()
# Train it
rng = list(range(N))
ms |= rng
for popix in (-1, 0):
for j in range(N):
ms.pop(popix)
ms |= rng
# Now should be stable..
indisize = ms._indisize
for popix in (-1, 0):
for i in range(0, N*10, N):
pops = []
for j in range(N):
pops.append(ms.pop(popix))
assert list(ms) == []
if popix == -1:
pops.reverse()
assert pops == rng
rng = list(range(i, i+N))
ms |= rng
assert indisize == ms._indisize
assert list(ms) == rng
def test13(self):
# append, remove for inverted bitsmuts,
# have inverted sense. 'nonzero' is always true.
# (pop is not supported - it seems it conceptually should give infite range of bits)
ms = bitsmut()
assert not ms
ms ^= ~0 # Make it inverted - contains 'all bits'
assert ms
ms.remove(0)
assert ms
assert list(~ms) == [0]
try:
ms.remove(0)
except ValueError:
pass
else:
raise AssertionError('expected ValueError for remove')
ms.append(0)
assert list(~ms) == []
try:
ms.append(0)
except ValueError:
pass
else:
raise AssertionError('expected ValueError for append')
ms.remove(0)
try:
ms.pop()
except ValueError:
pass
else:
raise AssertionError('expected ValueError for pop')
def test14(self):
# Test the bitrange() constructor
xs = (-1000, -100, -33, -32, -31, -10, -
1, 0, 1, 10, 31, 32, 33, 100, 1000)
for lo in xs:
assert list(bitrange(lo)) == list(range(lo))
for hi in xs:
assert list(bitrange(lo, hi)) == list(range(lo, hi))
for step in (1, 2, 3, 4, 5, 6, 7, 31, 32, 33):
r = list(range(lo, hi, step))
assert list(bitrange(lo, hi, step)) == r
def test15(self):
# Test the indexing
# Only index 0 or -1 is currently supported, for first or last bit -
# the others would take more work and might appear surprisingly slow.
for a in range(-33, 34):
for b in range(a+1, a+35):
rng = list(range(a, b))
bs = bitrange(a, b)
assert bs[0] == a
assert bs[-1] == b-1
ms = bitsmut(bs)
assert ms[0] == a
assert ms[-1] == b-1
i = 0
while ms:
x = ms[i]
assert x == ms.pop(i)
assert x == rng.pop(i)
i = -1 - i
def test16(self):
# Test shifting
for sh in range(64):
for v in range(64):
assert int(bitset(v) << sh) == int(v) << sh
maxint = sys.maxsize
minint = -maxint - 1
b = bitset([0])
for sh in (maxint, -maxint, minint):
assert b << sh == bitset([sh])
def tsv(bs, sh):
try:
bs << sh
except OverflowError:
pass
else:
raise AssertionError('expected OverflowError')
tsv(bitset([maxint]), 1)
tsv(bitset([minint]), -1)
tsv(bitset([-maxint]) << (-1), -1)
for a, b in ((0, 10), (0, 10000), (-1000, 1000)):
for sh in (-257, -256, -255, -1, 0, 1, 255, 256, 257):
for step in (1, 2, 3):
assert bitrange(a, b, step) << sh == bitrange(
a+sh, b+sh, step)
def test17(self):
# Comparisons: inclusion tests
for a in (0, 1, 2, list(range(31)), list(range(32)), list(range(33)), randlong()):
for b in (0, 1, 2, list(range(31)), list(range(32)), list(range(33)), randlong()):
for as_ in (bitset(a), ~bitset(a), bitsmut(a), bitsmut(~bitset(a))):
for bs in (as_, ~as_, bitset(b), ~bitset(b), bitsmut(b), bitsmut(~bitset(b))):
t = as_ <= bs
assert t == (bs >= as_)
assert t == ((as_ & bs) == as_)
assert t == ((int(as_) & int(bs)) == int(as_))
t = as_ < bs
assert t == (bs > as_)
assert t == ((as_ <= bs) and (as_ != bs))
assert t == ((as_ <= bs) and (int(as_) != int(bs)))
def test18(self):
# Testing internal consistency, with test values
# that may not be practical to convert to longs.
# Using Properties of Boolean algebras
# (from 'Mathematichal Handbook'... tables p.30, p.15)
# Some tests should be quite redundant given others passed,
# but are kept anyway for reference & doublechecking.
any = [bitset(abs(randlong())) << randint(),
bitset(abs(randlong())) << randint(),
bitset(abs(randlong())) << randint() | bitset(
abs(randlong())) << randint(),
bitset(abs(randlong())) << randint() | bitset(
abs(randlong())) << randint(),
]
any = [Empty, Omega, bitset([0]),
bitset(randlong()),
bitset(randlong())] + [a ^ randlong() for a in any]
any = any + [bitsmut(a) for a in any]
for a in any:
# Empty and Omega are the least and greatest elements
assert Empty <= a <= Omega
assert a & Empty == Empty
assert a | Omega == Omega
# Identity elements for & and |
assert a & Omega == a
assert a | Empty == a
# Complement laws
assert a & ~a == Empty
assert a | ~a == Omega
assert ~Empty == Omega
assert ~Omega == Empty
assert ~(~a) == a
idempotence(a)
for b in any:
# Relative complement, definition
assert a & ~b == a - b
# ...
absorption(a, b)
commutative(a, b)
deMorgan(a, b)
inclusion(a, b)
for c in any:
associative(a, b, c)
distributive(a, b, c)
# ...
assert ((a <= b) == (a & b == a) == (a | b == b) ==
(a & ~b == Empty) == (~b <= ~a) == (~a | b == Omega))
# Symmetric difference
# From p. 15
assert a ^ b == b ^ a
for c in any:
assert (a ^ b) ^ c == a ^ (b ^ c)
deMorgan(a, b, c)
assert a ^ Empty == a
assert a ^ a == Empty
assert a ^ b == (a & ~b) | (b & ~a)
def test19(self):
# Finding prime numbers using the Sieve of Eratosthenes
# - an excercise for eg bitrange().
N = 4000
primes = ([2] | bitrange(3, N, 2)).mutcopy()
for i in bitrange(3, N // 2, 2):
primes &= ~bitrange(2 * i, N, i)
primes = list(primes)
assert len(primes) == 550
assert primes[:10] == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
assert primes[399] == 2741
assert primes[549] == 3989
return primes
def test20(self):
# Some bitrange arguments used when debugging its optimized version.
# Entered here, in case some wasn't covered by previous tests.
maxint = sys.maxsize
minint = -maxint - 1
for a in (
(32,),
(31,),
(33,),
(13,),
(1, 33),
(1, 33, 2),
(1, 63, 2),
(0, 64, 32),
(0, 64+17, 32),
(0, 32*3, 32),
(0, 32*3+1, 32),
(0, 32*4, 32),
(0, 32*4, 16),
(0, 32*2, 16),
(0, 32*3, 16),
(maxint-32, maxint),
(maxint-32, maxint, 2),
(maxint-32, maxint, 4),
(maxint-32, maxint, 16),
(maxint-32, maxint, 20),
(maxint-320, maxint),
(maxint-320, maxint, 2),
(maxint-320, maxint, 4),
(maxint-320, maxint, 16),
(maxint-320, maxint, 20),
(-1, maxint, maxint),
(0, maxint, maxint),
(1, maxint, maxint),
(minint, maxint, maxint),
(minint, maxint, maxint//32),
(minint, maxint, maxint//320),
(minint, maxint, -(minint//32)),
(minint, maxint, -(minint//320)),
):
br = bitrange(*a)
assert list(br) == list(range(*a))
try:
bitrange(minint, maxint, 1)
except OverflowError:
pass
else:
raise AssertionError('expected OverflowError')
# a more exhaustive check,
# it tests some > 70000 combinations if not self.faster
if not self.faster:
print('bitrange testing many combinations, this may take some time...')
for a in range(0, 34, 1 + 8*self.faster):
print('a', a, end=' ')
sys.stdout.flush()
for l in range(1000, 1034, 1 + 8*self.faster):
for st in range(1, 34, 1 + 8*self.faster):
for arg in ((maxint - l, maxint - a, st),
(minint + a, minint + l, st)):
br = bitrange(*arg)
assert list(br) == list(range(*arg))
print('done')
def test21(self):
# Test bitset as dict key - i.e. hashing, equality
D = {}
a = bitrange(1)
b = bitrange(1)
c = ~a
d = ~b
D[a] = 1
D[c] = -1
assert D[b] == D[a] == 1
assert D[c] == D[d] == -1
def test22(self):
# Test pickling
any = [bitset() for x in range(10)]
any = any + [bitrange(x, y, z)
for x in (-1000, 0, 1000)
for y in (2000,)
for z in (1, 3, 300)]
any = any + [~x for x in any]
any = any + [bitsmut(x) for x in any]
for a in any:
for bin in (0, 1):
da = pickle.dumps(a, bin)
aa = pickle.loads(da)
assert aa == a
assert type(aa) is type(a)
def test23(self):
# bitset from general sequence with iterator
# We already special-cased list, tuple & dict
class T:
def __init__(self, data):
self.data = data
def __iter__(self):
return iter(self.data)
l = list(range(10))
t = T(l)
b = bitset(t)
assert list(b) == l
bo100 = b | T([100])
assert list(bo100) == l + [100]
ms = bitsmut(t)
assert ms == b
ms |= T([100])
assert ms == bo100
def test24(self):
# tests to do with the copy-on-write optimizations
# this should show in improved timing for some operation sequences
def f1(n):
return bitrange(n).mutcopy()[0]
t, v = eltime(f1, (10000000,), retx=1)
print(t)
assert v == 0
bs = bitrange(10000000)
def f2(bs):
ms = bs.mutcopy()
ms &= ~1
return ms[0], bs[0]
t, v = eltime(f2, (bs,), retx=1)
print(t)
assert v == (1, 0)
ms = bs.mutcopy()
# Test that a temporary immutable copy can be fast
def f3(ms):
bs = bitset(ms)
return ms[0], bs[0],
t, v = eltime(f3, (ms,), retx=1)
print(t)
assert v == (0, 0)
def f4(ms):
bs = bitset(ms)
ms &= ~1
return ms[0], bs[0],
def f4b(ms):
# make sure cur_field is cleared when bitset is made
ms |= 1
bs = bitset(ms)
ms ^= 1
return ms[0], bs[0],
for f in (f4, f4b):
ms = bs.mutcopy()
t, v = eltime(f, (ms,), retx=1)
print(t)
assert v == (1, 0)
ms = bs.mutcopy()
# Test that a temporary mutable copy of a bitsmut can be fast
def f5(ms):
mc = ms.mutcopy()
return mc[0], ms[0],
t, v = eltime(f5, (ms,), retx=1)
print(t)
assert v == (0, 0)
# Test that a temporary mutable copy of a bitsmut can be fast
# and still be separately updated
def f6(ms):
ms &= ~bitrange(15)
mc = ms.mutcopy()
mc |= [2]
ms |= [4]
return mc[0], ms[0],
def f6a(ms):
# as f6 but updating in the other order - tried to induce a bug
ms &= ~bitrange(15)
mc = ms.mutcopy()
ms |= [4]
mc |= [2]
return mc[0], ms[0],
def f6b(ms):
# working harder and managed to provoke test of a noticed copy-on-write
# requirement (cur_field had to be cleared when the set was borrowed)
ms &= ~bitrange(15)
ms |= [8]
mc = ms.mutcopy()
ms |= [1, 4]
mc |= [2]
ms &= ~bitsingle(1)
return mc[0], ms[0],
for f in (f6, f6a, f6b):
t, v = eltime(f, (ms,), retx=1)
print(t)
assert v == (2, 4)
# Temporary mutable copy of splitted bitsmut
for f in (f6, f6a, f6b):
bs = bitrange(100000) | bitrange(200000, 300000)
ms = bs.mutcopy()
ms |= bitsingle(150000) # Force a split
assert ms._num_seg > 1
print('num_seg', ms._num_seg)
t, v = eltime(f, (ms,), retx=1)
print(t)
assert v == (2, 4)
def test25(self):
# Thing that came up
# converting to int should fail here, not become negative.
# (Assuming 'standard' 2-complement int representation)
bs = bitset(int(sys.maxsize)+1)
# try:
# a = int(bs)
# except OverflowError:
# pass
# else:
# raise AssertionError('expected OverflowError')
assert int(bs) == int(sys.maxsize)+1
# These border cases should pass
assert int(bitset(sys.maxsize)) == sys.maxsize
assert int(bitset(-sys.maxsize - 1)) == - sys.maxsize - 1
def test26(self):
# len() tests
for thelen in [0, 15, 17, 31, 33, 1023, 1024, 1025, int(1e7)]:
for args in [(thelen,), (0, thelen * 3, 3)]:
bs = bitrange(*args)
t, v = eltime(len, (bs,), retx=1)
if t > 0.01:
print(t, v)
assert v == thelen
bs = bitsmut(bs)
t, v = eltime(len, (bs,), retx=1)
if t > 0.01:
print(t, v)
assert v == thelen
def test27(self):
# slices
for b in (bitset(64), bitrange(64), bitset(abs(randlong()))):
for st in (b, b.mutcopy()):
for i in (1, 2, 3, 30, 31, 32, 33, 34, 63, 64, 65):
assert b[:i] == bitset(list(b)[:i])
assert b[-i:] == bitset(list(b)[-i:])
def test28(self):
# test & set; test & clr
for s in (bitsmut(), bitsmut(~bitset() & ~bitset([14]))):
assert s.tas(14) == 0
assert s.tas(14) == 1
assert s.tac(14) == 1
assert s.tac(14) == 0
def test29(self):
# Compatibility functions added:
# add, discard, -, -=
# Also tests S.mutcopy() where S is mutable with 1 or 2 segments
def t(p):
q = p.mutcopy()
p.add(17)
assert p != q
q.append(17)
assert p == q
p.discard(-1)
assert p == q
p.discard(17)
assert p != q
q.remove(17)
assert p == q
r = p - q
assert r == bitsmut([])
ms = bitsmut(12345)
t(ms)
bs = bitrange(20, 100000) | bitrange(200000, 300000)
ms = bs.mutcopy()
ms |= bitsingle(150000) # Force a split
assert ms._num_seg > 1
t(ms)
all = 0, -1, 1, -2, 2, randlong(), -randlong()
all = [bitsmut(a) for a in all]
all = all + [bitsmut(a) for a in all]
for a in all:
a = a.mutcopy()
aa = a.mutcopy()
for b in all:
a -= b
aa &= ~b
assert a == aa
def test30(self):
# Test nodeset
nodeset = immnodeset
ns = mutnodeset()
ns0 = ns
a = []
b = ()
c = {}
d = 0
e = ''
# Test 5 ways to add elements
ns.add(a)
ns.append(b)
ns |= nodeset([c])
assert not ns.tas(d)
ns ^= [e]
assert ns == nodeset([a, b, c, d, e])
# Test 5 ways to remove elements
ns ^= [e]
assert ns == nodeset([a, b, c, d])
assert ns.tac(d)
assert ns == nodeset([a, b, c])
ns -= nodeset([c])
assert ns == nodeset([a, b])
ns.remove(b)
assert ns == nodeset([a])
ns.discard(a)
assert ns == nodeset([])
# Test pop
ns.add(a)
assert ns.pop() is a
try:
ns.pop()
except ValueError:
pass
else:
raise AssertionError('expected ValueError')
assert ns0 is ns
ns = immnodeset(ns)
ns |= nodeset([a])
assert ns == nodeset([a])
assert ns is not ns0
# ns is now immutable
# this is like bitset
# see note per Wed Jan 21 16:13:55 MET 2004
# The change was made after that.
ns1 = ns
ns -= nodeset([a])
# See note above. The following check
# applies since mutability behaviour is as for bitset
assert ns is not ns1
assert ns == nodeset([])
# Test clear
ns = mutnodeset([1, 2, 3])
assert len(ns) == 3
ns.clear()
assert len(ns) == 0
assert list(ns) == []
def test31(self):
# Test nodeset, element-wise operations & object deallocation w. gc
H = mutnodeset
from sys import getrefcount as grc
e1 = []
e2 = []
e3 = []
r1 = grc(e1)
r2 = grc(e2)
r3 = grc(e3)
s = H()
s.add(e1)
assert e1 in s
assert e2 not in s
s.append(e2)
assert e2 in s
assert s.tas(e3) == 0
assert e3 in s
assert r1 + 1 == grc(e1)
assert r2 + 1 == grc(e2)
assert r3 + 1 == grc(e3)
assert s.tas(e3) == 1
assert s.tac(e3) == 1
assert s.tac(e3) == 0
s.discard(e3)
s.remove(e2)
try:
s.append(e1)
except ValueError:
pass
else:
raise AssertionError('no exception from append')
s.remove(e1)
try:
s.remove(e1)
except ValueError:
pass
else:
raise AssertionError('no exception from remove')
assert r1 == grc(e1)
assert r2 == grc(e2)
assert r3 == grc(e3)
s.add(e1)
s.add(e2)
s.add(e3)
s = None
assert r1 == grc(e1)
assert r2 == grc(e2)
assert r3 == grc(e3)
# Test gc support
import gc
s = H()
s.append(e1)
s.append(s) # Make it cyclic
assert s in s
s = None
gc.collect()
assert r1 == grc(e1)
s = H()
s.append(e1)
s.append(e2)
e2.append(s) # Make it cyclic
s = None
e2 = None
gc.collect()
assert r1 == grc(e1)
def test32(self):
# Test extended NodeSet functionality
H = immnodeset
import gc
from sys import getrefcount as grc
gc.collect()
e1 = []
e2 = []
e3 = []
r1 = grc(e1)
r2 = grc(e2)
r3 = grc(e3)
s = H([e1, e2])
assert e1 in s and e2 in s and not e3 in s
s3 = H([e1, e3])
s |= s3
assert e3 in s
assert e2 in s
s &= s3
assert e2 not in s
assert e1 in s
la = [], [e1], [e1, e2], [e1, e2, e3], [e2], [e2, e3], [e3], [e1, e3, e3, e1]
ss = [H(x) for x in la]
test_set_operations(ss, ss, ss)
test_set_len(ss, ss)
test_set_sub(ss, ss)
test_set_convert(ss, ss)
for a in ss:
for b in ss:
# Not supported...yet..
for x in (
'assert list(b) | a == a | b',
'assert list(b) & a == a & b',
):
try:
exec(x, {'a': a, 'b': b}, {})
except TypeError:
pass
else:
raise Exception('Expected TypeError')
ss = s = s3 = la = a = b = c = x = None
gc.collect()
gc.collect()
assert r1 == grc(e1)
assert r2 == grc(e2)
assert r3 == grc(e3)
def test33(self):
# Test with multiple segments - so that code
# in union_realloc is covered
# I am unsure if any of the other tests used more segments than 2
# It is a bit tricky (and implementation-dependent)
# to make it make a specific number of segments.
# The testing with 20 segments will make 3 reallocations:
# to make place for 8, 16 and 24 segments.
numseg = 20
bs = bitset()
for i in range(numseg):
bs |= bitrange(i*2*100000+20, (i*2+1)*100000)
ms = bs.mutcopy()
mss = []
assert ms._num_seg == 1
for i in range(numseg-1):
mss.append(ms.mutcopy())
ms |= bitsingle((i*2+1)*100000+50000)
assert ms._num_seg == i+2
# Test that the copies were separate copies (Testing copy-on-write)
for i in range(numseg-1):
assert mss[i] == bs
bs |= bitsingle((i*2+1)*100000+50000)
def test34(self):
# Test nodeset inheritance
# This leaks in Python 2.3.3; whether or not H is MutNodeSet or list.
H = MutNodeSet
e1 = []
class X(H):
def extend(self, y):
for e in y:
self.append(e)
s = X()
assert e1 not in s
s.extend([e1])
assert e1 in s
def test35(self):
# Test bitset inheritance
for i in range(2):
# An error didn't show until second time around
for H in ImmBitSet, MutBitSet:
class X(H):
bitnames = ['red', 'green', 'blue']
def __new__(clas, *args):
return H.__new__(clas, [clas.bitnames.index(x) for x in args])
def __iter__(self):
for bit in H.__iter__(self):
yield self.bitnames[bit]
def __str__(self):
return '{%s}' % (', '.join(self))
def __eq__(self, other):
return str(self) == str(other)
x = X()
x = X('red', 'blue')
assert list(x) == ['red', 'blue']
# Test different kinds of construction args
assert (H.__new__(X, )) == '{}'
assert (H.__new__(X, immbitset(1))) == '{red}'
assert (H.__new__(X, mutbitset(2))) == '{green}'
assert (H.__new__(X, 3)) == '{red, green}'
assert (H.__new__(X, 4)) == '{blue}'
if H is ImmBitSet:
x = X('red', 'blue')
import guppy.sets.setsc
# See that we can pass a subtype to CplBitSet
assert(str(guppy.sets.setsc.CplBitSet(x))
== "(~ImmBitSet(['red', 'blue']))")
class MemStat:
def __init__(self):
self.nrefs = {}
from guppy import Root
self.R = R = Root()
self.V = R.guppy.heapy.View
self.P = R.guppy.heapy.Path
self.xmemstats = R.guppy.heapy.heapyc.xmemstats
#self.alset = R.guppy.heapy.heapyc.set_alset()
# self.mark()
def mark(self):
self.R.gc.collect()
h = self.V.horizon()
h.update(gc.get_objects())
self.h = h
def dump(self):
gc.collect()
self.xmemstats()
V = self.V
R = self.R
P = self.P
nrefs = self.nrefs
try:
co = sys.getcounts()
except AttributeError:
pass
else:
for (name, allo, free, max) in co:
nref = allo - free
if name not in nrefs or nref != nrefs[name]:
print((name, nref), end=' ', file=sys.stderr)
nrefs[name] = nref
print(file=sys.stderr)
h = self.h = n = co = name = allo = free = max = l = i = None
# self.mark()
#self.alset = None
# R.guppy.heapy.heapyc.clr_alset()
gc.collect()
#self.alset = R.guppy.heapy.heapyc.set_alset()
def test_nums(numbers, dump=None):
enufuncs = []
for n in numbers:
enufuncs.append((n, getattr(t, 'test%d' % n)))
for n, f in enufuncs:
print('Test #%d' % n)
f()
if dump is not None:
dump()
def test_leak():
import gc
# Test 34 is known to leak in Python 2.3.3.
nums = list(range(36))
nums.remove(34)
ms = MemStat()
i = 0
while 1:
test_nums(nums, ms.dump)
gc.collect()
i += 1
def test_main():
test_nums(list(range(36)))
t = Test()
if __name__ == '__main__':
# test_leak()
# t.test25()
# t.test30()
test_main()
# test_nums(range(30, 36))
# test_nums(range(13,35))
|