1# From: https://github.com/ActiveState/code/blob/master/recipes/Python/576696_OrderedSet_with_Weakrefs/  # noqa
2
3from weakref import proxy
4
5try:
6    import collections.abc as collections_abc
7except ImportError:
8    import collections as collections_abc
9
10
11class Link(object):
12    __slots__ = 'prev', 'next', 'key', '__weakref__'
13
14
15class OrderedSet(collections_abc.MutableSet):
16    'Set the remembers the order elements were added'
17    # Big-O running times for all methods are the same as for regular sets.
18    # The internal self.__map dictionary maps keys to links in a doubly linked
19    # list. The circular doubly linked list starts and ends with a sentinel
20    # element. The sentinel element never gets deleted (this simplifies the
21    # algorithm). The prev/next links are weakref proxies (to prevent circular
22    # references). Individual links are kept alive by the hard reference in
23    # self.__map. Those hard references disappear when a key is deleted from
24    # an OrderedSet.
25
26    def __init__(self, iterable=None):
27        self.__root = root = Link()  # sentinel node for doubly linked list
28        root.prev = root.next = root
29        self.__map = {}  # key --> link
30        if iterable is not None:
31            self |= iterable
32
33    def __len__(self):
34        return len(self.__map)
35
36    def __contains__(self, key):
37        return key in self.__map
38
39    def add(self, key):
40        # Store new key in a new link at the end of the linked list
41        if key not in self.__map:
42            self.__map[key] = link = Link()
43            root = self.__root
44            last = root.prev
45            link.prev, link.next, link.key = last, root, key
46            last.next = root.prev = proxy(link)
47
48    def discard(self, key):
49        # Remove an existing item using self.__map to find the link which is
50        # then removed by updating the links in the predecessor and successors.
51        if key in self.__map:
52            link = self.__map.pop(key)
53            link.prev.next = link.next
54            link.next.prev = link.prev
55
56    def __iter__(self):
57        # Traverse the linked list in order.
58        root = self.__root
59        curr = root.next
60        while curr is not root:
61            yield curr.key
62            curr = curr.next
63
64    def __reversed__(self):
65        # Traverse the linked list in reverse order.
66        root = self.__root
67        curr = root.prev
68        while curr is not root:
69            yield curr.key
70            curr = curr.prev
71
72    def pop(self, last=True):
73        if not self:
74            raise KeyError('set is empty')
75        key = next(reversed(self)) if last else next(iter(self))
76        self.discard(key)
77        return key
78
79    def __repr__(self):
80        if not self:
81            return '%s()' % (self.__class__.__name__,)
82        return '%s(%r)' % (self.__class__.__name__, list(self))
83
84    def __str__(self):
85        return self.__repr__()
86
87    def __eq__(self, other):
88        if isinstance(other, OrderedSet):
89            return len(self) == len(other) and list(self) == list(other)
90        return not self.isdisjoint(other)
91