Representing a set in a compact way (Python recipe) by jimmy2times

ActiveState Code (http://code.activestate.com/recipes/577660/)

class CompactSet:

    def __init__(self, numbers = None, bits = None):
        self.bits = bits or 0       
        if numbers:
            for n in numbers:
                self.add(n)

    def add(self, n):
        self.bits |= 1 << n

    def remove(self, n):
        self.bits &= ~(1 << n)

    def clear(self):
        self.bits = 0

    def union(self, other):
        return CompactSet(bits = self.bits | other.bits)

    __or__ = union

    def intersection(self, other):
        return CompactSet(bits = self.bits & other.bits)

    __and__ = intersection

    def difference(self, other):
        return CompactSet(bits = self.bits & ~other.bits)

    __sub__ = difference
    
    def union_update(self, other):
        self.bits |= other.bits

    def intersection_update(self, other):
        self.bits &= other.bits

    def difference_update(self, other):
        self.bits &= ~other.bits

    def numbers(self):
        return list(self)

    def isdisjoint(self, other):
        return not (self.bits & other.bits)
    
    def __eq__(self, other):
        return (self.bits == other.bits)

    def __ne__(self, other):
        return not (self == other)

    def issubset(self, other):
        return (self.bits | other.bits == other.bits)

    __le__ = issubset

    def issuperset(self, other):
        return (other <= self)

    __ge__ = issuperset
    
    def __lt__(self, other):
        return (self <= other and self != other)

    def __gt__(self, other):
        return (other < self)

    def __len__(self):
        bits = self.bits
        count = 0
        while bits:
            bits &= bits - 1
            count += 1
        return count
        
    def __contains__(self, n):
        return self.bits & (1 << n)

    def __iter__(self):
        if self.bits == 0:
            raise StopIteration
        mask = 1
        for n in range(self.bits.bit_length()):
            if self.bits & mask:
                yield n
            mask <<= 1
        
    def __repr__(self):
        return ''.join(["CompactSet(", str(self.numbers()), ")"])


if __name__ == '__main__':

    s = CompactSet([3, 7, 10])
    t = CompactSet([5, 2, 3])

    assert 7 in s
    assert s & t
    assert s | t == CompactSet([2, 3, 5, 7, 10])

    s.remove(3)
    assert not s & t

    assert CompactSet([2, 3]) < t

    print 'OK'
    

    import sys
    
    s = set(xrange(10000))
    cs = CompactSet(xrange(10000))
    print 'Size of set(xrange(10000)) is ', sys.getsizeof(s) # this is actually underestimated
    print 'Size of CompactSet(xrange(10000)) is ', sys.getsizeof(cs.bits)