Are there Python code for a FIFO-like structure?
Grant Griffin
g2 at seebelow.org
Fri Oct 6 17:07:24 EDT 2000
Huaiyu Zhu wrote:
>
> [Huaiyu Zhu]
>
> >> > I need something like a fifo, inplemented in a fixed length list...
> >> > an IndexError is raised if the tail gets
> >> > too close to the head.
>
> Hi, everyone,
>
> Thanks for all these good ideas.
>
> [Christian Tismer]
>
> >Hmm, why don't you really use a fixed length list, maintain
> >two rotating pointers, and check that they behave well?
>
> Yes, that's what I had in mind when I posted the query. The real work is to
> make the two pointers behave well, of course. I'm getting there.
>
If I understand what you're after, here is a description of generic FIFO
logic (caveat emptor: from memory):
1. Allocate the fixed-length FIFO buffer (probably as a Python list
or--maybe better--as a Numeric array.)
2. Initialize a read_index and write_index to zero.
3. The FIFO is empty whenever read_index == write_index (e.g. when both
are initialized to zero.)
4. The FIFO if full whenever write_index is one less than read_index.
(Note that a special "modulo" case of full is when write_index == length
- 1, and read_index == 0.)
5. To read, check for FIFO empty (if so, raise error), get data at
read_index, then increment read_index, modulo the length. (You can
quickly implement the modulo by just setting read_index to 0 when the
incremented read_index == length.)
6. To write, do the same thing: check for FIFO full (if so, raise
error), put data at write_index, increment, do quick modulo.)
if-i-could-ever-remember-where-i-put-all-those-fifo-implementations
-i've-written-over-the-years,-i-wouldn't-ever-have-written
-so-many-fifo-implementations-over-the-years-ly y'rs,
=g2
--
_____________________________________________________________________
Grant R. Griffin g2 at dspguru.com
Publisher of dspGuru http://www.dspguru.com
Iowegian International Corporation http://www.iowegian.com
More information about the Python-list
mailing list