An invariant is a rule that every valid state of a data structure or computation must satisfy. The useful question is not just “Is this true now?” but “Will each operation leave it true?” A well-chosen invariant can rule out awkward cases before they reach the code. section 2.4
Keep the front of a queue available
Build an immutable queue from two stacks: one receives enqueued items, and the other supplies dequeued items. Require every nonempty queue to have a nonempty dequeue stack. Enqueue puts the first item directly on that stack. Dequeue either pops it, returns the empty queue, or reverses the enqueue stack to replenish it. There is no need for a branch handling a nonempty queue whose only item is stranded on the enqueue stack: valid operations never create one. section 2.4
An invariant can also repair an algorithm’s boundary behavior. Stepping an n-quad in a Life simulation produces an (n−1)-quad, so repeated steps appear to shrink the grid—even when living cells may move outward. Surrounding living cells with empty space before each step, then enlarging the result, keeps them away from the edge and lets the grid expand when necessary. section 4.4.3
public void Step(int speed = 0) #1
{
IQuad current = cells;
if (!current.HasAllEmptyEdges())
current = current.Embiggen().Embiggen();
else if (!current.Center().HasAllEmptyEdges())
current = current.Embiggen(); #2
IQuad next = Step(current); #3
cells = next.Embiggen(); #4
}
The Step method checks the empty edges, enlarges the current grid as needed, takes a step, and enlarges the result. section 4.4.3
The rule need not have the same shape in every data structure:
- A deque initially permits only three-item groups in its recursive middle. When a side fills, pushing moves a Three inward. To support cheaper concatenation, the rule is deliberately weakened to permit Twos as well as Threes. section 3.3.2 section 3.7
- A Hughes list uses one shared delegate for every empty list. Its factory returns that same empty value when given an empty stack, making reference equality a usable emptiness test. section 2.7.3
- An incrementally built word graph permits one controlled exception: all words except the most recently added have minimized nodes. Adding the next word fixes the previous one; a final fix-up completes minimization. section 5.4
- An undirected graph wrapper prevents invalid adjacency data: an edge must connect nodes represented in the graph and appear in both directions. Exposing a raw multidictionary would allow missing nodes or one-way edges. section 8.3
