1from __future__ import absolute_import, print_function, division
2
3try:
4    from collections.abc import MutableSet
5except ImportError:
6    # this raises an DeprecationWarning on py37 and will become
7    # an Exception in py38
8    from collections import MutableSet
9import types
10import weakref
11
12from six import string_types
13
14
15def check_deterministic(iterable):
16    # Most places where OrderedSet is used, theano interprets any exception
17    # whatsoever as a problem that an optimization introduced into the graph.
18    # If I raise a TypeError when the DestoryHandler tries to do something
19    # non-deterministic, it will just result in optimizations getting ignored.
20    # So I must use an assert here. In the long term we should fix the rest of
21    # theano to use exceptions correctly, so that this can be a TypeError.
22    if iterable is not None:
23        if not isinstance(iterable, (
24                list, tuple, OrderedSet,
25                types.GeneratorType, string_types)):
26            if len(iterable) > 1:
27                # We need to accept length 1 size to allow unpickle in tests.
28                raise AssertionError(
29                    "Get an not ordered iterable when one was expected")
30
31# Copyright (C) 2009 Raymond Hettinger
32# Permission is hereby granted, free of charge, to any person obtaining a
33# copy of this software and associated documentation files (the
34# "Software"), to deal in the Software without restriction, including
35# without limitation the rights to use, copy, modify, merge, publish,
36# distribute, sublicense, and/or sell copies of the Software, and to permit
37# persons to whom the Software is furnished to do so, subject to the
38# following conditions:
39
40# The above copyright notice and this permission notice shall be included
41# in all copies or substantial portions of the Software.
42
43# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
44# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
45# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
46# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
47# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
48# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
49# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
50# {{{ http://code.activestate.com/recipes/576696/ (r5)
51
52
53class Link(object):
54    # This make that we need to use a different pickle protocol
55    # then the default.  Othewise, there is pickling errors
56    __slots__ = 'prev', 'next', 'key', '__weakref__'
57
58    def __getstate__(self):
59        # weakref.proxy don't pickle well, so we use weakref.ref
60        # manually and don't pickle the weakref.
61        # We restore the weakref when we unpickle.
62        ret = [self.prev(), self.next()]
63        try:
64            ret.append(self.key)
65        except AttributeError:
66            pass
67        return ret
68
69    def __setstate__(self, state):
70        self.prev = weakref.ref(state[0])
71        self.next = weakref.ref(state[1])
72        if len(state) == 3:
73            self.key = state[2]
74
75
76class OrderedSet(MutableSet):
77    'Set the remembers the order elements were added'
78    # Big-O running times for all methods are the same as for regular sets.
79    # The internal self.__map dictionary maps keys to links in a doubly linked list.
80    # The circular doubly linked list starts and ends with a sentinel element.
81    # The sentinel element never gets deleted (this simplifies the algorithm).
82    # The prev/next links are weakref proxies (to prevent circular references).
83    # Individual links are kept alive by the hard reference in self.__map.
84    # Those hard references disappear when a key is deleted from an OrderedSet.
85
86    # Added by IG-- pre-existing theano code expected sets
87    #   to have this method
88    def update(self, iterable):
89        check_deterministic(iterable)
90        self |= iterable
91
92    def __init__(self, iterable=None):
93        # Checks added by IG
94        check_deterministic(iterable)
95        self.__root = root = Link()         # sentinel node for doubly linked list
96        root.prev = root.next = weakref.ref(root)
97        self.__map = {}                     # key --> link
98        if iterable is not None:
99            self |= iterable
100
101    def __len__(self):
102        return len(self.__map)
103
104    def __contains__(self, key):
105        return key in self.__map
106
107    def add(self, key):
108        # Store new key in a new link at the end of the linked list
109        if key not in self.__map:
110            self.__map[key] = link = Link()
111            root = self.__root
112            last = root.prev
113            link.prev, link.next, link.key = last, weakref.ref(root), key
114            last().next = root.prev = weakref.ref(link)
115
116    def union(self, s):
117        check_deterministic(s)
118        n = self.copy()
119        for elem in s:
120            if elem not in n:
121                n.add(elem)
122        return n
123
124    def intersection_update(self, s):
125        l = []
126        for elem in self:
127            if elem not in s:
128                l.append(elem)
129        for elem in l:
130            self.remove(elem)
131        return self
132
133    def difference_update(self, s):
134        check_deterministic(s)
135        for elem in s:
136            if elem in self:
137                self.remove(elem)
138        return self
139
140    def copy(self):
141        n = OrderedSet()
142        n.update(self)
143        return n
144
145    def discard(self, key):
146        # Remove an existing item using self.__map to find the link which is
147        # then removed by updating the links in the predecessor and successors.
148        if key in self.__map:
149            link = self.__map.pop(key)
150            link.prev().next = link.next
151            link.next().prev = link.prev
152
153    def __iter__(self):
154        # Traverse the linked list in order.
155        root = self.__root
156        curr = root.next()
157        while curr is not root:
158            yield curr.key
159            curr = curr.next()
160
161    def __reversed__(self):
162        # Traverse the linked list in reverse order.
163        root = self.__root
164        curr = root.prev()
165        while curr is not root:
166            yield curr.key
167            curr = curr.prev()
168
169    def pop(self, last=True):
170        if not self:
171            raise KeyError('set is empty')
172        if last:
173            key = next(reversed(self))
174        else:
175            key = next(iter(self))
176        self.discard(key)
177        return key
178
179    def __repr__(self):
180        if not self:
181            return '%s()' % (self.__class__.__name__,)
182        return '%s(%r)' % (self.__class__.__name__, list(self))
183
184    def __eq__(self, other):
185        # Note that we implement only the comparison to another
186        # `OrderedSet`, and not to a regular `set`, because otherwise we
187        # could have a non-symmetric equality relation like:
188        #       my_ordered_set == my_set and my_set != my_ordered_set
189        if isinstance(other, OrderedSet):
190            return len(self) == len(other) and list(self) == list(other)
191        elif isinstance(other, set):
192            # Raise exception to avoid confusion.
193            raise TypeError(
194                'Cannot compare an `OrderedSet` to a `set` because '
195                'this comparison cannot be made symmetric: please '
196                'manually cast your `OrderedSet` into `set` before '
197                'performing this comparison.')
198        else:
199            return NotImplemented
200
201# end of http://code.activestate.com/recipes/576696/ }}}
202
203if __name__ == '__main__':
204    print(list(OrderedSet('abracadaba')))
205    print(list(OrderedSet('simsalabim')))
206    print(OrderedSet('boom') == OrderedSet('moob'))
207    print(OrderedSet('boom') == 'moob')
208