codekingpro/portable-devtools

1# Copyright (c) 2009 Raymond Hettinger
2#
3# Permission is hereby granted, free of charge, to any person
4# obtaining a copy of this software and associated documentation files
5# (the "Software"), to deal in the Software without restriction,
6# including without limitation the rights to use, copy, modify, merge,
7# publish, distribute, sublicense, and/or sell copies of the Software,
8# and to permit persons to whom the Software is furnished to do so,
9# subject to the following conditions:
10#
11#     The above copyright notice and this permission notice shall be
12#     included in all copies or substantial portions of the Software.
13#
14#     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15#     EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
16#     OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
17#     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
18#     HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
19#     WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20#     FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
21#     OTHER DEALINGS IN THE SOFTWARE.
22
23# used only in Python 2.6
24
25from UserDict import DictMixin
26
27
28class OrderedDict(dict, DictMixin):
29
30    def __init__(self, *args, **kwds):
31        if len(args) > 1:
32            raise TypeError('expected at most 1 arguments, got %d' % len(args))
33        try:
34            self.__end
35        except AttributeError:
36            self.clear()
37        self.update(*args, **kwds)
38
39    def clear(self):
40        self.__end = end = []
41        end += [None, end, end]         # sentinel node for doubly linked list
42        self.__map = {}                 # key --> [key, prev, next]
43        dict.clear(self)
44
45    def __setitem__(self, key, value):
46        if key not in self:
47            end = self.__end
48            curr = end[1]
49            curr[2] = end[1] = self.__map[key] = [key, curr, end]
50        dict.__setitem__(self, key, value)
51
52    def __delitem__(self, key):
53        dict.__delitem__(self, key)
54        key, prev, next = self.__map.pop(key)
55        prev[2] = next
56        next[1] = prev
57
58    def __iter__(self):
59        end = self.__end
60        curr = end[2]
61        while curr is not end:
62            yield curr[0]
63            curr = curr[2]
64
65    def __reversed__(self):
66        end = self.__end
67        curr = end[1]
68        while curr is not end:
69            yield curr[0]
70            curr = curr[1]
71
72    def popitem(self, last=True):
73        if not self:
74            raise KeyError('dictionary is empty')
75        if last:
76            key = reversed(self).next()
77        else:
78            key = iter(self).next()
79        value = self.pop(key)
80        return key, value
81
82    def __reduce__(self):
83        items = [[k, self[k]] for k in self]
84        tmp = self.__map, self.__end
85        del self.__map, self.__end
86        inst_dict = vars(self).copy()
87        self.__map, self.__end = tmp
88        if inst_dict:
89            return (self.__class__, (items,), inst_dict)
90        return self.__class__, (items,)
91
92    def keys(self):
93        return list(self)
94
95    setdefault = DictMixin.setdefault
96    update = DictMixin.update
97    pop = DictMixin.pop
98    values = DictMixin.values
99    items = DictMixin.items
100    iterkeys = DictMixin.iterkeys
101    itervalues = DictMixin.itervalues
102    iteritems = DictMixin.iteritems
103
104    def __repr__(self):
105        if not self:
106            return '%s()' % (self.__class__.__name__,)
107        return '%s(%r)' % (self.__class__.__name__, self.items())
108
109    def copy(self):
110        return self.__class__(self)
111
112    @classmethod
113    def fromkeys(cls, iterable, value=None):
114        d = cls()
115        for key in iterable:
116            d[key] = value
117        return d
118
119    def __eq__(self, other):
120        if isinstance(other, OrderedDict):
121            if len(self) != len(other):
122                return False
123            for p, q in zip(self.items(), other.items()):
124                if p != q:
125                    return False
126            return True
127        return dict.__eq__(self, other)
128
129    def __ne__(self, other):
130        return not self == other
131