[Python-checkins] r70539 - python/branches/py3k/Lib/collections.py
raymond.hettinger
python-checkins at python.org
Mon Mar 23 06:19:21 CET 2009
Author: raymond.hettinger
Date: Mon Mar 23 06:19:21 2009
New Revision: 70539
Log:
Forward port r70533 and r70538.
Modified:
python/branches/py3k/Lib/collections.py
Modified: python/branches/py3k/Lib/collections.py
==============================================================================
--- python/branches/py3k/Lib/collections.py (original)
+++ python/branches/py3k/Lib/collections.py Mon Mar 23 06:19:21 2009
@@ -11,74 +11,87 @@
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,)
More information about the Python-checkins
mailing list