alwayssortedlist (was Re: On PEP 322 (ireverse))

[Alex Martelli]

Anton Vredegoor wrote:
   ...
> How about this code:
> 
> a = alwaysssortedlist(range(10))
> a[5] = 20
> 
> What's the use of assigning to a specific list position if the object
> could end up being in some other place?

For an always-sorted list, this clearly means: replace the currently
sixth-lowest item with the value 20.  More generally, a[i] always
means "the (i+1)-th lowest item" -- referencing it no doubt going
to be useful much more often than replacing it, and value of i
different from the extremes (say 0, 1, -1) are going to be rare.
But, so what?  One can surely imagine use cases (if one can for any
use of an "always-sorted list" rather than sorting on request).

For example: "if there is any occurrence of 20 in the list, then
replace the immediately-smaller item (if any, i.e., unless 20 is
the smallest) with another copy of the value 20".  I.e.:

    try: i = a.index(20)
    except ValueError:
        print "value 20 is not in the list"
    else:
        if i==0:
            print "value 20 is in the list, but it's the smallest"
        else:
            a[i-1] = 20

I don't think I've ever needed to code this kind of thing in
production-code, but it doesn't seem particularly far-fetched
to me.  Why else, except for such kinds of uses, would one want
a listoid that's _always_ sorted, rather than a cheaper heap
(see module heapq) or a list that's sorted on request...?


Alex