Add method to OrderedDict for repositioning keys to the ends.

3 files changed, 31 insertions, 8 deletions

diff --git a/Lib/collections.py b/Lib/collections.py
index c3c51d120f..00886ef06e 100644
--- a/Lib/collections.py
+++ b/Lib/collections.py
@@ -173,18 +173,29 @@ class OrderedDict(dict, MutableMapping):
     def __del__(self):
         self.clear()                # eliminate cyclical references
 
-    def _renew(self, key, PREV=0, NEXT=1):
-        'Fast version of self[key]=self.pop(key).   Private method for internal use.'
+    def move_to_end(self, key, last=True, PREV=0, NEXT=1):
+        '''Move an existing element to the end (or beginning if last==False).
+
+        Raises KeyError if the element does not exist.
+        When last=True, acts like a fast version of self[key]=self.pop(key).
+
+        '''
         link = self.__map[key]
         link_prev = link[PREV]
         link_next = link[NEXT]
         link_prev[NEXT] = link_next
         link_next[PREV] = link_prev
         root = self.__root
-        last = root[PREV]
-        link[PREV] = last
-        link[NEXT] = root
-        last[NEXT] = root[PREV] = link
+        if last:
+            last = root[PREV]
+            link[PREV] = last
+            link[NEXT] = root
+            last[NEXT] = root[PREV] = link
+        else:
+            first = root[NEXT]
+            link[PREV] = root
+            link[NEXT] = first
+            root[NEXT] = first[PREV] = link
 
 
 ################################################################################
diff --git a/Lib/functools.py b/Lib/functools.py
index b2df390529..a723f66a3c 100644
--- a/Lib/functools.py
+++ b/Lib/functools.py
@@ -127,7 +127,7 @@ def lru_cache(maxsize=100):
                             len=len, KeyError=KeyError):
         cache = OrderedDict()           # ordered least recent to most recent
         cache_popitem = cache.popitem
-        cache_renew = cache._renew
+        cache_renew = cache.move_to_end
         kwd_mark = object()             # separate positional and keyword args
         lock = Lock()
 
diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py
index 75d660d628..7beb061b2f 100644
--- a/Lib/test/test_collections.py
+++ b/Lib/test/test_collections.py
@@ -973,7 +973,19 @@ class TestOrderedDict(unittest.TestCase):
         od['a'] = 1
         self.assertEqual(list(od.items()), [('b', 2), ('a', 1)])
 
-
+    def test_move_to_end(self):
+        od = OrderedDict.fromkeys('abcde')
+        self.assertEqual(list(od), list('abcde'))
+        od.move_to_end('c')
+        self.assertEqual(list(od), list('abdec'))
+        od.move_to_end('c', 0)
+        self.assertEqual(list(od), list('cabde'))
+        od.move_to_end('c', 0)
+        self.assertEqual(list(od), list('cabde'))
+        od.move_to_end('e')
+        self.assertEqual(list(od), list('cabde'))
+        with self.assertRaises(KeyError):
+            od.move_to_end('x')
 
 class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
     type2test = OrderedDict