Forward port r70470 and r70473 for OrderedDict to use a doubly linked list.
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 @@
.. 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 @@
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 @@
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 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