Represent the characteristic values of a bounded universe by one Boolean slot per possible member, a Boolean-array form of a bitset:
class BitMapSet(val MAXVALUE: Int) extends IntSet {
  require(MAXVALUE >= 0)
  private val bits = Array.fill(MAXVALUE)(false)
  private var count = 0

  def contains(elem: Int): Boolean =
    0 <= elem && elem < MAXVALUE && bits(elem)

  def add(elem: Int): Boolean = {
    require(0 <= elem && elem < MAXVALUE, "Outside bitmap universe")
    if (bits(elem)) false
    else {
      bits(elem) = true
      count += 1
      true
    }
  }

  def size: Int = count
}
The abstraction function is . The representation invariant is that bits.length==MAXVALUE, its entries are Boolean, and count equals the number of true entries. Initialization gives the empty set; changing a false entry to true adds exactly its index and increments the count once. A repeated addition preserves both. All three operations have time complexity after initialization; storage and explicit array initialization are .
The constructor requires , and add requires . contains remains total by returning false outside the representable universe; short-circuit evaluation protects the index. This finite representation cannot implement unrestricted addition of every Int while preserving the abstract contract. Its strengthened add precondition therefore makes it a restricted implementation, not a behaviorally substitutable implementation of the unrestricted trait for arbitrary clients. The sequence client below proves that it stays within the restricted universe.
Let denote the entry state. A conventional meaning for the Boolean returned by add is whether the call changes the set:
// add(elem):
//   S' = S0 union {elem}
//   result == !S0.contains(elem)

// contains(elem):
//   S' = S0
//   result == S0.contains(elem)

