In the Observer pattern, a subject maintains subscriptions through a common observation interface. Interested observers register and unregister; when a relevant state change occurs, the subject sends a notification, and each observer runs its own reaction. Notifications can carry the new information directly or prompt the observer to query the subject's coherent updated state.
This fits an event-driven programming interface in which one model can have several independently changing views: a displayed conversion, a chart or a status indicator can react to the same model change. It avoids hard-coding calls to every concrete view inside the subject, which would couple domain logic to presentation details and require editing the subject whenever another view is added. The subject depends on the observer interface rather than every concrete observer class.
The design still needs subscription cleanup and an update policy. Mutual notifications can create a feedback loop or a reentrant event handler, while an observer that reacts halfway through a state change can see inconsistent data. Publishing only coherent changes and controlling derived display updates address those problems; the pattern alone does not automatically solve them.
Test-driven development interleaves three small steps: write a test expressing the next required behavior and observe that it fails, implement enough behavior to make it pass, then improve the code's structure while keeping the tests passing. The retained tests become a regression suite. For example, before implementing a book deletion, test that deleting an existing contact removes it and returns true; later add the absent-name case. Each test guides a small implementation step rather than waiting for a finished component.[ref]
Compared with a traditional write-the-component-then-test workflow, tests guide the design before each increment is implemented. This does not imply that all non-TDD testing is postponed until a whole product is finished, or that TDD eliminates broader integration testing.
The test-first behavioral core is naturally black-box testing: expected outcomes come from the operation's contract. Later tests can use internal control flow or representation cases, becoming white-box testing. Thus a complete practice can use a mixture, with mainly contract-based black-box tests driving the next behavior. The classification depends on how test cases are chosen, not on whether the programmer personally knows the implementation. Passing a finite suite is not a proof of universal correctness.
Add the following concrete method inside FiniteDist[T]. It forms a pushforward of a finite probability distribution, adding the masses of outcomes that map to the same result:
def map[U](f: T => U): FiniteDist[U] = {
  val source = getDom
  val weighted = source.map(x => (f(x), getProb(x)))
  val target = weighted.map(_._1).distinct
  new FiniteDist[U] {
    def getDom: List[U] = target
    def getProb(y: U): Double =
      weighted.filter(pair => pair._1 == y).map(_._2).sum
  }
}
The input finite probability distribution is assumed to satisfy its interface, with stable masses during construction, and f must be a total deterministic pure function on its finite support. Output values need stable equality consistent with the mathematical equality being modeled; mutating equality-relevant fields afterwards would undermine any finite-support implementation. Computing weighted once also prevents later queries from re-evaluating f inconsistently.
Every source support element appears once in weighted. The distinct operation lists each image value once; every such image has a positive mathematical mass because it has a positive-mass preimage. For each , filtering selects exactly those with , so getProb(y) is the required sum, with an empty sum of zero off the image. The fibers form a set partition of the original support, giving
Thus colliding images have their probabilities added, not overwritten. For a concrete check, mapping a uniform distribution on by parity gives probability to each of ; mapping every source value to one constant gives a singleton domain with total mass one. Floating-point rounding can make a computed total differ slightly from one; the proof is for exact mathematical masses, and the representation uses Double approximations.
Programming language polymorphism lets one expression or operation work with values of different types or concrete representations. In object-oriented programming, subtype polymorphism lets a reference of an interface or superclass type designate instances of different implementing software classes. A call through that reference uses dynamic dispatch to select the receiver's overriding object method. For example, a routine taking Book can invoke recall on a linked-list or an array-based implementation while depending only on the common abstract contract.
Parametric polymorphism is another form: the type parameter in FiniteDist[T] lets the same interface describe distributions over Booleans, integers or characters. A generic method introduces a further type parameter when its output type differs. Method overloading, in contrast, supplies several statically selected signatures with one name; it should not be confused with receiver-dependent dynamic dispatch. Correct substitutability also requires implementations to respect the common behavioral contract, not merely to share method names.
Represent an applied edit by a command pattern object with undo and redo. Use zero-based positions. For move(from,to), define to as the slide's index in the resulting sequence; it is in for a presentation of length . Removing the slide first and then inserting at that index implements this convention in either direction.
trait Change {
  // Pre: this is the most recent applied change not yet undone.
  def undo(): Unit
  // Pre: this is the next change on the redo history.
  def redo(): Unit
}

class SlideSuite(initial: Sequence[Slide]) {
  private var slides = initial

  private def insertRaw(i: Int, x: Slide): Unit = {
    slides = slides.insert(i, x)
  }

  private def deleteRaw(i: Int): Unit = {
    slides = slides.delete(i)
  }

  private def moveRaw(from: Int, to: Int): Unit = {
    val x = slides.elementAt(from)
    slides = slides.delete(from).insert(to, x)
  }

  def insert(i: Int, x: Slide): Change = {
    insertRaw(i, x)
    new Change {
      def undo(): Unit = deleteRaw(i)
      def redo(): Unit = insertRaw(i, x)
    }
  }

