# compact set of integers import math class CompactSet: def __init__(self, numbers = None, bits = None): self.bits = 0 if numbers: for n in numbers: self.add(n) elif bits: self.bits = bits 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(iter(self)) def isdisjoint(self, other): return ((self & other).bits == 0) def __eq__(self, other): return (self.bits == other.bits) def __ne__(self, other): return not (self == other) def issubset(self, other): return (self.union(other) == other) __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) == 1 << n) def __iter__(self): if self.bits == 0: raise StopIteration for n in range(int(math.log(self.bits, 2)) + 1): if n in self: yield n def __repr__(self): return ''.join(["CompactSet(", str(self.numbers()), ")"]) if __name__ == '__main__': import sys s = set(range(10000)) cs = CompactSet(range(10000)) print 'Size of set(range(10000)) is ', sys.getsizeof(s) print 'Size of CompactSet(range(10000)) is ', sys.getsizeof(cs)