A sentinel node supplies a permanent predecessor for the first real node. Inserting or deleting at the front then uses the same predecessor.next update as an interior operation. Its datum is not a multiset element: the chosen extreme integer is merely unused sentinel data.
A representation invariant requires a nonnull fixed header, a finite acyclic chain starting at bagHeader.next, and exclusion of the header from that chain. Each node identity occurs once, although different nodes may have equal data. Representation links are owned by the implementation, so outside mutation cannot alter them unexpectedly.
The abstraction function counts occurrences:
This yields nonnegative multiplicities and finite support. Initialization with a null successor gives the empty multiset. Excluding the sentinel is essential even when a real item equals its datum.
For a finite acyclic linked list define the node sequence, retaining software object identities, by
Then scan without changing any links:
def findMin(first: Node): Node = {
  require(first != null)
  var best = first
  var cursor = first.next
  while (cursor != null) {
    if (cursor.datum < best.datum) best = cursor
    cursor = cursor.next
  }
  best
}
At each while loop head, write . The loop invariant says is nonempty, best belongs to , and its datum is no larger than that of every node in . Initially contains only first; comparing the next node extends the processed string prefix and preserves minimality. The loop variant strictly decreases. At exit the whole list is processed, so the returned reference identifies a minimum node. Ties retain the earliest minimum. Time is linear in the number of nodes and auxiliary space is constant.
The implementation maintains the two boundaries from part b:
class ArrayDoubleStack(val MAX: Int) extends DoubleStack {
  require(MAX >= 0)
  private val data = new Array[Int](MAX)
  private var left = 0
  private var right = MAX

  def isEmptya: Boolean = left == 0
  def isEmptyb: Boolean = right == MAX

