From dc879f033c9a1fd15e27f7bac2a46d38ca19e8c5 Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Thu, 19 Mar 2009 20:30:56 +0000
Subject: Forward port r70470 and r70473 for OrderedDict to use a doubly linked
 list.

---
 Doc/library/collections.rst  | 12 ++++++++++--
 Lib/collections.py           | 42 +++++++++++++++++++++++++++---------------
 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
-- 
cgit v0.12