Basically, operations involving the n-th position do not work well with this data structure, as counting must always start from the beginning or the end. Additionally, a separate dictionary would be needed for reverse lookups (key retrieval by value).
As a result, there are no efficient solutions for items 1, 2, 4, 6, 7, or 10.
Given these limitations, this topic might be better suited for a separate thread.
Fair, index lookup is not part of this.
What is left then:
For (1) I like your proposal.
od.move_to_end('a', last=False/True, endpos=‘c’)
I see that (2) would need 1 extra call:
od['a'] = 1
od.move_to_end('a', last=False/True, endpos=‘c’)
(3):
key_before_b = od.next_key('b', reverse=True)
od.move_to_end('b', endpos='c')
od.move_to_end('c', last=False, endpos=key_before_b)
A bit hefty, but given the benefit of next_key this might not be such a big cost.
Some actual use cases would be helpful here.
move_to_end argument logic and names don’t feel 100%. Feels overcrowded and I get confused whether it will move before or after endpos. It could well be other way round as there is more than one perspective to look from and there is insufficient information to be certain which one to take.
Maybe alternative could be extra method:
od.move('a', 'b', after=False/True)
or:
od.move_to('a', 'b', after=False/True)
Reusing the “last” keyword to describe a position that doesn’t actually have anything to do with being last doesn’t help make the API more intuitive to me.
I agree that the parameters in b.insert_after(‘b’, ‘x’, 0) could use a reordering though. Perhaps the order can follow the verbiage of the method name instead, i.e.:
b.insert_after('x', 0, 'b')
which makes it reads more intuitively like “insert 'x' with 0 after 'b'”.
I don’t think minimizing API changes is an important consideration here since neither approaches would result in a breaking change.
FWIW if we want to make it truly readable we can make the API like:
b.insert('x', 0).after('b')
although I can see that some may find the gain in readability not worth the overhead of creating an intermediate object with the before and after methods.
ISTM that this thread is approaching the problem from the wrong angle. It is all about everything that could be done with the OrderedDict implementation rather than focusing on the core functionality of an ordered dict should do or focusing on problems that users actually have.
The problem being solved in that you want to grow almost every API you look at (as evidenced by your posts over the last two years).
Task 3, “Swap key ‘b’ with key ‘c’” is not something that people ever seem to need with ordered dicts. It is most an imaginary application dreamed up as a possible change rather than something people actually need. In my career, I’ve need seen a need for this in an ordered dictionary context.
Tasks 1 and 2, more or insert before or after another key, arise in a completely different contexts than what ordered dicts are used for. Instead, those tasks arise in problem domains where the set of solutions is dominated by binary-trees.
Another issue with 1 and 2 is that they are irritating APIs to use because they fail with empty dicts or where the insertion point is at the ends. Users must handle corner cases every time or risk failure. It is an awkward API.
My personal opinion is that you should post a tool on PyPI rather than feature-creeping an otherwise clean API just because it is possible to do so.
I don’t use the term feature creep lightly. The current API fulfills the needs of people who need dictionaries that remember insertion order. In contrast, this thread is all about a different goal, what are the possible operations on a doubly-linked list augmented by a dictionary to locate the links.
You’re making it all about the implementation rather that the central the focus of the tool. In my opinion this isn’t Pythonic at all. People are drawn to Python because it avoids this. That is why dicts are called dictionaries (the task) rather than hashmaps (the implementation) or associative arrays (the computer science concept).
Although I agree that the angle you are referring to is most common one, but I think there are exceptions.
Motivation “it is highly wanted and being asked for” is and should be dominant, but approaching extensions from different angle can be appropriate for cases when it is sensible.
There are many examples of different motivations: performance, consistency, beauty (which is by the way the first line of Python Zen).
In this case motivation is a bit unique.
Namely, OrderedDict has become pretty much obsolete since builtins.dict is now preserving order.
There is only one case, where OrderedDict needs to be used - when move_to_end needs to be called with both last=True and last=False on the same object.
So OrderedDict is now pretty much obsolete. And it is a shame as it is well optimised object and I think people have put a fair amount of effort into it. And if something can be done with the fraction of effort that has already been put in to extract more value from it, then why not find out?
So 2 options:
a) do nothing
b) explore possibilities
(a) is sensible. It will either slowly die and be forgotten or some needs will surface and it will be revived without premeditative effort.
However, (b) is also an option. It is not that uncommon that people simply don’t get an idea of needing something until it becomes available. And when it does, everyone is happy that it makes things better.
While I agree that concrete needs of users should be a priority, I don’t see anything wrong by developers investigating what users might need before users know it themselves.
And I don’t think this thread is pushing anything blindly and is rather at investigation stage.
It is very slow moving, however.
By now, at least to me, it is clear what extensions are possible and a rough idea of API directions (2 rough paths have been suggested).
I guess the next stage is to find out whether some of the features could solve existing problems more elegantly.
Also, I agree that all proposed APIs have sharp corners that would need to be smoothed out.