Skip to content

Instantly share code, notes, and snippets.

@agfor
Created April 23, 2012 23:18
Show Gist options
  • Save agfor/2474465 to your computer and use it in GitHub Desktop.
Save agfor/2474465 to your computer and use it in GitHub Desktop.
Several Ordered Set implementations I wrote after seeing a question about them on Stack Overflow
from collections import OrderedDict
class OrderedSet(object):
def __init__(self, iterable = None):
self.storage = OrderedDict()
if iterable:
self.storage.update((elem, True) for elem in iterable)
def __contains__(self, elem):
return elem in self.storage
def __iter__(self):
return iter(self.storage)
def __len__(self):
return len(self.storage)
def isdisjoint(self, other):
return any(elem in other for elem in self)
def issubset(self, other):
return all(elem in other for elem in self)
__le__ = issubset
def __lt__(self, other):
return self <= other and len(self) != len(other)
def issuperset(self, other):
return all(elem in self for elem in other)
__ge__ = issuperset
def __gt__(self, other):
return self >= other and len(self) != len(other)
def copy(self):
return OrderedSet(self)
def update(self, *others):
for other in others:
for elem in other:
self.add(elem)
__ior__ = update
def intersection_update(self, *others):
for elem in self:
if any(elem not in other for other in others):
self.discard(elem)
__iand__ = intersection_update
def difference_update(self, *others):
for elem in self:
if any(elem in other for other in others):
self.discard(elem)
__isub__ = difference_update
def symmetric_difference_update(self, other):
new = other.difference(self)
self.difference_update(other)
self.update(new)
__ixor__ = symmetric_difference_update
def _copying(method, name):
def operation(self, *others):
new = self.copy()
getattr(cls, method)(new, *others)
return new
operation.__name__= name
return operation
union = _copying('update', 'union')
__or__ = union
intersection = _copying('intersection_update', 'intersection')
__and__ = intersection
difference = _copying('difference_update', 'difference')
__sub__ = difference
def symmetric_difference(self, other):
new = self.difference(other)
new.update(other.difference(self))
return new
__xor__ = symmetric_difference
def add(self, elem):
self.storage[elem] = True
def discard(self, elem):
self.storage.pop(elem, None)
def remove(self, elem):
del self.storage[elem]
def popelem(self, last=True):
return self.storage.popitem(last)[0]
def __eq__(self, other):
return len(self) == len(other) and all(mine == yours for mine, yours in zip(self, other))
def __ne__(self, other):
return not self == other
def __repr__(self):
return 'OrderedSet([{}])'.format(', '.join(repr(elem) for elem in self.storage))
if __name__ == '__main__':
a = OrderedSet()
b = OrderedSet((1,))
print a <= b
print a >= b
from itertools import count, izip
from collections import OrderedDict, Set
class IndexOrderedSet(Set):
"""An OrderedFrozenSet-like object
Allows constant time 'index'ing
But doesn't allow you to remove elements"""
def __init__(self, iterable = ()):
self.count = count()
self.dict = OrderedDict(izip(iterable, self.count))
def add(self, elem):
if elem not in self:
self.dict[elem] = next(self.count)
def index(self, elem):
return self.dict[elem]
def __contains__(self, elem):
return elem in self.dict
def __len__(self):
return len(self.dict)
def __iter__(self):
return iter(self.dict)
def __repr__(self):
return '{}({})'.format(self.__class__.__name__, list(self))
if __name__ == '__main__':
a = IndexOrderedSet(('hello', 'my', 'name', 'is', 'Adam'))
assert ('hello' in a, a.add('me'), len(a), a.index('is')) == (True, None, 6, 3)
assert repr(a) == "IndexOrderedSet(['hello', 'my', 'name', 'is', 'Adam', 'me'])"
assert tuple(a) == ('hello', 'my', 'name', 'is', 'Adam', 'me')
from itertools import count
from itertools import izip, ifilterfalse # only needed for 'update'
from collections import OrderedDict, Set
class IndexOrderedSet(Set, OrderedDict):
"""Allows constant time 'index'ing and adding of items
But doesn't allow you to remove elements"""
def __init__(self, iterable = ()):
self.count = count()
OrderedDict.__init__(self)
self.update(iterable)
def add(self, elem):
if elem not in self:
self[elem] = next(self.count)
def update(self, iterable):
OrderedDict.update(self, izip(ifilterfalse(self.__contains__, iterable), self.count))
index = OrderedDict.__getitem__
__len__ = OrderedDict.__len__
__contains__ = OrderedDict.__contains__
__iter__ = OrderedDict.__iter__
clear = pop = popitem = setdefault = fromkeys = __delitem__ = __cmp__ = None
def __repr__(self):
return '{}({})'.format(self.__class__.__name__, list(self))
if __name__ == '__main__':
a = IndexOrderedSet(('hello', 'my', 'my', 'name'))
a.update(('is', 'my', 'is'))
a.add('me')
assert ('is' in a, len(a), a.index('my')) == (True, 5, 1)
assert repr(a) == "IndexOrderedSet(['hello', 'my', 'name', 'is', 'me'])"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment