The design creates a separate concrete class in object-oriented programming for each selected platform combination. With independently selectable platforms, there are up to combinations. Adding a platform can therefore multiply the number of classes, even though each platform's send operation and per-message charge are simple independent behaviors.
Sending code and charges are duplicated across many classes; a changed charge must be updated consistently in every affected combination. A forgotten update can make billing and sending disagree. A customer's preferences are also tied to a concrete class, making recombination cumbersome. The repeated implementation has low modularity: it encodes a whole subset where a composition of independent capabilities would suffice. The Decorator pattern addresses exactly that structure.
The Memento pattern supports saving and later restoring an object's state while preserving encapsulation. The originator creates a snapshot and knows how to restore it; the memento stores that snapshot; the caretaker retains mementos and decides when to request restoration, without depending on their representation. Undo history is a typical use.
Scala's nested class in object-oriented programming definitions, access qualifiers, immutable values and path-dependent types help keep snapshots opaque and associated with their originator. For example:
final class Editor {
  private var text = ""
  final class Snapshot private[Editor] (
    private[Editor] val saved: String
  )
  def current: String = text
  def edit(next: String): Unit = { text = next }
  def save(): Snapshot = new Snapshot(text)
  def restore(s: Snapshot): Unit = { text = s.saved }
}

val editor = new Editor
editor.edit("first version")
val saved: editor.Snapshot = editor.save()
editor.edit("later version")
editor.restore(saved)
assert(editor.current == "first version")
The caretaker can retain saved but cannot inspect its private contents or construct an arbitrary snapshot. editor.Snapshot is a type tied to the stable editor value; a snapshot from a different Editor is not interchangeable without an explicit type escape. An immutable string is safe to share in this example. If the originator held mutable arrays or mutable nodes, storing only references to them would not freeze their contents; the memento would need a deep copy or a persistent immutable representation.[ref][ref]
A mixin is reusable behavior supplied by a trait and composed into a class in object-oriented programming. Scala allows only one direct superclass, so mixins allow several independently reusable capabilities without multiple concrete-class inheritance. A trait can provide implemented methods and require abstract members from its host class.
trait Named {
  def name: String
}
trait Greeting extends Named {
  def greeting: String = "Welcome, " + name
}
class Account(val name: String)
class WelcomedAccount(name: String) extends Account(name) with Greeting

val example = new WelcomedAccount("reader")
assert(example.greeting == "Welcome, reader")
Here the single superclass supplies name, and the mixin supplies the derived greeting. The same behavior can be mixed into another unrelated host that satisfies Named. Mixin composition uses a defined linearization and requires incompatible concrete member conflicts to be resolved; it does not make arbitrary combinations of concrete superclasses legal.[ref]
Method overloading gives one name several parameter signatures, such as show(A) and show(B). The compiler chooses an applicable signature using the receiver's static type and the argument expressions' static types, preferring a uniquely more specific applicable alternative. An argument whose type is a subtype of the parameter type is acceptable; ambiguous or inapplicable alternatives cause a compile-time error. The runtime type of an argument does not start a second overload search.
Method overriding replaces an inherited implementation of the same method signature. After overload selection, ordinary instance calls use dynamic dispatch on the receiver's runtime type to select the most-derived implementation of that signature. A concrete inherited method requires the override keyword in Scala; a super call invokes the corresponding superclass implementation instead of redispatching to the overriding body. In a trait stack, super follows the class's linearization.[ref][ref]
Insert a singleton mapping, retrieve a stored representative, or relabel every occurrence of the second block's old representative:
def makeSet(x: Int): Unit = {
  require(isInMap(x) == -1, "element already present")
  require(used < capacity, "capacity exhausted")
  elements(used) = x
  representatives(used) = x
  used += 1
}

def find(x: Int): Int = {
  val i = isInMap(x)
  require(i >= 0, "unknown element")
  representatives(i)
}

def union(x: Int, y: Int): Unit = {
  val keep = find(x)
  val replace = find(y)
  if (keep != replace) {
    var i = 0
    while (i < used) {
      if (representatives(i) == replace) representatives(i) = keep
      i += 1
    }
  }
}
For makeSet, the new key is absent, its representative is itself, and old mappings are unchanged. find is a read-only linear search. In union, snapshot both representatives before changing any cell: recomputing the representative of y during the scan could change the criterion halfway through. The loop invariant says that every processed index already has its specified final representative and every unprocessed index still has its old representative. The cached labels make this assertion stable.
At exit the abstract postcondition in part (a) holds. The surviving representative was already a fixed point and belongs to its old block; every member of the replaced block, including its old representative key, now maps to it. Thus idempotence and key uniqueness are preserved. Duplicate insertions, absent-element operations and capacity overflow fail before changing the map. Each operation is in the worst case, except that a same-block union can skip the relabel scan after its lookups. Storage is . These bounds follow from the chosen parallel-array quick-find representation; no parent-pointer optimization is being assumed.
Return the key's active array index, or -1 if absent:
private def isInMap(x: Int): Int = {
  var i = 0
  while (i < used && elements(i) != x) i += 1
  if (i < used) i else -1
}
The loop invariant states that every index below i has a key different from x. The scan ignores all inactive cells, and short-circuit evaluation protects the array access at the end of the active prefix. Key uniqueness makes a successful index unambiguous. Its running time is .
  • Both arrays have length capacity, with and .
  • The active keys elements(0 until used) are pairwise distinct.
  • For each active index , representatives(k) equals some active key elements(j).
  • Every such representative is fixed: if representatives(k) == elements(j), then representatives(j) == elements(j).
