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

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


class fifo(object):

    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(object):

    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(object):

    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 isinstance(front, tuple):
                        # 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())
