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