D7net
Home
Console
Upload
information
Create File
Create Folder
About
Tools
:
/
proc
/
self
/
root
/
opt
/
cloudlinux
/
venv
/
lib64
/
python3.11
/
site-packages
/
guppy
/
sets
/
Filename :
test.py
back
Copy
# 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 len(ns) == 1 assert ns.pop() is a try: ns.pop() except ValueError: pass else: raise AssertionError('expected ValueError') assert len(ns) == 0 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))