annotate ordereddict.py @ 41:74f09d6417f4

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