// size:
//   S' = S0
//   result == cardinality(S0)
Initially . In particular, re-adding an existing element returns false and does not increase the size. All operations have the stated empty precondition at the abstract level. The comment that add adds an element does not itself completely specify its Boolean result; the explicit changed/not-changed convention above completes that contract. As with any Int-valued size operation, exact cardinalities are understood to be representable by that result type.
Test singleton and two-element segments, first/last/interior requested ranks, nonzero segment offsets, already sorted and reversed inputs, random inputs, all-equal inputs and several patterns of duplicates. Include Int.MinValue and Int.MaxValue to expose overflow-prone comparisons. An independent sorted copy supplies the value oracle; also check preservation of the segment's multiset and of all outside entries. For speed tests, increase segment size and include deliberately unfavorable pivot arrangements, rather than timing random inputs alone.
Distinct entries do not guarantee linear worst-case time: the worst case is . A median of three can repeatedly be the second-smallest remaining value, leaving a segment of size when seeking its maximum. The quadratic median-of-three selection family gives explicit distinct inputs realizing this behavior for the implementation above; one six-entry member is . Its recurrence is , yielding a quadratic sum. Balanced reductions instead give . Randomized or suitable average-case analyses give expected linear selection, but this deterministic heuristic alone supplies no such worst-case guarantee. Unlike Quicksort, Quickselect explores only one side, so a balanced run is linear rather than .
Replace the tail call by updates to local bounds and a local rank:
def selectIterative(k: Int, l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  require(0 <= k && k < r - l)
  var low = l
  var high = r
  var rank = k
  while (high - low > 1) {
    val p = partition(low, high)
    val pivotRank = p - low
    if (rank == pivotRank) return a(p)
    if (rank < pivotRank) high = p
    else {
      rank -= pivotRank + 1
      low = p + 1
    }
  }
  a(low)
}
The loop invariant says that , , and selecting rank rank in the active segment yields the originally requested order statistic. The original segment's multiset is preserved, and outside it no entries change. The updates are exactly the recursive reductions proved in part (c). The loop variant is ; a non-returning iteration strictly decreases it. A one-entry segment has only rank zero, establishing the final return. Auxiliary space is , rather than a potentially deep call stack.
Ranks are relative to the current segment. The pivot's rank is p-l, not its absolute index:
def select(k: Int, l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  require(0 <= k && k < r - l)
  if (r - l == 1) a(l)
  else {
    val p = partition(l, r)
    val rank = p - l
    if (k == rank) a(p)
    else if (k < rank) select(k, l, p)
    else select(k - rank - 1, p + 1, r)
  }
}
The array partitioning places exactly rank strictly smaller entries before the pivot, with all later entries at least the pivot. Thus the pivot is the element of sorted rank rank, even when equal values occur later. A requested earlier rank is unchanged in the left segment; a later rank loses the low entries and the pivot, accounting for the subtraction rank+1. The recursive segment is nonempty in either branch that takes it, and its length strictly decreases. Induction on segment length therefore proves the returned value is the requested order statistic, with at most one recursive call. Only the selected segment is permuted; all outside entries remain unchanged. This is Quickselect.
Set aside the selected pivot at the end, array partitioning the other entries, then move the pivot to the separation index:
def partition(l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  def swap(i: Int, j: Int): Unit = {
    val t = a(i); a(i) = a(j); a(j) = t
  }
  val chosen = bestIndex(l, r)
  val x = a(chosen)
  swap(chosen, r - 1)
  var p = l
  var j = l
  while (j < r - 1) {
    if (a(j) < x) {
      swap(p, j)
      p += 1
    }
    j += 1
  }
  swap(p, r - 1)
  p
}
The loop invariant is , , , and . The segment's multiset is unchanged and all entries outside it are unchanged. A low entry is swapped into the low segment; a high entry simply extends the high segment. The loop variant is . At exit, exchanging the reserved pivot with a(p) gives , , and . The displaced value at the old pivot position was already at least . Length one is handled by self-swaps and an empty loop. Duplicate pivot values belong to the high side. This costs time and auxiliary space.
Compare values directly, avoiding subtraction that could overflow:
def bestIndex(l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  val first = l
  val middle = l + (r - l) / 2
  val last = r - 1
  if (a(first) <= a(middle)) {
    if (a(middle) <= a(last)) middle
    else if (a(first) <= a(last)) last
    else first
  } else {
    if (a(first) <= a(last)) first
    else if (a(middle) <= a(last)) last
    else middle
  }
}
Each branch returns an index whose value lies between the other two sampled values. Non-strict comparisons make ties harmless. The precondition is a nonempty valid segment, not a segment of at least three elements: for lengths one or two some sample indices coincide, but the code still returns a valid median of the sampled triple. This matters because selection can reach a two-element segment. With three distinct sample values, the pivot is not the minimum or maximum of the whole segment, but it need not be near the segment's true median. Median-of-three pivot selection is a heuristic, not a balance guarantee.
The first proposed identity can fail even without numerical error because binary fractions have nonunique textual representations. Leading zeroes, optional points and trailing fractional zeroes are normalized differently by a fixed-width output convention. It also fails if the input has more significant bits than Double can preserve, more fractional places than the output buffer can hold, an integer part outside the assumed Int range, or a value that overflows or underflows during decoding. Array identity here must mean equal contents: a newly allocated Scala array is a different software object, so use sameElements rather than reference equality for a content test.
The second identity fails when the stored fractional precision truncates a nonzero bit; with two fractional places, becomes zero. It can also fail outside the finite nonnegative input and integer-conversion assumptions. Within those assumptions, enough fractional positions to encode the finite Double exactly can permit the round trip, but an arbitrary fixed small width does not guarantee it. Every finite Double has a finite binary expansion; saying that a decimal-looking Double necessarily has an infinite binary expansion would confuse the represented number with an exact decimal real.
The source's introductory example is internally inconsistent: the displayed digit string has value , whereas its shortened character array encodes . The conversion rules above follow the actual input digits. Round-trip testing needs an independent value oracle as well as the two compositions, because two mutually consistent but incorrect routines can conceal each other's errors.
Equivalence partitioning divides the input domain into classes expected to exercise the same relevant behavior, then chooses representatives and boundary cases from each class. It is a way to select tests, not a proof that every member of a class must behave identically in a faulty implementation.
Useful classes for this parser include integer-only inputs, a leading point, a trailing point, and digits on both sides; all-zero inputs and inputs containing ones; leading or trailing zeroes; one-digit and longer blocks; and large integer or tiny fractional magnitudes near floating-point rounding, floating-point overflow and floating-point underflow boundaries. For instance, compare '1', '1.', '.1', '1.1', '0001.1000', and digit strings just beyond the exact integer precision of Double. Empty digit blocks have the zero convention used above. If a surrounding validator rejects an entirely empty representation or a bare point, test those as separate invalid-format classes. Unexpected digits and multiple points are likewise validator tests, since the conversion fragments assume well-formed input. Include representatives with independently calculated positional values, rather than relying only on inverse conversion.
Generate the fractional bits by repeated doubling, keeping only the unconverted residual:
res(digits) = '.'
var fraction = dec - int_part.toDouble
var out = digits + 1
while (out < res.length) {
  fraction = 2.0 * fraction
  if (fraction >= 1.0) {
    res(out) = '1'
    fraction -= 1.0
  } else res(out) = '0'
  out += 1
}
Let and . The loop invariant is , the first fractional digits have been written, and, in exact arithmetic,
Doubling exposes the next digit, and subtracting that digit leaves the next residual in . This proves preservation. The loop variant is . The loop fills the whole suffix, even when the residual has become zero; subsequent bits are zero. There is one multiplication per output bit. With fractional positions, the result is truncated, with exact-arithmetic error . An integer has an all-zero suffix. No rounding-up step is performed.
Extract low bits and fill the integer positions from right to left:
var remaining = int_part
var pos = digits - 1
while (pos >= 0) {
  res(pos) = if ((remaining & 1) == 0) '0' else '1'
  remaining = remaining >>> 1
  pos -= 1
}
At the start of an iteration, the loop invariant says that positions contain the correct low bits and
The bitwise AND extracts the remainder modulo two; the shift supplies its quotient. These two facts preserve the loop invariant. The loop variant is . The width established in part (c) ensures that remaining is zero at exit, so the first digits entries encode the whole integer part. For zero the single entry becomes '0'. There are no explicit multiplications or divisions, and no extra digit array is needed.
Represent zero by one digit. Since int_part is nonnegative, a logical right shift is exactly integer division by two:
var digits = 1
var scratch = int_part
while (scratch >= 2) {
  scratch = scratch >>> 1
  digits += 1
}
The loop invariant is and ; for positive int_part, also . The loop variant is scratch, strictly decreased whenever the guard holds. On exit, a positive input has , yielding . Therefore digits is the required width, including width one for zero. Shifting avoids an explicit multiplication or division in the code. This uses the supplied assumption that dec.toInt really is the mathematical floor; saturating or invalid conversions are not covered by that assumption.
Let point be the known point index. Work backwards so that each step uses just one division, rather than separately computing positional weights:
var j = bin.length - 1
var fractionalPart = 0.0
while (j > point) {
  fractionalPart = (fractionalPart + (bin(j) - '0')) / 2.0
  j -= 1
}
The loop invariant, under exact arithmetic, is
Initially the suffix is empty. Incorporating digit and dividing by two gives exactly the same formula with replaced by . At exit , the result is . The loop variant is when a point exists. If a no-point input is handled by setting point=bin.length, the loop is skipped and the fractional contribution is zero; is a loop variant covering that convention too. Trailing zeroes and an empty fractional suffix require no special arithmetic. Floating-point rounding qualifies the exact formula for long inputs.
Accumulate the prefix by Horner's method in base two. digit-'0' converts either permitted digit to its numerical value:
var i = 0
var integerPart = 0.0
while (i < bin.length && bin(i) != '.') {
  integerPart = 2.0 * integerPart + (bin(i) - '0')
  i += 1
}
The loop invariant, in exact arithmetic, is that i is the number of processed digits before the point and
Appending a digit shifts the old positional value by one binary place and adds that digit, which proves preservation. The loop variant is . At exit, i is the binary-point index or the length if no point occurs, and integerPart is the value of the integer prefix. An empty prefix contributes zero. There is one multiplication per processed digit, with no separate powers or repeated divisions. Short-circuit evaluation prevents an out-of-range access when the point is absent.
For Double, this exact-arithmetic invariant describes the intended value; the operational value is the rounded Horner recurrence. Very long prefixes can lose precision or overflow, as discussed in part (g). A fixed-width return type cannot represent every finite binary digit string exactly.
Let the committed model be amounts and an exchange rate , with invariant . Editing pounds keeps the rate and computes euros; editing euros keeps the rate and computes pounds; editing the rate keeps pounds and computes euros. A usable rate must be strictly positive, and every accepted floating-point number and derived result must be finite. Negative amounts are allowed. Rejecting invalid text preserves the last committed model.
Insert the following members inside the supplied MainFrame, after the three fields have been initialized. Its existing layout can remain as written:
private var p = 10.0
private var e = 11.5
private var r = 1.15
private var refreshing = false

