Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture II of XIV

Lecture II · Data Structures & Algorithms

Testing first

Last time out we built a mental model of names and objects. Today we build the habit that keeps that model honest: we write the tests before we write the code. Not because a style guide says so, but because it is the fastest way I know to turn a vague worry (“I think this works?”) into a question the machine can answer for you.

Write the test first

Here is the move, and it is almost too simple. Before you implement a thing, you write down, in code, what “working” would mean. Not in your head, not in a comment, in an executable statement the computer can check.

Think about what a test buys you. Without one, “does it work?” is a feeling. You squint at the code, you run it once by hand, you nod, you move on. With one, “does it work?” becomes a button. You press it and the answer comes back green or red, the same answer every time, on your machine and on mine and at three in the morning when you have changed something unrelated and want to know if you broke this.

That is the real product. A test is a contract you write with your future self. It says: whatever else I do to this code, these promises must keep holding. And because you wrote the contract first, before the temptation to declare victory set in, it describes what you actually wanted rather than whatever the code happens to do. Code that describes itself is not a test. It always passes, because it is just the implementation looking in a mirror.

unittest, up close

Python ships a testing framework in the standard library, unittest, and for our purposes it is small. You subclass unittest.TestCase, you write methods whose names start with test, and inside them you call assert methods that raise if the promise is broken. Suppose we have a tiny class, a click counter:

class Counter:
    def __init__(self):
        self.count = 0

    def click(self):
        self.count += 1

    def value(self):
        return self.count

The tests live in their own file and read like a list of promises:

import unittest
from counter import Counter

class TestCounter(unittest.TestCase):
    def test_starts_at_zero(self):
        c = Counter()
        self.assertEqual(c.value(), 0)

    def test_click_increments(self):
        c = Counter()
        c.click()
        c.click()
        self.assertEqual(c.value(), 2)

if __name__ == '__main__':
    unittest.main()

Run it with python -m unittest, and each test method becomes a separate line in a report. assertEqual(a, b) checks that a == b and, when it fails, prints both values so you are not left guessing which one was wrong. There are cousins: assertTrue, assertEqual, assertRaises for checking that the right exception fires. That is essentially the whole vocabulary you need to start. Notice how each method builds its own fresh Counter. Tests must not lean on each other; a test that only passes because a different test ran first is a test that will betray you the moment someone runs them in a new order.

Red, green, and back again

Now put those two ideas together and you get a rhythm. It goes: write a test that fails, then make it pass, then do it again. Red, green, red, green. This is test-driven development, and the discipline is in the order.

Start red on purpose. Before Counter even exists, write test_starts_at_zero and run it. It fails, loudly, because there is no Counter to import. Good. A test that has never been red has never been proven to test anything; maybe it passes because of a typo, maybe it asserts nothing at all. Watching it fail first is how you test the test.

Then write the least code that turns it green. Not the whole class you imagine, just enough to satisfy the promise in front of you. value returns zero? Fine, make value return the count and initialize the count to zero. Run it. Green. Now write the next failing test, test_click_increments, watch it go red, and add click. Green again.

It feels slow the first day and it stops feeling slow by the third, because you are never more than one small step from a working program. You are never staring at two hundred lines wondering which of them is the lie. The tests hold the ground you have already taken while you reach for the next inch.

Test the promise, not the plumbing

Here is the idea that makes the whole practice pay off, and it is the one people get wrong. Test the behavior the interface promises, never the way the code happens to keep that promise.

An abstract data type, an ADT, is a set of promises with the implementation left blank. A Stack promises last-in, first-out: whatever you pushed most recently is what pops next. It promises to know its own size. It promises to complain if you pop when it is empty. Those promises are the contract. How you store the items, in a Python list, in a linked chain, in something you have not invented yet, is nobody’s business but the Stack’s.

So test the promises. Push then pop and check you get the item back. Push three things and check they come off in reverse. Never write a test that reaches past the interface to poke at _items directly. The moment a test says assert stack._items[-1] == 5, it has stopped testing the Stack and started testing one particular way of building a Stack. Swap that list for a linked list tomorrow, a swap the contract explicitly allows, and your test breaks even though nothing is actually wrong. A good ADT test survives any correct implementation and fails every incorrect one. That is the line you are trying to draw.

The red–green loop

Enough theory. The plate below holds a Stack with a bug in it, and a contract of four checks written the way we just described: every one of them tests the promise, not the plumbing. Press Run. Watch which rows go red. Then fix the Stack in the editor until all four are green.

