Welcome, guest | Sign In | My Account | Store | Cart
```import collections
from weakref import proxy

__slots__ = 'prev', 'next', 'key', '__weakref__'

class OrderedSet(collections.MutableSet):
'Set the remembers the order elements were added'
# Big-O running times for all methods are the same as for regular sets.
# The internal self.__map dictionary maps keys to links in a doubly linked list.
# The circular doubly linked list starts and ends with a sentinel element.
# The sentinel element never gets deleted (this simplifies the algorithm).
# The prev/next links are weakref proxies (to prevent circular references).
# Individual links are kept alive by the hard reference in self.__map.
# Those hard references disappear when a key is deleted from an OrderedSet.

def __init__(self, iterable=None):
self.__root = root = Link()         # sentinel node for doubly linked list
root.prev = root.next = root
self.__map = {}                     # key --> link
if iterable is not None:
self |= iterable

def __len__(self):
return len(self.__map)

def __contains__(self, key):
return key in self.__map

# Store new key in a new link at the end of the linked list
if key not in self.__map:
root = self.__root
last = root.prev

# Remove an existing item using self.__map to find the link which is
# then removed by updating the links in the predecessor and successors.
if key in self.__map:

def __iter__(self):
# Traverse the linked list in order.
root = self.__root
curr = root.next
while curr is not root:
yield curr.key
curr = curr.next

def __reversed__(self):
# Traverse the linked list in reverse order.
root = self.__root
curr = root.prev
while curr is not root:
yield curr.key
curr = curr.prev

def pop(self, last=True):
if not self:
raise KeyError('set is empty')
key = next(reversed(self)) if last else next(iter(self))
return key

def __repr__(self):
if not self:
return '%s()' % (self.__class__.__name__,)
return '%s(%r)' % (self.__class__.__name__, list(self))

def __eq__(self, other):
if isinstance(other, OrderedSet):
return len(self) == len(other) and list(self) == list(other)
return not self.isdisjoint(other)
```

### History

• revision 5 (14 years ago)
• previous revisions are not available