1class OrderedDict(dict):
2    """
3    A dictionary that keeps its keys in the order in which they're inserted.
4
5    Copied from Django's SortedDict with some modifications.
6
7    """
8    def __new__(cls, *args, **kwargs):
9        instance = super(OrderedDict, cls).__new__(cls, *args, **kwargs)
10        instance.keyOrder = []
11        return instance
12
13    def __init__(self, data=None):
14        if data is None:
15            data = {}
16        super(OrderedDict, self).__init__(data)
17        if isinstance(data, dict):
18            self.keyOrder = data.keys()
19        else:
20            self.keyOrder = []
21            for key, value in data:
22                if key not in self.keyOrder:
23                    self.keyOrder.append(key)
24
25    def __deepcopy__(self, memo):
26        from copy import deepcopy
27        return self.__class__([(key, deepcopy(value, memo))
28                               for key, value in self.iteritems()])
29
30    def __setitem__(self, key, value):
31        super(OrderedDict, self).__setitem__(key, value)
32        if key not in self.keyOrder:
33            self.keyOrder.append(key)
34
35    def __delitem__(self, key):
36        super(OrderedDict, self).__delitem__(key)
37        self.keyOrder.remove(key)
38
39    def __iter__(self):
40        for k in self.keyOrder:
41            yield k
42
43    def pop(self, k, *args):
44        result = super(OrderedDict, self).pop(k, *args)
45        try:
46            self.keyOrder.remove(k)
47        except ValueError:
48            # Key wasn't in the dictionary in the first place. No problem.
49            pass
50        return result
51
52    def popitem(self):
53        result = super(OrderedDict, self).popitem()
54        self.keyOrder.remove(result[0])
55        return result
56
57    def items(self):
58        return zip(self.keyOrder, self.values())
59
60    def iteritems(self):
61        for key in self.keyOrder:
62            yield key, super(OrderedDict, self).__getitem__(key)
63
64    def keys(self):
65        return self.keyOrder[:]
66
67    def iterkeys(self):
68        return iter(self.keyOrder)
69
70    def values(self):
71        return [super(OrderedDict, self).__getitem__(k) for k in self.keyOrder]
72
73    def itervalues(self):
74        for key in self.keyOrder:
75            yield super(OrderedDict, self).__getitem__(key)
76
77    def update(self, dict_):
78        for k, v in dict_.items():
79            self.__setitem__(k, v)
80
81    def setdefault(self, key, default):
82        if key not in self.keyOrder:
83            self.keyOrder.append(key)
84        return super(OrderedDict, self).setdefault(key, default)
85
86    def value_for_index(self, index):
87        """Return the value of the item at the given zero-based index."""
88        return self[self.keyOrder[index]]
89
90    def insert(self, index, key, value):
91        """Insert the key, value pair before the item with the given index."""
92        if key in self.keyOrder:
93            n = self.keyOrder.index(key)
94            del self.keyOrder[n]
95            if n < index:
96                index -= 1
97        self.keyOrder.insert(index, key)
98        super(OrderedDict, self).__setitem__(key, value)
99
100    def copy(self):
101        """Return a copy of this object."""
102        # This way of initializing the copy means it works for subclasses, too.
103        obj = self.__class__(self)
104        obj.keyOrder = self.keyOrder[:]
105        return obj
106
107    def __repr__(self):
108        """
109        Replace the normal dict.__repr__ with a version that returns the keys
110        in their sorted order.
111        """
112        return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])
113
114    def clear(self):
115        super(OrderedDict, self).clear()
116        self.keyOrder = []
117
118    def index(self, key):
119        """ Return the index of a given key. """
120        return self.keyOrder.index(key)
121
122    def index_for_location(self, location):
123        """ Return index or None for a given location. """
124        if location == '_begin':
125            i = 0
126        elif location == '_end':
127            i = None
128        elif location.startswith('<') or location.startswith('>'):
129            i = self.index(location[1:])
130            if location.startswith('>'):
131                if i >= len(self):
132                    # last item
133                    i = None
134                else:
135                    i += 1
136        else:
137            raise ValueError('Not a valid location: "%s". Location key '
138                             'must start with a ">" or "<".' % location)
139        return i
140
141    def add(self, key, value, location):
142        """ Insert by key location. """
143        i = self.index_for_location(location)
144        if i is not None:
145            self.insert(i, key, value)
146        else:
147            self.__setitem__(key, value)
148
149    def link(self, key, location):
150        """ Change location of an existing item. """
151        n = self.keyOrder.index(key)
152        del self.keyOrder[n]
153        i = self.index_for_location(location)
154        try:
155            if i is not None:
156                self.keyOrder.insert(i, key)
157            else:
158                self.keyOrder.append(key)
159        except Error:
160            # restore to prevent data loss and reraise
161            self.keyOrder.insert(n, key)
162            raise Error
163