Are there Python code for a FIFO-like structure?

[Huaiyu Zhu]

On Fri, 06 Oct 2000 22:07:24 +0100, Grant Griffin <g2 at seebelow.org> wrote:
>
>If I understand what you're after, here is a description of generic FIFO
>logic (caveat emptor: from memory):

Thanks.  I've got it working the way I indended, as enclosed below.  The
tricky part is to use negative indexing to simplify wrapping around, which
produced an off-by-one bug that took me quite some time to trace. Otherwise
it is quite straightforward.


#!/usr/bin/env python
# (C) 2000 Huaiyu Zhu <hzhu at users.sourceforge.net>.  Licence: GPL
# $Id: fiforing.py,v 1.1.1.1 2000/10/09 22:26:18 hzhu Exp $
"""
FifoRing - a Fifo implemented as a list that wraps around.
Supports: append at tail.  pop at head.  setitem.  getitem.
Generates warning when prespecified buffer is used up.
Implementation trick: use negative index for wrapping around.
"""


class FifoFullWarning(IndexError): pass

class FifoRing:
	"A Fifo implemented as ring of length n, with at warning zone of size m"
	def __init__(self, n, m):
		"Initialize list with elements that should never be accessed"
		self.data = ['N']*n
		self.head = self.tail = 0
		self.space = m

	def __repr__(self):
		return "Fifo: (%s, %s) %s" % (self.head, self.tail, self.data)

	def __str__(self):
		if self.head < 0:
			return str(self.data[self.head:] + self.data[0: self.tail])
		else:
			return str(self.data[self.head : self.tail])

	def __getitem__(self, i):
		if i < 0:
			return self.data[self.tail+i]
		else:
			return self.data[self.head+i]

	def __setitem__(self, i, value):
		if i < 0:
			i += self.tail
			if i < self.head: raise IndexError, "Address before FiFo head"
		else:
			i += self.head
			if i > self.tail: raise IndexError, "Address after FiFo tail"
		self.data[i] = value

	def __len__(self): return self.tail - self.head

	def append(self, item):
		"""Append a new item at tail.
		Raise FifoFullWarning for using up buffer space (used, total).
		Raise Index error for Fifo overflow"""
		n = len(self.data)
		if not len(self) < n:
			raise IndexError, "Fifo overflow"
		self.tail += 1
		if self.tail > n:	self.head -= n; self.tail -= n
		self[-1] = item
		if n < len(self) + self.space:
			raise FifoFullWarning, (n - len(self),  self.space)

	def pop(self):
		"""Pop the head element.
		Raise IndexError if self is empty
		"""
		if len(self) < 1:
			raise IndexError, "poping empty Fifo"
		else:
			a = self[0]
			self[0] = 'N'
			self.head += 1
			return a
		
if __name__ == "__main__":
	a = FifoRing(10,2)
	print "appending 6 elements"
	for i in range(6):
		print a, i
		a.append(i)

	print "pop off 4 elements"
	for i in range(4):
		print a.pop(), a

	print "append another 6, wrap around"
	for i in range(6):
		print a, i
		a.append(i)

	print "Changing elements (the real ones are wrap around)"
	for i in range(7):
		a[i] = a[i]*2
		print a

	print "Calling each element"
	for i in range(len(a)):
		print a[i]

	print "And backwards"
	for i in range(len(a)):
		print a[-1-i]

	print "Pop off 6 elements. 2 left"
	for i in range(6):
		print a.pop(), a
	
	print "Append more til it overflows"
	for i in range(20):
		print a, i
		try:
			a.append(i)
		except FifoFullWarning:
			print "Warning: using buffer area", a	
		except:
			print "Fatal: overflow", a
			break