rotating an ordereddict

[pitrou]

BPO	17100
Nosy	@rhettinger, @pitrou, @ericsnowcurrently, @serhiy-storchaka
Files	od_rotate.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2013-03-23.13:51:43.331>
created_at = <Date 2013-02-01.16:32:03.414>
labels = ['type-feature']
title = 'rotating an ordereddict'
updated_at = <Date 2013-03-23.13:51:43.330>
user = 'https://github.com/pitrou'

bugs.python.org fields:

activity = <Date 2013-03-23.13:51:43.330>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2013-03-23.13:51:43.331>
closer = 'rhettinger'
components = []
creation = <Date 2013-02-01.16:32:03.414>
creator = 'pitrou'
dependencies = []
files = ['29213']
hgrepos = []
issue_num = 17100
keywords = ['patch']
message_count = 15.0
messages = ['181086', '181132', '181140', '181142', '181147', '181148', '181150', '181152', '181160', '182838', '182864', '182866', '183165', '183173', '185047']
nosy_count = 5.0
nosy_names = ['rhettinger', 'pitrou', 'eric.snow', 'Ramchandra Apte', 'serhiy.storchaka']
pr_nums = []
priority = 'low'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue17100'
versions = ['Python 3.4']

[pitrou]

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.

[RamchandraApte]

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

[serhiy-storchaka]

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.

[pitrou]

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.

[serhiy-storchaka]

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.

[pitrou]

> 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.

[serhiy-storchaka]

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).

[pitrou]

> 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?

[serhiy-storchaka]

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).

[pitrou]

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

[serhiy-storchaka]

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.

[pitrou]

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.

[rhettinger]

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.