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