Skip to content

Commit 1a469d7

Browse files
michilumichilu
committed
Copy collections.OrderedDict from 3.2
1 parent a2a9675 commit 1a469d7

1 file changed

Lines changed: 216 additions & 0 deletions

File tree

‎functools32.py‎

Lines changed: 216 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,222 @@
1818
except:
1919
from _dummy_thread import allocate_lock as Lock
2020

21+
################################################################################
22+
### OrderedDict
23+
################################################################################
24+
25+
class _Link(object):
26+
__slots__ = 'prev', 'next', 'key', '__weakref__'
27+
28+
class OrderedDict(dict):
29+
'Dictionary that remembers insertion order'
30+
# An inherited dict maps keys to values.
31+
# The inherited dict provides __getitem__, __len__, __contains__, and get.
32+
# The remaining methods are order-aware.
33+
# Big-O running times for all methods are the same as regular dictionaries.
34+
35+
# The internal self.__map dict maps keys to links in a doubly linked list.
36+
# The circular doubly linked list starts and ends with a sentinel element.
37+
# The sentinel element never gets deleted (this simplifies the algorithm).
38+
# The sentinel is in self.__hardroot with a weakref proxy in self.__root.
39+
# The prev links are weakref proxies (to prevent circular references).
40+
# Individual links are kept alive by the hard reference in self.__map.
41+
# Those hard references disappear when a key is deleted from an OrderedDict.
42+
43+
def __init__(self, *args, **kwds):
44+
'''Initialize an ordered dictionary. The signature is the same as
45+
regular dictionaries, but keyword arguments are not recommended because
46+
their insertion order is arbitrary.
47+
48+
'''
49+
if len(args) > 1:
50+
raise TypeError('expected at most 1 arguments, got %d' % len(args))
51+
try:
52+
self.__root
53+
except AttributeError:
54+
self.__hardroot = _Link()
55+
self.__root = root = _proxy(self.__hardroot)
56+
root.prev = root.next = root
57+
self.__map = {}
58+
self.__update(*args, **kwds)
59+
60+
def __setitem__(self, key, value,
61+
dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
62+
'od.__setitem__(i, y) <==> od[i]=y'
63+
# Setting a new item creates a new link at the end of the linked list,
64+
# and the inherited dictionary is updated with the new key/value pair.
65+
if key not in self:
66+
self.__map[key] = link = Link()
67+
root = self.__root
68+
last = root.prev
69+
link.prev, link.next, link.key = last, root, key
70+
last.next = link
71+
root.prev = proxy(link)
72+
dict_setitem(self, key, value)
73+
74+
def __delitem__(self, key, dict_delitem=dict.__delitem__):
75+
'od.__delitem__(y) <==> del od[y]'
76+
# Deleting an existing item uses self.__map to find the link which gets
77+
# removed by updating the links in the predecessor and successor nodes.
78+
dict_delitem(self, key)
79+
link = self.__map.pop(key)
80+
link_prev = link.prev
81+
link_next = link.next
82+
link_prev.next = link_next
83+
link_next.prev = link_prev
84+
85+
def __iter__(self):
86+
'od.__iter__() <==> iter(od)'
87+
# Traverse the linked list in order.
88+
root = self.__root
89+
curr = root.next
90+
while curr is not root:
91+
yield curr.key
92+
curr = curr.next
93+
94+
def __reversed__(self):
95+
'od.__reversed__() <==> reversed(od)'
96+
# Traverse the linked list in reverse order.
97+
root = self.__root
98+
curr = root.prev
99+
while curr is not root:
100+
yield curr.key
101+
curr = curr.prev
102+
103+
def clear(self):
104+
'od.clear() -> None. Remove all items from od.'
105+
root = self.__root
106+
root.prev = root.next = root
107+
self.__map.clear()
108+
dict.clear(self)
109+
110+
def popitem(self, last=True):
111+
'''od.popitem() -> (k, v), return and remove a (key, value) pair.
112+
Pairs are returned in LIFO order if last is true or FIFO order if false.
113+
114+
'''
115+
if not self:
116+
raise KeyError('dictionary is empty')
117+
root = self.__root
118+
if last:
119+
link = root.prev
120+
link_prev = link.prev
121+
link_prev.next = root
122+
root.prev = link_prev
123+
else:
124+
link = root.next
125+
link_next = link.next
126+
root.next = link_next
127+
link_next.prev = root
128+
key = link.key
129+
del self.__map[key]
130+
value = dict.pop(self, key)
131+
return key, value
132+
133+
def move_to_end(self, key, last=True):
134+
'''Move an existing element to the end (or beginning if last==False).
135+
136+
Raises KeyError if the element does not exist.
137+
When last=True, acts like a fast version of self[key]=self.pop(key).
138+
139+
'''
140+
link = self.__map[key]
141+
link_prev = link.prev
142+
link_next = link.next
143+
link_prev.next = link_next
144+
link_next.prev = link_prev
145+
root = self.__root
146+
if last:
147+
last = root.prev
148+
link.prev = last
149+
link.next = root
150+
last.next = root.prev = link
151+
else:
152+
first = root.next
153+
link.prev = root
154+
link.next = first
155+
root.next = first.prev = link
156+
157+
def __sizeof__(self):
158+
sizeof = _sys.getsizeof
159+
n = len(self) + 1 # number of links including root
160+
size = sizeof(self.__dict__) # instance dictionary
161+
size += sizeof(self.__map) * 2 # internal dict and inherited dict
162+
size += sizeof(self.__hardroot) * n # link objects
163+
size += sizeof(self.__root) * n # proxy objects
164+
return size
165+
166+
update = __update = MutableMapping.update
167+
keys = MutableMapping.keys
168+
values = MutableMapping.values
169+
items = MutableMapping.items
170+
__ne__ = MutableMapping.__ne__
171+
172+
__marker = object()
173+
174+
def pop(self, key, default=__marker):
175+
'''od.pop(k[,d]) -> v, remove specified key and return the corresponding
176+
value. If key is not found, d is returned if given, otherwise KeyError
177+
is raised.
178+
179+
'''
180+
if key in self:
181+
result = self[key]
182+
del self[key]
183+
return result
184+
if default is self.__marker:
185+
raise KeyError(key)
186+
return default
187+
188+
def setdefault(self, key, default=None):
189+
'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
190+
if key in self:
191+
return self[key]
192+
self[key] = default
193+
return default
194+
195+
@_recursive_repr()
196+
def __repr__(self):
197+
'od.__repr__() <==> repr(od)'
198+
if not self:
199+
return '%s()' % (self.__class__.__name__,)
200+
return '%s(%r)' % (self.__class__.__name__, list(self.items()))
201+
202+
def __reduce__(self):
203+
'Return state information for pickling'
204+
items = [[k, self[k]] for k in self]
205+
inst_dict = vars(self).copy()
206+
for k in vars(OrderedDict()):
207+
inst_dict.pop(k, None)
208+
if inst_dict:
209+
return (self.__class__, (items,), inst_dict)
210+
return self.__class__, (items,)
211+
212+
def copy(self):
213+
'od.copy() -> a shallow copy of od'
214+
return self.__class__(self)
215+
216+
@classmethod
217+
def fromkeys(cls, iterable, value=None):
218+
'''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.
219+
If not specified, the value defaults to None.
220+
221+
'''
222+
self = cls()
223+
for key in iterable:
224+
self[key] = value
225+
return self
226+
227+
def __eq__(self, other):
228+
'''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
229+
while comparison to a regular mapping is order-insensitive.
230+
231+
'''
232+
if isinstance(other, OrderedDict):
233+
return len(self)==len(other) and \
234+
all(p==q for p, q in zip(self.items(), other.items()))
235+
return dict.__eq__(self, other)
236+
21237
# update_wrapper() and wraps() are tools to help write
22238
# wrapper functions that can handle naive introspection
23239

0 commit comments

Comments
 (0)