1""" 2 3Available at repository https://github.com/LuminosoInsight/ordered-set 4 5 salt.utils.oset 6 ~~~~~~~~~~~~~~~~ 7 8An OrderedSet is a custom MutableSet that remembers its order, so that every 9entry has an index that can be looked up. 10 11Based on a recipe originally posted to ActiveState Recipes by Raymond Hettiger, 12and released under the MIT license. 13 14Rob Speer's changes are as follows: 15 16 - changed the content from a doubly-linked list to a regular Python list. 17 Seriously, who wants O(1) deletes but O(N) lookups by index? 18 - add() returns the index of the added item 19 - index() just returns the index of an item 20 - added a __getstate__ and __setstate__ so it can be pickled 21 - added __getitem__ 22""" 23 24from collections.abc import MutableSet 25 26SLICE_ALL = slice(None) 27__version__ = "2.0.1" 28 29 30def is_iterable(obj): 31 """ 32 Are we being asked to look up a list of things, instead of a single thing? 33 We check for the `__iter__` attribute so that this can cover types that 34 don't have to be known by this module, such as NumPy arrays. 35 36 Strings, however, should be considered as atomic values to look up, not 37 iterables. The same goes for tuples, since they are immutable and therefore 38 valid entries. 39 40 We don't need to check for the Python 2 `unicode` type, because it doesn't 41 have an `__iter__` attribute anyway. 42 """ 43 return ( 44 hasattr(obj, "__iter__") 45 and not isinstance(obj, str) 46 and not isinstance(obj, tuple) 47 ) 48 49 50class OrderedSet(MutableSet): 51 """ 52 An OrderedSet is a custom MutableSet that remembers its order, so that 53 every entry has an index that can be looked up. 54 """ 55 56 def __init__(self, iterable=None): 57 self.items = [] 58 self.map = {} 59 if iterable is not None: 60 self |= iterable 61 62 def __len__(self): 63 return len(self.items) 64 65 def __getitem__(self, index): 66 """ 67 Get the item at a given index. 68 69 If `index` is a slice, you will get back that slice of items. If it's 70 the slice [:], exactly the same object is returned. (If you want an 71 independent copy of an OrderedSet, use `OrderedSet.copy()`.) 72 73 If `index` is an iterable, you'll get the OrderedSet of items 74 corresponding to those indices. This is similar to NumPy's 75 "fancy indexing". 76 """ 77 if index == SLICE_ALL: 78 return self 79 elif hasattr(index, "__index__") or isinstance(index, slice): 80 result = self.items[index] 81 if isinstance(result, list): 82 return OrderedSet(result) 83 else: 84 return result 85 elif is_iterable(index): 86 return OrderedSet([self.items[i] for i in index]) 87 else: 88 raise TypeError( 89 "Don't know how to index an OrderedSet by {}".format(repr(index)) 90 ) 91 92 def copy(self): 93 return OrderedSet(self) 94 95 def __getstate__(self): 96 if not self.items: 97 # The state can't be an empty list. 98 # We need to return a truthy value, or else __setstate__ won't be run. 99 # 100 # This could have been done more gracefully by always putting the state 101 # in a tuple, but this way is backwards- and forwards- compatible with 102 # previous versions of OrderedSet. 103 return (None,) 104 else: 105 return list(self) 106 107 def __setstate__(self, state): 108 if state == (None,): 109 self.__init__([]) 110 else: 111 self.__init__(state) 112 113 def __contains__(self, key): 114 return key in self.map 115 116 def add(self, key): # pylint: disable=arguments-differ 117 """ 118 Add `key` as an item to this OrderedSet, then return its index. 119 120 If `key` is already in the OrderedSet, return the index it already 121 had. 122 """ 123 if key not in self.map: 124 self.map[key] = len(self.items) 125 self.items.append(key) 126 return self.map[key] 127 128 append = add 129 130 def update(self, sequence): 131 """ 132 Update the set with the given iterable sequence, then return the index 133 of the last element inserted. 134 """ 135 item_index = None 136 try: 137 for item in sequence: 138 item_index = self.add(item) 139 except TypeError: 140 raise ValueError( 141 "Argument needs to be an iterable, got {}".format(type(sequence)) 142 ) 143 return item_index 144 145 def index(self, key): 146 """ 147 Get the index of a given entry, raising an IndexError if it's not 148 present. 149 150 `key` can be an iterable of entries that is not a string, in which case 151 this returns a list of indices. 152 """ 153 if is_iterable(key): 154 return [self.index(subkey) for subkey in key] 155 return self.map[key] 156 157 def pop(self): 158 """ 159 Remove and return the last element from the set. 160 161 Raises KeyError if the set is empty. 162 """ 163 if not self.items: 164 raise KeyError("Set is empty") 165 166 elem = self.items[-1] 167 del self.items[-1] 168 del self.map[elem] 169 return elem 170 171 def discard(self, key): # pylint: disable=arguments-differ 172 """ 173 Remove an element. Do not raise an exception if absent. 174 175 The MutableSet mixin uses this to implement the .remove() method, which 176 *does* raise an error when asked to remove a non-existent item. 177 """ 178 if key in self: 179 i = self.map[key] 180 del self.items[i] 181 del self.map[key] 182 for k, v in self.map.items(): 183 if v >= i: 184 self.map[k] = v - 1 185 186 def clear(self): 187 """ 188 Remove all items from this OrderedSet. 189 """ 190 del self.items[:] 191 self.map.clear() 192 193 def __iter__(self): 194 return iter(self.items) 195 196 def __reversed__(self): 197 return reversed(self.items) 198 199 def __repr__(self): 200 if not self: 201 return "{}()".format(self.__class__.__name__) 202 return "{}({})".format(self.__class__.__name__, repr(list(self))) 203 204 def __eq__(self, other): 205 if isinstance(other, OrderedSet): 206 return len(self) == len(other) and self.items == other.items 207 try: 208 other_as_set = set(other) 209 except TypeError: 210 # If `other` can't be converted into a set, it's not equal. 211 return False 212 else: 213 return set(self) == other_as_set 214