  def delete(i: Int): Change = {
    val x = slides.elementAt(i)
    deleteRaw(i)
    new Change {
      def undo(): Unit = insertRaw(i, x)
      def redo(): Unit = deleteRaw(i)
    }
  }

  def move(from: Int, to: Int): Change = {
    moveRaw(from, to)
    new Change {
      def undo(): Unit = moveRaw(to, from)
      def redo(): Unit = moveRaw(from, to)
    }
  }
}
Sequence and Slide are the supplied external types. Valid insertion positions are , deletion positions are , and both move positions are valid indices of the original length. These are the permitted unchecked argument preconditions. The private raw operations perform exactly their named state transformation and do not create history entries. A move to the same index is a legitimate no-op.
The deleted slide must be saved because its index alone cannot reconstruct it. By contrast, insertion already receives the slide to retain. For a move, the inverse of moving the slide from from to its final index to is to remove it at to and reinsert it at from; all other slides retain their relative order. Thus each returned object satisfies undo restores the state immediately before the edit, and redo restores the state immediately after it, under the stated history protocol.
A controller can enforce the protocol with two stacks. This code records changes that have already been executed:
class History {
  private var done = List.empty[Change]
  private var undone = List.empty[Change]

  // Pre: c is a fresh, already-applied change of this history's suite.
  def record(c: Change): Unit = {
    done = c :: done
    undone = Nil
  }

  def undo(): Unit = {
    require(done.nonEmpty)
    val c = done.head
    c.undo()
    done = done.tail
    undone = c :: undone
  }

  def redo(): Unit = {
    require(undone.nonEmpty)
    val c = undone.head
    c.redo()
    undone = undone.tail
    done = c :: done
  }
}
For example, history.record(suite.move(i,j)) executes and records one move. The representation invariant says that done contains applied changes in reverse application order, while undone contains undone changes in the next-redo order, all belonging to the same suite. A fresh edit clears the redo branch. Undo and redo transfer one command between the two heads, so they neither skip intervening edits nor generate new history records. Unrecorded external edits and out-of-order use of old command objects are excluded by this protocol.
The return types suggest an immutable sequence implementation: insertion and deletion return a new Sequence[A], while the receiver can remain unchanged. A mutable implementation would more naturally return Unit for in-place edits, though it could return itself. Thus the signatures are evidence of an intended immutable object implementation, not a logical guarantee. For the snapshot solution below, require that returned and retained Sequence values really are immutable. The owning SlideSuite can still have a mutable variable referring to its current immutable sequence.
Keep the same player until an occupied, in-range cell is supplied:
val board = new Chomps(6)
var player = 1
while (board.Count() > 0) {
  board.Display()
  var x = -1
  var y = -1
  while (!board.Legal(x, y)) {
    println("Player " + player + ": enter x, then y")
    try {
      x = scala.io.StdIn.readInt()
      y = scala.io.StdIn.readInt()
    } catch {
      case _: NumberFormatException =>
        x = -1
        y = -1
    }
    if (!board.Legal(x, y)) println("Choose an occupied cell")
  }
  board.Move(x, y)
  if (board.Count() == 0)
    println("Player " + player + " loses; player " + (3 - player) + " wins")
  else player = 3 - player
}
The outer loop invariant is that player is the next player's number, either one or two, and the board is the result of the accepted moves. The inner loop invariant says that the board and player have not changed; rejected inputs do not consume a turn. Assuming the input source continues and eventually supplies a legal coordinate pair, the inner loop finishes. No program can guarantee that a user stops entering illegal moves, so that interaction assumption is necessary.
Every accepted move removes at least its selected token, so the outer loop variant is Count(), a decreasing nonnegative integer. In a nonempty order ideal, is occupied. Removing it removes the entire board, whereas a move at any other cell leaves it. Therefore the player making the final move is exactly the loser; the code reports that player before changing the turn. At most legal moves occur.
Use the row boundary and cache its sum. The restriction on the initial total makes the fixed Int return type of Count meaningful; Display separately checks the requested single-digit coordinate range.
class Chomps(N: Int) {
  require(N > 0 && N.toLong * N.toLong <= Int.MaxValue.toLong)
  private val row = Array.fill(N)(N)
  private var remaining = N * N

  def Count(): Int = remaining

  def Legal(x: Int, y: Int): Boolean =
    0 <= x && x < N && 0 <= y && y < N && x < row(y)

  def Move(x: Int, y: Int): Unit = {
    require(Legal(x, y))
    var j = y
    while (j < N) {
      val next = math.min(row(j), x)
      remaining -= row(j) - next
      row(j) = next
      j += 1
    }
  }

