think_complexity: ch4ex1.py comparison

Added exercises 1 and 2 from chapter 4.

comparison

equal deleted inserted replaced

-:55880b29b4d4
+:84e183b40c63
+"""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

Mercurial > public > think_complexity