The iterator pattern exposes sequential traversal through a small interface while hiding the representation of the underlying data. A client asks whether another entry is available and requests the next entry; it need not know whether the producer uses an array, linked list, tree or generated sequence.
The key design benefit is encapsulation of traversal state and representation. The same consuming algorithm can work through the interface for different producers, and each traversal can keep its own cursor state when a fresh iterator is supplied. This independence requires separate consumption states; two references to one iterator share a cursor.
The two abstract methods areThe first reports availability; the second returns and consumes the next entry, or throws a
def hasNext: Boolean
def next(): TNoSuchElementException if none exists. Other standard iterator operations are supplied in terms of this interface. Repeated availability checks must not lose entries, although they may perform preparatory internal work.[ref]Scala 2.13 iterator API documentation. Iterator, abstract members hasNext and next; class-level mutation and reuse contract
Yes in special cases; an ordinary finite iterator that progresses through its input needs changing consumption state. For a genuine immutable counterexample, an iterator over an infinite constant sequence needs no changing fields:Removing the first entry of that sequence leaves the same sequence, so this satisfies the iterator behaviour without changing object state. A permanently empty iterator is another example.
final class Ones extends Iterator[Int] {
def hasNext: Boolean = true
def next(): Int = 1
}For a normal finite nonempty traversal, however, repeated
next() calls must eventually change the returned entry or availability, so the implementation needs mutable cursor state somewhere. Declaring only val fields is not a proof of deep immutability: those fields can refer to another mutable iterator, an array, or a stateful closure. The standard API's description of iterators as mutable captures the usual consuming case, rather than enforcing a mutable field in every possible implementation.Delay both initial skipping and every later skipped entry until a caller actually requests availability or an output:The state flag means that the next underlying entry, if present, must be skipped before the next selected entry can be exposed. It is initially false for odd positions and true for even positions. Returning a selected entry reinstates that obligation.
class HalfIterator[T](iter: Iterator[T], odd: Boolean)
extends Iterator[T] {
private var needSkip = !odd
def hasNext: Boolean = {
if (needSkip && iter.hasNext) {
iter.next()
needSkip = false
}
iter.hasNext
}
def next(): T = {
if (!hasNext)
throw new java.util.NoSuchElementException("empty half iterator")
val result = iter.next()
needSkip = true
result
}
}Construction does not call the underlying iterator at all. A successful availability check may discard the one required intervening entry, but does not fetch the selected entry. It then clears the flag, so repeated availability checks cannot skip again. To decide whether a second entry exists through this interface, consuming the preceding discarded entry is necessary. After
next() returns, it does not eagerly request the following skipped entry. This gives the intended laziness while retaining correct exhaustion behaviour, including an even-position iterator over a singleton input.Use short-circuit evaluation so that even an availability test of the second iterator is delayed until the first is exhausted:Each successful call returns from the first producer while it has entries, then from the second. There is no constructor-time request or element prefetch. This implements concatenation of the producers' remaining sequences, subject to their ordinary iterator contracts.
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 if (second.hasNext) second.next()
else throw new java.util.NoSuchElementException("empty concatenation")
}
}For the implementations above the value isThe first half-iterator returns the odd-position characters while consuming the even-position characters as its required skips. By the time it is exhausted, it has consumed the entire shared underlying iterator. The second half-iterator consequently has no entries left when concatenation reaches it. Sharing one source does not create two independent traversals. Neither constructor consumes anything, so it also does not shift the first output before iteration begins. The source's implementation references here should be read as parts (d) and (e); the printed reference to (c) and (d) is a cross-reference slip.
List('1', '3', '5', '7', '9') Articles by others on the same topic
There are currently no matching articles.