root / kamaki / clients / utils / ordereddict.py @ e51c7d5b
History | View | Annotate | Download (10.2 kB)
1 |
# Copyright 2012-2013 GRNET S.A. All rights reserved.
|
---|---|
2 |
#
|
3 |
# Redistribution and use in source and binary forms, with or
|
4 |
# without modification, are permitted provided that the following
|
5 |
# conditions are met:
|
6 |
#
|
7 |
# 1. Redistributions of source code must retain the above
|
8 |
# copyright notice, this list of conditions and the following
|
9 |
# disclaimer.
|
10 |
#
|
11 |
# 2. Redistributions in binary form must reproduce the above
|
12 |
# copyright notice, this list of conditions and the following
|
13 |
# disclaimer in the documentation and/or other materials
|
14 |
# provided with the distribution.
|
15 |
#
|
16 |
# THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS
|
17 |
# OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
|
18 |
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
19 |
# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR
|
20 |
# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
|
21 |
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
|
22 |
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
|
23 |
# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
|
24 |
# AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
|
25 |
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
|
26 |
# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
|
27 |
# POSSIBILITY OF SUCH DAMAGE.
|
28 |
#
|
29 |
# The views and conclusions contained in the software and
|
30 |
# documentation are those of the authors and should not be
|
31 |
# interpreted as representing official policies, either expressed
|
32 |
# or implied, of GRNET S.A.
|
33 |
|
34 |
# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and
|
35 |
# pypy. Passes Python2.7's test suite and incorporates all the latest updates.
|
36 |
|
37 |
try:
|
38 |
from thread import get_ident as _get_ident |
39 |
except ImportError: |
40 |
from dummy_thread import get_ident as _get_ident |
41 |
|
42 |
try:
|
43 |
from _abcoll import KeysView, ValuesView, ItemsView |
44 |
except ImportError: |
45 |
pass
|
46 |
|
47 |
|
48 |
class OrderedDict(dict): |
49 |
"""Dictionary that remembers insertion order
|
50 |
An inherited dict maps keys to values.
|
51 |
The inherited dict provides __getitem__, __len__, __contains__, and get.
|
52 |
The remaining methods are order-aware.
|
53 |
Big-O running times for all methods are the same as for regular
|
54 |
dictionaries.
|
55 |
The internal self.__map dictionary maps keys to links in a doubly linked
|
56 |
list.
|
57 |
The circular doubly linked list starts and ends with a sentinel element.
|
58 |
The sentinel element never gets deleted (this simplifies the algorithm).
|
59 |
Each link is stored as a list of length three: [PREV, NEXT, KEY].
|
60 |
"""
|
61 |
|
62 |
def __init__(self, *args, **kwds): |
63 |
'''Initialize an ordered dictionary. Signature is the same as for
|
64 |
regular dictionaries, but keyword arguments are not recommended
|
65 |
because their insertion order is arbitrary.
|
66 |
|
67 |
'''
|
68 |
if len(args) > 1: |
69 |
raise TypeError('expected at most 1 arguments, got %d' % len(args)) |
70 |
try:
|
71 |
self.__root
|
72 |
except AttributeError: |
73 |
self.__root = root = [] # sentinel node |
74 |
root[:] = [root, root, None]
|
75 |
self.__map = {}
|
76 |
self.__update(*args, **kwds)
|
77 |
|
78 |
def __setitem__(self, key, value, dict_setitem=dict.__setitem__): |
79 |
'od.__setitem__(i, y) <==> od[i]=y'
|
80 |
# Setting a new item creates a new link which goes at the end of the
|
81 |
# linked
|
82 |
# list, and the inherited dictionary is updated with the new key/value
|
83 |
# pair.
|
84 |
if key not in self: |
85 |
root = self.__root
|
86 |
last = root[0]
|
87 |
last[1] = root[0] = self.__map[key] = [last, root, key] |
88 |
dict_setitem(self, key, value)
|
89 |
|
90 |
def __delitem__(self, key, dict_delitem=dict.__delitem__): |
91 |
'od.__delitem__(y) <==> del od[y]'
|
92 |
# Deleting an existing item uses self.__map to find the link which is
|
93 |
# then removed by updating the links in the predecessor and successor
|
94 |
# nodes.
|
95 |
dict_delitem(self, key)
|
96 |
link_prev, link_next, key = self.__map.pop(key)
|
97 |
link_prev[1] = link_next
|
98 |
link_next[0] = link_prev
|
99 |
|
100 |
def __iter__(self): |
101 |
'od.__iter__() <==> iter(od)'
|
102 |
root = self.__root
|
103 |
curr = root[1]
|
104 |
while curr is not root: |
105 |
yield curr[2] |
106 |
curr = curr[1]
|
107 |
|
108 |
def __reversed__(self): |
109 |
'od.__reversed__() <==> reversed(od)'
|
110 |
root = self.__root
|
111 |
curr = root[0]
|
112 |
while curr is not root: |
113 |
yield curr[2] |
114 |
curr = curr[0]
|
115 |
|
116 |
def clear(self): |
117 |
'od.clear() -> None. Remove all items from od.'
|
118 |
try:
|
119 |
for node in self.__map.itervalues(): |
120 |
del node[:]
|
121 |
root = self.__root
|
122 |
root[:] = [root, root, None]
|
123 |
self.__map.clear()
|
124 |
except AttributeError: |
125 |
pass
|
126 |
dict.clear(self) |
127 |
|
128 |
def popitem(self, last=True): |
129 |
"""od.popitem() -> (k, v), return and remove a (key, value) pair.
|
130 |
Pairs are returned in LIFO order if last is true or FIFO order if
|
131 |
false.
|
132 |
"""
|
133 |
|
134 |
if not self: |
135 |
raise KeyError('dictionary is empty') |
136 |
root = self.__root
|
137 |
if last:
|
138 |
link = root[0]
|
139 |
link_prev = link[0]
|
140 |
link_prev[1] = root
|
141 |
root[0] = link_prev
|
142 |
else:
|
143 |
link = root[1]
|
144 |
link_next = link[1]
|
145 |
root[1] = link_next
|
146 |
link_next[0] = root
|
147 |
key = link[2]
|
148 |
del self.__map[key] |
149 |
value = dict.pop(self, key) |
150 |
return key, value
|
151 |
|
152 |
# -- the following methods do not depend on the internal structure --
|
153 |
|
154 |
def keys(self): |
155 |
'od.keys() -> list of keys in od'
|
156 |
return list(self) |
157 |
|
158 |
def values(self): |
159 |
'od.values() -> list of values in od'
|
160 |
return [self[key] for key in self] |
161 |
|
162 |
def items(self): |
163 |
'od.items() -> list of (key, value) pairs in od'
|
164 |
return [(key, self[key]) for key in self] |
165 |
|
166 |
def iterkeys(self): |
167 |
'od.iterkeys() -> an iterator over the keys in od'
|
168 |
return iter(self) |
169 |
|
170 |
def itervalues(self): |
171 |
'od.itervalues -> an iterator over the values in od'
|
172 |
for k in self: |
173 |
yield self[k] |
174 |
|
175 |
def iteritems(self): |
176 |
'od.iteritems -> an iterator over the (key, value) items in od'
|
177 |
for k in self: |
178 |
yield (k, self[k]) |
179 |
|
180 |
def update(*args, **kwds): |
181 |
'''od.update(E, **F) -> None. Update od from dict/iterable E and F.
|
182 |
|
183 |
If E is a dict instance, does: for k in E: od[k] = E[k]
|
184 |
If E has a .keys() method, does: for k in E.keys(): od[k]=E[k]
|
185 |
Or if E is an iterable of items, does: for k, v in E: od[k] = v
|
186 |
In either case, this is followed by: for k, v in F.items(): od[k]=v
|
187 |
|
188 |
'''
|
189 |
if len(args) > 2: |
190 |
raise TypeError('update() takes at most 2 positional ' |
191 |
'arguments (%d given)' % (len(args),)) |
192 |
elif not args: |
193 |
raise TypeError('update() takes at least 1 argument (0 given)') |
194 |
self = args[0] |
195 |
# Make progressively weaker assumptions about "other"
|
196 |
other = () |
197 |
if len(args) == 2: |
198 |
other = args[1]
|
199 |
if isinstance(other, dict): |
200 |
for key in other: |
201 |
self[key] = other[key]
|
202 |
elif hasattr(other, 'keys'): |
203 |
for key in other.keys(): |
204 |
self[key] = other[key]
|
205 |
else:
|
206 |
for key, value in other: |
207 |
self[key] = value
|
208 |
for key, value in kwds.items(): |
209 |
self[key] = value
|
210 |
|
211 |
# let subclasses override update without breaking __init__
|
212 |
__update = update |
213 |
|
214 |
__marker = object()
|
215 |
|
216 |
def pop(self, key, default=__marker): |
217 |
"""od.pop(k[,d]) -> v, remove specified key and return the
|
218 |
corresponding value. If key is not found, d is returned if given,
|
219 |
otherwise KeyError is raised.
|
220 |
"""
|
221 |
if key in self: |
222 |
result = self[key]
|
223 |
del self[key] |
224 |
return result
|
225 |
if default is self.__marker: |
226 |
raise KeyError(key) |
227 |
return default
|
228 |
|
229 |
def setdefault(self, key, default=None): |
230 |
"""od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in
|
231 |
od
|
232 |
"""
|
233 |
if key in self: |
234 |
return self[key] |
235 |
self[key] = default
|
236 |
return default
|
237 |
|
238 |
def __repr__(self, _repr_running={}): |
239 |
"""od.__repr__() <==> repr(od)"""
|
240 |
call_key = id(self), _get_ident() |
241 |
if call_key in _repr_running: |
242 |
return '...' |
243 |
_repr_running[call_key] = 1
|
244 |
try:
|
245 |
if not self: |
246 |
return '%s()' % (self.__class__.__name__,) |
247 |
return '%s(%r)' % (self.__class__.__name__, self.items()) |
248 |
finally:
|
249 |
del _repr_running[call_key]
|
250 |
|
251 |
def __reduce__(self): |
252 |
"""Return state information for pickling"""
|
253 |
items = [[k, self[k]] for k in self] |
254 |
inst_dict = vars(self).copy() |
255 |
for k in vars(OrderedDict()): |
256 |
inst_dict.pop(k, None)
|
257 |
if inst_dict:
|
258 |
return (self.__class__, (items,), inst_dict) |
259 |
return self.__class__, (items,) |
260 |
|
261 |
def copy(self): |
262 |
"""od.copy() -> a shallow copy of od"""
|
263 |
return self.__class__(self) |
264 |
|
265 |
@classmethod
|
266 |
def fromkeys(cls, iterable, value=None): |
267 |
"""OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
|
268 |
and values equal to v (which defaults to None).
|
269 |
"""
|
270 |
d = cls() |
271 |
for key in iterable: |
272 |
d[key] = value |
273 |
return d
|
274 |
|
275 |
def __eq__(self, other): |
276 |
"""od.__eq__(y) <==> od==y. Comparison to another OD is
|
277 |
order-sensitive while comparison to a regular mapping is
|
278 |
order-insensitive.
|
279 |
"""
|
280 |
if isinstance(other, OrderedDict): |
281 |
return len(self) == len(other) and self.items() == other.items() |
282 |
return dict.__eq__(self, other) |
283 |
|
284 |
def __ne__(self, other): |
285 |
return not self == other |
286 |
|
287 |
# -- the following methods are only used in Python 2.7 --
|
288 |
|
289 |
def viewkeys(self): |
290 |
"od.viewkeys() -> a set-like object providing a view on od's keys"
|
291 |
return KeysView(self) |
292 |
|
293 |
def viewvalues(self): |
294 |
"od.viewvalues() -> an object providing a view on od's values"
|
295 |
return ValuesView(self) |
296 |
|
297 |
def viewitems(self): |
298 |
"od.viewitems() -> a set-like object providing a view on od's items"
|
299 |
return ItemsView(self) |