"""Section 4.2, exercise 1 of Allen Downey's Think Complexity book.

"Write an implementation of a FIFO using either a doubly-linked list or
a circular buffer."

"""

class Node(object):

    def __init__(self, data):
        self.prev = self.next = None
        self.data = data

class Fifo(object):

    def __init__(self):
        self.first = None
        self.last = None

    def append(self, val):
        """Append a value onto the back of the queue."""

        node = Node(val)

        if self.last:
            self.last.next = node
            node.prev = self.last

        self.last = node

        if not self.first:
            self.first = node

    def pop(self):
        """Remove and return the value at the front of the queue.

        Raises an IndexError if the queue is empty.
        """
        if not self.first:
            raise IndexError

        node = self.first
        self.first = node.next
        node.prev = node.next = None

        if self.last is node:
            self.last = None

        return node.data

    def empty(self):
        """Returns True if the queue is empty and False otherwise."""
        return self.first is None and self.last is None


if __name__ == '__main__':
    import random
    values = range(100)
    random.shuffle(values)

    fifo = Fifo()
    assert fifo.empty()

    for v in values:
        fifo.append(v)

    got = []
    while not fifo.empty():
        got.append(fifo.pop())

    assert got == values

    fifo.append(42)
    assert fifo.pop() == 42
    assert fifo.empty()

    try:
        fifo.pop()
    except IndexError:
        pass
    else:
        assert False