diff options
| -rw-r--r-- | Doc/library/collections.rst | 12 | ||||
| -rw-r--r-- | Lib/collections.py | 42 | ||||
| -rw-r--r-- | Lib/test/test_collections.py | 7 |
3 files changed, 44 insertions, 17 deletions
diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst index 1a23fca..b136cf1 100644 --- a/Doc/library/collections.rst +++ b/Doc/library/collections.rst @@ -836,8 +836,11 @@ the items are returned in the order their keys were first added. .. versionadded:: 3.1 -The :meth:`popitem` method for ordered dictionaries returns and removes the -last added entry. The key/value pairs are returned in LIFO order. +.. method:: OrderedDict.popitem(last=True) + + The :meth:`popitem` method for ordered dictionaries returns and removes + a (key, value) pair. The pairs are returned in LIFO order if *last* is + true or FIFO order if false. Equality tests between :class:`OrderedDict` objects are order-sensitive and are implemented as ``list(od1.items())==list(od2.items())``. @@ -846,6 +849,11 @@ Equality tests between :class:`OrderedDict` objects and other This allows :class:`OrderedDict` objects to be substituted anywhere a regular dictionary is used. +.. seealso:: + + `Equivalent OrderedDict recipe <http://code.activestate.com/recipes/576693/>`_ + that runs on Python 2.4 or later. + :class:`UserDict` objects ------------------------- diff --git a/Lib/collections.py b/Lib/collections.py index 2b0de18..f1b62c7 100644 --- a/Lib/collections.py +++ b/Lib/collections.py @@ -23,45 +23,57 @@ class OrderedDict(dict, MutableMapping): if len(args) > 1: raise TypeError('expected at most 1 arguments, got %d' % len(args)) try: - self.__keys + self.__end except AttributeError: - # Note the underlying data structure for this class is likely to - # change in the future. Do not rely on it or access it directly. - self.__keys = deque() + self.clear() self.update(*args, **kwds) def clear(self): - self.__keys.clear() + self.__end = end = [] + end += [None, end, end] # sentinel node for doubly linked list + self.__map = {} # key --> [key, prev, next] dict.clear(self) def __setitem__(self, key, value): if key not in self: - self.__keys.append(key) + end = self.__end + curr = end[1] + curr[2] = end[1] = self.__map[key] = [key, curr, end] dict.__setitem__(self, key, value) def __delitem__(self, key): dict.__delitem__(self, key) - self.__keys.remove(key) + key, prev, next = self.__map.pop(key) + prev[2] = next + next[1] = prev def __iter__(self): - return iter(self.__keys) + end = self.__end + curr = end[2] + while curr is not end: + yield curr[0] + curr = curr[2] def __reversed__(self): - return reversed(self.__keys) + end = self.__end + curr = end[1] + while curr is not end: + yield curr[0] + curr = curr[1] - def popitem(self): + def popitem(self, last=True): if not self: raise KeyError('dictionary is empty') - key = self.__keys.pop() - value = dict.pop(self, key) + key = next(reversed(self)) if last else next(iter(self)) + value = self.pop(key) return key, value def __reduce__(self): items = [[k, self[k]] for k in self] - tmp = self.__keys - del self.__keys + tmp = self.__map, self.__end + del self.__map, self.__end inst_dict = vars(self).copy() - self.__keys = tmp + self.__map, self.__end = tmp if inst_dict: return (self.__class__, (items,), inst_dict) return self.__class__, (items,) diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py index 1800bec..3d00973 100644 --- a/Lib/test/test_collections.py +++ b/Lib/test/test_collections.py @@ -770,12 +770,19 @@ class TestOrderedDict(unittest.TestCase): class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol): type2test = OrderedDict + def test_popitem(self): + d = self._empty_mapping() + self.assertRaises(KeyError, d.popitem) + class MyOrderedDict(OrderedDict): pass class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol): type2test = MyOrderedDict + def test_popitem(self): + d = self._empty_mapping() + self.assertRaises(KeyError, d.popitem) import doctest, collections |