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.
The essential abstract methods are:
def hasNext: Boolean
def next(): T
hasNext 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]
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]
Use iterator concatenation and short-circuit the second availability test while the first iterator still has results:
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()
  }
}
The abstract remaining sequence is the remaining sequence of 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 expression constructs a valid iterator object; it does not itself return the concatenated numeric or character values. The element types have a common supertype 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
)
Successive calls return 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 one cached optional result. Only a request for availability or the next result fills that cache:
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")
    }
  }
}
This is a demand-driven filtering iterator. When the cache is empty, its abstract remaining sequence is the filtered remaining input. When it holds 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.
Make two separate character iterators so that scanning uppercase letters does not consume the lowercase pass:
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)
}
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 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.

Ancestors (10)

  1. Imperative programming
  2. 2019
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version