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