ordered_dict.py revision 2a99a7e74a7f215066514fe81d2bfa6639d9eddd 
1"""Drop-in replacement for collections.OrderedDict by Raymond Hettinger
2
3http://code.activestate.com/recipes/576693/
4
5"""
6from UserDict import DictMixin
7
8# Modified from original to support Python 2.4, see
9# http://code.google.com/p/simplejson/issues/detail?id=53
10try:
11    all
12except NameError:
13    def all(seq):
14        for elem in seq:
15            if not elem:
16                return False
17        return True
18
19class OrderedDict(dict, DictMixin):
20
21    def __init__(self, *args, **kwds):
22        if len(args) > 1:
23            raise TypeError('expected at most 1 arguments, got %d' % len(args))
24        try:
25            self.__end
26        except AttributeError:
27            self.clear()
28        self.update(*args, **kwds)
29
30    def clear(self):
31        self.__end = end = []
32        end += [None, end, end]         # sentinel node for doubly linked list
33        self.__map = {}                 # key --> [key, prev, next]
34        dict.clear(self)
35
36    def __setitem__(self, key, value):
37        if key not in self:
38            end = self.__end
39            curr = end[1]
40            curr[2] = end[1] = self.__map[key] = [key, curr, end]
41        dict.__setitem__(self, key, value)
42
43    def __delitem__(self, key):
44        dict.__delitem__(self, key)
45        key, prev, next = self.__map.pop(key)
46        prev[2] = next
47        next[1] = prev
48
49    def __iter__(self):
50        end = self.__end
51        curr = end[2]
52        while curr is not end:
53            yield curr[0]
54            curr = curr[2]
55
56    def __reversed__(self):
57        end = self.__end
58        curr = end[1]
59        while curr is not end:
60            yield curr[0]
61            curr = curr[1]
62
63    def popitem(self, last=True):
64        if not self:
65            raise KeyError('dictionary is empty')
66        # Modified from original to support Python 2.4, see
67        # http://code.google.com/p/simplejson/issues/detail?id=53
68        if last:
69            key = reversed(self).next()
70        else:
71            key = iter(self).next()
72        value = self.pop(key)
73        return key, value
74
75    def __reduce__(self):
76        items = [[k, self[k]] for k in self]
77        tmp = self.__map, self.__end
78        del self.__map, self.__end
79        inst_dict = vars(self).copy()
80        self.__map, self.__end = tmp
81        if inst_dict:
82            return (self.__class__, (items,), inst_dict)
83        return self.__class__, (items,)
84
85    def keys(self):
86        return list(self)
87
88    setdefault = DictMixin.setdefault
89    update = DictMixin.update
90    pop = DictMixin.pop
91    values = DictMixin.values
92    items = DictMixin.items
93    iterkeys = DictMixin.iterkeys
94    itervalues = DictMixin.itervalues
95    iteritems = DictMixin.iteritems
96
97    def __repr__(self):
98        if not self:
99            return '%s()' % (self.__class__.__name__,)
100        return '%s(%r)' % (self.__class__.__name__, self.items())
101
102    def copy(self):
103        return self.__class__(self)
104
105    @classmethod
106    def fromkeys(cls, iterable, value=None):
107        d = cls()
108        for key in iterable:
109            d[key] = value
110        return d
111
112    def __eq__(self, other):
113        if isinstance(other, OrderedDict):
114            return len(self)==len(other) and \
115                   all(p==q for p, q in  zip(self.items(), other.items()))
116        return dict.__eq__(self, other)
117
118    def __ne__(self, other):
119        return not self == other
120