1from builtins import next
2## {{{ http://code.activestate.com/recipes/576693/ (r6)
3from UserDict import DictMixin as _DictMixin
4
5class OrderedDict(dict, _DictMixin):
6    """Backported Ordered Dict for Python < 2.7"""
7    def __init__(self, *args, **kwds):
8        if len(args) > 1:
9            raise TypeError('expected at most 1 arguments, got %d' % len(args))
10        try:
11            self.__end
12        except AttributeError:
13            self.clear()
14        self.update(*args, **kwds)
15
16    def clear(self):
17        self.__end = end = []
18        end += [None, end, end]         # sentinel node for doubly linked list
19        self.__map = {}                 # key --> [key, prev, next]
20        dict.clear(self)
21
22    def __setitem__(self, key, value):
23        if key not in self:
24            end = self.__end
25            curr = end[1]
26            curr[2] = end[1] = self.__map[key] = [key, curr, end]
27        dict.__setitem__(self, key, value)
28
29    def __delitem__(self, key):
30        dict.__delitem__(self, key)
31        key, prev, next = self.__map.pop(key)
32        prev[2] = next
33        next[1] = prev
34
35    def __iter__(self):
36        end = self.__end
37        curr = end[2]
38        while curr is not end:
39            yield curr[0]
40            curr = curr[2]
41
42    def __reversed__(self):
43        end = self.__end
44        curr = end[1]
45        while curr is not end:
46            yield curr[0]
47            curr = curr[1]
48
49    def popitem(self, last=True):
50        if not self:
51            raise KeyError('dictionary is empty')
52        if last:
53            key = next(reversed(self))
54        else:
55            key = next(iter(self))
56        value = self.pop(key)
57        return key, value
58
59    def __reduce__(self):
60        items = [[k, self[k]] for k in self]
61        tmp = self.__map, self.__end
62        del self.__map, self.__end
63        inst_dict = vars(self).copy()
64        self.__map, self.__end = tmp
65        if inst_dict:
66            return (self.__class__, (items,), inst_dict)
67        return self.__class__, (items,)
68
69    def keys(self):
70        return list(self)
71
72    setdefault = _DictMixin.setdefault
73    update = _DictMixin.update
74    pop = _DictMixin.pop
75    values = _DictMixin.values
76    items = _DictMixin.items
77    iterkeys = _DictMixin.iterkeys
78    itervalues = _DictMixin.itervalues
79    iteritems = _DictMixin.iteritems
80
81    def __repr__(self):
82        if not self:
83            return '%s()' % (self.__class__.__name__,)
84        return '%s(%r)' % (self.__class__.__name__, list(self.items()))
85
86    def copy(self):
87        return self.__class__(self)
88
89    @classmethod
90    def fromkeys(cls, iterable, value=None):
91        d = cls()
92        for key in iterable:
93            d[key] = value
94        return d
95
96    def __eq__(self, other):
97        if isinstance(other, OrderedDict):
98            return len(self)==len(other) and list(self.items()) == list(other.items())
99        return dict.__eq__(self, other)
100
101    def __ne__(self, other):
102        return not self == other
103## end of http://code.activestate.com/recipes/576693/ }}}
104