diff options
Diffstat (limited to 'Lib/collections.py')
| -rw-r--r-- | Lib/collections.py | 230 |
1 files changed, 125 insertions, 105 deletions
diff --git a/Lib/collections.py b/Lib/collections.py index bb6b15dbcc..d87c55d36b 100644 --- a/Lib/collections.py +++ b/Lib/collections.py @@ -6,37 +6,16 @@ import _abcoll __all__ += _abcoll.__all__ from _collections import deque, defaultdict -from operator import itemgetter as _itemgetter, eq as _eq +from operator import itemgetter as _itemgetter from keyword import iskeyword as _iskeyword import sys as _sys import heapq as _heapq -from itertools import repeat as _repeat, chain as _chain, starmap as _starmap, \ - ifilter as _ifilter, imap as _imap +from itertools import repeat as _repeat, chain as _chain, starmap as _starmap + try: - from thread import get_ident + from thread import get_ident as _get_ident except ImportError: - from dummy_thread import get_ident - -def _recursive_repr(user_function): - 'Decorator to make a repr function return "..." for a recursive call' - repr_running = set() - - def wrapper(self): - key = id(self), get_ident() - if key in repr_running: - return '...' - repr_running.add(key) - try: - result = user_function(self) - finally: - repr_running.discard(key) - return result - - # Can't use functools.wraps() here because of bootstrap issues - wrapper.__module__ = getattr(user_function, '__module__') - wrapper.__doc__ = getattr(user_function, '__doc__') - wrapper.__name__ = getattr(user_function, '__name__') - return wrapper + from dummy_thread import get_ident as _get_ident ################################################################################ @@ -48,17 +27,17 @@ class OrderedDict(dict): # An inherited dict maps keys to values. # The inherited dict provides __getitem__, __len__, __contains__, and get. # The remaining methods are order-aware. - # Big-O running times for all methods are the same as for regular dictionaries. + # Big-O running times for all methods are the same as regular dictionaries. - # The internal self.__map dictionary maps keys to links in a doubly linked list. + # The internal self.__map dict 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). # Each link is stored as a list of length three: [PREV, NEXT, KEY]. def __init__(self, *args, **kwds): - '''Initialize an ordered dictionary. Signature is the same as for - regular dictionaries, but keyword arguments are not recommended - because their insertion order is arbitrary. + '''Initialize an ordered dictionary. The signature is the same as + regular dictionaries, but keyword arguments are not recommended because + their insertion order is arbitrary. ''' if len(args) > 1: @@ -66,17 +45,15 @@ class OrderedDict(dict): try: self.__root except AttributeError: - self.__root = root = [None, None, None] # sentinel node - PREV = 0 - NEXT = 1 - root[PREV] = root[NEXT] = root + self.__root = root = [] # sentinel node + root[:] = [root, root, None] self.__map = {} self.__update(*args, **kwds) def __setitem__(self, key, value, PREV=0, NEXT=1, dict_setitem=dict.__setitem__): 'od.__setitem__(i, y) <==> od[i]=y' - # 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. + # Setting a new item creates a new link at the end of the linked list, + # and the inherited dictionary is updated with the new key/value pair. if key not in self: root = self.__root last = root[PREV] @@ -85,79 +62,82 @@ class OrderedDict(dict): def __delitem__(self, key, PREV=0, NEXT=1, dict_delitem=dict.__delitem__): 'od.__delitem__(y) <==> del od[y]' - # 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. + # Deleting an existing item uses self.__map to find the link which gets + # removed by updating the links in the predecessor and successor nodes. dict_delitem(self, key) - link = self.__map.pop(key) - link_prev = link[PREV] - link_next = link[NEXT] + link_prev, link_next, key = self.__map.pop(key) link_prev[NEXT] = link_next link_next[PREV] = link_prev - def __iter__(self, NEXT=1, KEY=2): + def __iter__(self): 'od.__iter__() <==> iter(od)' # Traverse the linked list in order. + NEXT, KEY = 1, 2 root = self.__root curr = root[NEXT] while curr is not root: yield curr[KEY] curr = curr[NEXT] - def __reversed__(self, PREV=0, KEY=2): + def __reversed__(self): 'od.__reversed__() <==> reversed(od)' # Traverse the linked list in reverse order. + PREV, KEY = 0, 2 root = self.__root curr = root[PREV] while curr is not root: yield curr[KEY] curr = curr[PREV] - def __reduce__(self): - 'Return state information for pickling' - items = [[k, self[k]] for k in self] - tmp = self.__map, self.__root - del self.__map, self.__root - inst_dict = vars(self).copy() - self.__map, self.__root = tmp - if inst_dict: - return (self.__class__, (items,), inst_dict) - return self.__class__, (items,) - def clear(self): 'od.clear() -> None. Remove all items from od.' - try: - for node in self.__map.itervalues(): - del node[:] - self.__root[:] = [self.__root, self.__root, None] - self.__map.clear() - except AttributeError: - pass + for node in self.__map.itervalues(): + del node[:] + root = self.__root + root[:] = [root, root, None] + self.__map.clear() dict.clear(self) - update = __update = MutableMapping.update - keys = MutableMapping.keys - values = MutableMapping.values - items = MutableMapping.items - iterkeys = MutableMapping.iterkeys - itervalues = MutableMapping.itervalues - iteritems = MutableMapping.iteritems - __ne__ = MutableMapping.__ne__ + # -- the following methods do not depend on the internal structure -- - def viewkeys(self): - "od.viewkeys() -> a set-like object providing a view on od's keys" - return KeysView(self) + def keys(self): + 'od.keys() -> list of keys in od' + return list(self) - def viewvalues(self): - "od.viewvalues() -> an object providing a view on od's values" - return ValuesView(self) + def values(self): + 'od.values() -> list of values in od' + return [self[key] for key in self] - def viewitems(self): - "od.viewitems() -> a set-like object providing a view on od's items" - return ItemsView(self) + def items(self): + 'od.items() -> list of (key, value) pairs in od' + return [(key, self[key]) for key in self] + + def iterkeys(self): + 'od.iterkeys() -> an iterator over the keys in od' + return iter(self) + + def itervalues(self): + 'od.itervalues -> an iterator over the values in od' + for k in self: + yield self[k] + + def iteritems(self): + 'od.iteritems -> an iterator over the (key, value) pairs in od' + for k in self: + yield (k, self[k]) + + update = MutableMapping.update + + __update = update # let subclasses override update without breaking __init__ __marker = object() def pop(self, key, default=__marker): + '''od.pop(k[,d]) -> v, remove specified key and return the corresponding + value. If key is not found, d is returned if given, otherwise KeyError + is raised. + + ''' if key in self: result = self[key] del self[key] @@ -184,12 +164,28 @@ class OrderedDict(dict): value = self.pop(key) return key, value - @_recursive_repr - def __repr__(self): + def __repr__(self, _repr_running={}): 'od.__repr__() <==> repr(od)' - if not self: - return '%s()' % (self.__class__.__name__,) - return '%s(%r)' % (self.__class__.__name__, self.items()) + call_key = id(self), _get_ident() + if call_key in _repr_running: + return '...' + _repr_running[call_key] = 1 + try: + if not self: + return '%s()' % (self.__class__.__name__,) + return '%s(%r)' % (self.__class__.__name__, self.items()) + finally: + del _repr_running[call_key] + + def __reduce__(self): + 'Return state information for pickling' + items = [[k, self[k]] for k in self] + inst_dict = vars(self).copy() + for k in vars(OrderedDict()): + inst_dict.pop(k, None) + if inst_dict: + return (self.__class__, (items,), inst_dict) + return self.__class__, (items,) def copy(self): 'od.copy() -> a shallow copy of od' @@ -197,14 +193,14 @@ class OrderedDict(dict): @classmethod def fromkeys(cls, iterable, value=None): - '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S - and values equal to v (which defaults to None). + '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S. + If not specified, the value defaults to None. ''' - d = cls() + self = cls() for key in iterable: - d[key] = value - return d + self[key] = value + return self def __eq__(self, other): '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive @@ -212,10 +208,27 @@ class OrderedDict(dict): ''' if isinstance(other, OrderedDict): - return len(self)==len(other) and \ - all(_imap(_eq, self.iteritems(), other.iteritems())) + return len(self)==len(other) and self.items() == other.items() return dict.__eq__(self, other) + def __ne__(self, other): + 'od.__ne__(y) <==> od!=y' + return not self == other + + # -- the following methods support python 3.x style dictionary views -- + + def viewkeys(self): + "od.viewkeys() -> a set-like object providing a view on od's keys" + return KeysView(self) + + def viewvalues(self): + "od.viewvalues() -> an object providing a view on od's values" + return ValuesView(self) + + def viewitems(self): + "od.viewitems() -> a set-like object providing a view on od's items" + return ItemsView(self) + ################################################################################ ### namedtuple @@ -516,8 +529,8 @@ class Counter(dict): self.subtract(kwds) def copy(self): - 'Like dict.copy() but returns a Counter instance instead of a dict.' - return Counter(self) + 'Return a shallow copy.' + return self.__class__(self) def __reduce__(self): return self.__class__, (dict(self),) @@ -552,10 +565,13 @@ class Counter(dict): if not isinstance(other, Counter): return NotImplemented result = Counter() - for elem in set(self) | set(other): - newcount = self[elem] + other[elem] + for elem, count in self.items(): + newcount = count + other[elem] if newcount > 0: result[elem] = newcount + for elem, count in other.items(): + if elem not in self and count > 0: + result[elem] = count return result def __sub__(self, other): @@ -568,10 +584,13 @@ class Counter(dict): if not isinstance(other, Counter): return NotImplemented result = Counter() - for elem in set(self) | set(other): - newcount = self[elem] - other[elem] + for elem, count in self.items(): + newcount = count - other[elem] if newcount > 0: result[elem] = newcount + for elem, count in other.items(): + if elem not in self and count < 0: + result[elem] = 0 - count return result def __or__(self, other): @@ -584,11 +603,14 @@ class Counter(dict): if not isinstance(other, Counter): return NotImplemented result = Counter() - for elem in set(self) | set(other): - p, q = self[elem], other[elem] - newcount = q if p < q else p + for elem, count in self.items(): + other_count = other[elem] + newcount = other_count if count < other_count else count if newcount > 0: result[elem] = newcount + for elem, count in other.items(): + if elem not in self and count > 0: + result[elem] = count return result def __and__(self, other): @@ -601,11 +623,9 @@ class Counter(dict): if not isinstance(other, Counter): return NotImplemented result = Counter() - if len(self) < len(other): - self, other = other, self - for elem in _ifilter(self.__contains__, other): - p, q = self[elem], other[elem] - newcount = p if p < q else q + for elem, count in self.items(): + other_count = other[elem] + newcount = count if count < other_count else other_count if newcount > 0: result[elem] = newcount return result |