[Python-checkins] r70476 - python/branches/py3k/Lib/collections.py

[raymond.hettinger]

Author: raymond.hettinger
Date: Fri Mar 20 00:14:39 2009
New Revision: 70476

Log:
Forward port 70475:  Add implementation notes.  Put methods in more readable order.

Modified:
   python/branches/py3k/Lib/collections.py

Modified: python/branches/py3k/Lib/collections.py
==============================================================================
--- python/branches/py3k/Lib/collections.py	(original)
+++ python/branches/py3k/Lib/collections.py	Fri Mar 20 00:14:39 2009
@@ -18,6 +18,18 @@
 ################################################################################
 
 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 @@
 
     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]
@@ -85,6 +90,13 @@
     values = MutableMapping.values
     items = MutableMapping.items
 
+    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__,)