bgneal@22: """Section 4.2, exercise 1 of Allen Downey's Think Complexity book.
bgneal@22: 
bgneal@22: "Write an implementation of a FIFO using either a doubly-linked list or
bgneal@22: a circular buffer."
bgneal@22: 
bgneal@22: """
bgneal@22: 
bgneal@22: class Node(object):
bgneal@22: 
bgneal@22:     def __init__(self, data):
bgneal@22:         self.prev = self.next = None
bgneal@22:         self.data = data
bgneal@22: 
bgneal@22: class Fifo(object):
bgneal@22: 
bgneal@22:     def __init__(self):
bgneal@22:         self.first = None
bgneal@22:         self.last = None
bgneal@22: 
bgneal@22:     def append(self, val):
bgneal@22:         """Append a value onto the back of the queue."""
bgneal@22: 
bgneal@22:         node = Node(val)
bgneal@22: 
bgneal@22:         if self.last:
bgneal@22:             self.last.next = node
bgneal@22:             node.prev = self.last
bgneal@22: 
bgneal@22:         self.last = node
bgneal@22: 
bgneal@22:         if not self.first:
bgneal@22:             self.first = node
bgneal@22: 
bgneal@22:     def pop(self):
bgneal@22:         """Remove and return the value at the front of the queue.
bgneal@22: 
bgneal@22:         Raises an IndexError if the queue is empty.
bgneal@22:         """
bgneal@22:         if not self.first:
bgneal@22:             raise IndexError
bgneal@22: 
bgneal@22:         node = self.first
bgneal@22:         self.first = node.next
bgneal@22:         node.prev = node.next = None
bgneal@22: 
bgneal@22:         if self.last is node:
bgneal@22:             self.last = None
bgneal@22: 
bgneal@22:         return node.data
bgneal@22: 
bgneal@22:     def empty(self):
bgneal@22:         """Returns True if the queue is empty and False otherwise."""
bgneal@22:         return self.first is None and self.last is None
bgneal@22: 
bgneal@22: 
bgneal@22: if __name__ == '__main__':
bgneal@22:     import random
bgneal@22:     values = range(100)
bgneal@22:     random.shuffle(values)
bgneal@22: 
bgneal@22:     fifo = Fifo()
bgneal@22:     assert fifo.empty()
bgneal@22: 
bgneal@22:     for v in values:
bgneal@22:         fifo.append(v)
bgneal@22: 
bgneal@22:     got = []
bgneal@22:     while not fifo.empty():
bgneal@22:         got.append(fifo.pop())
bgneal@22: 
bgneal@22:     assert got == values
bgneal@22: 
bgneal@22:     fifo.append(42)
bgneal@22:     assert fifo.pop() == 42
bgneal@22:     assert fifo.empty()
bgneal@22: 
bgneal@22:     try:
bgneal@22:         fifo.pop()
bgneal@22:     except IndexError:
bgneal@22:         pass
bgneal@22:     else:
bgneal@22:         assert False