# 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) # note: this is actually underestimated
print 'Size of CompactSet(range(10000)) is ', sys.getsizeof(cs.bits)
Diff to Previous Revision
--- revision 1 2011-04-17 01:37:22
+++ revision 2 2011-04-17 16:21:02
@@ -100,5 +100,5 @@
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)
+ print 'Size of set(range(10000)) is ', sys.getsizeof(s) # note: this is actually underestimated
+ print 'Size of CompactSet(range(10000)) is ', sys.getsizeof(cs.bits)