The checks · run against your code

# push then pop returns the pushed item
s = Stack()
s.push(7)
assert s.pop() == 7
# LIFO order across three pushes
s = Stack()
s.push('a')
s.push('b')
s.push('c')
assert s.pop() == 'c'
assert s.pop() == 'b'
assert s.pop() == 'a'
# size tracks pushes and pops
s = Stack()
assert s.size() == 0
s.push(1)
s.push(2)
assert s.size() == 2
s.pop()
assert s.size() == 1
# pop on empty raises
s = Stack()
try:
    s.pop()
    raised = False
except IndexError:
    raised = True
assert raised
python runs in your browser · first run downloads ~240 kb
Plate I The red–green loop. One subtly broken Stack, four labeled checks that encode the LIFO contract. Press Run to see the contract light up red and green; edit the Stack until every row passes. The checks never touch a private attribute, so any correct Stack satisfies them.

Read the report carefully, because it is teaching you something about tests, not just about this Stack. Three rows are green and one is red. The single push-then-pop check passes, because with only one item on the Stack the top and the bottom are the same place: a one-element test cannot tell a real LIFO from a fraud. It takes the three-push check to corner the bug, and that is exactly the row glowing red. The size check passes and the empty check passes too, which tells you the break is narrow: it is only about which end pop reaches for.

Hint one

Every check that touches order fails, and every check that ignores order passes. So the bug is about which end of the list pop takes from, not about counting or errors.

Hint two

A list’s pop() with no argument removes the last item; pop(0) removes the first. The last item pushed sits at the end. Which one does LIFO want?

The solution

The buggy pop calls self._items.pop(0), which removes from the front: that is first-in, first-out, a queue wearing a Stack’s name. LIFO wants the end of the list, so drop the argument:

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        return self._items.pop()

    def size(self):
        return len(self._items)

Because append and pop() both work at the end of the list, both are cheap, which is the other reason a list is the natural backing for a Stack. Run the checks again and all four go green.

A test that corners the bug

Fixing a red row is the easy half. The hard half is writing the check that catches a bug in the first place, and some bugs hide from lazy tests. Consider a pop that returns the right value but quietly corrupts the Stack underneath it.

python runs in your browser · first run downloads ~240 kb
Plate II A bug that survives a single pop. This pop returns the top but deletes the bottom, so one pop looks perfect. Add assert lines that pop more than once and check the survivors, then Run: a failing assert stops the program and prints the line, which is all a test really is.

If your assertions pass here, they are too gentle: the code is broken, so a good test must complain. Pop 'c' and you get 'c', which looks fine, but the Stack quietly threw away 'a' instead. Pop again and a correct Stack owes you 'b'; this one hands back 'c' a second time. An assert stack.pop() == 'b' on that second pop is the sentence that catches it. This is the everyday reason we push on the contract from more than one angle: a promise checked only at its easiest point is barely checked at all.

Bugs cluster at the edges

There is a pattern to where bugs live, and once you see it you cannot unsee it. They collect at the boundaries. The empty collection, the collection with exactly one thing in it, the moment a counter ticks from below a limit to exactly the limit, the largest value that still fits and the first one that does not. The comfortable middle of the input range is where code tends to be right. The edges are where the off-by-one hides, where a < should have been a <=, where someone forgot that a list can be empty.

The reason is human. When you write a loop or a guard, you are picturing the typical case: a Stack with a few things in it, a number safely inside its range. The edges are the cases you were not picturing, so they are the cases you did not code for. Which means testing the middle proves almost nothing. Push three items and pop them and you exercise the same happy path the author already had in mind. To actually stress the code you have to go where the author’s imagination ran out: to zero, to one, to exactly full, to one past full.

So build a boundary checklist and run down it for every structure you test. Empty. One element. Full, if there is a capacity. Just over full. The smallest and largest values the thing is supposed to hold. Duplicates, if the structure treats sameness specially. Most bugs you will ever write are sitting on that list, waiting for a test that thinks to visit them.

The checks · run against your code

# below capacity, push works and size tracks it
s = BoundedStack(3)
s.push('a')
s.push('b')
assert s.size() == 2
# LIFO order still holds under capacity
s = BoundedStack(3)
s.push('a')
s.push('b')
assert s.pop() == 'b'
assert s.pop() == 'a'
# is_full turns true exactly at capacity
s = BoundedStack(2)
s.push('a')
assert not s.is_full()
s.push('b')
assert s.is_full()
# pushing onto a full stack raises
s = BoundedStack(2)
s.push('a')
s.push('b')
try:
    s.push('c')
    raised = False
