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