homepage

It can be useful to rotate an OrderedDict (for example when managing a circular playlist). I haven't found any efficient way to do so from user code, without poking at the internals.
Actually, I envision three methods:
 OrderedDict.rotate(self, n):
 rotate n steps to the right (similarly to deque.rotate())
 OrderedDict.rotate_at(self, key):
 rotate so that the given key ends up in first position
 OrderedDict.rotate_after(self, key):
 rotate so that the given key ends up in last position
(rotate_at, rotate_after could be merged in a single method with a "last" argument, if deemed more elegant)
Note: another solution to the playlist problem would be to have insert_after() and insert_before() methods.

Will attach patch when I get free (10 hours from now)

It is trivial.
def rotate(od, n):
 for i in range(n):
 k, v = od.popitem(False)
 od[k] = v
And those functions look too specialized.

> It is trivial.
> 
> def rotate(od, n):
> for i in range(n):
> k, v = od.popitem(False)
> od[k] = v
That's O(n), with many spurious insertions and deletions.
> And those functions look too specialized.
How so? rotating sounds quite generic to me. deques already allow
rotating.

> That's O(n), with many spurious insertions and deletions.
Any implementation is O(n).
> deques already allow rotating.
I agree that the rotation makes some sense for such collections as deque or OrderedDict (although it is easy implemented in user code). But there are no rotate_at() and rotate_after() in deque.

> > That's O(n), with many spurious insertions and deletions.
> 
> Any implementation is O(n).
For rotate() perhaps (but still, it can be more efficient in that it can
just move the list head once instead of repeatedly deleting and
inserting elements). But rotate_at() / rotate_after() can probably be
O(1), unless I'm missing something.
> > deques already allow rotating.
> 
> I agree that the rotation makes some sense for such collections as
> deque or OrderedDict (although it is easy implemented in user code).
> But there are no rotate_at() and rotate_after() in deque.
That's because a deque is not a mapping ;-) In other words, if a deque
was enough I'd be using a deque, not a OrderedDict.

> But rotate_at() / rotate_after() can probably be O(1), unless I'm missing something.
Hmm, perhaps. But only for current implementation. With more effective deque-like implementation (when linked list items grouped in fixed-size chunks) it will be O(n).

> > But rotate_at() / rotate_after() can probably be O(1), unless I'm
> missing something.
> 
> Hmm, perhaps. But only for current implementation. With more effective
> deque-like implementation (when linked list items grouped in
> fixed-size chunks) it will be O(n).
Does your deque-like implementation preserve O(1) deletion?

> Does your deque-like implementation preserve O(1) deletion?
Ah, OrderedDict should provide O(1) deletion for arbitrary key. Then deque-
like implementation should use variable-size chunks and rotate_at() / 
rotate_after() are possible with O(1).

Attaching proof of concept patch for rotate_at() and rotate_after().
I am now conviced that bare rotate() isn't very useful.

Perhaps for consistency with popitem() and move_to_end() it is worth to merge rotate_at() and rotate_after() in one method (rotate_to()? move_to()?) with a boolean parameter.

> Perhaps for consistency with popitem() and move_to_end() it is worth
> to merge rotate_at() and rotate_after() in one method (rotate_to()?
> move_to()?) with a boolean parameter.
Yes, perhaps. rotate_to(last=False) sounds ok, but perhaps a native
English speaker can suggest a better name.

My only attraction to adding any of the rotate variants is that they provide functionality that can't be done efficiently by a user without access to the underlying data structure.
However, looking only at the API, the methods seem a bit awkward and a bit at odds with how people think of ordered dicts (rotate is not a method that comes to mind for my mental model). 
When I built the OD code, I looked at many existing implementations (in Python and other languages), and I don't recall seeing rotation in any of them.
In the absence of strong use cases, I prefer to keep the API thin so that OD's remain easy to learn and remember.

> In the absence of strong use cases, I prefer to keep the API thin
> so that OD's remain easy to learn and remember.
It could be a separate function or a dedicated subclass if you prefer.
But providing it in the stdlib would avoid 3rd party code having to poke inside the OD internals.

For the time being, I want to keep the OrderedDict API simple and avoid feature creep into rotation logic.