Home Original page

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

Alex Martelli aleax at aleax.it
Wed Oct 29 15:12:23 EST 2003 
Roy Smith wrote:

> "Terry Reedy" <tjreedy at udel.edu> wrote:
>> As I suggested elsewhere, make iter() the type object for iterator.
>> Then iter.reversed is closely parallel to list.sorted.
> 
> I've got a question about list.sorted.  I assume it's just a list that's
> initialized to have its elements sorted when it's created?  We're not
> talking about some new magic container type which keeps its elements
> sorted all the time?
> 
> In other words, I'm assuming that
> 
> l = list.sorted ((1, 2, 5, 3))
> l.append (4)
> print l
> 
> will print [1, 2, 3, 5, 4], right?

Perfectly right.  If you DO want a listoid container that keeps its
elements sorted, that's not hard to make for yourself.  There are
basically two obvious implementation strategies:
  -- ensure the underlying list is re-sorted at each insertion,
     append &c, and/or
  -- let the underlying list grow as it will on insertion &c, but
     make sure it's sorted at any method that accesses it (you can
     use a flag -- 'have there being any append/insert/... since
     the last sort?' -- to re-sort only when needed).

I'll choose the first for general use because:
  -- accesses are much more frequent than modifications,
  -- list.sort is VERY fast when a list is "nearly sorted"
  -- the second approach would require sorting also on many
     kind of changes (e.g. __setitem__ -- to ensure the items
     being replaced ARE those the user expects...)
&c.

So, we clearly start with:

class alwayssortedlist(list):

    def __init__(self, *args):
        list.__init__(self, *args)
        self.sort()

We need to ensure sorting at creation.  We _might_ make the sort
method in this class a noop and call list.sort(self) instead,
but, naah -- list.sort is SO fast when called on an already
sorted list that it ain't even funny, so, choose simplicity.
Onwards to simple mods:

    def append(self, *args):
        list.append(self, *args)
        self.sort()

    def __setitem__(self, *args):
        list.__setitem__(self, *args)
        self.sort()

...starting to see a pattern, by any chance...?-)  Yep, ALL
list mutators we _need_ to override are exactly like this!
(We MAY override e.g. index and remove to take advantage
of the sortedness, but, that's optional...:-).  extend and
insert too (now, reverse IS an interesting issue...!-), and
__iadd__ and __imul__ (methods creating new lists, such as
__add__, __mul__ and __rmul__, are slightly different).  Oh,
__setslice__, too.

Well, doing it in longhand is fine, of course, but why not
have a bit more fun with (not showing the __add__ &c):

class solist(list): pass

def solist_method(methname):
    list_method = getattr(list, methname)
    def method(self, *args):
        list_method(self, *args)
        self.sort()
    setattr(solist, methname, method)
for n in 'init setitem iadd imul'.split:
    solist_method('__%s__' % n)
for n in 'append extend insert'.split:
    solist_method('%s' % n)

Not much shorter than the boilerplate/longhand, and not
perfect (we should make a new function object to give it
the right func_name -- as is, all the methods' names
will be "method" in tracebacks &c...:-), but sorta fun.

Testing & completion left as an exercise to the student...


Alex
More information about the Python-list mailing list