  def Display(): Unit = {
    require(N < 10)
    var y = N - 1
    while (y >= 0) {
      print(y.toString + " ")
      var x = 0
      while (x < N) {
        print(if (x < row(y)) "* " else "  ")
        x += 1
      }
      println()
      y -= 1
    }
    print("  ")
    var x = 0
    while (x < N) {
      print(x.toString + " ")
      x += 1
    }
    println()
  }
}
The additional representation invariant is . It initially holds. For Move, write for the boundary at entry. The loop invariant says that rows before are unchanged, rows from through equal , rows from onwards still equal , and remaining equals the sum of the current entries. The loop variant is . Each iteration subtracts exactly the newly removed number of cells from the cache. At exit all affected rows are truncated as required, and the nonincreasing boundary is restored. During a partially completed update it need not be nonincreasing; only the stated loop invariant, not the full externally visible representation invariant, is required internally.
For Display, the outer loop invariant says that exactly the rows with indices greater than have been printed correctly; its loop variant is . The inner loop invariant says that the current row's first cells have been emitted correctly; its loop variant is . The final labels loop has the same decreasing loop variant, and prints exactly the first column labels before each iteration. Short-circuit evaluation in Legal checks both coordinates before indexing. An illegal Move fails before changing the board.
Push the right child before the left child so that the LIFO stack exposes the left child first:
def preorderIterative(t: Tree): Unit = {
  val pending = new Stack
  if (t != null) pending.push(t)
  while (!pending.isEmpty) {
    val u = pending.pop
    println(u.datum)
    if (u.right != null) pending.push(u.right)
    if (u.left != null) pending.push(u.left)
  }
}
Let be the sequence of labels in the preorder traversal of . If the abstract pending stack, top first, is , the loop invariant is that the output already printed, followed by , is the required full output. Each pending root is non-null, and its subtree is still unvisited. This is the pending-work form of explicit-stack depth-first tree traversal.
One iteration discharges the first root's own label and replaces its remaining obligation by the left subtree followed by the right subtree. The push order makes that precisely the new top-first pending order. Thus the loop invariant is preserved. The loop variant is the sum of the numbers of vertices in all pending subtrees; it decreases by exactly one per iteration, even if the number of stack entries increases. When the stack is empty there is no remaining output obligation, proving correctness and termination. This assumes a finite genuine binary tree and, as permitted, sufficient stack capacity. Each vertex is pushed and popped once, giving time and pending references for binary tree height .
Store the bottom of the stack at index zero and the top at the last occupied index:
class Stack {
  private val MAX = 1000
  private val data = new Array[Tree](MAX)
  private var used = 0

  // Pre: used < MAX.
  def push(t: Tree): Unit = {
    require(used < MAX, "Stack full")
    data(used) = t
    used += 1
  }

  // Pre: used > 0.
  def pop: Tree = {
    require(used > 0, "Stack empty")
    used -= 1
    val result = data(used)
    data(used) = null
    result
  }

  // Pre: true.
  def isEmpty: Boolean = used == 0
}
The representation invariant is that data.length==MAX, , and unused slots from used onwards contain null references. Occupied slots contain the stored Tree references; the stack itself need not forbid null values. The abstraction function, written with the first sequence element at the top, is
Initially this is the empty sequence. push prepends its argument, pop removes and returns the first abstract element, and isEmpty reports whether the abstract sequence is empty. These postconditions follow directly from the index changes. Clearing a popped slot avoids retaining an otherwise unused tree reference. All three operations take time. No loops are needed.
Treat a null reference as the empty binary tree and perform the visit before descending:
def preorderRecursive(t: Tree): Unit = {
  if (t != null) {
    println(t.datum)
    preorderRecursive(t.left)
    preorderRecursive(t.right)
  }
}
By structural induction, the empty binary tree produces the empty output. A nonempty binary tree prints its root label, then the complete preorder traversal of the left subtree, then that of the right subtree. These are exactly the required output positions. The recursion terminates on a finite binary tree because each recursive call has strictly fewer vertices. For the three-node example, the output order is . The time complexity is linear in the number of vertices, with call stack depth bounded by the height of a binary tree plus a constant.
Use the move-to-front heuristic. Replace only recall in LinkedBook by:
def recall(name: String): String = {
  require(name != null)
  val p = findPrev(name)
  require(p.next != null, "Name is not in the book")
  val found = p.next
  if (p ne header) {
    p.next = found.next
    found.next = header.next
    header.next = found
  }
  found.number
}
The search has the same loop invariant and loop variant as before. Detach the existing linked list node before inserting it immediately after the dummy header node. The branch for an already-first linked list node avoids linking it to itself. Every real contact still occurs exactly once with the same name/number binding, so the representation invariant and abstraction function are preserved at return. No new linked list node is allocated, and an immediate repeated recall needs one name comparison. The present recall still pays its original search cost; the gain is for later repeated access.
Let be the number of real contacts, and suppose the requested name is at position , counting from one. The implementation above makes exactly name-equality comparisons, including the successful comparison; null checks are not string comparisons. Thus the minimum is one, when the first real contact is requested, and the maximum is , when the last is requested. The precondition excludes unsuccessful recalls and recalls on an empty book. This counts calls to string equality, not individual character inspections within each call.

There are unlisted articles, also show them or only show them.