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]
Test-driven development in the Agile Alliance glossary. What is TDD?: interleaving unit tests, implementation and refactoring in a short cycle
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 The input finite probability distribution is assumed to satisfy its interface, with stable masses during construction, and
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
}
}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, givingThus 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:For example,
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
}
}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:The outer loop invariant is that
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
}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 The additional representation invariant is . It initially holds. For
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()
}
}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: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.
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)
}
}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:The representation invariant is that
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
}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, isInitially 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: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.
def preorderRecursive(t: Tree): Unit = {
if (t != null) {
println(t.datum)
preorderRecursive(t.left)
preorderRecursive(t.right)
}
}Use the move-to-front heuristic. Replace only 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.
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
}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.