except IndexError:
    raised = True
assert raised
python runs in your browser · first run downloads ~240 kb
Plate III A boundary bug in a capacity stack. Three checks stay under the limit and pass; only the fourth pushes one item too many. Press Run to see which row goes red, then repair the guard inside push until the stack refuses its overflowing item and all four rows are green.

Three rows are green and one is red, and it is the one that pushes a third item onto a full stack. Everything below the boundary behaves: a stack with room to spare pushes and pops and reports its size correctly, and is_full even flips true at the right moment. The code misbehaves only on the single push that should have been refused and was not. That is the signature of a boundary bug. It is invisible everywhere except the one place you have to deliberately aim at, which is precisely why the middle-of-the-range tests all sailed through.

Hint one

Every check that stays under capacity passes. The only failure is the push that should be rejected once the stack is full. So the bug is in the guard inside push, the comparison that decides whether the stack is already full.

Hint two

The guard reads if len(self._items) > self._capacity. Walk it for capacity 2: after two pushes the length is 2, and 2 > 2 is false, so a third push slips straight through. What comparison would catch the stack at exactly full, rather than one item past it?

The solution

The guard is off by one. len(self._items) > self._capacity only fires after the stack has already overfilled, and by then the illegal item is on board. Full means the length has reached the capacity, so the test is >=:

def push(self, item):
    if len(self._items) >= self._capacity:
        raise IndexError('stack is full')
    self._items.append(item)

Now a capacity-2 stack refuses its third push, is_full still reads true at exactly two, and all four checks go green. One character, > to >=, and the boundary is sealed. Nearly every off-by-one you meet will look this small and cost this much.

An edge in the logic, not the container

That bug lived at the edge of a container, the push that tips it past full. But edges are not only about collections filling up. They live inside ordinary logic too, in the exact spot where a loop decides how far to go. A single wrong number in a range is a boundary bug with no capacity anywhere in sight.

Here is a plain function, largest, that walks a list and hands back the biggest number it finds. It works on most lists you would think to give it. It has a bug, and the bug sits at one specific edge: the very last position.

The checks · run against your code

# the largest value sitting in the middle is found
assert largest([3, 9, 4]) == 9
# a single element is its own largest
assert largest([5]) == 5
# a run of equal values returns that value
assert largest([2, 2, 2]) == 2
# the largest value sitting in the last position is found too
assert largest([1, 2, 7]) == 7
python runs in your browser · first run downloads ~240 kb
Plate IV A boundary bug with no container in sight. Three checks put the largest value in the middle, alone, or in a tie of equals, and all pass; the fourth puts it last and fails. Press Run to see which row goes red, then fix the loop bound until every row is green.

Three rows are green and one is red, the row whose largest value hides in the final slot. The middle case, the single element, the tie of equals, all of them sail through, because the biggest number happens to sit somewhere the loop actually looks. Only when the answer lives at the last index does the off-by-one show its face. It is the capacity bug’s cousin: the same shape, a loop bound that stops one step short instead of a comparison that fires one step late, and the same lesson underneath. If your tests only ever drop the interesting value into the comfortable middle, this loop looks flawless.

Hint one

Every check that keeps the largest value away from the end passes; the only failure puts it last. So the loop is not looking at the final element at all.

Hint two

The loop runs for i in range(len(nums) - 1). Walk it for a three-element list: range(2) gives you indices 0 and 1, so index 2, the last one, is never visited. What bound would let the loop reach it?

The solution

The - 1 is the whole bug. range(len(nums) - 1) stops one index short, so the final element never gets compared and a largest value hiding there is missed. Let the loop reach the end:

def largest(nums):
    best = nums[0]
    for x in nums:
        if x > best:
            best = x
    return best

Iterating over nums directly sidesteps the index arithmetic entirely, which is usually the cleaner fix: fewer places to be off by one. Run the checks again and the last-position row goes green with the rest.

What a good test looks like

We have been writing tests; let me name what makes one good, because a sloppy test is worse than none. It fails for the wrong reasons, you learn to shrug at the red, and then it misses the failure that mattered. Three habits carry most of the weight.

