gvsig-scripting / org.gvsig.scripting / trunk / org.gvsig.scripting / org.gvsig.scripting.app / org.gvsig.scripting.app.mainplugin / src / main / resources-plugin / scripting / lib / requests / packages / urllib3 / packages / ordered_dict.py @ 564
History | View | Annotate | Download (8.73 KB)
1 |
# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.
|
---|---|
2 |
# Passes Python2.7's test suite and incorporates all the latest updates.
|
3 |
# Copyright 2009 Raymond Hettinger, released under the MIT License.
|
4 |
# http://code.activestate.com/recipes/576693/
|
5 |
try:
|
6 |
from thread import get_ident as _get_ident |
7 |
except ImportError: |
8 |
from dummy_thread import get_ident as _get_ident |
9 |
|
10 |
try:
|
11 |
from _abcoll import KeysView, ValuesView, ItemsView |
12 |
except ImportError: |
13 |
pass
|
14 |
|
15 |
|
16 |
class OrderedDict(dict): |
17 |
'Dictionary that remembers insertion order'
|
18 |
# An inherited dict maps keys to values.
|
19 |
# The inherited dict provides __getitem__, __len__, __contains__, and get.
|
20 |
# The remaining methods are order-aware.
|
21 |
# Big-O running times for all methods are the same as for regular dictionaries.
|
22 |
|
23 |
# The internal self.__map dictionary maps keys to links in a doubly linked list.
|
24 |
# The circular doubly linked list starts and ends with a sentinel element.
|
25 |
# The sentinel element never gets deleted (this simplifies the algorithm).
|
26 |
# Each link is stored as a list of length three: [PREV, NEXT, KEY].
|
27 |
|
28 |
def __init__(self, *args, **kwds): |
29 |
'''Initialize an ordered dictionary. Signature is the same as for
|
30 |
regular dictionaries, but keyword arguments are not recommended
|
31 |
because their insertion order is arbitrary.
|
32 |
|
33 |
'''
|
34 |
if len(args) > 1: |
35 |
raise TypeError('expected at most 1 arguments, got %d' % len(args)) |
36 |
try:
|
37 |
self.__root
|
38 |
except AttributeError: |
39 |
self.__root = root = [] # sentinel node |
40 |
root[:] = [root, root, None]
|
41 |
self.__map = {}
|
42 |
self.__update(*args, **kwds)
|
43 |
|
44 |
def __setitem__(self, key, value, dict_setitem=dict.__setitem__): |
45 |
'od.__setitem__(i, y) <==> od[i]=y'
|
46 |
# Setting a new item creates a new link which goes at the end of the linked
|
47 |
# list, and the inherited dictionary is updated with the new key/value pair.
|
48 |
if key not in self: |
49 |
root = self.__root
|
50 |
last = root[0]
|
51 |
last[1] = root[0] = self.__map[key] = [last, root, key] |
52 |
dict_setitem(self, key, value)
|
53 |
|
54 |
def __delitem__(self, key, dict_delitem=dict.__delitem__): |
55 |
'od.__delitem__(y) <==> del od[y]'
|
56 |
# Deleting an existing item uses self.__map to find the link which is
|
57 |
# then removed by updating the links in the predecessor and successor nodes.
|
58 |
dict_delitem(self, key)
|
59 |
link_prev, link_next, key = self.__map.pop(key)
|
60 |
link_prev[1] = link_next
|
61 |
link_next[0] = link_prev
|
62 |
|
63 |
def __iter__(self): |
64 |
'od.__iter__() <==> iter(od)'
|
65 |
root = self.__root
|
66 |
curr = root[1]
|
67 |
while curr is not root: |
68 |
yield curr[2] |
69 |
curr = curr[1]
|
70 |
|
71 |
def __reversed__(self): |
72 |
'od.__reversed__() <==> reversed(od)'
|
73 |
root = self.__root
|
74 |
curr = root[0]
|
75 |
while curr is not root: |
76 |
yield curr[2] |
77 |
curr = curr[0]
|
78 |
|
79 |
def clear(self): |
80 |
'od.clear() -> None. Remove all items from od.'
|
81 |
try:
|
82 |
for node in self.__map.itervalues(): |
83 |
del node[:]
|
84 |
root = self.__root
|
85 |
root[:] = [root, root, None]
|
86 |
self.__map.clear()
|
87 |
except AttributeError: |
88 |
pass
|
89 |
dict.clear(self) |
90 |
|
91 |
def popitem(self, last=True): |
92 |
'''od.popitem() -> (k, v), return and remove a (key, value) pair.
|
93 |
Pairs are returned in LIFO order if last is true or FIFO order if false.
|
94 |
|
95 |
'''
|
96 |
if not self: |
97 |
raise KeyError('dictionary is empty') |
98 |
root = self.__root
|
99 |
if last:
|
100 |
link = root[0]
|
101 |
link_prev = link[0]
|
102 |
link_prev[1] = root
|
103 |
root[0] = link_prev
|
104 |
else:
|
105 |
link = root[1]
|
106 |
link_next = link[1]
|
107 |
root[1] = link_next
|
108 |
link_next[0] = root
|
109 |
key = link[2]
|
110 |
del self.__map[key] |
111 |
value = dict.pop(self, key) |
112 |
return key, value
|
113 |
|
114 |
# -- the following methods do not depend on the internal structure --
|
115 |
|
116 |
def keys(self): |
117 |
'od.keys() -> list of keys in od'
|
118 |
return list(self) |
119 |
|
120 |
def values(self): |
121 |
'od.values() -> list of values in od'
|
122 |
return [self[key] for key in self] |
123 |
|
124 |
def items(self): |
125 |
'od.items() -> list of (key, value) pairs in od'
|
126 |
return [(key, self[key]) for key in self] |
127 |
|
128 |
def iterkeys(self): |
129 |
'od.iterkeys() -> an iterator over the keys in od'
|
130 |
return iter(self) |
131 |
|
132 |
def itervalues(self): |
133 |
'od.itervalues -> an iterator over the values in od'
|
134 |
for k in self: |
135 |
yield self[k] |
136 |
|
137 |
def iteritems(self): |
138 |
'od.iteritems -> an iterator over the (key, value) items in od'
|
139 |
for k in self: |
140 |
yield (k, self[k]) |
141 |
|
142 |
def update(*args, **kwds): |
143 |
'''od.update(E, **F) -> None. Update od from dict/iterable E and F.
|
144 |
|
145 |
If E is a dict instance, does: for k in E: od[k] = E[k]
|
146 |
If E has a .keys() method, does: for k in E.keys(): od[k] = E[k]
|
147 |
Or if E is an iterable of items, does: for k, v in E: od[k] = v
|
148 |
In either case, this is followed by: for k, v in F.items(): od[k] = v
|
149 |
|
150 |
'''
|
151 |
if len(args) > 2: |
152 |
raise TypeError('update() takes at most 2 positional ' |
153 |
'arguments (%d given)' % (len(args),)) |
154 |
elif not args: |
155 |
raise TypeError('update() takes at least 1 argument (0 given)') |
156 |
self = args[0] |
157 |
# Make progressively weaker assumptions about "other"
|
158 |
other = () |
159 |
if len(args) == 2: |
160 |
other = args[1]
|
161 |
if isinstance(other, dict): |
162 |
for key in other: |
163 |
self[key] = other[key]
|
164 |
elif hasattr(other, 'keys'): |
165 |
for key in other.keys(): |
166 |
self[key] = other[key]
|
167 |
else:
|
168 |
for key, value in other: |
169 |
self[key] = value
|
170 |
for key, value in kwds.items(): |
171 |
self[key] = value
|
172 |
|
173 |
__update = update # let subclasses override update without breaking __init__
|
174 |
|
175 |
__marker = object()
|
176 |
|
177 |
def pop(self, key, default=__marker): |
178 |
'''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
|
179 |
If key is not found, d is returned if given, otherwise KeyError is raised.
|
180 |
|
181 |
'''
|
182 |
if key in self: |
183 |
result = self[key]
|
184 |
del self[key] |
185 |
return result
|
186 |
if default is self.__marker: |
187 |
raise KeyError(key) |
188 |
return default
|
189 |
|
190 |
def setdefault(self, key, default=None): |
191 |
'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
|
192 |
if key in self: |
193 |
return self[key] |
194 |
self[key] = default
|
195 |
return default
|
196 |
|
197 |
def __repr__(self, _repr_running={}): |
198 |
'od.__repr__() <==> repr(od)'
|
199 |
call_key = id(self), _get_ident() |
200 |
if call_key in _repr_running: |
201 |
return '...' |
202 |
_repr_running[call_key] = 1
|
203 |
try:
|
204 |
if not self: |
205 |
return '%s()' % (self.__class__.__name__,) |
206 |
return '%s(%r)' % (self.__class__.__name__, self.items()) |
207 |
finally:
|
208 |
del _repr_running[call_key]
|
209 |
|
210 |
def __reduce__(self): |
211 |
'Return state information for pickling'
|
212 |
items = [[k, self[k]] for k in self] |
213 |
inst_dict = vars(self).copy() |
214 |
for k in vars(OrderedDict()): |
215 |
inst_dict.pop(k, None)
|
216 |
if inst_dict:
|
217 |
return (self.__class__, (items,), inst_dict) |
218 |
return self.__class__, (items,) |
219 |
|
220 |
def copy(self): |
221 |
'od.copy() -> a shallow copy of od'
|
222 |
return self.__class__(self) |
223 |
|
224 |
@classmethod
|
225 |
def fromkeys(cls, iterable, value=None): |
226 |
'''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
|
227 |
and values equal to v (which defaults to None).
|
228 |
|
229 |
'''
|
230 |
d = cls() |
231 |
for key in iterable: |
232 |
d[key] = value |
233 |
return d
|
234 |
|
235 |
def __eq__(self, other): |
236 |
'''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
|
237 |
while comparison to a regular mapping is order-insensitive.
|
238 |
|
239 |
'''
|
240 |
if isinstance(other, OrderedDict): |
241 |
return len(self)==len(other) and self.items() == other.items() |
242 |
return dict.__eq__(self, other) |
243 |
|
244 |
def __ne__(self, other): |
245 |
return not self == other |
246 |
|
247 |
# -- the following methods are only used in Python 2.7 --
|
248 |
|
249 |
def viewkeys(self): |
250 |
"od.viewkeys() -> a set-like object providing a view on od's keys"
|
251 |
return KeysView(self) |
252 |
|
253 |
def viewvalues(self): |
254 |
"od.viewvalues() -> an object providing a view on od's values"
|
255 |
return ValuesView(self) |
256 |
|
257 |
def viewitems(self): |
258 |
"od.viewitems() -> a set-like object providing a view on od's items"
|
259 |
return ItemsView(self) |