sorteddict PEP proposal [started off as orderedict]

[A.T.Hofkamp]

On 2007-09-25, Mark Summerfield <m.n.summerfield at googlemail.com> wrote:
> If there is positive feedback I will submit the PEP to the reviewers,
> so if you think it is a good idea please say so. (I'm sure that if you
> _don't_ like it you'll tell me anyway:-)

I like the idea, ie +1.

>     This PEP proposes the addition of a sorted dictionary class to the
>     standard library's collections module.

You don't seem to mention the sort criterium. I'd suggest to use the __lt__
operator, which you probably intended since it is commonly used.

Also, can I specify a custom sort function, as with list.sort() ?

>     In addition, the keys() method has two optional arguments:
>
>     keys(firstindex : int = None, secondindex : int = None) -> list of

Not sure this is a good idea. Wouldn't simply

mysorteddict.keys()[firstindex:secondindex]

be much better? It can do all you propose, and more (with iterators/generators
and such). I see no need to implement it inside the sorteddict as well.


>     Since the sorteddict's data is always kept in key order, indexes
>     (integer offsets) into the sorteddict make sense.  Five additional
>     methods are proposed to take advantage of this:
>
>     key(index : int) -> value
>
>     item(index : int) -> (key, value)
>
>     value(index : int) -> key
>
>     set_value(index : int, value)
>
>     delete(index : int)

I wouldn't do this. It breaks compability with the normal dict. A beginning
user will expect dict and sorteddict to behave the same (except for
sortedness), including their set of supporting functions imho.

Otherwise, please make a case for them (and maybe even a new PEP to get them in
both types of dicts).

> Examples
>
>     To keep a collection of filenames on a case-insensitive file
> system in
>     sorted order, we could use code like this:
>
>         files = collections.sorteddict.sorteddict()
>         for name in os.listdir("."):
>             files[name.lower()] = name

The more interesting case would be to you preserve case of the files within the
keys.

I usually need this data structure with an A* algorithm implementation, where I
need to obtain the cheapest solution found so far.

>         for item in listOfItems:
>             itemsByDate["%s\t%17X" % (item.date, id(item))] = item
>             itemsByName["%s\t%17X" % (item.name, id(item))] = item
>             itemsBySize["%s\t%17X" % (item.size, id(item))] = item

Wouldn't a line like "itemsBySize[(item.size, id(item))] = item" do as well?

(or with a custom sort function on items?)

>     Now we can iterate in date or name order, for example:
>
>         for item in itemsByDate:
>             print item.name, item.date

Hmm, not with dict:

>>> for x in {1:10, 2:20}:
...   print x
...
1
2

So you should get your "%s\t%17X" strings here.


Sincerely,
Albert