private def finite(x: Double): Boolean = !x.isNaN && !x.isInfinity

private def showModel(): Unit = {
  refreshing = true
  try {
    pounds.text = java.lang.String.format(java.util.Locale.ROOT, "%.2f", Double.box(p))
    euros.text = java.lang.String.format(java.util.Locale.ROOT, "%.2f", Double.box(e))
    rate.text = r.toString
  } finally {
    refreshing = false
  }
}

private def edit(source: TextField): Unit = {
  try {
    val v = source.text.trim.toDouble
    if (finite(v)) {
      var nextP = p
      var nextE = e
      var nextR = r
      if (source eq pounds) {
        nextP = v
        nextE = v * r
      } else if (source eq euros) {
        nextE = v
        nextP = v / r
      } else if (source eq rate) {
        nextR = v
        nextE = p * v
      }
      if (nextR > 0.0 && finite(nextP) && finite(nextE) && finite(nextR)) {
        p = nextP
        e = nextE
        r = nextR
      }
    }
  } catch {
    case _: NumberFormatException => ()
  }
  showModel()
}

listenTo(pounds, euros, rate)
reactions += {
  case EditDone(source) if !refreshing => edit(source)
}
The invariant is interpreted with the usual floating-point rounding in multiplication and division. All candidate values are calculated before committing any of them, so invalid text, zero/negative rates, NaN, infinity and floating-point overflow leave the old model intact. The committed r remains positive, so euro-to-pound division is defined. Using a fixed formatting locale keeps the decimal separator compatible with toDouble. The displayed amounts are rounded to two decimal places, while the model retains their full available precision. The rate is not forcibly rounded to two places, which could otherwise turn a valid small positive rate into displayed zero.
The refreshing guard prevents synchronous derived-field notifications from recursively committing another edit. EditDone is an edit-completion event, not a request to react to every partial keystroke; pressing the field's completion action is enough to trigger the conversion. If a particular UI additionally needs live updates, it can subscribe to the appropriate text-change events with the same validation and authoritative-source policy. The supplied API and archived Scala Swing documentation suffice for the requested completion-event implementation; no unidentified practical library is required.[ref]
In Scala Swing, a Publisher is the observable subject and a Reactor supplies an observer's reactions. A reactor calls listenTo(pounds, euros, rate) to subscribe to the relevant publishing components. It adds a partial function from events to actions with reactions += { case ... => ... }; unmatched event types need no action. When a publisher calls publish(e), subscribed reactions that handle that event are notified. Calling deafTo removes subscriptions that are no longer wanted.[ref]
The publisher does not need to know the concrete frame or its currency-conversion code. A TextField supplies the relevant editing events, and the frame's reaction distinguishes the source field using EditDone(source). Both registration and a matching reaction are needed: installing a case handler without subscribing does not establish the notification path. The observer logic should update the conversion model once and then refresh the other fields from that coherent state.

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