First, one behavior per test. Each test should be able to fail for exactly one reason. When test_starts_at_zero breaks, you want to know instantly that the initial value is wrong, not go spelunking through a method that also pushed, popped, resized, and checked six other things along the way. A test that asserts one idea points straight at the fault. A test that asserts ten points nowhere.

Second, a shape worth memorizing: arrange, act, assert. Arrange the world (build the Stack, push what the case needs). Act, the single operation under test (call pop). Assert what must now be true. Keeping those three beats visible and in order makes a test read like a sentence and makes it obvious which line is the actual claim, so a reader can check the claim against the promise at a glance.

Third, make the failure legible. When a test fails at two in the morning, the message is all you have. This is why assertEqual(got, 2) beats assertTrue(got == 2): the first prints both values when it breaks, the second just says “false” and leaves you guessing which number was wrong. Well-named tests and expressive asserts turn a red run into a set of instructions.

And here is the quiet bonus. Tests written this way become the documentation. A newcomer who reads your test file sees, in executable form, exactly what your Stack promises and how it is meant to be called. Comments drift out of date and no one notices; a test that lied would be a test that failed. Your suite is the one description of the code that cannot rot without someone’s build going red.

Green is evidence, not proof

It is tempting, when the whole suite goes green, to believe the code is correct. That is not what green means. A passing test says: for the exact inputs I tried, the code did what I expected. It says nothing about the inputs you did not try. Tests are evidence, sometimes overwhelming evidence, but never proof.

Think about what green can hide. A bug in a case you never wrote a test for, the boundary you forgot to visit. A test that asserts too little, so broken code limps past it. Two bugs that cancel: push and pop both reach for the wrong end and the errors undo each other, so a round trip looks perfect while each half is broken. And whole categories that tests barely touch, performance in particular: our list-backed Queue passes every correctness check and is still quietly linear on every dequeue, a fact no assertEqual will ever surface.

None of this is a reason to skip tests. It is a reason to hold them at their true worth. Green is the floor, not the ceiling: it says the promises you thought to check are holding. The bugs that survive are, by definition, the ones you did not think to check for, which is exactly why the boundary checklist and the habit of pressing on the contract from several angles matter so much. You are not trying to prove the code correct, an impossible errand for anything interesting. You are trying to shrink the space where a bug can still be hiding.

Turn every bug into a test

Some bugs get past the tests and reach you as a bug report: a crash, a wrong answer, a colleague saying “the stack loses my last item when it’s full.” The instinct is to dive in and fix it. Resist for one minute and do something better first. Reproduce the bug as a failing test.

Write the smallest test that fails because of exactly this bug, and watch it go red. That red is proof you have actually cornered the bug and not some innocent neighbor of it. Now fix the code and watch the same test go green. You have not only repaired the fault, you have left a tripwire: if anyone, future you included, ever reintroduces that bug, this test catches it the instant the suite runs. The bug can never come back silently.

This is regression testing, and it is how a suite gets wise over time. It does not spring into the world complete. It grows one scar at a time, every bug that ever hurt you becoming a permanent guard against its own return, so that a mature codebase’s tests are in large part an autobiography of its past mistakes. The boundary bug you just fixed in the capacity stack is a perfect case: the check that pushes a third item onto a full stack is precisely the regression test that would have caught it, and now always will.

Testing that the error happens

We keep saying a Stack promises to complain when you pop it empty, and that word, promise, is exact. Raising the right error is part of the contract, every bit as binding as returning the right value. So it has to be tested, which means writing a test that passes only when the code fails, and fails in the correct way. You have already seen the shape, in the empty-pop check on the very first plate:

s = Stack()
try:
    s.pop()
    raised = False
except IndexError:
    raised = True
assert raised

Read it as a claim: calling pop on an empty Stack must raise IndexError. If it raises, we catch it and record success. If it does not raise, control falls through to raised = False and the final assert fails, because a Stack that quietly returns None from an empty pop has broken its promise just as surely as one that hands back the wrong item. In real unittest you write the same claim with a context manager, which says it in one line:

def test_pop_empty_raises(self):
    s = Stack()
    with self.assertRaises(IndexError):
        s.pop()

Either way the point stands: an error is not the absence of behavior, it is behavior, specified and owed. When we reach exceptions in their own right a couple of lectures on, this is the ground we build from. Errors are part of the contract, and a contract clause you never tested is a clause you are only hoping holds.

Now you write the tests

