12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)"""Drop-in replacement for collections.OrderedDict by Raymond Hettinger 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)http://code.activestate.com/recipes/576693/ 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)""" 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)from UserDict import DictMixin 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)# Modified from original to support Python 2.4, see 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)# http://code.google.com/p/simplejson/issues/detail?id=53 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)try: 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) all 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)except NameError: 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def all(seq): 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for elem in seq: 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if not elem: 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return False 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return True 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class OrderedDict(dict, DictMixin): 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __init__(self, *args, **kwds): 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if len(args) > 1: 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) raise TypeError('expected at most 1 arguments, got %d' % len(args)) 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) try: 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self.__end 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) except AttributeError: 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self.clear() 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self.update(*args, **kwds) 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def clear(self): 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self.__end = end = [] 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) end += [None, end, end] # sentinel node for doubly linked list 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self.__map = {} # key --> [key, prev, next] 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) dict.clear(self) 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __setitem__(self, key, value): 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if key not in self: 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) end = self.__end 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) curr = end[1] 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) curr[2] = end[1] = self.__map[key] = [key, curr, end] 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) dict.__setitem__(self, key, value) 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __delitem__(self, key): 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) dict.__delitem__(self, key) 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) key, prev, next = self.__map.pop(key) 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) prev[2] = next 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) next[1] = prev 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __iter__(self): 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) end = self.__end 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) curr = end[2] 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while curr is not end: 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) yield curr[0] 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) curr = curr[2] 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __reversed__(self): 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) end = self.__end 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) curr = end[1] 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while curr is not end: 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) yield curr[0] 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) curr = curr[1] 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def popitem(self, last=True): 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if not self: 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) raise KeyError('dictionary is empty') 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) # Modified from original to support Python 2.4, see 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) # http://code.google.com/p/simplejson/issues/detail?id=53 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if last: 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) key = reversed(self).next() 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else: 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) key = iter(self).next() 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) value = self.pop(key) 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return key, value 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __reduce__(self): 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) items = [[k, self[k]] for k in self] 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) tmp = self.__map, self.__end 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) del self.__map, self.__end 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) inst_dict = vars(self).copy() 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) self.__map, self.__end = tmp 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if inst_dict: 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return (self.__class__, (items,), inst_dict) 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return self.__class__, (items,) 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def keys(self): 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return list(self) 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) setdefault = DictMixin.setdefault 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) update = DictMixin.update 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pop = DictMixin.pop 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) values = DictMixin.values 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) items = DictMixin.items 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iterkeys = DictMixin.iterkeys 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) itervalues = DictMixin.itervalues 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) iteritems = DictMixin.iteritems 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __repr__(self): 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if not self: 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return '%s()' % (self.__class__.__name__,) 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return '%s(%r)' % (self.__class__.__name__, self.items()) 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def copy(self): 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return self.__class__(self) 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) @classmethod 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def fromkeys(cls, iterable, value=None): 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) d = cls() 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for key in iterable: 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) d[key] = value 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return d 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __eq__(self, other): 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if isinstance(other, OrderedDict): 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return len(self)==len(other) and \ 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) all(p==q for p, q in zip(self.items(), other.items())) 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return dict.__eq__(self, other) 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) def __ne__(self, other): 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return not self == other 120