1""" 2 :codeauthor: Pedro Algarvio (pedro@algarvio.me) 3 4 5 salt.utils.odict 6 ~~~~~~~~~~~~~~~~ 7 8 This is a compatibility/"importability" layer for an ordered dictionary. 9 Tries to import from the standard library if python >= 2.7, then from the 10 ``ordereddict`` package available from PyPi, and, as a last resort, 11 provides an ``OrderedDict`` implementation based on:: 12 13 http://code.activestate.com/recipes/576669/ 14 15 It also implements a DefaultOrderedDict Class that serves as a 16 combination of ``OrderedDict`` and ``defaultdict`` 17 It's source was submitted here:: 18 19 http://stackoverflow.com/questions/6190331/ 20""" 21 22 23from collections.abc import Callable 24 25try: 26 # pylint: disable=E0611,minimum-python-version 27 import collections 28 29 class OrderedDict(collections.OrderedDict): 30 __hash__ = None 31 32 33except (ImportError, AttributeError): 34 try: 35 import ordereddict 36 37 class OrderedDict(ordereddict.OrderedDict): # pylint: disable=W0232 38 __hash_ = None 39 40 except ImportError: 41 # {{{ http://code.activestate.com/recipes/576693/ (r9) 42 # Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy. 43 # Passes Python2.7's test suite and incorporates all the latest updates. 44 45 try: 46 from _thread import get_ident as _get_ident 47 except ImportError: 48 from _dummy_thread import get_ident as _get_ident 49 50 # try: 51 # from _abcoll import KeysView, ValuesView, ItemsView 52 # except ImportError: 53 # pass 54 55 class OrderedDict(dict): 56 "Dictionary that remembers insertion order" 57 # An inherited dict maps keys to values. 58 # The inherited dict provides __getitem__, __len__, __contains__, and get. 59 # The remaining methods are order-aware. 60 # Big-O running times for all methods are the same as for regular dictionaries. 61 62 # The internal self.__map dictionary maps keys to links in a doubly linked list. 63 # The circular doubly linked list starts and ends with a sentinel element. 64 # The sentinel element never gets deleted (this simplifies the algorithm). 65 # Each link is stored as a list of length three: [PREV, NEXT, KEY]. 66 __hash_ = None 67 68 def __init__(self, *args, **kwds): # pylint: disable=E1003 69 """Initialize an ordered dictionary. Signature is the same as for 70 regular dictionaries, but keyword arguments are not recommended 71 because their insertion order is arbitrary. 72 73 """ 74 super().__init__() 75 if len(args) > 1: 76 raise TypeError( 77 "expected at most 1 arguments, got {}".format(len(args)) 78 ) 79 try: 80 self.__root 81 except AttributeError: 82 self.__root = root = [] # sentinel node 83 root[:] = [root, root, None] 84 self.__map = {} 85 self.__update(*args, **kwds) 86 87 def __setitem__(self, key, value, dict_setitem=dict.__setitem__): 88 "od.__setitem__(i, y) <==> od[i]=y" 89 # Setting a new item creates a new link which goes at the end of the linked 90 # list, and the inherited dictionary is updated with the new key/value pair. 91 if key not in self: 92 root = self.__root 93 last = root[0] 94 last[1] = root[0] = self.__map[key] = [last, root, key] 95 dict_setitem(self, key, value) 96 97 def __delitem__(self, key, dict_delitem=dict.__delitem__): 98 "od.__delitem__(y) <==> del od[y]" 99 # Deleting an existing item uses self.__map to find the link which is 100 # then removed by updating the links in the predecessor and successor nodes. 101 dict_delitem(self, key) 102 link_prev, link_next, key = self.__map.pop(key) 103 link_prev[1] = link_next 104 link_next[0] = link_prev 105 106 def __iter__(self): 107 "od.__iter__() <==> iter(od)" 108 root = self.__root 109 curr = root[1] 110 while curr is not root: 111 yield curr[2] 112 curr = curr[1] 113 114 def __reversed__(self): 115 "od.__reversed__() <==> reversed(od)" 116 root = self.__root 117 curr = root[0] 118 while curr is not root: 119 yield curr[2] 120 curr = curr[0] 121 122 def clear(self): 123 "od.clear() -> None. Remove all items from od." 124 try: 125 for node in self.__map.values(): 126 del node[:] 127 root = self.__root 128 root[:] = [root, root, None] 129 self.__map.clear() 130 except AttributeError: 131 pass 132 dict.clear(self) 133 134 def popitem(self, last=True): 135 """od.popitem() -> (k, v), return and remove a (key, value) pair. 136 Pairs are returned in LIFO order if last is true or FIFO order if false. 137 138 """ 139 if not self: 140 raise KeyError("dictionary is empty") 141 root = self.__root 142 if last: 143 link = root[0] 144 link_prev = link[0] 145 link_prev[1] = root 146 root[0] = link_prev 147 else: 148 link = root[1] 149 link_next = link[1] 150 root[1] = link_next 151 link_next[0] = root 152 key = link[2] 153 del self.__map[key] 154 value = dict.pop(self, key) 155 return key, value 156 157 # -- the following methods do not depend on the internal structure -- 158 159 def keys(self): 160 "od.keys() -> list of keys in od" 161 return list(self) 162 163 def values(self): 164 "od.values() -> list of values in od" 165 return [self[key] for key in self] 166 167 def items(self): 168 "od.items() -> list of (key, value) pairs in od" 169 return [(key, self[key]) for key in self] 170 171 def iterkeys(self): 172 "od.iterkeys() -> an iterator over the keys in od" 173 return iter(self) 174 175 def itervalues(self): 176 "od.itervalues -> an iterator over the values in od" 177 for k in self: 178 yield self[k] 179 180 def iteritems(self): 181 "od.iteritems -> an iterator over the (key, value) items in od" 182 for k in self: 183 yield (k, self[k]) 184 185 def update(*args, **kwds): # pylint: disable=E0211 186 """od.update(E, **F) -> None. Update od from dict/iterable E and F. 187 188 If E is a dict instance, does: for k in E: od[k] = E[k] 189 If E has a .keys() method, does: for k in E.keys(): od[k] = E[k] 190 Or if E is an iterable of items, does: for k, v in E: od[k] = v 191 In either case, this is followed by: for k, v in F.items(): od[k] = v 192 193 """ 194 if len(args) > 2: 195 raise TypeError( 196 "update() takes at most 2 positional " 197 "arguments ({} given)".format(len(args)) 198 ) 199 elif not args: 200 raise TypeError("update() takes at least 1 argument (0 given)") 201 self = args[0] 202 # Make progressively weaker assumptions about "other" 203 other = () 204 if len(args) == 2: 205 other = args[1] 206 if isinstance(other, dict): 207 for key in other: 208 self[key] = other[key] 209 elif hasattr(other, "keys"): 210 for key in other: 211 self[key] = other[key] 212 else: 213 for key, value in other: 214 self[key] = value 215 for key, value in kwds.items(): 216 self[key] = value 217 218 __update = ( 219 update # let subclasses override update without breaking __init__ 220 ) 221 222 __marker = object() 223 224 def pop(self, key, default=__marker): 225 """od.pop(k[,d]) -> v, remove specified key and return the corresponding value. 226 If key is not found, d is returned if given, otherwise KeyError is raised. 227 228 """ 229 if key in self: 230 result = self[key] 231 del self[key] 232 return result 233 if default is self.__marker: 234 raise KeyError(key) 235 return default 236 237 def setdefault(self, key, default=None): 238 "od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od" 239 if key in self: 240 return self[key] 241 self[key] = default 242 return default 243 244 def __repr__(self, _repr_running={}): # pylint: disable=W0102 245 "od.__repr__() <==> repr(od)" 246 call_key = id(self), _get_ident() 247 if call_key in _repr_running: 248 return "..." 249 _repr_running[call_key] = 1 250 try: 251 if not self: 252 return "{}()".format(self.__class__.__name__) 253 return "{}('{}')".format( 254 self.__class__.__name__, list(self.items()) 255 ) 256 finally: 257 del _repr_running[call_key] 258 259 def __reduce__(self): 260 "Return state information for pickling" 261 items = [[k, self[k]] for k in self] 262 inst_dict = vars(self).copy() 263 for k in vars(OrderedDict()): 264 inst_dict.pop(k, None) 265 if inst_dict: 266 return (self.__class__, (items,), inst_dict) 267 return self.__class__, (items,) 268 269 def copy(self): 270 "od.copy() -> a shallow copy of od" 271 return self.__class__(self) 272 273 @classmethod 274 def fromkeys(cls, iterable, value=None): 275 """OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S 276 and values equal to v (which defaults to None). 277 278 """ 279 d = cls() 280 for key in iterable: 281 d[key] = value 282 return d 283 284 def __eq__(self, other): 285 """od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive 286 while comparison to a regular mapping is order-insensitive. 287 288 """ 289 if isinstance(other, OrderedDict): 290 return len(self) == len(other) and self.items() == other.items() 291 return dict.__eq__(self, other) 292 293 def __ne__(self, other): 294 return not self == other 295 296 297# # -- the following methods are only used in Python 2.7 -- 298# 299# def viewkeys(self): 300# "od.viewkeys() -> a set-like object providing a view on od's keys" 301# return KeysView(self) 302# 303# def viewvalues(self): 304# "od.viewvalues() -> an object providing a view on od's values" 305# return ValuesView(self) 306# 307# def viewitems(self): 308# "od.viewitems() -> a set-like object providing a view on od's items" 309# return ItemsView(self) 310# ## end of http://code.activestate.com/recipes/576693/ }}} 311 312 313class DefaultOrderedDict(OrderedDict): 314 """ 315 Dictionary that remembers insertion order 316 """ 317 318 def __init__(self, default_factory=None, *a, **kw): 319 if default_factory is not None and not isinstance(default_factory, Callable): 320 raise TypeError("first argument must be callable") 321 super().__init__(*a, **kw) 322 self.default_factory = default_factory 323 324 def __getitem__(self, key): 325 try: 326 return OrderedDict.__getitem__(self, key) 327 except KeyError: 328 return self.__missing__(key) 329 330 def __missing__(self, key): 331 if self.default_factory is None: 332 raise KeyError(key) 333 self[key] = value = self.default_factory() 334 return value 335 336 def __reduce__(self): 337 if self.default_factory is None: 338 args = tuple() 339 else: 340 args = (self.default_factory,) 341 return type(self), args, None, None, self.items() 342 343 def copy(self): 344 return self.__copy__() 345 346 def __copy__(self): 347 return type(self)(self.default_factory, self) 348 349 def __deepcopy__(self): 350 import copy 351 352 return type(self)(self.default_factory, copy.deepcopy(self.items())) 353 354 def __repr__(self, _repr_running={}): # pylint: disable=W0102 355 return "DefaultOrderedDict({}, {})".format( 356 self.default_factory, super().__repr__() 357 ) 358