#!/usr/bin/env python
import weakref
class OrderedSet(object):
"""
A linked-list with a uniqueness constraint and O(1) lookups/removal.
Modification during iteration is partially supported. If you
remove the just yielded element, it will go on to what was the
next element. If you remove the next element, it will use the
new next element. If you remove both, you get an error.
"""
def __init__(self, iterable=(), allow_move=True):
self._map = {}
self._start = _SentinalNode()
self._end = _SentinalNode()
self._start.next = self._end
self._end.prev = self._start
self._allow_move = allow_move
self.extend(iterable)
def __contains__(self, element):
return element in self._map
def __eq__(self, other):
raise TypeError("OrderedSet does not support comparisons")
def __hash__(self):
raise TypeError("OrderedSet is not hashable")
def __iter__(self):
curnode = self._start
nextnode = curnode.next
while True:
if hasattr(curnode, 'next'):
curnode = curnode.next
elif hasattr(nextnode, 'next'):
curnode = nextnode
else:
raise RuntimeError("OrderedSet modified inappropriately "
"during iteration")
if type(curnode) is _SentinalNode:
return
nextnode = curnode.next
yield curnode.content
def __reversed__(self):
curnode = self._end
prevnode = curnode.prev
while True:
if hasattr(curnode, 'prev'):
curnode = curnode.prev
elif hasattr(prevnode, 'prev'):
curnode = prevnode
else:
raise RuntimeError("OrderedSet modified inappropriately "
"during iteration")
if type(curnode) is _SentinalNode:
return
prevnode = curnode.prev
yield curnode.content
def __len__(self):
return len(self._map)
def __repr__(self):
return '%s(%r)' % (self.__class__.__name__, list(self))
def append(self, element):
"""Add an element to the right side of the OrderedSet."""
self._insertatnode(self._end.prev, element)
def appendleft(self, element):
"""Add an element to the left side of the OrderedSet."""
self._insertatnode(self._start, element)
def clear(self):
"""Remove all elements from the OrderedSet."""
while self:
self.pop()
def extend(self, iterable):
"""Extend the right side of the OrderedSet with elements from the iterable."""
for element in iterable:
self.append(element)
def extendleft(self, iterable):
"""Extend the left side of the OrderedSet with elements from the iterable."""
for element in iterable:
self.appendleft(element)
def insertleft(self, poselement, element):
"""Inserts element immediately left of poselement's position."""
self._insertatnode(self._map[poselement].prev, element)
def insertright(self, poselement, element):
"""Inserts element immediately right of poselement's position."""
self._insertatnode(self._map[poselement], element)
def _insertatnode(self, node, element):
left = node
right = node.next
if element in self._map:
if self._allow_move:
self.remove(element)
else:
raise ValueError("element already exists")
newnode = _Node()
newnode.content = element
newnode.prev = right.prev
newnode.next = right
right.prev = newnode
left.next = newnode
self._map[element] = newnode
def pop(self):
"""Remove and return the rightmost element."""
element = self._end.prev.content
self.remove(element)
return element
def popleft(self):
"""Remove and return the leftmost element."""
element = self._start.next.content
self.remove(element)
return element
def remove(self, element):
"""Remove element from the OrderedSet."""
node = self._map.pop(element)
assert type(node) is not _SentinalNode
left = node.prev
right = node.next
left.next = right
right.prev = node.prev
del node.prev
del node.next
class _Node(object):
__slots__ = '_prev', 'next', 'content', '__weakref__'
# A weakref is used for prev so as to avoid creating cycles.
def _prev_get(self):
return self._prev()
def _prev_set(self, value):
self._prev = weakref.ref(value)
def _prev_del(self):
del self._prev
prev = property(_prev_get, _prev_set, _prev_del)
class _SentinalNode(_Node):
__slots__ = []
__test__ = {
'__foo__': """
>>> OrderedSet(range(10))
OrderedSet([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> list(reversed(OrderedSet(range(10))))
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> stuff = OrderedSet()
>>> stuff.extendleft(range(20, 25))
>>> stuff.pop()
20
>>> stuff
OrderedSet([24, 23, 22, 21])
>>> stuff.insertleft(23, 99)
>>> stuff
OrderedSet([24, 99, 23, 22, 21])
>>> stuff.remove(21)
>>> stuff
OrderedSet([24, 99, 23, 22])
>>> len(stuff)
4
>>> 23 in stuff
True
>>> 44 in stuff
False
>>> OrderedSet([1, 2, 3, 2])
OrderedSet([1, 3, 2])
>>> OrderedSet([1, 2, 3, 2], allow_move=False)
Traceback (most recent call last):
...
ValueError: element already exists
""",
}
def _test():
import doctest
doctest.testmod()
if __name__ == '__main__':
_test()
