1from builtins import next 2## {{{ http://code.activestate.com/recipes/576693/ (r6) 3from UserDict import DictMixin as _DictMixin 4 5class OrderedDict(dict, _DictMixin): 6 """Backported Ordered Dict for Python < 2.7""" 7 def __init__(self, *args, **kwds): 8 if len(args) > 1: 9 raise TypeError('expected at most 1 arguments, got %d' % len(args)) 10 try: 11 self.__end 12 except AttributeError: 13 self.clear() 14 self.update(*args, **kwds) 15 16 def clear(self): 17 self.__end = end = [] 18 end += [None, end, end] # sentinel node for doubly linked list 19 self.__map = {} # key --> [key, prev, next] 20 dict.clear(self) 21 22 def __setitem__(self, key, value): 23 if key not in self: 24 end = self.__end 25 curr = end[1] 26 curr[2] = end[1] = self.__map[key] = [key, curr, end] 27 dict.__setitem__(self, key, value) 28 29 def __delitem__(self, key): 30 dict.__delitem__(self, key) 31 key, prev, next = self.__map.pop(key) 32 prev[2] = next 33 next[1] = prev 34 35 def __iter__(self): 36 end = self.__end 37 curr = end[2] 38 while curr is not end: 39 yield curr[0] 40 curr = curr[2] 41 42 def __reversed__(self): 43 end = self.__end 44 curr = end[1] 45 while curr is not end: 46 yield curr[0] 47 curr = curr[1] 48 49 def popitem(self, last=True): 50 if not self: 51 raise KeyError('dictionary is empty') 52 if last: 53 key = next(reversed(self)) 54 else: 55 key = next(iter(self)) 56 value = self.pop(key) 57 return key, value 58 59 def __reduce__(self): 60 items = [[k, self[k]] for k in self] 61 tmp = self.__map, self.__end 62 del self.__map, self.__end 63 inst_dict = vars(self).copy() 64 self.__map, self.__end = tmp 65 if inst_dict: 66 return (self.__class__, (items,), inst_dict) 67 return self.__class__, (items,) 68 69 def keys(self): 70 return list(self) 71 72 setdefault = _DictMixin.setdefault 73 update = _DictMixin.update 74 pop = _DictMixin.pop 75 values = _DictMixin.values 76 items = _DictMixin.items 77 iterkeys = _DictMixin.iterkeys 78 itervalues = _DictMixin.itervalues 79 iteritems = _DictMixin.iteritems 80 81 def __repr__(self): 82 if not self: 83 return '%s()' % (self.__class__.__name__,) 84 return '%s(%r)' % (self.__class__.__name__, list(self.items())) 85 86 def copy(self): 87 return self.__class__(self) 88 89 @classmethod 90 def fromkeys(cls, iterable, value=None): 91 d = cls() 92 for key in iterable: 93 d[key] = value 94 return d 95 96 def __eq__(self, other): 97 if isinstance(other, OrderedDict): 98 return len(self)==len(other) and list(self.items()) == list(other.items()) 99 return dict.__eq__(self, other) 100 101 def __ne__(self, other): 102 return not self == other 103## end of http://code.activestate.com/recipes/576693/ }}} 104