diff options
author | Raymond Hettinger <python@rcn.com> | 2009-03-23 05:19:21 (GMT) |
---|---|---|
committer | Raymond Hettinger <python@rcn.com> | 2009-03-23 05:19:21 (GMT) |
commit | f173654db89ef5a74fd631c3cb996f9d84ce1d1b (patch) | |
tree | 453e13c4dffd5fc1973b84ab8a5c44ca265ffebf /Lib | |
parent | 30364204d3caf04b13264a750b34555072b32e33 (diff) | |
download | cpython-f173654db89ef5a74fd631c3cb996f9d84ce1d1b.zip cpython-f173654db89ef5a74fd631c3cb996f9d84ce1d1b.tar.gz cpython-f173654db89ef5a74fd631c3cb996f9d84ce1d1b.tar.bz2 |
Forward port r70533 and r70538.
Diffstat (limited to 'Lib')
-rw-r--r-- | Lib/collections.py | 77 |
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,) |