Every plate so far handed you the checks and asked you to repair the code. Real work runs the other way at least as often: the code is written, maybe by someone else, maybe right, maybe not, and the tests are yours to supply. So let me flip the exercise. Below are two Stacks, one correct and one whose pop reaches for the wrong end, the same fraud from the very first plate. Your job is to write a suite that tells them apart. It must accept the good Stack and reject the broken one.

This is the definition of a good ADT test made executable. Hold the line in your head: a good test survives any correct implementation and fails every incorrect one. The two checks below hold your check_contract to exactly that standard. The first runs it against the correct Stack and expects no complaint. The second runs it against the broken Stack and expects an AssertionError, because a suite that cannot catch a wrong-end pop is not testing order at all.

The checks · run against your code

# your suite accepts the correct Stack
check_contract(Good)
# your suite rejects a Stack whose pop takes the wrong end
try:
    check_contract(Broken)
    rejected = False
except AssertionError:
    rejected = True
assert rejected
python runs in your browser · first run downloads ~240 kb
Plate V Now you write the tests. Fill in check_contract with asserts on push, pop, and size. The first check demands your suite accept a correct Stack; the second demands it reject a Stack whose pop takes the wrong end. Press Run until both rows are green.

The trap in that prediction is the whole lesson. A one-element suite passes the first check and fails the second, because with a single item on the Stack the top and the bottom are the same place, so a wrong-end pop is indistinguishable from a right-end one. To reject the fraud your suite has to push at least two different items and assert the order they come back in. The moment it does, the second row goes green, and you have written, by hand, the smallest test that actually encodes LIFO.

Hint one

The starter check_contract asserts nothing, so it accepts everything, the broken Stack included. That is why the reject check is red: your suite never disagrees with anyone.

Hint two

To tell LIFO from a wrong-end pop you need at least two different items and you must check the order they come off. Push three, then assert the pops come back newest first.

The solution

Push a few distinct items and assert the LIFO order:

def check_contract(Stack):
    s = Stack()
    s.push('a')
    s.push('b')
    s.push('c')
    assert s.pop() == 'c'
    assert s.pop() == 'b'
    assert s.pop() == 'a'

Against Good the pops come back 'c', 'b', 'a' and every assert holds, so the first check is green. Against Broken, whose pop takes from the front, the first pop returns 'a', the assert s.pop() == 'c' raises AssertionError, and the second check catches it and goes green. Notice that a single push-and-pop would never have raised on Broken, so this is the shortest suite that does the job: exactly the multi-element order test the LIFO promise demands.

Write the code to the contract

One more direction to practice, and it is the one you will live in most. The tests exist, the contract is pinned down, and you have to write the code that satisfies it. This is where red and green feel most like a conversation: the checks tell you precisely what is missing, and you add the least code that quiets them.

The Stack below is finished except for one promise. It should be able to say whether it is empty, and right now is_empty does nothing, so it returns None and all three checks are red. None is neither True nor False, so even the report is honest about the gap. Fill the method in and drive the rows to green.

The checks · run against your code

# a fresh Stack is empty
s = Stack()
assert s.is_empty() == True
# after one push it is not empty
s = Stack()
s.push(1)
assert s.is_empty() == False
# pushed then popped, it is empty again
s = Stack()
s.push(1)
s.pop()
assert s.is_empty() == True
python runs in your browser · first run downloads ~240 kb
Plate VI Write the code to the contract. The three checks pin down what is_empty must promise: true when nothing has been pushed, false after a push, true again once the last item is popped. Fill in the one method and press Run until every row is green.

One line does it: empty means the size is zero, and you already have size to ask. This is the whole loop in miniature. You did not invent the checks, you inherited them, and they handed you a to-do list precise enough that the implementation nearly writes itself. That is the quiet luxury of tests written first: the code you still owe is never a mystery, it is a set of red rows waiting to turn green.

Hint one

The stub falls through to None, and None equals neither True nor False, so every row is red. You need the method to return an actual boolean.

Hint two

A Stack is empty exactly when it holds nothing, which is exactly when its size is zero. You already have a way to ask for the size.

The solution

Empty means the count of items is zero, and comparison already gives you a boolean:

    def is_empty(self):
        return self.size() == 0

A fresh Stack has size zero, so is_empty reads true; after a push the size is one, so it reads false; pop that item and the size falls back to zero, so it reads true again. All three rows go green. Leaning on size rather than poking at _items keeps the method honest for the same reason your tests do: it speaks through the interface, not around it.

