Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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.
23import sys
25if not sys.version_info < (2, 7):
27 from collections import OrderedDict
29else:
31 from UserDict import DictMixin
33 class OrderedDict(dict, DictMixin):
35 def __init__(self, *args, **kwds):
36 if len(args) > 1:
37 raise TypeError('expected at most 1 arguments, got %d' % len(args))
38 try:
39 self.__end
40 except AttributeError:
41 self.clear()
42 self.update(*args, **kwds)
44 def clear(self):
45 self.__end = end = []
46 end += [None, end, end] # sentinel node for doubly linked list
47 self.__map = {} # key --> [key, prev, next]
48 dict.clear(self)
50 def __setitem__(self, key, value):
51 if key not in self:
52 end = self.__end
53 curr = end[1]
54 curr[2] = end[1] = self.__map[key] = [key, curr, end]
55 dict.__setitem__(self, key, value)
57 def __delitem__(self, key):
58 dict.__delitem__(self, key)
59 key, prev, next_ = self.__map.pop(key)
60 prev[2] = next_
61 next_[1] = prev
63 def __iter__(self):
64 end = self.__end
65 curr = end[2]
66 while curr is not end:
67 yield curr[0]
68 curr = curr[2]
70 def __reversed__(self):
71 end = self.__end
72 curr = end[1]
73 while curr is not end:
74 yield curr[0]
75 curr = curr[1]
77 def popitem(self, last=True):
78 if not self:
79 raise KeyError('dictionary is empty')
80 if last:
81 key = reversed(self).next()
82 else:
83 key = iter(self).next()
84 value = self.pop(key)
85 return key, value
87 def __reduce__(self):
88 items = [[k, self[k]] for k in self]
89 tmp = self.__map, self.__end
90 del self.__map, self.__end
91 inst_dict = vars(self).copy()
92 self.__map, self.__end = tmp
93 if inst_dict:
94 return (self.__class__, (items,), inst_dict)
95 return self.__class__, (items,)
97 def keys(self):
98 return list(self)
100 setdefault = DictMixin.setdefault
101 update = DictMixin.update
102 pop = DictMixin.pop
103 values = DictMixin.values
104 items = DictMixin.items
105 iterkeys = DictMixin.iterkeys
106 itervalues = DictMixin.itervalues
107 iteritems = DictMixin.iteritems
109 def __repr__(self):
110 if not self:
111 return '%s()' % (self.__class__.__name__,)
112 return '%s(%r)' % (self.__class__.__name__, self.items())
114 def copy(self):
115 return self.__class__(self)
117 @classmethod
118 def fromkeys(cls, iterable, value=None):
119 d = cls()
120 for key in iterable:
121 d[key] = value
122 return d
124 def __eq__(self, other):
125 if isinstance(other, OrderedDict):
126 if len(self) != len(other):
127 return False
128 for p, q in zip(self.items(), other.items()):
129 if p != q:
130 return False
131 return True
132 return dict.__eq__(self, other)
134 def __ne__(self, other):
135 return not self == other