1""" 2Ordered dictionary class with more flexible initialization and convenience methods. 3 4 5Modified 2007-2015 by Samuel M Smith 6 7Modifications CopyRight 2007-2015 by Samuel M smith 8 9Based on various ordered dict implementations found in the wild 10 11""" 12from __future__ import absolute_import, division, print_function 13 14from .sixing import * 15 16 17class odict(dict): 18 """ 19 Dictionary whose keys maintain the order they are added to the dict. Not 20 order they are updated. 21 22 Similar to the collections OrderedDict but with more flexible initialization 23 and additional methods. 24 25 The first key added to the dictionary is the first key in .keys() 26 Changing the value of a key does not affect the order of the key 27 28 """ 29 __slots__ = ['_keys'] 30 31 def __new__(cls, *args, **kwargs): 32 self = dict.__new__(cls,*args, **kwargs) 33 self._keys = [] 34 return self 35 36 def __init__(self, *pa, **kwa): 37 """ 38 Create new empty odict 39 odict() returns new empty dictionary. 40 41 odict(pa1, pa2, ...) creates new dictionary from 42 pa = tuple of positional args, (pa1, pa2, ...) 43 44 d = {} 45 for a in pa: 46 if hasattr(a,'get'): 47 for k, v in a.items(): 48 d[k] = v 49 else: 50 for k, v in a: 51 d[k] = v 52 53 if pa is a sequence of duples (k,v) then ordering is preserved 54 if pa is an ordered dictionary then ordering is preserved 55 if pa is not an ordered dictionary then ordering is not preserved 56 57 odict(k1 = v1, k2 = v2, ...) creates new dictionary from 58 59 kwa = dictionary of keyword args, {k1: v1, k2 : v2, ...} 60 61 d = {} 62 for k, v in kwa: 63 d[k] = v 64 65 in this case key ordering is not preserved due to limitation of python 66 """ 67 dict.__init__(self) 68 69 for a in pa: 70 if hasattr(a,'get'): #positional arg is dictionary 71 for k in a: 72 self[k] = a[k] 73 else: #positional arg is sequence of duples (k,v) 74 for k, v in a: 75 self[k] = v 76 77 for k in kwa: 78 self[k] = kwa[k] 79 80 def __delitem__(self, key): 81 """ del x[y] """ 82 dict.__delitem__(self, key) 83 self._keys.remove(key) 84 85 def __iter__(self): 86 """ iter(x)""" 87 for key in self._keys: 88 yield key 89 90 def __repr__(self): 91 """ 92 odict representation 93 """ 94 return ("{0}({1})".format(self.__class__.__name__, 95 repr(self.items()))) 96 97 def __setitem__(self, key, val): 98 """ x[key]=val""" 99 dict.__setitem__(self, key, val) 100 if not hasattr(self, '_keys'): 101 self._keys = [key] 102 if key not in self._keys: 103 self._keys.append(key) 104 105 def __getnewargs__(self): 106 """ 107 Needed to force __new__ which creates _keys. 108 if empty odict then __getstate__ returns empty list which is logically false so 109 __setstate__ is not called. 110 """ 111 return tuple() 112 113 def __getstate__(self): 114 """ 115 return state as items list. need this so pickle works since defined slots 116 """ 117 return self.items() 118 119 def __setstate__(self, state): 120 """ 121 restore from state items list 122 """ 123 self.__init__(state) 124 125 def append(self, key, item): 126 """ 127 D[key] = item. 128 """ 129 if key in self: 130 raise KeyError('append(): key %r already in dictionary' % key) 131 self[key] = item 132 133 def clear(self): 134 """ Remove all items from odict""" 135 dict.clear(self) 136 self._keys = [] 137 138 def copy(self): 139 """ 140 Make a shallow copy of odict 141 """ 142 items = [(key, dict.__getitem__(self, key)) for key in self._keys] 143 return self.__class__(items) #creates new odict and populates with items 144 145 def create(self, *pa, **kwa): 146 """ 147 Create items in this odict but only if key not already existent 148 pa may be sequence of duples (k,v) or dict 149 kwa is dict of keyword arguments 150 """ 151 for a in pa: 152 if hasattr(a,'get'): #positional arg is dictionary 153 for k in a: 154 if k not in self._keys: 155 self[k] = a[k] 156 else: #positional arg is sequence of duples (k,v) 157 for k, v in a: 158 if k not in self._keys: 159 self[k] = v 160 161 for k in kwa: 162 if k not in self._keys: 163 self[k] = kwa[k] 164 165 def sift(self, fields=None): 166 """ 167 Return shallaw copy odict of items keyed by field name strings 168 provided in optional fields sequence in that order with each value 169 given by the associated 170 item in self 171 If fields is not provided then return odict copy of self with all 172 the fields 173 Raises KeyError if no entry for a given field name 174 """ 175 if fields is None: 176 return self.copy() 177 178 items = [(key, dict.__getitem__(self, key)) for key in fields] 179 return self.__class__(items) #creates new odict and populates with items 180 181 def insert(self, index, key, val): 182 """ 183 Insert val at index if key not in odict 184 """ 185 if key in self: 186 raise KeyError('Key %r already exists.' % key) 187 dict.__setitem__(self, key, val) 188 self._keys.insert(index, key) 189 190 def items(self): 191 return [(key, dict.__getitem__(self, key)) for key in self._keys] 192 193 def iterkeys(self): 194 """ 195 Return an iterator over the keys of odict 196 """ 197 return iter(self) 198 199 def iteritems(self): 200 """ 201 Return an iterator over the items (key, value) of odict. 202 """ 203 return ((key, dict.__getitem__(self, key)) for key in self._keys) 204 205 def itervalues(self): 206 """ 207 Return an iterator over the values of odict. 208 """ 209 return (dict.__getitem__(self, key) for key in self._keys) 210 211 def keys(self): 212 """ 213 Return the list of keys of odict. 214 """ 215 return self._keys[:] 216 217 def pop(self, key, *default): 218 """ 219 Remove key and the associated item and return the associated value 220 If key not found return default if given otherwise raise KeyError 221 """ 222 value = dict.pop(self, key, *default) 223 if key in self._keys: 224 self._keys.remove(key) 225 return value 226 227 def popitem(self): 228 """ 229 Remove and return last item (key, value) duple 230 If odict is empty raise KeyError 231 """ 232 try: 233 key = self._keys[-1] 234 except IndexError: 235 raise KeyError('Empty odict.') 236 value = dict.__getitem__(self, key) 237 del self[key] 238 return (key, value) 239 240 def reorder(self, other): 241 """ 242 Update values in this odict based on the `other` odict. 243 Raises ValueError if other is not an odict 244 """ 245 if not isinstance(other, odict): 246 raise ValueError('other must be an odict') 247 248 if other is self: 249 #raise ValueError('other cannot be the same odict') 250 pass #updating with self makes no changes 251 252 dict.update(self, other) 253 keys = self._keys 254 255 for key in other: 256 if key in keys: 257 keys.remove(key) 258 keys.append(key) 259 260 def setdefault(self, key, default=None): 261 """ 262 If key in odict, return value at key 263 Otherwise set value at key to default and return default 264 """ 265 value = dict.setdefault(self, key, default) 266 if key not in self._keys: 267 self._keys.append(key) 268 return value 269 270 def update(self, *pa, **kwa): 271 """ 272 Update values in this odict 273 pa may be sequence of duples (k,v) or dict 274 kwa is dict of keyword arguments 275 """ 276 for a in pa: 277 if hasattr(a,'get'): #positional arg is dictionary 278 for k in a: 279 self[k] = a[k] 280 else: #positional arg is sequence of duples (k,v) 281 for k, v in a: 282 self[k] = v 283 284 for k in kwa: 285 self[k] = kwa[k] 286 287 def values(self): 288 return [dict.__getitem__(self, key) for key in self._keys] 289 290ODict = odict # alias 291 292#from . import optimize 293#optimize.bind_all(odict) 294 295 296class lodict(odict): 297 """ 298 Lowercase odict ensures that all keys are lower case. 299 """ 300 def __init__(self, *pa, **kwa): 301 """ 302 lodict() -> new empty lodict instance. 303 304 lodict(pa1, pa2, ...) where pa = tuple of positional args, 305 (pa1, pa2, ...) each paX may be a sequence of duples (k,v) or a dict 306 307 lodict(k1 = v1, k2 = v2, ...) where kwa = dictionary of keyword args, 308 {k1: v1, k2 : v2, ...} 309 """ 310 super(lodict, self).__init__() # must do this first 311 self.update(*pa, **kwa) 312 313 def __setitem__(self, key, val): 314 """ 315 Make key lowercalse then setitem 316 """ 317 super(lodict, self).__setitem__(key.lower(), val) 318 319 def __delitem__(self, key): 320 """ 321 Make key lowercase then delitem 322 """ 323 super(lodict, self).__delitem__(key.lower()) 324 325 def __contains__(self, key): 326 """ 327 Make key lowercase then test for inclusion 328 """ 329 return super(lodict, self).__contains__(key.lower()) 330 331 def __getitem__(self, key): 332 """ 333 Make key lowercase then getitem 334 """ 335 return super(lodict, self).__getitem__(key.lower()) 336 337 def get(self, key, default=None): 338 """ 339 May key lowercase then get 340 """ 341 return super(lodict, self).get(key.lower(), default) 342 343 def setdefault(self, key, default=None, kind=None): 344 """ 345 convert key to lower and then 346 347 If key is in the dictionary, return the val at key 348 349 If not, insert key with a value of default and return default. 350 The default value of default is None. 351 352 kind = callable is used to cast the returned value into a specific type. 353 354 Exceptions are suppressed and result in the default value being set 355 """ 356 try: 357 val = super(lodict, self).__getitem__(key.lower()) 358 return kind(val) if kind else val 359 except Exception: 360 super(lodict, self).__setitem__(key.lower(), default) 361 return default 362 363 364 def update(self, *pa, **kwa): 365 """ 366 lodict.update(pa1, pa2, ...) where pa = tuple of positional args, 367 (pa1, pa2, ...) each paX may be a sequence of duples (k,v) or a dict 368 369 lodict.update(k1 = v1, k2 = v2, ...) where kwa = dictionary of keyword args, 370 {k1: v1, k2 : v2, ...} 371 """ 372 d = odict() 373 for a in pa: 374 if hasattr(a, 'get'): #positional arg is dictionary 375 for k in a: 376 d[k.lower()] = a[k] 377 378 else: #positional arg is sequence of duples (k,v) 379 for k, v in a: 380 d[k.lower()] = v 381 382 for k in kwa: 383 d[k.lower()] = kwa[k] 384 385 super(lodict, self).update(d) 386 387 388 389 390class modict(odict): 391 """ 392 Multiple Ordered Dictionary. Inspired by other MultiDicts in the wild. 393 Associated with each key is a list of values. 394 Setting the value of an item appends the value to the list 395 associated with the item key. 396 Getting the value of an item returns the last 397 item in the list associated with the item key. 398 It behaves like an ordered dict 399 in that the order of item insertion is remembered. 400 401 There are special methods available to access or replace or append to 402 the full list of values for a given item key. 403 Aliases method names to match other multidict like interfaces like 404 webob. 405 """ 406 407 def __init__(self, *pa, **kwa): 408 """ 409 modict() -> new empty modict instance. 410 411 modict(pa1, pa2, ...) where pa = tuple of positional args, 412 (pa1, pa2, ...) each paX may be a sequence of duples (k,v) or a dict 413 414 modict(k1 = v1, k2 = v2, ...) where kwa = dictionary of keyword args, 415 {k1: v1, k2 : v2, ...} 416 """ 417 super(modict, self).__init__() # must do this first 418 self.update(*pa, **kwa) 419 420 def __getitem__(self, key): 421 return super(modict, self).__getitem__(key)[-1] #newest 422 def __setitem__(self, key, value): 423 self.append(key, value) #append 424 def values(self): 425 return [v[-1] for v in super(modict, self).itervalues()] 426 def listvalues(self): 427 return [v for v in super(modict, self).itervalues()] 428 def allvalues(self): 429 return [v for k, vl in super(modict, self).iteritems() for v in vl] 430 def items(self): 431 return [(k, v[-1]) for k, v in super(modict, self).iteritems()] 432 def listitems(self): 433 return [(k, v) for k, v in super(modict, self).iteritems()] 434 def allitems(self): 435 return [(k, v) for k, vl in super(modict, self).iteritems() for v in vl] 436 437 def itervalues(self): 438 return (v[-1] for v in super(modict, self).itervalues()) 439 def iterlistvalues(self): 440 return (v for v in super(modict, self).itervalues()) 441 def iterallvalues(self): 442 return (v for k, vl in super(modict, self).iteritems() for v in vl) 443 def iteritems(self): 444 return ((k, v[-1]) for k, v in super(modict, self).iteritems()) 445 def iterlistitems(self): 446 return ((k, v) for k, v in super(modict, self).iteritems()) 447 def iterallitems(self): 448 return ((k, v) for k, vl in super(modict, self).iteritems() for v in vl) 449 450 def has_key(self, key): 451 return key in self 452 453 def append(self, key, value): 454 """ 455 Add a new value to the list of values for this key. 456 """ 457 super(modict, self).setdefault(key, []).append(value) 458 459 def copy(self): 460 return self.__class__(self) 461 462 def get(self, key, default=None, index=-1, kind=None): 463 """ 464 Return the most recent value for a key, that is, the last element 465 in the keyed item's value list. 466 467 default = value to be returned if the key is not 468 present or the type conversion fails. 469 index = index into the keyed item's value list. 470 kind = callable is used to cast the value into a specific type. 471 Exception are suppressed and result in the default value 472 to be returned. 473 """ 474 try: 475 val = self[key][index] 476 return kind(val) if kind else val 477 except Exception: 478 pass 479 return default 480 481 def getlist(self, key): 482 """ 483 Return a (possibly empty) list of values for a key. 484 """ 485 return super(modict, self).get(key) or [] 486 487 def replace(self, key, value): 488 """ 489 Replace the list of values with a single item list of value. 490 """ 491 super(modict, self).__setitem__(key, [value]) 492 493 def setdefault(self, key, default=None, kind=None): 494 """ 495 If key is in the dictionary, return the last (most recent) element 496 from the keyed items's value list. 497 498 If not, insert key with a value of default and return default. 499 The default value of default is None. 500 501 kind = callable is used to cast the returned value into a specific type. 502 503 Exceptions are suppressed and result in the default value being set 504 """ 505 try: 506 val = super(modict, self).__getitem__(key) 507 return kind(val[-1]) if kind else val[-1] 508 except Exception: 509 self.append(key, default) 510 return default 511 512 513 def pop(self, key, *pa, **kwa): 514 """ 515 If key exists remove and return the indexed element of the key element 516 list else return the optional following positional argument. 517 If the optional positional arg is not provided and key does not exit 518 then raise KeyError. If provided the index keyword arg determines 519 which value in the key element list to return. Default is last element. 520 """ 521 index = kwa.get('index', -1) 522 try: 523 val = super(modict, self).pop(key) 524 except KeyError: 525 if pa: 526 return pa[0] 527 else: 528 raise 529 530 return val[index] 531 532 def poplist(self, key, *pa): 533 """ 534 If key exists remove and return keyed item's value list, 535 else return the optional following positional argument. 536 If the optional positional arg is not provided and key does not exit 537 then raise KeyError. 538 539 """ 540 try: 541 val = super(modict, self).pop(key) 542 except KeyError: 543 if pa: 544 return pa[0] 545 else: 546 raise 547 548 return val 549 550 def popitem(self, last=True, index=-1): 551 """ 552 Return and remove a key value pair. The index determines 553 which value in the keyed item's value list to return. 554 If last is True pop in LIFO order. 555 If last is False pop in FIFO order. 556 """ 557 key, val = super(modict, self).popitem(last=last) 558 return (key, val[index]) 559 560 def poplistitem(self, last=True): 561 """ 562 Return and remove a key value list pair. 563 If last is True pop in LIFO order. 564 If last is False pop in FIFO order. 565 """ 566 return (super(modict, self).popitem(last=last)) 567 568 def fromkeys(self, seq, default=None): 569 """ 570 Return new modict with keys from sequence seq with values set to default 571 """ 572 return modict((k, default) for k in seq) 573 574 def update(self, *pa, **kwa): 575 """ 576 modict.update(pa1, pa2, ...) where pa = tuple of positional args, 577 (pa1, pa2, ...) each paX may be a sequence of duples (k,v) or a dict 578 579 modict.update(k1 = v1, k2 = v2, ...) where kwa = dictionary of keyword args, 580 {k1: v1, k2 : v2, ...} 581 """ 582 for a in pa: 583 if isinstance(a, modict): #positional arg is modict 584 for k, v in a.iterallitems(): 585 self.append(k, v) 586 elif hasattr(a, 'get'): #positional arg is dictionary 587 for k, v in a.iteritems(): 588 self.append(k, v) 589 else: #positional arg is sequence of duples (k,v) 590 for k, v in a: 591 self.append(k, v) 592 593 for k,v in kwa.items(): 594 self.append(k, v) 595 596 # aliases to mimic other multi-dict APIs 597 getone = get 598 add = append 599 popall = poplist 600 601 602 603def TestPickle(): 604 """tests ability of odict to be pickled and unpickled 605 606 607 New-style types can provide a __getnewargs__() method that is used for protocol 2. 608 609 Note that last phrase about requiring protocol 2. Your 610 example works if you add a third parameter to pickle.dump() 611 with the value of 2. Version 2 is not default. 612 613 """ 614 import pickle 615 import StringIO 616 617 x = odict([('z',1),('a',2),('r',3)]) 618 s = StringIO.StringIO() 619 pickle.dump(x,s,2) 620 s.seek(0) 621 y = pickle.load(s) 622 print(x) 623 print(y) 624 625 #empty odict 626 x = odict() 627 s = StringIO.StringIO() 628 pickle.dump(x,s,2) 629 s.seek(0) 630 y = pickle.load(s) 631 print(x) 632 print(y) 633 634def Test(): 635 """Self test 636 637 """ 638 seq = [('b', 1), ('c', 2), ('a', 3)] 639 dct = {} 640 for k,v in seq: 641 dct[k] = v 642 643 odct = odict() 644 for k,v in seq: 645 odct[k] = v 646 647 648 print("Intialized from sequence of duples 'seq' = %s" % seq) 649 x = odict(seq) 650 print(" odict(seq) = %s" % x) 651 652 print("Initialized from unordered dictionary 'dct' = %s" % dct) 653 x = odict(dct) 654 print(" odict(dct) = %s" % x) 655 656 print("Initialized from ordered dictionary 'odct' = %s" % odct) 657 x = odict(odct) 658 print(" odict(odct) = %s" % x) 659 660 print("Initialized from keyword arguments 'b = 1, c = 2, a = 3'") 661 x = odict(b = 1, c = 2, a = 3) 662 print(" odict(b = 1, c = 2, a = 3) = %s" % x) 663 664 print("Initialized from mixed arguments") 665 x = odict(odct, seq, [('e', 4)], d = 5) 666 print(" odict(odct, seq, d = 4) = %s" % x) 667 668