efficient idiomatic queue?

[Aahz Maruch]

In article <a23cjl$dps$1 at serv1.iunet.it>, Alex Martelli <aleax at aleax.it> wrote:
>"David Eppstein" <eppstein at ics.uci.edu> wrote in message
>news:eppstein-3B0408.21320615012002 at news.service.uci.edu...
>> In article <a22rhr$bn1$1 at panix3.panix.com>, aahz at panix.com (Aahz Maruch)
>> wrote:
>>>
>>> Just to be a jerk, why not use a dict with a couple of index variables?
>>
>> Maybe you could unpack that a little? dicts are useful but AFAIK they
>> aren't the same thing as queues, index variables or no.
>
>Well, they obviously CAN be used to IMPLEMENT queues -- performance
>characteristics apart:
>
>class DictFifo:
>    def __init__(self):
>        self.data = {}
>        self.nextin = 0
>        self.nextout = 0
>    def append(self, value):
>        self.data[self.nextin] = value
>        self.nextin += 1
>    def pop(self):
>        value = self.data[self.nextout]
>        del self.data[self.nextout]
>        self.nextout += 1
>
>No "being the same" asserted or implied, of course -- the dict and
>the two indices are just tools to _implement_ a fifo queue, here.

Yup.  Note that for Python < 2.2, you should use:

    def __init__(self):
        self.data = {}
        self.nextin = 0L
        self.nextout = 0L

to make sure that you can use it for more than two billion entries.  ;-)

I haven't tested this, but I think that if you expect queues to be
large, this might actually be a fast, clear implementation.
-- 
                      --- Aahz  <*>  (Copyright 2002 by aahz at pobox.com)

Hugs and backrubs -- I break Rule 6                 http://www.rahul.net/aahz/
Androgynous poly kinky vanilla queer het Pythonista   

"There are times when effort is important and necessary, but this should
not be taken as any kind of moral imperative."  --jdecker