1# Unmodified from http://code.activestate.com/recipes/576693/
2# other than to add MIT license header (as specified on page, but not in code).
3# Linked from Python documentation here:
4# http://docs.python.org/2/library/collections.html#collections.OrderedDict
5#
6# This should be deleted once Py2.7 is available on all bots, see
7# http://crbug.com/241769.
8#
9# Copyright (c) 2009 Raymond Hettinger.
10#
11# Permission is hereby granted, free of charge, to any person obtaining a copy
12# of this software and associated documentation files (the "Software"), to deal
13# in the Software without restriction, including without limitation the rights
14# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15# copies of the Software, and to permit persons to whom the Software is
16# furnished to do so, subject to the following conditions:
17#
18# The above copyright notice and this permission notice shall be included in
19# all copies or substantial portions of the Software.
20#
21# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
27# THE SOFTWARE.
28
29# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.
30# Passes Python2.7's test suite and incorporates all the latest updates.
31
32try:
33    from thread import get_ident as _get_ident
34except ImportError:
35    from dummy_thread import get_ident as _get_ident
36
37try:
38    from _abcoll import KeysView, ValuesView, ItemsView
39except ImportError:
40    pass
41
42
43class OrderedDict(dict):
44    'Dictionary that remembers insertion order'
45    # An inherited dict maps keys to values.
46    # The inherited dict provides __getitem__, __len__, __contains__, and get.
47    # The remaining methods are order-aware.
48    # Big-O running times for all methods are the same as for regular dictionaries.
49
50    # The internal self.__map dictionary maps keys to links in a doubly linked list.
51    # The circular doubly linked list starts and ends with a sentinel element.
52    # The sentinel element never gets deleted (this simplifies the algorithm).
53    # Each link is stored as a list of length three:  [PREV, NEXT, KEY].
54
55    def __init__(self, *args, **kwds):
56        '''Initialize an ordered dictionary.  Signature is the same as for
57        regular dictionaries, but keyword arguments are not recommended
58        because their insertion order is arbitrary.
59
60        '''
61        if len(args) > 1:
62            raise TypeError('expected at most 1 arguments, got %d' % len(args))
63        try:
64            self.__root
65        except AttributeError:
66            self.__root = root = []                     # sentinel node
67            root[:] = [root, root, None]
68            self.__map = {}
69        self.__update(*args, **kwds)
70
71    def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
72        'od.__setitem__(i, y) <==> od[i]=y'
73        # Setting a new item creates a new link which goes at the end of the linked
74        # list, and the inherited dictionary is updated with the new key/value pair.
75        if key not in self:
76            root = self.__root
77            last = root[0]
78            last[1] = root[0] = self.__map[key] = [last, root, key]
79        dict_setitem(self, key, value)
80
81    def __delitem__(self, key, dict_delitem=dict.__delitem__):
82        'od.__delitem__(y) <==> del od[y]'
83        # Deleting an existing item uses self.__map to find the link which is
84        # then removed by updating the links in the predecessor and successor nodes.
85        dict_delitem(self, key)
86        link_prev, link_next, key = self.__map.pop(key)
87        link_prev[1] = link_next
88        link_next[0] = link_prev
89
90    def __iter__(self):
91        'od.__iter__() <==> iter(od)'
92        root = self.__root
93        curr = root[1]
94        while curr is not root:
95            yield curr[2]
96            curr = curr[1]
97
98    def __reversed__(self):
99        'od.__reversed__() <==> reversed(od)'
100        root = self.__root
101        curr = root[0]
102        while curr is not root:
103            yield curr[2]
104            curr = curr[0]
105
106    def clear(self):
107        'od.clear() -> None.  Remove all items from od.'
108        try:
109            for node in self.__map.itervalues():
110                del node[:]
111            root = self.__root
112            root[:] = [root, root, None]
113            self.__map.clear()
114        except AttributeError:
115            pass
116        dict.clear(self)
117
118    def popitem(self, last=True):
119        '''od.popitem() -> (k, v), return and remove a (key, value) pair.
120        Pairs are returned in LIFO order if last is true or FIFO order if false.
121
122        '''
123        if not self:
124            raise KeyError('dictionary is empty')
125        root = self.__root
126        if last:
127            link = root[0]
128            link_prev = link[0]
129            link_prev[1] = root
130            root[0] = link_prev
131        else:
132            link = root[1]
133            link_next = link[1]
134            root[1] = link_next
135            link_next[0] = root
136        key = link[2]
137        del self.__map[key]
138        value = dict.pop(self, key)
139        return key, value
140
141    # -- the following methods do not depend on the internal structure --
142
143    def keys(self):
144        'od.keys() -> list of keys in od'
145        return list(self)
146
147    def values(self):
148        'od.values() -> list of values in od'
149        return [self[key] for key in self]
150
151    def items(self):
152        'od.items() -> list of (key, value) pairs in od'
153        return [(key, self[key]) for key in self]
154
155    def iterkeys(self):
156        'od.iterkeys() -> an iterator over the keys in od'
157        return iter(self)
158
159    def itervalues(self):
160        'od.itervalues -> an iterator over the values in od'
161        for k in self:
162            yield self[k]
163
164    def iteritems(self):
165        'od.iteritems -> an iterator over the (key, value) items in od'
166        for k in self:
167            yield (k, self[k])
168
169    # Suppress 'OrderedDict.update: Method has no argument':
170    # pylint: disable=E0211
171    def update(*args, **kwds):
172        '''od.update(E, **F) -> None.  Update od from dict/iterable E and F.
173
174        If E is a dict instance, does:           for k in E: od[k] = E[k]
175        If E has a .keys() method, does:         for k in E.keys(): od[k] = E[k]
176        Or if E is an iterable of items, does:   for k, v in E: od[k] = v
177        In either case, this is followed by:     for k, v in F.items(): od[k] = v
178
179        '''
180        if len(args) > 2:
181            raise TypeError('update() takes at most 2 positional '
182                            'arguments (%d given)' % (len(args),))
183        elif not args:
184            raise TypeError('update() takes at least 1 argument (0 given)')
185        self = args[0]
186        # Make progressively weaker assumptions about "other"
187        other = ()
188        if len(args) == 2:
189            other = args[1]
190        if isinstance(other, dict):
191            for key in other:
192                self[key] = other[key]
193        elif hasattr(other, 'keys'):
194            for key in other.keys():
195                self[key] = other[key]
196        else:
197            for key, value in other:
198                self[key] = value
199        for key, value in kwds.items():
200            self[key] = value
201
202    __update = update  # let subclasses override update without breaking __init__
203
204    __marker = object()
205
206    def pop(self, key, default=__marker):
207        '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
208        If key is not found, d is returned if given, otherwise KeyError is raised.
209
210        '''
211        if key in self:
212            result = self[key]
213            del self[key]
214            return result
215        if default is self.__marker:
216            raise KeyError(key)
217        return default
218
219    def setdefault(self, key, default=None):
220        'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
221        if key in self:
222            return self[key]
223        self[key] = default
224        return default
225
226    def __repr__(self, _repr_running={}):
227        'od.__repr__() <==> repr(od)'
228        call_key = id(self), _get_ident()
229        if call_key in _repr_running:
230            return '...'
231        _repr_running[call_key] = 1
232        try:
233            if not self:
234                return '%s()' % (self.__class__.__name__,)
235            return '%s(%r)' % (self.__class__.__name__, self.items())
236        finally:
237            del _repr_running[call_key]
238
239    def __reduce__(self):
240        'Return state information for pickling'
241        items = [[k, self[k]] for k in self]
242        inst_dict = vars(self).copy()
243        for k in vars(OrderedDict()):
244            inst_dict.pop(k, None)
245        if inst_dict:
246            return (self.__class__, (items,), inst_dict)
247        return self.__class__, (items,)
248
249    def copy(self):
250        'od.copy() -> a shallow copy of od'
251        return self.__class__(self)
252
253    @classmethod
254    def fromkeys(cls, iterable, value=None):
255        '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
256        and values equal to v (which defaults to None).
257
258        '''
259        d = cls()
260        for key in iterable:
261            d[key] = value
262        return d
263
264    def __eq__(self, other):
265        '''od.__eq__(y) <==> od==y.  Comparison to another OD is order-sensitive
266        while comparison to a regular mapping is order-insensitive.
267
268        '''
269        if isinstance(other, OrderedDict):
270            return len(self)==len(other) and self.items() == other.items()
271        return dict.__eq__(self, other)
272
273    def __ne__(self, other):
274        return not self == other
275
276    # -- the following methods are only used in Python 2.7 --
277
278    def viewkeys(self):
279        "od.viewkeys() -> a set-like object providing a view on od's keys"
280        return KeysView(self)
281
282    def viewvalues(self):
283        "od.viewvalues() -> an object providing a view on od's values"
284        return ValuesView(self)
285
286    def viewitems(self):
287        "od.viewitems() -> a set-like object providing a view on od's items"
288        return ItemsView(self)
289
290