# -*- Mode: Python; tab-width: 4 -*-

# fifo, implemented with lisp-style pairs.
# [quick translation of scheme48/big/queue.scm]
	
class fifo:

	def __init__ (self):
		self.head, self.tail = None, None
		self.length = 0
		self.node_cache = None
		
	def __len__ (self):
		return self.length

	def push (self, v):
		self.node_cache = None
		self.length = self.length + 1
		p = [v, None]
		if self.head is None:
			self.head = p
		else:
			self.tail[1] = p
		self.tail = p

	def pop (self):
		self.node_cache = None
		pair = self.head
		if pair is None:
			raise ValueError, "pop() from an empty queue"
		else:
			self.length = self.length - 1
			[value, next] = pair
			self.head = next
			if next is None:
				self.tail = None
			return value

	def first (self):
		if self.head is None:
			raise ValueError, "first() of an empty queue"
		else:
			return self.head[0]

	def push_front (self, thing):
		self.node_cache = None
		self.length = self.length + 1
		old_head = self.head
		new_head = [thing, old_head]
		self.head = new_head
		if old_head is None:
			self.tail = new_head

	def _nth (self, n):
		i = n
		h = self.head
		while i:
			h = h[1]
			i = i - 1
		self.node_cache = n, h[1]
		return h[0]

	def __getitem__ (self, index):
		if (index < 0) or (index >= self.length):
			raise IndexError, "index out of range"
		else:
			if self.node_cache:
				j, h = self.node_cache
				if j == index - 1:
					result = h[0]
					self.node_cache = index, h[1]
					return result
				else:
					return self._nth (index)
			else:
				return self._nth (index)

			
class protected_fifo:
	
	def __init__ (self, lock=None):
		if lock is None:
			import thread
			self.lock = thread.allocate_lock()
		else:
			self.lock = lock
		self.fifo = fifo.fifo()

	def push (self, item):
		try:
			self.lock.acquire()
			self.fifo.push (item)
		finally:
			self.lock.release()

	enqueue = push

	def pop (self):
		try:
			self.lock.acquire()
			return self.fifo.pop()
		finally:
			self.lock.release()

	dequeue = pop
	
	def __len__ (self):
		try:
			self.lock.acquire()
			return len(self.queue)
		finally:
			self.lock.release()

class output_fifo:
	
	EMBEDDED	= 'embedded'
	EOF			= 'eof'
	TRIGGER		= 'trigger'

	def __init__ (self):
		# containment, not inheritance
		self.fifo = fifo()
		self._embedded = None

	def push_embedded (self, fifo):
		# push embedded fifo
		fifo.parent = self # CYCLE
		self.fifo.push ((self.EMBEDDED, fifo))

	def push_eof (self):
		# push end-of-fifo
		self.fifo.push ((self.EOF, None))

	def push_trigger (self, thunk):
		self.fifo.push ((self.TRIGGER, thunk))

	def push (self, item):
		# item should be a producer or string
		self.fifo.push (item)

	# 'length' is an inaccurate term.  we should
	# probably use an 'empty' method instead.
	def __len__ (self):
		if self._embedded is None:
			return len(self.fifo)
		else:
			return len(self._embedded)

	def empty (self):
		return len(self) == 0

	def first (self):
		if self._embedded is None:
			return self.fifo.first()
		else:
			return self._embedded.first()

	def pop (self):
		if self._embedded is not None:
			return self._embedded.pop()
		else:
			result = self.fifo.pop()
			# unset self._embedded
			self._embedded = None
			# check for special items in the front
			if len(self.fifo):
				front = self.fifo.first()
				if type(front) is type(()):
					# special
					kind, value = front
					if kind is self.EMBEDDED:
						self._embedded = value
					elif kind is self.EOF:
						# break the cycle
						parent = self.parent
						self.parent = None
						# pop from parent
						parent._embedded = None
					elif kind is self.TRIGGER:
						# call the trigger thunk
						value()
					# remove the special
					self.fifo.pop()
			# return the originally popped result
			return result

def test_embedded():
	of = output_fifo()
	f2 = output_fifo()
	f3 = output_fifo()
	of.push ('one')
	of.push_embedded (f2)
	f2.push ('two')
	f3.push ('three')
	f3.push ('four')
	f2.push_embedded (f3)
	f3.push_eof()
	f2.push ('five')
	f2.push_eof()
	of.push ('six')
	of.push ('seven')
	while 1:
		print of.pop()