[Python-ideas] priorityqueue, sortedlist in collections?
rhamph at gmail.com
Fri Mar 2 01:37:37 CET 2007
On 3/1/07, Jason Orendorff <jason.orendorff at gmail.com> wrote:
> I wonder if anyone else finds the heapq and bisect APIs a little dated.
> It seems like these things could be offered in a more intuitive and
> featureful way by making them classes. They could go in the
> collections module:
I agree, at least for heapq. The algorithm involves enough voodoo
that it's not obvious how to extend it, so it might as well be wrapped
in a class that hides as much as possible.
The same can't be said for bisect though. All it does is replace del
a[bisect_left(a, x)] with a.remove(x). A little cleaner, but no more
obvious. And the cost is still O(n) since it involves moving all the
pointers after x.
> class priorityqueue:
Should inherit from object if this is going into 2.x.
> def __init__(self, elements=(), *,
> cmp=None, key=None, reversed=False)
> def add(self, element)
> def pop(self) --> remove and return the min element
> def __iter__(self) --> (while self: yield self.pop())
__iter__ shouldn't modify the container.
> ... any other list methods that make sense
> ... for example, __len__ but not __getitem__
Adam Olsen, aka Rhamphoryncus
More information about the Python-ideas