# -*- 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()