관리-도구

편집 파일: test.py

# 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 |= 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))