Make two separate character iterators so that scanning uppercase letters does not consume the lowercase pass:Each filtering iterator preserves the original order of its selected characters. Concatenation therefore yields all uppercase letters in source order, then all lowercase letters in source order, omitting other characters. The two
def upperLower(s: String): Iterator[Char] = {
val upper = new FilterIterator[Char]((c: Char) => c.isUpper, s.iterator)
val lower = new FilterIterator[Char]((c: Char) => c.isLower, s.iterator)
new ConcatIterator[Char](upper, lower)
}s.iterator calls are essential: reusing a single consuming iterator would let the first pass discard lowercase characters before the second pass could return them. Construction remains lazy; an empty string yields an exhausted iterator without a special case.Use one cached optional result. Only a request for availability or the next result fills that cache:This is a demand-driven filtering iterator. When the cache is empty, its abstract remaining sequence is the filtered remaining input. When it holds
class FilterIterator[T](test: T => Boolean, iter: Iterator[T])
extends Iterator[T] {
private var cached: Option[T] = None
private def prepare(): Unit = {
while (cached.isEmpty && iter.hasNext) {
val x = iter.next()
if (test(x)) cached = Some(x)
}
}
def hasNext: Boolean = {
prepare()
cached.nonEmpty
}
def next(): T = {
prepare()
cached match {
case Some(x) =>
cached = None
x
case None => throw new NoSuchElementException("Filtered iterator exhausted")
}
}
}Some(x), the abstract sequence is x followed by the filtered remaining input. The loop invariant for prepare says that all input elements consumed during the present search have failed test, except for the one cached passing value if one has been found. The first passing value stops the loop, so it cannot read past a result that the client has not yet consumed.Construction performs no underlying reads, and repeated
hasNext calls reuse a cached result. next also works without a preceding hasNext, clears only the result it returns, and does not prefetch its successor. Some(x), rather than Option(x), allows a passing null value to remain a genuine cached value. For finite remaining input, its length is a loop variant; for infinite input, availability can legitimately run forever if no further passing element exists. Deterministic terminating tests and exclusive ownership of the consuming input are assumed. One cache slot is extra storage.The expression constructs a valid iterator object; it does not itself return the concatenated numeric or character values. The element types have a common supertype Successive calls return
AnyVal, and covariance lets Iterator[Int] and Iterator[Char] serve as the two inputs to ConcatIterator[AnyVal]. In the ordinary Scala 2 typing of this expression, the common element type is AnyVal. One can make the intended widening explicit:new ConcatIterator[AnyVal](
List(1, 2, 3).iterator,
List('a', 'b', 'c').iterator
)1, 2, 3, 'a', 'b', 'c', then exhaustion. Characters remain characters: viewing an existing iterator at a wider type does not convert its contents to integer character codes. No next() is invoked merely by constructing this adapter. The common-type argument uses subtype polymorphism and covariant type parameters, rather than requiring the two concrete input types to be equal.Use iterator concatenation and short-circuit the second availability test while the first iterator still has results:The abstract remaining sequence is the remaining sequence of
class ConcatIterator[T](first: Iterator[T], second: Iterator[T])
extends Iterator[T] {
def hasNext: Boolean = first.hasNext || second.hasNext
def next(): T = {
if (first.hasNext) first.next()
else second.next()
}
}first followed by that of second. Each next() consumes the head of precisely this sequence. When both are exhausted, delegation to second.next() raises the required exception. Construction consumes no elements, and hasNext never calls either underlying next(). As usual, clients should not separately consume these iterators while relying on the adapter's traversal. Sharing one underlying iterator between both arguments also shares its state; it does not duplicate its elements.The plus marks a covariant type parameter: if , then
Iterator[S] <: Iterator[T]. An iterator producing a subtype's values can be used where an iterator of the supertype is required. For example, a string iterator can be viewed as an iterator of AnyRef, because strings are reference values. The direction is appropriate for a producer: calling next() gives a value valid at the wider type. It would not be safe to expose an ordinary insertion method accepting arbitrary wider-type values into a subtype-only collection. This is a subtyping relationship, not a request to transform each produced value.[ref]Scala 2.12 types specification. Conformance of parameterized types with covariant parameters
The essential abstract methods are:
def hasNext: Boolean
def next(): ThasNext reports whether another result is available. next() returns that result and advances; if exhausted, it throws NoSuchElementException. The other ordinary iterator operations are implemented using these primitives. An availability check must not silently discard a result visible to the client, although an adapter may need to fetch and cache underlying values in order to decide availability.[ref]Scala 2.12 iterator API documentation. Iterator abstract members hasNext and next; exhaustion contract
The Iterator pattern gives clients a uniform way to inspect and consume the elements of a collection without exposing how that collection is stored. An iterator has a traversal state separate from the abstract collection interface, so the same client loop can process an array, a linked list or generated values. It preserves encapsulation and representation independence: changing the underlying data structure need not change the traversal client. Separate iterator instances can track separate traversals; two aliases of one consuming iterator instead share its progress.
Insert before the first entry that is at least the new value; equal values remain separate occurrences:In the scanning branch, the loop invariant says that
class ListPriorityQueue extends PriorityQueue[Int] {
private var first: Node = null
def clear(): Unit = { first = null }
def isEmpty(): Boolean = first == null
def insert(x: Int): Unit = {
if (first == null || x <= first.value) {
first = new Node(x, first)
} else {
var p = first
while (p.next != null && p.next.value < x) {
p = p.next
}
p.next = new Node(x, p.next)
}
}
def delMin(): Int = {
require(first != null, "Empty priority queue")
val result = first.value
first = first.next
result
}
}p is reachable and all values from first through p are strictly smaller than x. The rest of the chain is unchanged and remains sorted. The loop variant is the number of nodes after p. At exit either the next value is at least x or there is no next node, so inserting between p and p.next preserves the representation invariant and adds exactly one occurrence under the abstraction function. The head branch covers an empty chain, a new minimum and equality with the old minimum. delMin returns the head's minimum value and removes exactly that occurrence.Insertion is worst-case;
delMin, isEmpty and the head-resetting clear are . Reclaiming an abandoned chain later is garbage-collection work, not an explicit traversal performed by clear. Storage is , including separate nodes for duplicate values. No fixed insertion-capacity precondition has been added.Use one real linked list node per occurrence, with a private reference to the first:The representation invariant says that the reachable chain is finite, acyclic and nondecreasing in
class Node(val value: Int, var next: Node)
// Inside the queue implementation:
private var first: Node = nullvalue, and is owned by the queue. Equal adjacent values are explicitly allowed. The abstraction function is the multiset containing one occurrence of v.value for every reachable real linked list node v. Initially first==null represents the empty multiset. No artificial smallest Int is needed as a sentinel, and Int.MinValue remains a valid real value.The abstract state is a finite multiset of ordered values, initially empty. Multiplicity matters: deleting the minimum removes one occurrence, not every equal occurrence. Assume a consistent total order on This abstract data type places no fixed-capacity bound on insertion. The only operation requiring a nonempty collection is
T.trait PriorityQueue[T] {
// Pre: true. Post: Q' is the empty multiset.
def clear(): Unit
// Pre: true. Post: Q' = Q with one additional occurrence of x.
def insert(x: T): Unit
// Pre: Q is nonempty.
// Post: result is a minimum of Q;
// Q' is Q with exactly one occurrence of result removed.
def delMin(): T
// Pre: true. Post: result iff Q is empty, and Q' = Q.
def isEmpty(): Boolean
}delMin. The representation must preserve duplicates even if it uses a data structure commonly associated with sets.Give each solving session a shared visited set keyed by immutable snapshots of permutation contents, for example
game.toList, and insert the initial snapshot immediately. Have all successor objects refer to that same session's set. The refined flip first constructs the candidate state; if its key is present, return None. Otherwise add the key immediately and return Some(candidate). The search enqueues only Some results. Keys must compare contents rather than array identities, and a fresh solving session must start with a fresh visited set.Marking at generation time prevents the same state from being queued repeatedly, including the immediate cycle made by applying the same reversal twice. First discovery in breadth-first search already has minimum depth, so discarding later discoveries cannot remove a shorter solution. The graph now has at most admitted states. If only cycles along one path were to be rejected, a path-local set would suffice, but it would still repeat states reached by different paths; the shared session-wide set avoids both kinds of repetition. Public game fields must not be externally mutated while their states are being searched.
Use breadth-first search with the supplied FIFO queue, taking one edge to mean one permitted prefix reversal:The FIFO queue holds pending paths in nondecreasing history length. Initially it holds only the zero-move path. Removing a path at depth and appending its children at depth preserves that order. The inner loop invariant says that precisely moves of the removed state have been appended; its loop variant is while the guard holds. The first identity state removed therefore has the minimum possible number of moves. A stack-based depth-first search does not generally have that property.
def solve(puzzle: Flip): Flip = {
val pending = scala.collection.mutable.Queue[Flip]()
pending.enqueue(puzzle)
while (!pending.isEmpty) {
val current = pending.dequeue()
if (current.isIdentity) return current
var k = 2L
while (k <= current.game.length.toLong) {
pending.enqueue(current.flip(k.toInt))
k += 1L
}
}
throw new IllegalStateException("No solution")
}
val puzzle = new Flip(n)
println("Solving:")
println(puzzle)
val answer = solve(puzzle)
println("Solved:")
println(answer)Termination does not rely on avoiding repeats in this first version. Every permutation can be sorted by prefix reversal sorting: place the largest misplaced value at the front if necessary, flip it into its final position, and repeat on the shorter prefix. This constructs a route of at most moves. Each search depth has finitely many paths, with at most children per path, so breadth-first search reaches some solution depth after finitely many expansions. This gives a finite bound on remaining expansions before the first solution even though the repeated-state path tree is infinite. The one-element game is already solved. Repeated paths can nevertheless make time and storage enormous; part (e) removes that waste.
The history is built by prepending, so reverse it when displaying chronological moves:Thus a reverse-stored history
override def toString: String =
game.mkString("[", ", ", "]") +
" history of flips: " + flips.reverse.toString[3,2,4] is displayed as List(4, 2, 3). The initial empty history remains List(). Neither traversal mutates the game or the immutable history. Displaying the stored list without reversing it would describe the moves backwards.Allocate a distinct game and copy every destination entry from the corresponding source position:The loop invariant says that the receiver is unchanged and destination positions before
def flip(k: Int): Flip = {
require(1 < k && k <= game.length)
val result = new Flip(game.length)
var i = 0
while (i < game.length) {
val source = if (i < k) k - 1 - i else i
result.game(i) = game(source)
i += 1
}
result.flips = k :: flips
result
}i equal the reversal of the first source entries followed by the untouched suffix. The loop variant is . At exit the copying is complete. Reversal is a bijection on positions, so the destination remains a permutation. The returned object's array is independent of the receiver's array, while the immutable tail of its history list can safely be shared. The source's only supplied constructor randomizes the new array before the copy; that work is redundant but does not affect correctness. An additional private constructor could avoid it without changing the required result.Check entries against their own indices, stopping on the first mismatch:The loop invariant is and for every . The loop variant is . A false guard means either every position has passed or the next position is wrong, so the returned Boolean is true exactly for the identity permutation. Neither the game nor its history is changed. Short-circuit evaluation protects the final indexed comparison.
def isIdentity: Boolean = {
var i = 0
while (i < game.length && game(i) == i) {
i += 1
}
i == game.length
} There are unlisted articles, also show them or only show them.