Interpret After calls to
step as a positive increment, consistent with the increasing sequence and exclusive upper bound. State this precondition explicitly; a zero increment would not define the intended finite progression. Use a wider cursor to avoid integer overflow on the update after the last valid Int result.class RangeIter(lower: Int, upper: Int, step: Int) extends Iter[Int] {
require(step > 0)
private var current = lower.toLong
def hasNext: Boolean = current < upper.toLong
def next(): Int = {
require(hasNext)
val answer = current.toInt
current += step.toLong
answer
}
}next, the abstraction function is the sequence of values with , in increasing order. Repeated calls to hasNext do not change it; next removes precisely its first value. ThereforeIf lower >= upper, the represented sequence is empty immediately. The paper does not specify a descending-range convention; this implementation exposes its positive-step precondition rather than assigning one implicitly.A demand-driven filtering iterator needs one cached accepted value. Otherwise The representation invariant says that
hasNext would either lose an element or consume another accepted value every time it is queried.def filterIter[T](p: T => Boolean, it: Iter[T]): Iter[T] =
new Iter[T] {
private var buffered: Option[T] = None
private var finished = false
private def fill(): Unit = {
while (buffered.isEmpty && !finished) {
if (!it.hasNext) finished = true
else {
val x = it.next()
if (p(x)) buffered = Some(x)
}
}
}
def hasNext: Boolean = {
fill()
buffered.nonEmpty
}
def next(): T = {
fill()
require(buffered.nonEmpty)
val answer = buffered.get
buffered = None
answer
}
}buffered holds at most one accepted value. The represented sequence is the buffered value, if present, followed by the subsequence of the underlying remainder satisfying the predicate. Filling moves the next accepted value into the cache and discards only rejected values, so this abstract sequence is unchanged by hasNext. Clearing the cache in next removes its head. Thusnext works even when the client has not first called hasNext; exhaustion violates its stated precondition. As with ordinary iterator adapters, clients should give this wrapper exclusive consumption of it, and the predicate should give a stable answer for each element. One call may scan several rejected elements, but across a complete traversal each source element is consumed once. Cache storage is constant.Use the iterator adapter from part (b) with a primality test by trial division. A composite positive integer has a divisor no greater than its square root.Before each trial division iteration, no integer in divides
def primeIter(upperBound: Int): Iter[Int] = {
def isPrime(n: Int): Boolean = {
if (n < 2) false
else {
var d = 2
while (d <= n / d && n % d != 0) d += 1
d > n / d
}
}
filterIter[Int](isPrime _, new RangeIter(2, upperBound, 1))
}n. If division succeeds, the condition becomes false with , and isPrime returns false. Otherwise the loop ends with , so every possible small divisor has been excluded. The quotient comparison is equivalent to for positive values and avoids integer overflow in d*d.Bounds at most two give an empty iterator. This method tests candidates lazily and uses trial divisions for candidate ; no efficiency requirement in the question forces a sieve of Eratosthenes implementation. Articles by others on the same topic
There are currently no matching articles.