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)
Diff to Previous Revision
--- revision 4 2011-04-21 13:45:16
+++ revision 5 2011-04-24 10:55:45
@@ -112,5 +112,5 @@
s = set(xrange(10000))
cs = CompactSet(xrange(10000))
- print 'Size of set(xrange(10000)) is ', sys.getsizeof(s)
+ 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)
