Ordering python sets

[Lie Ryan]

On Wed, 22 Oct 2008 10:43:35 -0700, bearophileHUGS wrote:

> Mr.SpOOn:
>> Is there another convenient structure or shall I use lists and define
>> the operations I need?
> 
> <musings>
> As Python becomes accepted for more and more "serious" projects some
> more data structures can eventually be added to the collections module:
> - SortedSet, SortedDict: can be based on red-black trees. Require items
> to be sortable (them being hashable isn't required, but it's probably
> more safe that they are immutable). - Odict: a dict ordered according to
> insertion order. - Bidict: a unordered dict that allows O(1) retrieval
> on both keys and values (that are both unique).
> - Graph: a directed unsorted data structure like mine may be acceptable
> too.
> - Bitset: dynamically re-sizable and efficient in space and time, easy
> to implement in C.
> - Chain: simulates a double linked list, but its implementation can be
> similar to the current Deque but allowing not completely filled blocks
> in the middle too. (I haven't named it just List because there's a name
> clash with the list()).
> - I use all those data structures in Python programs, plus some more,
> like interval map, trie (and a dawg), persistent dict and persistent
> list, kd-tree, BK-tree, Fibonacci Heap, a rank & select, a disjoint-
> set, and maybe more. But those are uncommon enough to be left out of a
> standard library.
> - A problem with the Chain data structure is how to represent iterators
> in Python. I think this is a big problem, that I don't know how to solve
> yet. A possible solution is to make them owned by the Chain itself, but
> this makes the code slow down linearly in accord to the number of the
> iterators. If someone has a solution I'm all ears. </musings>
> 
> Bye,
> bearophile

<anotherrandommusing>
Since python is dynamic language, I think it should be possible to do 
something like this:

a = list([1, 2, 3, 4, 5], implementation = 'linkedlist')
b = dict({'a': 'A'}, implementation = 'binarytree')
c = dict({'a': 'A'}, implementation = 'binarytree')

i.e. basically since a data structure can have different implementations, 
and different implementations have different performance characteristics, 
it should be possible to dynamically change the implementation used.

In the far future, the data structure and its implementation could be 
abstracted even further:

a = list() # ordered list
b = set() # unordered list
c = dict() # unordered dictionary
d = sorteddict() # ordered dictionary

Each of the implementations would share a common subset of methods and 
possibly a few implementation dependent method that could only work on 
certain implementations (or is extremely slow except in the correct 
implementation).
</anotherrandommusing>