summaryrefslogtreecommitdiffstats
path: root/Lib
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2009-03-23 05:19:21 (GMT)
committerRaymond Hettinger <python@rcn.com>2009-03-23 05:19:21 (GMT)
commitf173654db89ef5a74fd631c3cb996f9d84ce1d1b (patch)
tree453e13c4dffd5fc1973b84ab8a5c44ca265ffebf /Lib
parent30364204d3caf04b13264a750b34555072b32e33 (diff)
downloadcpython-f173654db89ef5a74fd631c3cb996f9d84ce1d1b.zip
cpython-f173654db89ef5a74fd631c3cb996f9d84ce1d1b.tar.gz
cpython-f173654db89ef5a74fd631c3cb996f9d84ce1d1b.tar.bz2
Forward port r70533 and r70538.
Diffstat (limited to 'Lib')
-rw-r--r--Lib/collections.py77
1 files changed, 45 insertions, 32 deletions
diff --git a/Lib/collections.py b/Lib/collections.py
index 1ed5e4a..eaecd96 100644
--- a/Lib/collections.py
+++ b/Lib/collections.py
@@ -11,74 +11,87 @@ from operator import itemgetter as _itemgetter
from keyword import iskeyword as _iskeyword
import sys as _sys
import heapq as _heapq
+from weakref import proxy
from itertools import repeat as _repeat, chain as _chain, starmap as _starmap
################################################################################
### OrderedDict
################################################################################
+class _Link(object):
+ __slots__ = 'prev', 'next', 'key', '__weakref__'
+
class OrderedDict(dict, MutableMapping):
'Dictionary that remembers insertion order'
- # The inherited dict maps keys to values.
- # The internal self.__map dictionary maps keys to links in a doubly linked list.
- # The doubly linked list starts and ends with a sentinel element.
- # The sentinel element never gets deleted. It simplifies the algorithm.
- # Setting a new item causes a new link to append to the doubly linked list.
- # Deleting an item uses self.__map to find the link, which is then removed.
- # Iteration follows the linked list in order.
- # Reverse iteration follows the links backwards.
+ # An inherited dict maps keys to values.
# The inherited dict provides __getitem__, __len__, __contains__, and get.
# The remaining methods are order-aware.
- # Big-Oh running times for all methods are the same as for regular dictionaries.
+ # Big-O running times for all methods are the same as for regular dictionaries.
+
+ # The internal self.__map dictionary maps keys to links in a doubly linked list.
+ # The circular doubly linked list starts and ends with a sentinel element.
+ # The sentinel element never gets deleted (this simplifies the algorithm).
+ # The prev/next links are weakref proxies (to prevent circular references).
+ # Individual links are kept alive by the hard reference in self.__map.
+ # Those hard references disappear when a key is deleted from an OrderedDict.
def __init__(self, *args, **kwds):
if len(args) > 1:
raise TypeError('expected at most 1 arguments, got %d' % len(args))
try:
- self.__end
+ self.__root
except AttributeError:
+ self.__root = _Link() # sentinel node for the doubly linked list
self.clear()
self.update(*args, **kwds)
def clear(self):
- self.__end = end = []
- end += [None, end, end] # sentinel node for doubly linked list
- self.__map = {} # key --> [key, prev, next]
+ root = self.__root
+ root.prev = root.next = root
+ self.__map = {}
dict.clear(self)
def __setitem__(self, key, value):
+ # Setting a new item creates a new link which goes at the end of the linked
+ # list, and the inherited dictionary is updated with the new key/value pair.
if key not in self:
- end = self.__end
- curr = end[1]
- curr[2] = end[1] = self.__map[key] = [key, curr, end]
+ self.__map[key] = link = _Link()
+ root = self.__root
+ last = root.prev
+ link.prev, link.next, link.key = last, root, key
+ last.next = root.prev = proxy(link)
dict.__setitem__(self, key, value)
def __delitem__(self, key):
+ # Deleting an existing item uses self.__map to find the link which is
+ # then removed by updating the links in the predecessor and successor nodes.
dict.__delitem__(self, key)
- key, prev, next = self.__map.pop(key)
- prev[2] = next
- next[1] = prev
+ link = self.__map.pop(key)
+ link.prev.next = link.next
+ link.next.prev = link.prev
def __iter__(self):
- end = self.__end
- curr = end[2] # start at first link
- while curr is not end:
- yield curr[0] # yield KEY for each link
- curr = curr[2] # goto next link
+ # Traverse the linked list in order.
+ root = self.__root
+ curr = root.next
+ while curr is not root:
+ yield curr.key
+ curr = curr.next
def __reversed__(self):
- end = self.__end
- curr = end[1] # start at last link
- while curr is not end:
- yield curr[0] # yield KEY for each link
- curr = curr[1] # goto prev link
+ # Traverse the linked list in reverse order.
+ root = self.__root
+ curr = root.prev
+ while curr is not root:
+ yield curr.key
+ curr = curr.prev
def __reduce__(self):
items = [[k, self[k]] for k in self]
- tmp = self.__map, self.__end
- del self.__map, self.__end
+ tmp = self.__map, self.__root
+ del self.__map, self.__root
inst_dict = vars(self).copy()
- self.__map, self.__end = tmp
+ self.__map, self.__root = tmp
if inst_dict:
return (self.__class__, (items,), inst_dict)
return self.__class__, (items,)