Home Original page

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