sorteddict PEP proposal [started off as orderedict]

[Mark Summerfield]

On 25 Sep, 12:11, Jeremy Sanders <jeremy
+complangpyt... at jeremysanders.net> wrote:
> Mark Summerfield 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:-)
>
> It would be nice to have the ability to use numerical indexes and the key,
> but I don't think they should share the same methods.

They don't; you use [] for key index and key(), value(), or item() for
index access.

> A useful use case would be to make a LRU (least recently used) dictionary,
> where the keys are time-based (e.g. an incrementing counter). You should be
> able to identify the least recently used object for discarding by just
> accessing the last item in the dictionary.

You could do that with a sorteddict simply by using datetime.date
objects or timestamp strings for keys. You could get the first or last
item (no matter what its key). For example:

d = sorteddict({1200:"lunch", 1100:"elevensies", 1600:"tea",
1900:"dinner"})
d.items()
[(1100, 'elevensies'), (1200, 'lunch'), (1600, 'tea'), (1900,
'dinner')]
d.item(0), d.item(-1)
((1100, 'elevensies'), (1900, 'dinner'))

So you could remove the last item using d.delete(-1).

> By the way, I think a LRU cache dictionary would be a great addition to the
> standard library.
>
> Is there any speed advantage from implementing the sorteddict as a red-black
> tree or something similar in C?

I'm sure that a C-based implementation using red-black or AVL trees or
skiplists would be faster, but right now I'm just trying to get an
acceptable API.

Corrections to my original PEP:

   value(index : int) -> value # I incorrectly had the return value as
key

Also, now in the second example I use a tuple of string, int ID rather
than strings.

> Jeremy
>
> --
> Jeremy Sandershttp://www.jeremysanders.net/