--- /dev/null
+
+class SortedDict(dict):
+ """
+ A dictionary that keeps its keys in the order in which they're inserted.
+ """
+ def __init__(self, data=None):
+ if data is None:
+ data = {}
+ super(SortedDict, self).__init__(data)
+ if isinstance(data, dict):
+ self.keyOrder = data.keys()
+ else:
+ self.keyOrder = []
+ for key, value in data:
+ if key not in self.keyOrder:
+ self.keyOrder.append(key)
+
+ def __deepcopy__(self, memo):
+ from copy import deepcopy
+ return self.__class__([(key, deepcopy(value, memo))
+ for key, value in self.iteritems()])
+
+ def __setitem__(self, key, value):
+ super(SortedDict, self).__setitem__(key, value)
+ if key not in self.keyOrder:
+ self.keyOrder.append(key)
+
+ def __delitem__(self, key):
+ super(SortedDict, self).__delitem__(key)
+ self.keyOrder.remove(key)
+
+ def __iter__(self):
+ for k in self.keyOrder:
+ yield k
+
+ def pop(self, k, *args):
+ result = super(SortedDict, self).pop(k, *args)
+ try:
+ self.keyOrder.remove(k)
+ except ValueError:
+ # Key wasn't in the dictionary in the first place. No problem.
+ pass
+ return result
+
+ def popitem(self):
+ result = super(SortedDict, self).popitem()
+ self.keyOrder.remove(result[0])
+ return result
+
+ def items(self):
+ return zip(self.keyOrder, self.values())
+
+ def iteritems(self):
+ for key in self.keyOrder:
+ yield key, super(SortedDict, self).__getitem__(key)
+
+ def keys(self):
+ return self.keyOrder[:]
+
+ def iterkeys(self):
+ return iter(self.keyOrder)
+
+ def values(self):
+ return [super(SortedDict, self).__getitem__(k) for k in self.keyOrder]
+
+ def itervalues(self):
+ for key in self.keyOrder:
+ yield super(SortedDict, self).__getitem__(key)
+
+ def update(self, dict_):
+ for k, v in dict_.items():
+ self.__setitem__(k, v)
+
+ def setdefault(self, key, default):
+ if key not in self.keyOrder:
+ self.keyOrder.append(key)
+ return super(SortedDict, self).setdefault(key, default)
+
+ def value_for_index(self, index):
+ """Returns the value of the item at the given zero-based index."""
+ return self[self.keyOrder[index]]
+
+ def insert(self, index, key, value):
+ """Inserts the key, value pair before the item with the given index."""
+ if key in self.keyOrder:
+ n = self.keyOrder.index(key)
+ del self.keyOrder[n]
+ if n < index:
+ index -= 1
+ self.keyOrder.insert(index, key)
+ super(SortedDict, self).__setitem__(key, value)
+
+ def copy(self):
+ """Returns a copy of this object."""
+ # This way of initializing the copy means it works for subclasses, too.
+ obj = self.__class__(self)
+ obj.keyOrder = self.keyOrder[:]
+ return obj
+
+ def __repr__(self):
+ """
+ Replaces the normal dict.__repr__ with a version that returns the keys
+ in their sorted order.
+ """
+ return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])
+
+ def clear(self):
+ super(SortedDict, self).clear()
+ self.keyOrder = []
\ No newline at end of file