  def pusha(x: Int): Unit = {
    require(left < right, "double stack is full")
    data(left) = x
    left += 1
  }
  def pushb(x: Int): Unit = {
    require(left < right, "double stack is full")
    right -= 1
    data(right) = x
  }
  def popa: Int = {
    require(left > 0, "stack a is empty")
    left -= 1
    data(left)
  }
  def popb: Int = {
    require(right < MAX, "stack b is empty")
    val answer = data(right)
    right += 1
    answer
  }
}
Initialization gives empty abstract lists. Each push consumes one free position next to the appropriate top; each pop returns that top and releases its position. The guards preserve the ordering of the two boundaries and prevent invalid indexing. The abstraction function shows directly that the untouched stack is unchanged. Keeping data private prevents clients from violating the representation invariant; this strengthens encapsulation relative to a publicly exposed implementation field without changing the six required operations.
All six operations run in time, with a fixed array of MAX integers and constant extra state. Creating and zero-initializing the array takes time, outside those operation bounds. Capacity zero gives a valid always-empty bounded structure whose pushes fail their precondition.
A fixed-capacity implementation needs a bounded contract: , and a push requires strict inequality. Pop preconditions and all successful-operation postconditions remain unchanged. An implementation that rejects full-array pushes cannot satisfy an unbounded specification promising every push; the capacity restriction must be part of the agreed abstract data type, or its resource-failure behavior must be specified.
Use one array and two boundaries left and right. The first stack occupies indices below left and grows rightwards; the second occupies indices at least right and grows leftwards. The representation invariant is
The abstraction function is
Both lists are top-first. The unoccupied middle interval has length right - left; a push is possible exactly when this is positive. Thus every array position can be used by either stack, avoiding a rigid half-array allocation.
Figure 1.
Original shared-array double-stack layout: two stacks grow towards a common free interval
. Details.
Use two finite integer lists , with the head of each list representing its stack top. Initially both are empty. A suitable abstract object interface is
trait DoubleStack {
  def pusha(x: Int): Unit
  def pushb(x: Int): Unit
  def popa: Int
  def popb: Int
  def isEmptya: Boolean
  def isEmptyb: Boolean
}
For the unbounded abstract data type, each push has no logical precondition. The postcondition of pusha(x) is and ; pushb(x) symmetrically gives and . The precondition of popa is , and its postcondition is return value , new state , and unchanged . The specification for popb exchanges . Each emptiness query leaves both lists unchanged and returns exactly whether its corresponding list is empty.
These frame conditions matter: an operation on one stack must preserve the other, not merely produce the right return value.
Sort string suffix starting positions, then examine only adjacent entries:
def longestRepeated(): (Int, Int, Int) = {
  require(N >= 2)
  val suffixes = (0 until N).toArray.sortWith(before)
  var besti = suffixes(0)
  var bestj = suffixes(1)
  var bestk = 0
  var t = 1
  while (t < N) {
    val i = suffixes(t - 1)
    val j = suffixes(t)
    val k = longestFrom(i, j)
    if (k > bestk) {
      besti = i; bestj = j; bestk = k
    }
    t += 1
  }
  (besti, bestj, bestk)
}
The while loop retains a best triple among adjacent pairs already visited. All string suffix starting positions are distinct, and the adjacent-suffix characterization proves that considering these pairs suffices. The two definitions named longestRepeated in parts b and e are alternatives, not duplicate members of one software class.
Assuming a comparison sort using comparator calls, sorting takes time, because each comparison scans characters. The final pass takes . Thus overall time is , at worst , with auxiliary storage for indices and ordinary sorting workspace. Merely storing indices does not make string suffix comparisons constant-time; claiming here would omit their cost. Faster suffix-array constructions require additional machinery beyond this comparator-based solution.
Reuse the verified longest-common-prefix scan, handling equality before scanning:
def before(i: Int, j: Int): Boolean = {
  require(0 <= i && i < N && 0 <= j && j < N)
  if (i == j) false
  else {
    val k = longestFrom(i, j)
    if (j + k == N) false
    else if (i + k == N) true
    else a(i + k) < a(j + k)
  }
}
There is no additional while loop: the helper's loop invariant is that the first k characters agree and both indices remain in bounds. If the second string suffix ends first, the first cannot precede it; if the first ends first, it is a proper string prefix and precedes the second. Otherwise the first mismatching characters decide lexicographic order. Distinct suffixes cannot both end after the same number of characters, since their lengths differ.
The i == j case ensures a strict comparator, returning false for a string suffix compared with itself, in constant time. For distinct suffixes its running time is , where is the longest repeated-substring length of the full array.
All suffixes beginning with a fixed string form an interval in lexicographic order. To see this, suppose two suffixes start with a string , while a string suffix between them fails to start with . At its first differing character it must be either smaller than both or larger than both; if it ends before does, it is smaller than both. Either possibility contradicts its position between them.
Now take a longest repeated substring . Its two occurrences are prefixes of two distinct suffixes. Every string suffix between them also begins with , so at least one adjacent pair in that interval has a common string prefix of length at least . A greater length would contradict maximality of . Therefore the maximum common-prefix length over adjacent sorted suffixes equals the longest repeated-substring length. If the maximum is zero, any adjacent pair still attains it. The argument does not assume nonoverlapping occurrences.
Figure 1.
Original suffix-array example for banana: an interval of suffixes shares the repeated prefix ana
. Details.
Compare every unordered pair of distinct starting positions:
def longestRepeated(): (Int, Int, Int) = {
  require(N >= 2)
  var besti = 0
  var bestj = 1
  var bestk = 0
  var i = 0
  while (i < N - 1) {
    var j = i + 1
    while (j < N) {
      val k = longestFrom(i, j)
      if (k > bestk) {
        besti = i; bestj = j; bestk = k
      }
      j += 1
    }
    i += 1
  }
  (besti, bestj, bestk)
}
After each comparison, the stored triple attains the largest common-prefix length among pairs processed so far; its positions remain distinct. The nested while loops enumerate exactly pairs. Reversing the two positions does not change their common-prefix length, so no omitted ordered pair could improve the answer. Initialization also supplies a valid length-zero answer if no character repeats.
Write for the final maximal length. Each comparison takes time, including a possible first mismatch. Hence time is , at worst , and auxiliary space is . Writing merely would miss the case. The explicit precondition excludes arrays with fewer than two valid starting positions; the requested distinct-position triple has no answer there under this domain convention.
Scan the two suffixes until a mismatch or an endpoint:
def longestFrom(i: Int, j: Int): Int = {
  require(0 <= i && i <= N && 0 <= j && j <= N)
  var k = 0
  while (k < N - i && k < N - j && a(i + k) == a(j + k)) {
    k += 1
  }
  k
}
The loop invariant is and equality of the two array segments of length . The loop variant is , which decreases whenever the while loop runs. Short-circuit evaluation checks both bounds before indexing. On exit either a string suffix has ended or the next characters differ, so no longer common string prefix is possible. Thus the returned value is the longest common prefix length. Overlap is allowed: the code only reads the array, so the two matching segments need not occupy disjoint storage.
First find a sign bracket by exponential search, then bisect that bracket without evaluating its endpoints again:
def floorRoot(): Int = {
  require(eval(0.0) < 0.0)
  var lo = 0
  var hi = 1
  while (eval(hi.toDouble) <= 0.0) {
    lo = hi
    require(hi <= Int.MaxValue / 2, "doubling bound exceeds Int range")
    hi *= 2
  }
  while (hi - lo > 1) {
    val mid = lo + (hi - lo) / 2
    if (eval(mid.toDouble) <= 0.0) lo = mid
    else hi = mid
  }
  lo
}
For the first while loop the loop invariant is , with hi a positive power of two, and either or . Every previously tested power of two has nonpositive value. Let be the least nonnegative integer for which . It exists by the positive leading coefficient. If the current upper endpoint is , a mathematical loop variant is while the guard holds; the next doubling decreases it by one. The first while loop's postcondition is . The second while loop has exactly the invariant, variant and adjacent-integer postcondition established in part c.
There are evaluations at powers of two. If , the final bracket has width and takes exactly midpoint evaluations. Including the initial sign check, the total is evaluations for , and two for . Thus evaluation cost is for the first positive dyadic bound ; it is not a claim about the first positive root of a polynomial when the polynomial is nonmonotone.
The mathematical argument uses unbounded integer endpoints and reliable signs. The guarded Int implementation requires the successful dyadic bound to fit in Int; otherwise it explicitly fails rather than wrapping to a negative bound. The coefficient assumptions alone cannot guarantee that a requested integer result fits a fixed-width type. Floating-point overflow or unreliable signs likewise need a wider or certified evaluator for a fully general implementation.
Maintain opposite signs at the endpoints, rather than assuming that the polynomial is monotone:
def floorRoot(X: Int): Int = {
  require(X > 0 && eval(0.0) <= 0.0 && eval(X.toDouble) > 0.0)
  var lo = 0
  var hi = X
  while (hi - lo > 1) {
    val mid = lo + (hi - lo) / 2
    if (eval(mid.toDouble) <= 0.0) lo = mid
    else hi = mid
  }
  lo
}
The loop invariant is and . Both branches preserve those signs, even when there are other roots of a polynomial or sign reversals elsewhere. When the interval width exceeds one, the midpoint is strictly between its endpoints, so the positive integer loop variant hi - lo strictly decreases. On exit hi == lo + 1, giving the required postcondition . Continuity establishes a root of a polynomial between those adjacent integers, possibly at the left endpoint.
The width is at most halved with rounding upwards, so there are at most midpoint evaluations, plus two endpoint evaluations in the precondition check. The midpoint expression avoids adding two large endpoints. The explicit positive upper-bound precondition supplies the interval order assumed in the question. For the literal computed-eval contract, the same proof holds provided evaluated midpoints are not NaN; identifying its bracket with the real polynomial additionally requires trustworthy evaluation signs.
The coefficient assumptions imply a nonconstant polynomial with and a positive leading coefficient. Thus as : dividing by its leading power of leaves the positive leading coefficient plus terms tending to zero. There is some with . A polynomial is continuous, so the intermediate value theorem supplies at least one positive root of a polynomial in .
This gives neither uniqueness nor monotonicity. Multiple crossings are possible. If the degree of a polynomial is an even integer, the same leading-term argument gives as , so there is also a negative root of a polynomial. For an odd integer degree of a polynomial no negative root of a polynomial is forced; a linear polynomial with negative constant coefficient and positive slope is a counterexample.
Use Horner's method, accumulating the high-degree coefficients before the low-degree ones:
def eval(x: Double): Double = {
  var i = a.length
  var value = 0.0
  while (i > 0) {
    i -= 1
    value = a(i) + x * value
  }
  value
}
At each while loop head the loop invariant is
The initial sum is empty. Decreasing i and replacing the accumulator by a(i) + x * value extends that sum by one coefficient with the required powers shifted. The loop variant is i; on exit it is zero, so the accumulator equals . The code uses exactly multiplications and time, with constant auxiliary space, and also handles the empty coefficient array as the zero polynomial. Initializing from the last coefficient instead would save one multiplication for nonempty arrays.
The invariant is an exact-arithmetic specification. With Double, each arithmetic operation rounds; consequently the code evaluates the Horner expression in floating-point arithmetic, rather than guaranteeing the exact real value for arbitrary coefficients.
Choose the following explicit policy: an edit of pounds recomputes euros; an edit of euros recomputes pounds; an edit of the rate keeps pounds fixed and recomputes euros. Amounts may be any finite signed values, while a rate must be finite and strictly positive. Invalid text, non-finite numbers and overflowing conversions leave the last accepted state intact and restore its display.
import scala.swing._
import scala.swing.event.EditDone
import scala.util.Try

