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

[raymond.hettinger]

Author: raymond.hettinger
Date: Thu Sep  2 20:44:16 2010
New Revision: 84437

Log:
Make OrderedDict.popitem() a bit smarter and faster

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	Thu Sep  2 20:44:16 2010
@@ -108,25 +108,37 @@
             pass
         dict.clear(self)
 
-    setdefault = MutableMapping.setdefault
-    update = MutableMapping.update
-    pop = MutableMapping.pop
-    keys = MutableMapping.keys
-    values = MutableMapping.values
-    items = MutableMapping.items
-    __ne__ = MutableMapping.__ne__
-
-    def popitem(self, last=True):
+    def popitem(self, last=True, PREV=0, NEXT=1, KEY=2, dict_pop=dict.pop):
         '''od.popitem() -> (k, v), return and remove a (key, value) pair.
         Pairs are returned in LIFO order if last is true or FIFO order if false.
 
         '''
         if not self:
             raise KeyError('dictionary is empty')
-        key = next(reversed(self) if last else iter(self))
-        value = self.pop(key)
+        root = self.__root
+        if last:                    # link_prev <--> link <--> root
+            link = root[PREV]
+            link_prev = link[PREV]
+            link_prev[NEXT] = root
+            root[PREV] = link_prev
+        else:                       # root <--> link <--> link_next
+            link = root[NEXT]
+            link_next = link[NEXT]
+            root[NEXT] = link_next
+            link_next[PREV] = root
+        key = link[KEY]
+        del self.__map[key]
+        value = dict_pop(self, key)
         return key, value
 
+    setdefault = MutableMapping.setdefault
+    update = MutableMapping.update
+    pop = MutableMapping.pop
+    keys = MutableMapping.keys
+    values = MutableMapping.values
+    items = MutableMapping.items
+    __ne__ = MutableMapping.__ne__
+
     def __repr__(self):
         'od.__repr__() <==> repr(od)'
         if not self: