Mercurial > public > think_complexity
annotate ch4ex1.py @ 38:d876711b88b5
Comment out the calculation of L as it may take a long time.
| author | Brian Neal <bgneal@gmail.com> |
|---|---|
| date | Thu, 10 Jan 2013 20:24:56 -0600 |
| parents | 84e183b40c63 |
| children |
| rev | line source |
|---|---|
| bgneal@22 | 1 """Section 4.2, exercise 1 of Allen Downey's Think Complexity book. |
| bgneal@22 | 2 |
| bgneal@22 | 3 "Write an implementation of a FIFO using either a doubly-linked list or |
| bgneal@22 | 4 a circular buffer." |
| bgneal@22 | 5 |
| bgneal@22 | 6 """ |
| bgneal@22 | 7 |
| bgneal@22 | 8 class Node(object): |
| bgneal@22 | 9 |
| bgneal@22 | 10 def __init__(self, data): |
| bgneal@22 | 11 self.prev = self.next = None |
| bgneal@22 | 12 self.data = data |
| bgneal@22 | 13 |
| bgneal@22 | 14 class Fifo(object): |
| bgneal@22 | 15 |
| bgneal@22 | 16 def __init__(self): |
| bgneal@22 | 17 self.first = None |
| bgneal@22 | 18 self.last = None |
| bgneal@22 | 19 |
| bgneal@22 | 20 def append(self, val): |
| bgneal@22 | 21 """Append a value onto the back of the queue.""" |
| bgneal@22 | 22 |
| bgneal@22 | 23 node = Node(val) |
| bgneal@22 | 24 |
| bgneal@22 | 25 if self.last: |
| bgneal@22 | 26 self.last.next = node |
| bgneal@22 | 27 node.prev = self.last |
| bgneal@22 | 28 |
| bgneal@22 | 29 self.last = node |
| bgneal@22 | 30 |
| bgneal@22 | 31 if not self.first: |
| bgneal@22 | 32 self.first = node |
| bgneal@22 | 33 |
| bgneal@22 | 34 def pop(self): |
| bgneal@22 | 35 """Remove and return the value at the front of the queue. |
| bgneal@22 | 36 |
| bgneal@22 | 37 Raises an IndexError if the queue is empty. |
| bgneal@22 | 38 """ |
| bgneal@22 | 39 if not self.first: |
| bgneal@22 | 40 raise IndexError |
| bgneal@22 | 41 |
| bgneal@22 | 42 node = self.first |
| bgneal@22 | 43 self.first = node.next |
| bgneal@22 | 44 node.prev = node.next = None |
| bgneal@22 | 45 |
| bgneal@22 | 46 if self.last is node: |
| bgneal@22 | 47 self.last = None |
| bgneal@22 | 48 |
| bgneal@22 | 49 return node.data |
| bgneal@22 | 50 |
| bgneal@22 | 51 def empty(self): |
| bgneal@22 | 52 """Returns True if the queue is empty and False otherwise.""" |
| bgneal@22 | 53 return self.first is None and self.last is None |
| bgneal@22 | 54 |
| bgneal@22 | 55 |
| bgneal@22 | 56 if __name__ == '__main__': |
| bgneal@22 | 57 import random |
| bgneal@22 | 58 values = range(100) |
| bgneal@22 | 59 random.shuffle(values) |
| bgneal@22 | 60 |
| bgneal@22 | 61 fifo = Fifo() |
| bgneal@22 | 62 assert fifo.empty() |
| bgneal@22 | 63 |
| bgneal@22 | 64 for v in values: |
| bgneal@22 | 65 fifo.append(v) |
| bgneal@22 | 66 |
| bgneal@22 | 67 got = [] |
| bgneal@22 | 68 while not fifo.empty(): |
| bgneal@22 | 69 got.append(fifo.pop()) |
| bgneal@22 | 70 |
| bgneal@22 | 71 assert got == values |
| bgneal@22 | 72 |
| bgneal@22 | 73 fifo.append(42) |
| bgneal@22 | 74 assert fifo.pop() == 42 |
| bgneal@22 | 75 assert fifo.empty() |
| bgneal@22 | 76 |
| bgneal@22 | 77 try: |
| bgneal@22 | 78 fifo.pop() |
| bgneal@22 | 79 except IndexError: |
| bgneal@22 | 80 pass |
| bgneal@22 | 81 else: |
| bgneal@22 | 82 assert False |