[issue22097] Linked list API for ordereddict

Change by STINNER Victor : -- nosy: -vstinner ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.p

[issue22097] Linked list API for ordereddict

Change by Yoann Aubineau : -- nosy: -yaubi ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.pyth

[issue22097] Linked list API for ordereddict

Raymond Hettinger added the comment: > Perhaps someone should make a blog post comparing > theoretical and actual performance of various data > types (hint hint ;-)). Great idea. Thanks Antoine. -- resolution: -> rejected stage: -> resolved status: open -> closed _

[issue22097] Linked list API for ordereddict

Antoine Pitrou added the comment: Yes, I think it's clear it's not going anywhere. In a way the standard list is good enough for those uses, except when your lists start growing really big (I don't know where the threshold is, but tens of thousands I'd say). Perhaps someone should make a blog

[issue22097] Linked list API for ordereddict

Raymond Hettinger added the comment: Antoine, can I close this one? -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubs

[issue22097] Linked list API for ordereddict

Antoine Pitrou added the comment: Le 29/07/2014 21:15, Raymond Hettinger a écrit : > > * One use case for the insert methods is trying to maintain a sort order (such as an alphabetical order) but we don't have any efficient search methods such as a binary search to find an insertion point. For ex

[issue22097] Linked list API for ordereddict

Raymond Hettinger added the comment: Just for the record, when I originally looked at insert_before() and insert_after(), here's some of things that bugged me a little: * insert_before(currkey, newkey, newvalue) ncan raise TypeErrors for hashability from either key. It can raise a KeyError w

[issue22097] Linked list API for ordereddict

Antoine Pitrou added the comment: > This does not meet your requirement of supporting insert_after(x), > its insert(x, before) requires to give a dllistnode. Indeed it lacks that piece of prettiness in the API. And adding a mapping to allow lookups from item to node really means using a ordered

[issue22097] Linked list API for ordereddict

Martin v. Löwis added the comment: Am 29.07.14 17:41, schrieb Antoine Pitrou: > > Antoine Pitrou added the comment: > >> I don't know about the collections module. All I'm saying is that >> a linked list with an efficient insert_after(x) could be implemented. >> I'm not seeing one on PyPI > >

[issue22097] Linked list API for ordereddict

Antoine Pitrou added the comment: > I don't know about the collections module. All I'm saying is that > a linked list with an efficient insert_after(x) could be implemented. > I'm not seeing one on PyPI See https://pypi.python.org/pypi/llist/ (and probably others) -- __

[issue22097] Linked list API for ordereddict

Martin v. Löwis added the comment: > Are you suggesting the collections module is ready for a linked list > implementation to go into it? I don't know about the collections module. All I'm saying is that a linked list with an efficient insert_after(x) could be implemented. I'm not seeing one on

[issue22097] Linked list API for ordereddict

Antoine Pitrou added the comment: Le 29/07/2014 05:40, Martin v. Löwis a écrit : > > ISTM that a dictionary is not the proper data structure for an instruction list. The support for the Mapping interface is not needed at all (AFAICT). This is true. > It's possible to make a list implementation

[issue22097] Linked list API for ordereddict

Antoine Pitrou added the comment: Le 29/07/2014 07:09, Serhiy Storchaka a écrit : > > About your use case. Note that all indices after inserted element should be shifted. If you inserted more than one statement in the same ir_block, all but first insertions can be at wrong position. Thanks for n

[issue22097] Linked list API for ordereddict

Serhiy Storchaka added the comment: About your use case. Note that all indices after inserted element should be shifted. If you inserted more than one statement in the same ir_block, all but first insertions can be at wrong position. -- ___ Python t

[issue22097] Linked list API for ordereddict

Martin v. Löwis added the comment: ISTM that a dictionary is not the proper data structure for an instruction list. The support for the Mapping interface is not needed at all (AFAICT). It's possible to make a list implementation with O(1) insert_after, using the same strategy that OrderedDict

[issue22097] Linked list API for ordereddict

Antoine Pitrou added the comment: My current use case is manipulation of Numba IR code. I'm working on a transformation pass that adds instructions at arbitrary places in existing IR. The primitive I need is "add an instruction after another one" (which is exactly the insert_after() primitive

[issue22097] Linked list API for ordereddict

Raymond Hettinger added the comment: I would like any proposed API extensions to be use case driven. The omission of these methods wasn't accidental. I studied pre-existing OD implementations for Python and looked at how they were used in the real-world (back when we still had Google Code Sea

[issue22097] Linked list API for ordereddict

Yoann Aubineau added the comment: Here is an attempt to implement such an API. The patch adds 4 methods to OrderedDict: move_before, move_after, insert_before and insert_after with corresponding tests. The method signatures do not feel right though. I am not sure where the reference key shoul

[issue22097] Linked list API for ordereddict

Changes by Yoann Aubineau : -- nosy: +yaubi ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python

[issue22097] Linked list API for ordereddict

Changes by Ezio Melotti : -- nosy: +ezio.melotti ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.p

[issue22097] Linked list API for ordereddict

Changes by STINNER Victor : -- nosy: +haypo ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python

[issue22097] Linked list API for ordereddict

New submission from Antoine Pitrou: Right now Python doesn't have an ordered container which allows O(1) insertion at any place. It would be nice to have such an API on ordered dicts (e.g. insert_after() / insert_before()). -- messages: 224191 nosy: pitrou, rhettinger, serhiy.storchaka