Viewing file:  test.py (37.09 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.
import gc, random, 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 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)]
from time import clock
import cPickle
import pickle
from guppy.sets import *
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 = 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=1l<<30):
# Return a random signed int
return long(random.randrange(-lim, lim))
def randlong():
a = randint()
b = randint()
ash = randint() & 255l
c = randint()
d = randint()
bsh = randint() & 255l
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 = 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:
faster = 1 # Set to 1 if test should be faster (less exhaustive) than normally
def test0(self):
pass
def test1(self):
import StringIO
f = StringIO.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]) | range(100)
bitset([1,3,4]) | range(100,-1,-1)
empties = (
bitset(),
bitset([]),
bitset(()),
bitset(0),
bitset(0l),
bitset(bitset())
)
print >>f, empties
for e in empties:
assert e is Empty
bitset(0x1l<<30)
bitset(0x1l<<32)
print >>f,bitset(0x8000)
print >>f,bitset((4,))
print >>f,~bitset(0x8000)
print >>f,bitset([1]) | bitset(3)
print >>f,long(bitset([1]))
print >>f,int(bitset([1]))
ms = bitset(0).mutcopy()
msa = ms
ms |= 1
print >>f,list(ms)
ms |= 0x4000l
print >>f,list(ms)
ms |= [3, 4]
print >>f,list(ms)
ms |= (6, 8)
print >>f,list(ms)
ms |= bitset([7])
print >>f,list(ms), ms
ms |= bitset([37])
ts = bitset(ms)
print >>f,ts
ms &= ts
print >>f,ms
ms &= 1
print >>f,ms
ms |= ts
ms &= 0x4000l
print >>f,list(ms)
ms |= ts
ms &= [3, 4]
print >>f,list(ms)
ms |= ts
ms &= (6, 8)
print >>f,list(ms)
ms |= ts
ms &= bitset([7])
print >>f,ms
ms |= ts
ms &= ~bitset([6])
print >>f,ms, 'ts&.', ts &~bitset([6])
ms ^= 1
print >>f,ms
ms ^= 0x4000l
print >>f,list(ms)
ms ^= [3, 4]
print >>f,list(ms)
ms ^= (6, 8)
print >>f,list(ms)
ms ^= bitset([7])
print >>f,ms
ms &= 0
ms |= ts
ms |= ~ts
print >>f,ms, 'mt',ms |~ ts, ts |~ts, ~bitset([]) |~ts
xs = bitset(ms)
ms |= 1
print >>f,ms, xs | 1, long(xs), int(xs)
ms ^= ms
print >>f,ms
ms &= ~ms
print >>f,ms, long(ms), int(ms)
ms |= -1
print >>f,ms, long(ms)
ms &= -2
print >>f,ms, long(ms)
ms ^= -4
print >>f,ms, long(ms)
ms |= -1l
print >>f,ms, long(ms)
ms &= -2l
print >>f,ms, long(ms)
ms ^= -4l
print >>f,ms, long(ms)
ms |= bitset(-1)
print >>f,ms, long(ms)
ms &= bitset(-2)
print >>f,ms, long(ms)
assert ms is msa
print >>f,bitset(-1)
print >>f,bitset([-1])
print >>f,bitset([-1]) | bitset([4])
#print >>f,long(bitset([-1]))
# LP: #770882
if sys.hexversion < 0x2070000:
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)
# LP: #770882
if sys.hexversion >= 0x2070000:
continue
for tr in ts[1:]:
for r, x in zip(tr, ts[0]):
assert long(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(long(tb))
tb &= ta
tr.append(long(tb))
tb ^= ta
tr.append(long(tb))
tb |= ~ta
tr.append(long(tb))
tb &= ~ta
tr.append(long(tb))
tb ^= ~ta
tr.append(long(tb))
ts.append(tr)
# LP: #770882
if sys.hexversion >= 0x2070000:
return
for tr in ts[1:]:
#print tr
for r, x in zip(tr, ts[0]):
assert long(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 = 0l
for exp in range(0,1024*32,16*32*(1+self.faster*31)):
y = 1l<<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
# LP: #770882
if sys.hexversion >= 0x2070000:
return
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 StringIO
f = StringIO.StringIO()
a=bitsmut(0)
print >>f,a
a.append(1)
print >>f,a, a.pop(), a
a.append(1)
print >>f,a, a.pop(-1), a
a.append(1)
print >>f,a, a.pop(0), a
a.append(1)
a.append(2)
a.append(3)
print >>f,a, a.pop(), a
print >>f,a, a.pop(0), a
a.remove(2)
print >>f,a
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 = 0l
def f(a, b):
for bit in b:
a |= 1l<<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 ( range(0, 10000, step),
range(0, 100000, step),
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 = 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
try:
from snidioms import ListLikeDictSet
except ImportError:
print 'can not import snidioms, skipping a performance comparison'
else:
rng = range(10000)
for s in [], BS(), ListLikeDictSet():
print eltime(t_append, (s, rng))
for s in [], bitsmut([]),:
print eltime(t_append_id, (s, rng))
def test9(self):
# Making bigger bitsmuts - testing the split
for i in (1000, 10000, 100000):
r = 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 = 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 = 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 = 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 'expected ValueError for remove'
ms.append(0)
assert list(~ms) == []
try:
ms.append(0)
except ValueError:
pass
else:
raise 'expected ValueError for append'
ms.remove(0)
try:
ms.pop()
except ValueError:
pass
else:
raise '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)) == range(lo)
for hi in xs:
assert list(bitrange(lo, hi)) == range(lo, hi)
for step in (1, 2, 3, 4, 5, 6, 7, 31, 32, 33):
r = 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 = 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 long(bitset(v) << sh) == long(v)<<sh
maxint = sys.maxint
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 '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, range(31), range(32), range(33), randlong()):
for b in (0, 1, 2, range(31), range(32), 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 == ((long(as_) & long(bs)) == long(as_))
t = as_ < bs
assert t == (bs > as_)
assert t == ((as_ <= bs) and (as_ != bs))
assert t == ((as_ <= bs) and (long(as_) != long(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)
# print primes._indisize, primes._num_seg
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.maxint
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)
#print br
assert list(br) == range(*a)
try:
bitrange(minint,maxint,1)
except OverflowError:
pass
else:
raise '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,
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) == 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 p in pickle, cPickle:
for bin in (0, 1):
da = p.dumps(a, bin)
#print len(da), len(bitset(a))
aa = p.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 = 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(long(sys.maxint)+1)
try:
a = int(bs)
except OverflowError:
pass
else:
raise 'expected OverflowError'
assert long(bs) == long(sys.maxint)+1
# These border cases should pass
assert int(bitset(sys.maxint)) == sys.maxint
assert int(bitset(-sys.maxint - 1)) == - sys.maxint - 1
if 0:
# This was added without implementing & testing
# I have not implemented it yet.
# It is possible but I don't need to right now. / Also Notes May 19 2005
#
# Relation operation with iterable right argument,
# apparently not tested before. (Nov. 10 2004)
assert not immbitset([1,2,3]) <= [1,2]
assert not mutbitset([1,2,3]) <= [1,2]
assert not mutnodeset([1,2,3]) <= [1,2]
assert not immnodeset([1,2,3]) <= [1,2]
assert immbitset([1,2,3]) <= [1,2, 3]
assert mutbitset([1,2,3]) <= [1,2, 3]
assert immnodeset([1,2,3]) <= [1,2, 3]
assert mutnodeset([1,2,3]) <= [1,2, 3]
assert [1,2] <= immbitset([1,2,3])
assert [1,2] <= mutbitset([1,2,3])
assert [1,2] <= immnodeset([1,2,3])
assert [1,2] <= mutnodeset([1,2,3])
assert not [1,2,3] <= immbitset([1,2])
assert not [1,2,3] <= mutbitset([1,2])
assert not [1,2,3] <= immnodeset([1,2])
assert not [1,2,3] <= mutnodeset([1,2])
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):
# print p._num_seg
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 '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
if 0:
print H.add.__doc__
print H.append.__doc__
print H.discard.__doc__
print H.remove.__doc__
print H.tas.__doc__
print H.tac.__doc__
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 'no exception from append'
s.remove(e1)
try:
s.remove(e1)
except ValueError:
pass
else:
raise '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
except TypeError:
pass
else:
raise Exception, 'Expected TypeError'
ss = s=s3=la=a=b=c=x=None
locals().clear()
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, 4l)) == '{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()
#print 'len alset', len(self.alset)
V = self.V
R = self.R
P = self.P
nrefs = self.nrefs
if 0:
h = self.h
n = h.news(gc.get_objects())
print V.retset(n)
if len(n) <= 12:
l = list(n)
for i in range(len(n)):
V.enter(
lambda : P.shpaths((), l[i]).pp())
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 >>sys.stderr, (name, nref),
nrefs[name] = nref
print >>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 = range(36)
nums.remove(34)
ms = MemStat()
if 0:
clr_alset = ms.R.guppy.heapy.heapyc.clr_alset
dump_alset = ms.R.guppy.heapy.heapyc.dump_alset
#dump_alset()
i = 0
while 1:
test_nums(nums, ms.dump)
gc.collect()
if 0 and i >= 2:
dump_alset();
i += 1
#ms.dump()
def test_main():
test_nums(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))
|