16516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queruclass OrderedDict(dict): 26516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """ 36516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru A dictionary that keeps its keys in the order in which they're inserted. 46516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 56516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru Copied from Django's SortedDict with some modifications. 66516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 76516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """ 86516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def __new__(cls, *args, **kwargs): 96516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru instance = super(OrderedDict, cls).__new__(cls, *args, **kwargs) 106516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru instance.keyOrder = [] 116516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return instance 126516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 136516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def __init__(self, data=None): 146516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if data is None: 156516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru data = {} 166516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru super(OrderedDict, self).__init__(data) 176516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if isinstance(data, dict): 186516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder = data.keys() 196516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru else: 206516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder = [] 216516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru for key, value in data: 226516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if key not in self.keyOrder: 236516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.append(key) 246516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 256516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def __deepcopy__(self, memo): 266516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru from copy import deepcopy 276516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return self.__class__([(key, deepcopy(value, memo)) 286516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru for key, value in self.iteritems()]) 296516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 306516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def __setitem__(self, key, value): 316516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru super(OrderedDict, self).__setitem__(key, value) 326516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if key not in self.keyOrder: 336516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.append(key) 346516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 356516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def __delitem__(self, key): 366516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru super(OrderedDict, self).__delitem__(key) 376516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.remove(key) 386516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 396516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def __iter__(self): 406516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru for k in self.keyOrder: 416516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru yield k 426516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 436516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def pop(self, k, *args): 446516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru result = super(OrderedDict, self).pop(k, *args) 456516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru try: 466516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.remove(k) 476516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru except ValueError: 486516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru # Key wasn't in the dictionary in the first place. No problem. 496516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru pass 506516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return result 516516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 526516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def popitem(self): 536516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru result = super(OrderedDict, self).popitem() 546516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.remove(result[0]) 556516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return result 566516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 576516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def items(self): 586516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return zip(self.keyOrder, self.values()) 596516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 606516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def iteritems(self): 616516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru for key in self.keyOrder: 626516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru yield key, super(OrderedDict, self).__getitem__(key) 636516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 646516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def keys(self): 656516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return self.keyOrder[:] 666516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 676516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def iterkeys(self): 686516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return iter(self.keyOrder) 696516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 706516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def values(self): 716516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return [super(OrderedDict, self).__getitem__(k) for k in self.keyOrder] 726516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 736516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def itervalues(self): 746516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru for key in self.keyOrder: 756516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru yield super(OrderedDict, self).__getitem__(key) 766516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 776516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def update(self, dict_): 786516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru for k, v in dict_.items(): 796516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.__setitem__(k, v) 806516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 816516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def setdefault(self, key, default): 826516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if key not in self.keyOrder: 836516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.append(key) 846516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return super(OrderedDict, self).setdefault(key, default) 856516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 866516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def value_for_index(self, index): 876516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """Return the value of the item at the given zero-based index.""" 886516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return self[self.keyOrder[index]] 896516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 906516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def insert(self, index, key, value): 916516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """Insert the key, value pair before the item with the given index.""" 926516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if key in self.keyOrder: 936516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru n = self.keyOrder.index(key) 946516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru del self.keyOrder[n] 956516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if n < index: 966516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru index -= 1 976516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.insert(index, key) 986516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru super(OrderedDict, self).__setitem__(key, value) 996516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 1006516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def copy(self): 1016516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """Return a copy of this object.""" 1026516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru # This way of initializing the copy means it works for subclasses, too. 1036516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru obj = self.__class__(self) 1046516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru obj.keyOrder = self.keyOrder[:] 1056516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return obj 1066516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 1076516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def __repr__(self): 1086516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """ 1096516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru Replace the normal dict.__repr__ with a version that returns the keys 1106516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru in their sorted order. 1116516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """ 1126516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()]) 1136516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 1146516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def clear(self): 1156516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru super(OrderedDict, self).clear() 1166516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder = [] 1176516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 1186516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def index(self, key): 1196516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """ Return the index of a given key. """ 1206516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return self.keyOrder.index(key) 1216516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 1226516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def index_for_location(self, location): 1236516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """ Return index or None for a given location. """ 1246516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if location == '_begin': 1256516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru i = 0 1266516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru elif location == '_end': 1276516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru i = None 1286516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru elif location.startswith('<') or location.startswith('>'): 1296516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru i = self.index(location[1:]) 1306516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if location.startswith('>'): 1316516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if i >= len(self): 1326516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru # last item 1336516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru i = None 1346516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru else: 1356516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru i += 1 1366516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru else: 1376516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru raise ValueError('Not a valid location: "%s". Location key ' 1386516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 'must start with a ">" or "<".' % location) 1396516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru return i 1406516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 1416516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def add(self, key, value, location): 1426516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """ Insert by key location. """ 1436516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru i = self.index_for_location(location) 1446516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if i is not None: 1456516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.insert(i, key, value) 1466516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru else: 1476516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.__setitem__(key, value) 1486516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru 1496516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru def link(self, key, location): 1506516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru """ Change location of an existing item. """ 1516516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru n = self.keyOrder.index(key) 1526516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru del self.keyOrder[n] 1536516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru i = self.index_for_location(location) 1546516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru try: 1556516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru if i is not None: 1566516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.insert(i, key) 1576516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru else: 1586516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.append(key) 1596516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru except Error: 1606516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru # restore to prevent data loss and reraise 1616516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru self.keyOrder.insert(n, key) 1626516b99bb74dfb7187a08f7090bf7ca22a006f15Jean-Baptiste Queru raise Error 163