Problems

  1. Add a fifth check to the Stack contract in Plate I, on paper: peeking. Suppose a Stack also promises a peek that returns the top item without removing it. Write the labeled check you would add (“peek returns the top without removing it”) as two or three asserts that push, peek, and then confirm the size did not change. Explain why testing peek through size and a following pop, rather than through _items, keeps the check honest.

  2. A colleague’s Stack test reads assert stack._items == [1, 2, 3]. It passes today. Describe a correct change to the Stack, one the LIFO contract explicitly permits, that would break this test even though the Stack still works perfectly. Then rewrite the assertion so it tests the promise instead of the plumbing.

  3. Explain why test-driven development asks you to watch a test fail before you make it pass. Give a concrete example of a test that would pass against an empty, unwritten function, and say what watching it go red first would have revealed.

  4. Write the boundary checklist for the capacity stack in Plate III, on paper. Name the specific cases you would test (empty, one element, exactly at capacity, one push past capacity, and the smallest legal capacity) and, for each, the single assertion that would exercise it. Then say which case caught the off-by-one, and explain why a suite that tested only a “comfortable middle” stack, say capacity 10 with three items in it, would have reported all green while the bug sat untouched.

  5. A bug report lands: “my Queue drops its first item after I dequeue once.” Following the regression discipline, list the steps you would take, in order, before and after fixing the code, and write the smallest failing test you would add first, as a try-free block of plain asserts against a fresh Queue. Say what the test proves while it is red and what it proves once it is green, and explain why writing that test before the fix is worth the extra minute.

  6. Test-drive a Queue. The plate below holds a Queue with a bug and a contract of four checks that encode FIFO, first-in first-out: the item you enqueue first is the one you dequeue first. Run it, read which row goes red, and fix the Queue until every check is green. As with the Stack, the checks never reach past the interface, so any correct Queue passes them.

    The checks · run against your code

    # enqueue then dequeue returns that item
    q = Queue()
    q.enqueue(7)
    assert q.dequeue() == 7
    # FIFO order across three enqueues
    q = Queue()
    q.enqueue('a')
    q.enqueue('b')
    q.enqueue('c')
    assert q.dequeue() == 'a'
    assert q.dequeue() == 'b'
    assert q.dequeue() == 'c'
    # size tracks enqueues and dequeues
    q = Queue()
    assert q.size() == 0
    q.enqueue(1)
    q.enqueue(2)
    assert q.size() == 2
    q.dequeue()
    assert q.size() == 1
    # dequeue on empty raises
    q = Queue()
    try:
        q.dequeue()
        raised = False
    except IndexError:
        raised = True
    assert raised
    python runs in your browser · first run downloads ~240 kb
    Plate VII Test-driving a Queue. Four checks encode the FIFO contract; the buggy dequeue takes from the wrong end. Press Run, watch the order check fail, and repair dequeue until all four rows are green.
    Hint one

    The single enqueue-then-dequeue check passes and the size and empty checks pass; only the three-item order check fails. So dequeue is returning from the wrong end, just as the broken Stack did, only here the correct end is the opposite one.

    Hint two

    A Queue serves the oldest item first. New items were appended to the end of the list, so the oldest one sits at the front. Which argument to pop reaches the front?

    The solution

    The buggy dequeue calls self._items.pop(), taking the newest item from the end: that is a Stack’s move, not a Queue’s. FIFO wants the front of the list, so pop at index zero:

    class Queue:
        def __init__(self):
            self._items = []
    
        def enqueue(self, item):
            self._items.append(item)
    
        def dequeue(self):
            return self._items.pop(0)
    
        def size(self):
            return len(self._items)

    All four checks pass. Worth noticing for later: pop(0) has to shift every remaining item down by one, so this list-backed Queue pays a linear cost on every dequeue. A Stack got constant time from a list for free; a Queue does not, and closing that gap is exactly the itch that drives us to the ADTs and linked lists ahead.

  7. In “Now you write the tests” your suite had to reject a Stack whose pop took the wrong end. Suppose instead you are handed a Stack whose pop is perfectly correct but whose push silently drops every second item it is given, so pushing ‘a’, ‘b’, ‘c’ leaves only ‘a’ and ‘c’ on board. Write, on paper, the smallest check_contract body, as asserts on push, pop, and size, that a correct Stack passes and this one fails. Explain why a single push followed by a single pop can never expose the bug, and say whether the promise your check leans on is the LIFO order or the size.

  8. Test-drive a min-tracking Stack. A MinStack is an ordinary Stack that also promises a min method returning the smallest item currently on it. The one below caches the minimum as items are pushed, which is fast but fragile. Run the checks, find the row that goes red, and repair min until the contract holds. Then, in a sentence, name which boundary the failing check visits and say why a cache that is only ever updated on push is bound to go stale.

    The checks · run against your code

    # min reports the smallest item on the stack
    s = MinStack()
    s.push(3)
    s.push(1)
    s.push(2)
    assert s.min() == 1
    # a single element is its own min
    s = MinStack()
    s.push(7)
    assert s.min() == 7
    # after the minimum is popped off, min reflects what remains
    s = MinStack()
    s.push(5)
    s.push(2)
    assert s.min() == 2
    s.pop()
    assert s.min() == 5
    python runs in your browser · first run downloads ~240 kb
    Plate VIII Test-driving a MinStack. Three checks pin down what min must report; the buggy version caches the minimum on push and never repairs it on pop, so it lies once the smallest item is gone. Press Run, find the red row, and fix min until all three are green.
    Hint one

    The first two checks pass and only the third fails. Min is right until the current minimum is popped off, and then it keeps reporting a value that is no longer on the stack.

    Hint two

    push updates _min whenever a smaller item arrives, but pop never touches _min. So once the smallest item leaves, the cache is stale. Where does the true, current minimum actually live?

    The solution

    The cached _min is the whole problem: push keeps it current but pop never repairs it, so the moment the smallest item is removed the cache lies. The source of truth is the list of items itself, so ask it directly:

        def min(self):
            return min(self._items)

    Now min recomputes from what is actually on the stack, so it cannot fall out of step with reality. The third check pops the current minimum and then asks for the new one, exactly the boundary a push-only cache forgets to handle, and it goes green with the others. (A recompute is more work per call; if that ever mattered you would test-drive a smarter cache, one that repairs itself on pop too, and the extra tests you would owe it are precisely the pop-the-minimum cases this check already names. One caveat the checks do not visit: min on an empty stack has no answer, so a fuller contract would specify whether that raises, and test it.)

