From 45a03a20290a4c91f22787b2a13c2db195022f47 Mon Sep 17 00:00:00 2001
From: "raymond.hettinger"
 <raymond.hettinger@6015fed2-1504-0410-9fe1-9d1591cc4771>
Date: Thu, 19 Mar 2009 23:12:41 +0000
Subject: [PATCH] * Add implementation notes. * Re-order methods so that those
 touching the underlying data   structure come first and the derived methods
 come last.

git-svn-id: http://svn.python.org/projects/python/trunk@70475 6015fed2-1504-0410-9fe1-9d1591cc4771
---
 Lib/collections.py | 38 +++++++++++++++++++++++++-------------
 1 file changed, 25 insertions(+), 13 deletions(-)

diff --git a/Lib/collections.py b/Lib/collections.py
index 8c0b4265f4..130337df82 100644
--- a/Lib/collections.py
+++ b/Lib/collections.py
@@ -18,6 +18,18 @@ from itertools import repeat as _repeat, chain as _chain, starmap as _starmap, \
 ################################################################################
 
 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 cause 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.
+    # The inherited dict provides __getitem__, __len__, __contains__, and get.
+    # The remaining methods are order-aware.
+    # Big-Oh running times for all methods is the same as for regular dictionaries.
 
     def __init__(self, *args, **kwds):
         if len(args) > 1:
@@ -49,24 +61,17 @@ class OrderedDict(dict, MutableMapping):
 
     def __iter__(self):
         end = self.__end
-        curr = end[2]
+        curr = end[2]                   # start at first link
         while curr is not end:
-            yield curr[0]
-            curr = curr[2]
+            yield curr[0]               # yield KEY for each link
+            curr = curr[2]              # goto next link
 
     def __reversed__(self):
         end = self.__end
-        curr = end[1]
+        curr = end[1]                   # start at last link
         while curr is not end:
-            yield curr[0]
-            curr = curr[1]
-
-    def popitem(self, last=True):
-        if not self:
-            raise KeyError('dictionary is empty')
-        key = next(reversed(self)) if last else next(iter(self))
-        value = self.pop(key)
-        return key, value
+            yield curr[0]               # yield KEY for each link
+            curr = curr[1]              # goto prev link
 
     def __reduce__(self):
         items = [[k, self[k]] for k in self]
@@ -89,6 +94,13 @@ class OrderedDict(dict, MutableMapping):
     iteritems = MutableMapping.iteritems
     __ne__ = MutableMapping.__ne__
 
+    def popitem(self, last=True):
+        if not self:
+            raise KeyError('dictionary is empty')
+        key = next(reversed(self)) if last else next(iter(self))
+        value = self.pop(key)
+        return key, value
+
     def __repr__(self):
         if not self:
             return '%s()' % (self.__class__.__name__,)
-- 
2.11.4.GIT