The abstraction function is
The last two conditions ensure each representative is a genuine member of its own block and that the abstract function is idempotent function. Cells beyond used are unconstrained and ignored. When used == 0, these conditions hold vacuously and the abstraction function yields the empty map. This is an explicit-key version of quick-find, rather than a parent-pointer disjoint-set forest.
Use parallel arrays for keys and their representative values, with only a prefix active:
override val capacity: Int = 1000
private val elements = new Array[Int](capacity)
private val representatives = new Array[Int](capacity)
private var used = 0
The chosen bound is an explicit implementation parameter of the abstract data type; another a-priori positive bound works identically. The initial map is empty because used == 0. Zero-filled unused cells are not members of the map, so zero and negative keys remain valid integers. Use DisjointSets consistently as the trait name; the source's prose variation DisjointSubsets does not change the declared interface.
Choose a fixed positive capacity and represent the abstract state by a finite partial function . Its domain of a partial function has at most members; each belongs to and is a fixed point:
The blocks of a set partition are the nonempty fibres of rep, and their shared values are their disjoint-set representatives. Initially , so . Representatives need not be the minimum members of their blocks.
trait DisjointSets {
  val capacity: Int
  // State: rep is a finite idempotent map, |dom rep| <= capacity.
  // Initially: rep is empty; capacity is fixed and positive.

  // Pre: x is absent and |dom rep| < capacity.
  // Post: add x -> x; leave every old mapping unchanged.
  def makeSet(x: Int): Unit

  // Pre: x belongs to dom rep.
  // Post: state unchanged; return rep(x).
  def find(x: Int): Int

  // Pre: x and y belong to dom rep.
  // Post: merge their blocks, retaining old rep(x).
  def union(x: Int, y: Int): Unit
}
Precisely, makeSet(x) extends the domain of a partial function by with . For union(x,y), snapshot and , keep unchanged, and set
This merges the two blocks and keeps the representative of the first argument's block. If , it is an identity operation. This deterministic design choice satisfies disjoint set union without imposing minimum-element representatives. The capacity bound is explicit in the abstract data type so that the bounded implementation does not silently strengthen makeSet's precondition.
Update an existing node, otherwise append one fresh node while preserving the cycle:
def store(name: String, number: String): Unit = {
  val p = find(name)
  if (p != null) p.number = number
  else {
    val fresh = new Node(name, number, null)
    if (last == null) {
      fresh.next = fresh
      last = fresh
    } else {
      fresh.next = last.next
      last.next = fresh
      last = fresh
    }
  }
}
For an existing name, changing only its number realizes replacement in the abstract partial function. On an empty book, the new node points to itself, establishing a singleton cycle. On a nonempty book, its successor becomes the old first node and the old last points to it; advancing last leaves the first node unchanged and closes the enlarged cycle. Since a full search established absence, name uniqueness is preserved. Thus the postcondition is exactly the old book with this name mapped to the supplied number, and all other entries unchanged. A store takes running time for the name search and additional pointer work.
Starting at last.next, visit each node once and stop when the traversal would return to its start. This helper is private so that callers do not receive writable nodes from the representation.
private def find(name: String): Node = {
  if (last == null) return null
  val first = last.next
  var p = first
  do {
    if (p.name == name) return p
    p = p.next
  } while (p ne first)
  null
}
Null means no entry has that name. The test p ne first compares object identity, not the equality of name or number fields. At each iteration all previously visited nodes failed the name test. The finite simple cycle guarantees that either a match is found or the traversal returns to first after exactly one turn. A singleton cycle is inspected exactly once. Stopping at null instead would fail to terminate on this representation.
Use a non-dummy circular linked list with a pointer to its last node:
private var last: Node = null
Null represents the empty book. In a nonempty book, last.next is the first node, and following next makes one finite simple cycle containing last. Names are unique around that cycle. This representation makes appending a new entry constant-time once a failed name search has established absence. The abstraction function collects every name/number pair on one complete turn of the cycle, rather than following pointers until null.
Save the next pointer before redirecting it, then advance the two working heads. No node is allocated and the name/number fields are untouched.
def reverseBook(): Unit = {
  var prev: Node = null
  var cur = list
  while (cur != null) {
    val following = cur.next
    cur.next = prev
    prev = cur
    cur = following
  }
  list = prev
}
Let be the original sequence of node identities, not just their possibly equal field values. Write for the sequence currently headed by prev and for that headed by cur. A suitable loop invariant for in-place linked-list reversal is
with both working lists finite, acyclic, disjoint, together containing exactly the original nodes, and with every name and number unchanged. Here ++ means concatenation. Initially and . One iteration takes from the front of and replaces by . Since , the equation is preserved. Saving following before changing cur.next retains access to .
The loop variant is the length of , decreasing by one. At exit , so ; assigning the head establishes reversal. The empty and singleton cases work without a special branch. The abstraction function of the phone book ignores order, so it still maps every original name to its original number. All original node identities are reused, with running time and auxiliary space.
Figure 1.
In-place reversal preserves node identities while moving nodes from an untouched suffix into a reversed prefix
. Details.
Inside LinkedListBook, traverse without modifying the head or any node:
def printBook(): Unit = {
  var p = list
  while (p != null) {
    println(p.name + ":" + p.number)
    p = p.next
  }
}
The loop invariant is that precisely the prefix before p has been printed, once per node, in list order; p heads the remaining suffix. The null-terminated linked list invariant proves termination and prevents duplicate output through cycles. An empty list prints nothing. The abstraction function is unchanged, and the traversal takes node visits for entries.

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