object CurrencyConverter extends SimpleSwingApplication {
  def top: Frame = new MainFrame {
    title = "Currency converter"
    val pounds = new TextField(8)
    val euros = new TextField(8)
    val rate = new TextField(8)
    private var poundsValue = 10.0
    private var rateValue = 1.15
    private var updating = false

    private def finite(x: Double): Boolean =
      java.lang.Double.isFinite(x)

    private def money(x: Double): String =
      java.lang.String.format(java.util.Locale.ROOT, "%.2f",
                              java.lang.Double.valueOf(x))

    private def showValues(): Unit = {
      updating = true
      try {
        pounds.text = money(poundsValue)
        euros.text = money(poundsValue * rateValue)
        rate.text = java.lang.Double.toString(rateValue)
      } finally updating = false
    }

    private def commit(field: TextField): Unit = {
      if (!updating) {
        val proposed = Try(field.text.trim.toDouble).toOption
          .filter(finite).map { value =>
            if (field eq pounds) (value, rateValue)
            else if (field eq euros) (value / rateValue, rateValue)
            else (poundsValue, value)
          }
        proposed.foreach { case (newPounds, newRate) =>
          if (finite(newPounds) && finite(newRate) && newRate > 0.0 &&
              finite(newPounds * newRate)) {
            poundsValue = newPounds
            rateValue = newRate
          }
        }
        showValues()
      }
    }

    contents = new FlowPanel {
      contents += new Label("Pounds")
      contents += pounds
      contents += new Label("Euros")
      contents += euros
      contents += new Label("Euros per pound")
      contents += rate
    }
    listenTo(pounds, euros, rate)
    reactions += {
      case EditDone(source) if source eq pounds => commit(pounds)
      case EditDone(source) if source eq euros => commit(euros)
      case EditDone(source) if source eq rate => commit(rate)
    }
    showValues()
  }
}
The numeric state has the invariant and ; euros are derived instead of being stored independently. A proposal is validated before either stored value changes. The update flag prevents a synchronous programmatic display update from recursively committing another edit. Currency amounts display two decimal places, while the rate retains its parsed precision; display rounding is not repeatedly fed back into the numeric model. Locale.ROOT ensures that formatted decimal points match the input parser.
The code handles the EditDone events used by the paper rather than trying to parse every intermediate keystroke. It uses Scala 2 style and Java 8-or-newer numeric helpers. No Scala compiler or Swing runtime execution was available in the checking environment; the state transitions were checked independently, and the API usage was compared with the supplied contract and official Scala/Swing documentation.[ref]
A widget or model implementing Publisher is the subject. It calls publish(event) when an observable change occurs. An interested Reactor subscribes with listenTo(subject), and adds a partial function to reactions that handles the event types it understands. deafTo(subject) ends that subscription when it is no longer needed.
The connection is therefore made through publisher and reactor interfaces rather than through a hard-coded list of particular application classes. A reactor may observe several publishers and inspect an event's source to distinguish them. The implementation's registration machinery delivers published events to interested reactions; registering a reaction alone is not a substitute for subscribing to the source.[ref]
For the converter, the three text fields are publishers and the frame is a reactor. Register the three fields once, then handle their edit-completion events to update the stored numeric state and refresh the appropriate displayed values.
The observer pattern connects one event-producing subject to a changing set of interested consumers. Consumers register through an observation interface; when a relevant change occurs, the producer notifies them through that interface rather than naming every concrete consumer. Consumers can be added or removed without rewriting the producer's core behaviour.
This is useful for keeping displays, controls or other derived views synchronized with changing state. The design avoids tight coupling from the producer to all concrete dependants, which otherwise makes every new consumer require changes to the producer. Publishing after the producer's representation invariant has been restored also lets callbacks observe a coherent state. The pattern does not by itself prevent notification cycles or obsolete subscriptions; update policy and unregistration still matter.
Test-driven development uses a repeating sequence: write a small test for the next required behaviour, observe it fail for the expected reason, add enough implementation to make it pass, and refactor while keeping the tests passing. The initial failure checks that the test can actually detect the absent behaviour. This differs from writing a whole implementation first and only then constructing tests for it; it also uses the tests to guide interface and design decisions rather than only to inspect a finished program.[ref]
A mixture of test-selection styles is possible; the defining test-first step is normally behaviour-driven. Choosing inputs and expected results from a public contract is black-box testing with respect to the implementation, even if the developer writes the test. Knowing the internal branches can then motivate white-box tests for boundary paths or exceptional cases. TDD specifies the order of development activities, not a rule forbidding either source of test cases. It therefore does not guarantee branch coverage, and passing the growing test suite is not a proof of correctness for untested inputs.
Add a generic mapping method inside the supplied trait. Snapshot the finitely many source masses, and sum masses when different entries have the same image:
def map[U](f: T => U): FiniteDist[U] = {
  val entries = getDom.map(x => (f(x), getProb(x)))
  val support = entries.map(_._1).distinct

  new FiniteDist[U] {
    def getDom: List[U] = support
    def getProb(y: U): Double =
      entries.foldLeft(0.0) { case (sum, (image, mass)) =>
        if (image == y) sum + mass else sum
      }
  }
}
Here the mapping is a mathematical function, and keys are assumed to have stable equality consistent with their intended identity. Each source atom is evaluated once when the new distribution is constructed. The distinct image list is exactly the finite support because all listed source atoms have positive mass. Summing collisions, rather than overwriting a previous mass, implements the probability pushforward.
The sets of source atoms with a fixed image partition the original support. Hence nonnegativity is preserved and, in exact probability arithmetic,
Thus the result is a finite probability distribution. For a constant mapping, every atom merges into one outcome of mass one. Floating-point additions in the implementation can introduce rounding error, so numerical tests of normalization should use a suitable tolerance rather than demand exact equality of Double sums.

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