Keep a buffered first match and a flag recording whether the initial prefix still needs to be skipped:
class DropUntil[T] private (
p: T => Boolean,
iter: Iter[T],
private var cached: Option[T],
private var seeking: Boolean) extends Iter[T] {
def this(p: T => Boolean, iter: Iter[T]) =
this(p, iter, None, true)
private def prepare(): Unit = {
if (seeking) {
while (cached.isEmpty && iter.hasNext) {
val x = iter.next()
if (p(x)) cached = Some(x)
}
seeking = false
}
}
def hasNext: Boolean = {
prepare()
cached.nonEmpty || iter.hasNext
}
def next(): T = {
prepare()
cached match {
case Some(x) => cached = None; x
case None =>
if (!iter.hasNext) throw new NoSuchElementException("DropUntil.next")
iter.next()
}
}
def copy(): Iter[T] = {
prepare()
new DropUntil[T](p, iter.copy(), cached, false)
}
}While seeking,
prepare drops exactly the rejected prefix and caches the first accepted value, including a possible null payload as Some(null). Afterwards the abstract remainder is the cache, if any, followed by the underlying remainder; later values are returned even when they fail p. Repeated hasNext calls do not lose the cached value.The iterator snapshot copies the underlying cursor and the cached value, then marks the initial search complete. It does not reconstruct a fresh two-argument
DropUntil, which could incorrectly discard later values. Resolving the initial search before copying also avoids having two snapshots independently rerun a privately stateful predicate. The wrapper owns consumption of the supplied source cursor. If that source is infinite and never produces an accepted value, seeking cannot finish. This is a prefix-dropping iterator, rather than a repeatedly demand-driven filtering iterator.These methods consume the receiver's remaining sequence;
exists stops as soon as it finds a witness:trait RichIter[T] extends Iter[T] {
def foreach(f: T => Unit): Unit = {
while (hasNext) f(next())
}
def exists(p: T => Boolean): Boolean = {
while (hasNext) {
if (p(next())) return true
}
false
}
def foldLeft[U](x: U)(f: (U,T) => U): U = {
var result = x
while (hasNext) result = f(result, next())
result
}
}After consumed elements,
foreach has invoked its callback on exactly that prefix, exists has found no witness in it unless it has already returned, and the left fold accumulator is the fold of that prefix in its original order. These loop invariants prove the finite-sequence results. On an infinite sequence, exists may still terminate when it reaches a witness; a full traversal or fold generally does not. To retain the original cursor, a caller can invoke the operation on a suitable copy.import scala.collection.immutable.Stream
class FunIter[T] private (
private var rest: Stream[T]) extends Iter[T] {
def this(v: T, f: T => T) = this(Stream.iterate(v)(f))
def hasNext: Boolean = true
def next(): T = {
val result = rest.head
rest = rest.tail
result
}
def copy(): Iter[T] = new FunIter[T](rest)
}For a total step function, the stream is infinite and its values are . At every call,
rest starts with the next unconsumed value. Copying that reference gives a new cursor at exactly the same position; later cursor assignments are independent.The memoized iterator snapshot is useful for the next part: if
f owns private mutable state, advancing either cursor realizes a previously unknown tail only once, and both copies can then read the same cached values. Merely constructing new FunIter(current, f) would share the mutable closure while generating two independent futures, which could diverge. Memoization instead makes the generated sequence shared and the consumption positions independent. The closure must not be mutated externally, and generic element payloads are shared rather than deep-copied. Retaining an old cursor can retain cached cells.[ref]Scala 2.12 Stream API documentation. Opening memoization example and notes on retained heads
Give the step function one private previous-value cell, freshly allocated for each independent Fibonacci generator:
def fibonacci(): Iter[BigInt] = {
var previous = BigInt(1)
val step: BigInt => BigInt = { current =>
val following = previous + current
previous = current
following
}
new FunIter[BigInt](BigInt(0), step)
}The initial artificial previous value is , making the first update return one. Thereafter, just before advancing from , the captured cell holds ; the assignment produces and retains . Induction gives .
BigInt avoids the fixed-width overflow that would prevent Int from representing all Fibonacci numbers.Copies made through part (c) share memoized future cells, so interleaving their traversal does not advance this private state twice for the same sequence position. A separate call to
fibonacci() receives a separate closure. Another valid construction uses a pure step on the pair and projects the first coordinate; the stateful construction above follows the suggested single-current-value approach. Articles by others on the same topic
There are currently no matching articles.