[Python-Dev] FIFO data structure?

[Tim Peters]

[Agthorr]
>> However, speaking of subclassing Queue: is it likely there are many
>> user applications that subclass it in a way that would break? (i.e.,
>> they override some, but not all, of the functions intended for
>> overriding).

[Agthorr]
> Answering myself, I notice that the bisect class documents this use of
> the Queue class:
> ------------------------------------------------------------------------
> The bisect module can be used with the Queue module to implement
> a priority queue (example courtesy of Fredrik Lundh): \index{Priority
> Queue}
>
> \begin{verbatim}
> import Queue, bisect
>
> class PriorityQueue(Queue.Queue):
>     def _put(self, item):
>         bisect.insort(self.queue, item)
> ------------------------------------------------------------------------
>
> This example relies on the behavior of the other internal functions of
> the Queue class.  Since my faster Queue class changes the internal
> structure, it breaks this example.  Strangely, the internal functions
> are not actually mentioned in the documentation for Queue, so this
> example is somewhat anomalous.  However, the comments inside Queue.py
> *do* suggest subclassing Queue to create non-FIFO queues.
>
> The example was not present in 2.2, so removing it may not hurt too
> many people.

I'm sorry I had to let this thread drop.  I had lots of time to type on the
weekend, and on Monday because I took that day off from work sick.  My time
is gone now, though.

As a delayed answer to your question, yes, people do this.  I expect the
most common subclass does just this:

    def _get(self):
        return self.queue.pop()

That is, for many apps, the first-in part of FIFO isn't needed, and a stack
of work is just as good.  I'm not sure it wouldn't be just as good for your
simulation app, either!

People aren't "supposed to" muck with private names, and a single underscore
at the front is a convention for saying "please don't muck with this".

I don't believe you made a strong enough case to break code that cheats,
though:  the code as it is now is obviously correct at first glance.  The
best that can be said for the much hairier circular-buffer business is that
it's not obviously incorrect at first glance, and Python isn't immune to
that ongoing maintenacne is more expensive than initial development.  I also
think your use of (presumably many) thousands of Queue items is unusual.  A
subclass may be welcome, and doc clarifications would certainly be welcome.

> I confess I'm new to the Python development process.  Who makes
> decisions about whether this type of change should go in, or not?  Do
> I just submit a patch and cross my fingers? ;)

There aren't enough volunteers to review patches, and "Guido's team" doesn't
spend work hours on Python anymore except as it happens to intersect with
important Zope needs, so I'm afraid it may sit there forever.  Talking about
it on Python-Dev was/is a good thing.  If you haven't already, you should
devour the developer material at:

    http://www.python.org/dev/

Right now we're trying to conserve our "spare time" for resolving issues
necessary to release 2.3b1 on Friday, so it's hard to keep a conversation
going.

Don't let any of this discourage you!  To become a Python developer requires
an almost supernatural love of discouragement -- you'll know what I mean
when you meet any of us <wink>.