Add method to OrderedDict for repositioning keys to the ends.
diff --git a/Lib/collections.py b/Lib/collections.py
index c3c51d1..00886ef 100644
--- a/Lib/collections.py
+++ b/Lib/collections.py
@@ -173,18 +173,29 @@
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 b2df390..a723f66 100644
--- a/Lib/functools.py
+++ b/Lib/functools.py
@@ -127,7 +127,7 @@
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 75d660d..7beb061 100644
--- a/Lib/test/test_collections.py
+++ b/Lib/test/test_collections.py
@@ -973,7 +973,19 @@
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