The whole loop in one figure

We have run the loop in pieces: a red row cornered a bug, a one-character change turned it green, and once every promise held we were free to tidy the code without fear. The plate below runs all three beats on a fresh example, a median(nums) with two planted bugs, so you can watch red become green become a cleaner green. The six cases partition the input space the way our boundary checklist says they should: the empty list, a single element, the odd and even lengths, the smallest even case at n=2n = 2, and a tie of equals. Pick which cases go into the run, step the code forward one fix at a time, and watch the failures squash and the refactor leave every row untouched.

Notice how the reds cluster. In the first cut, the even-length rows and the empty row are the only ones that fail, which tells you where to look before you have read a line of the fix: the middle-index trick is fine for odd lengths and wrong for even ones, and the empty case was never handled at all. Two bugs, two fixes, then a refactor that collapses the parity branch into one line and, crucially, moves not a single row from green. That last step is the point people skip: refactoring is only safe because the tests are watching, and the tests only let you tidy the code because none of them cares how the median is computed, just what it returns.

v3 · one line for both parities · refactored, every case green

def median(nums):
    if not nums:
        raise ValueError('median of empty sequence')
    n = len(nums)
    lo = nums[(n - 1) // 2]
    hi = nums[n // 2]
    return (lo + hi) / 2
case call expected got ·
empty median([]) raises ValueError raises ValueError green
single median([5]) = 5 = 5.0 green
typical, odd n median([1, 3, 7]) = 3 = 3.0 green
even n median([1, 2, 3, 4]) = 2.5 = 2.5 green
boundary, n = 2 median([2, 8]) = 5.0 = 5.0 green
tie of equals median([4, 4, 4]) = 4 = 4.0 green

Red, green, refactor on a median function. Enable JavaScript to pick which cases go into the suite, step the code forward through two fixes and watch the failing rows squash one at a time, then a refactor that changes the code and leaves all six rows green.

Plate IX Red, green, refactor on a median function. Six labeled cases partition the input space; two planted bugs light the even-length and empty rows red. Step the code through two fixes to squash the failures one at a time, then a refactor that changes the code and leaves all six rows green. Drop cases from the run to see how a thinner suite corners the bug less sharply.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.