A Class Design Example With Class Invariants: 25-Comp-B11 Advanced Software Design, December 2018, Q12

Question 12: A Class Design Example With Class Invariants (Part II)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Example: BoundedQueue, a fixed-capacity FIFO queue backed by a circular array.

class BoundedQueue {
  private Object[] items;
  private int capacity;
  private int size;      // number of elements currently stored
  private int head;      // index of the front element
  // invariant: 0 <= size <= capacity
  // invariant: 0 <= head < capacity  (whenever capacity > 0)
  // invariant: items.length == capacity
  void enqueue(Object x) { /* precondition: size < capacity */ }
  Object dequeue()       { /* precondition: size > 0 */ }
}

Class invariants and why they hold. 0 ≤ size ≤ capacity expresses that the queue can never report holding more elements than its backing array can physically store, nor a negative count; every enqueue increments size only after checking its precondition size < capacity, and every dequeue decrements it only after checking size > 0, so no public operation can push either bound. 0 ≤ head < capacity keeps the circular index that marks the logical front of the queue within the backing array's valid range at all times, wrapping via modulo arithmetic rather than growing unboundedly. items.length == capacity ties the array's physical size to the class's own notion of capacity, so no index computed from head/size can ever run past the array's actual bounds.

Together these invariants are exactly what let enqueue/dequeue be implemented with simple, unchecked array indexing internally: because the invariant guarantees every index the methods compute is already in range, no method needs an internal bounds check on every array access — the invariant, established once at construction and re-verified at every public-method boundary, does the safety work that would otherwise require redundant per-access checks.

Concept & Theory: An Invariant as a Standing Safety Guarantee

Topic: A class invariant that, once established, lets method bodies skip redundant internal checks.

Key relations: Invariant holds at entry (by the calling convention) → method body may rely on it → invariant re-established before return.

Why this works: Precisely because the invariant is checked/preserved at every public boundary (Question 10), a method's internal logic can assume it holds on entry without re-verifying it, which is what makes contracts a genuine implementation simplification and not just a documentation exercise.

Common pitfall: Stating an invariant that is not actually preserved by every public method — e.g. forgetting to check size < capacity in enqueue would let size exceed capacity, silently invalidating every later index computation.

Source: Meyer, Object-Oriented Software Construction (class invariants as part of the contract triad).

Question 12 of 28: A Class Design Example With Class Invariants

Question 12: A Class Design Example With Class Invariants (Part II)