root / kamaki / clients / utils / ordereddict.py @ c6ebe715
History  View  Annotate  Download (10.2 kB)
1 
# Copyright 20122013 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 orderaware.

53 
BigO 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 
ordersensitive while comparison to a regular mapping is

278 
orderinsensitive.

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 setlike 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 setlike object providing a view on od's items"

299 
return ItemsView(self) 