diff options
Diffstat (limited to 'src/library/scala/collection/Iterator.scala')
| -rw-r--r-- | src/library/scala/collection/Iterator.scala | 217 |
1 files changed, 145 insertions, 72 deletions
diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala index 8d88b1c6b1..1426278954 100644 --- a/src/library/scala/collection/Iterator.scala +++ b/src/library/scala/collection/Iterator.scala @@ -11,9 +11,8 @@ package collection import mutable.ArrayBuffer import scala.annotation.{tailrec, migration} +import scala.annotation.unchecked.{uncheckedVariance => uV} import immutable.Stream -import scala.collection.generic.CanBuildFrom -import scala.annotation.unchecked.{ uncheckedVariance => uV } /** The `Iterator` object provides various functions for creating specialized iterators. * @@ -162,30 +161,49 @@ object Iterator { def next = elem } - /** Avoid stack overflows when applying ++ to lots of iterators by - * flattening the unevaluated iterators out into a vector of closures. + /** Creates an iterator to which other iterators can be appended efficiently. + * Nested ConcatIterators are merged to avoid blowing the stack. */ - private[scala] final class ConcatIterator[+A](private[this] var current: Iterator[A], initial: Vector[() => Iterator[A]]) extends Iterator[A] { - @deprecated def this(initial: Vector[() => Iterator[A]]) = this(Iterator.empty, initial) // for binary compatibility - private[this] var queue: Vector[() => Iterator[A]] = initial - private[this] var currentHasNextChecked = false + private final class ConcatIterator[+A](private var current: Iterator[A @uV]) extends Iterator[A] { + private var tail: ConcatIteratorCell[A @uV] = null + private var last: ConcatIteratorCell[A @uV] = null + private var currentHasNextChecked = false + // Advance current to the next non-empty iterator // current is set to null when all iterators are exhausted @tailrec private[this] def advance(): Boolean = { - if (queue.isEmpty) { + if (tail eq null) { current = null + last = null false } else { - current = queue.head() - queue = queue.tail - if (current.hasNext) { + current = tail.headIterator + tail = tail.tail + merge() + if (currentHasNextChecked) true + else if (current.hasNext) { currentHasNextChecked = true true } else advance() } } + + // If the current iterator is a ConcatIterator, merge it into this one + @tailrec + private[this] def merge(): Unit = + if (current.isInstanceOf[ConcatIterator[_]]) { + val c = current.asInstanceOf[ConcatIterator[A]] + current = c.current + currentHasNextChecked = c.currentHasNextChecked + if (c.tail ne null) { + c.last.tail = tail + tail = c.tail + } + merge() + } + def hasNext = if (currentHasNextChecked) true else if (current eq null) false @@ -193,47 +211,73 @@ object Iterator { currentHasNextChecked = true true } else advance() + def next() = if (hasNext) { currentHasNextChecked = false current.next() } else Iterator.empty.next() - override def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] = - new ConcatIterator(current, queue :+ (() => that.toIterator)) + override def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] = { + val c = new ConcatIteratorCell[B](that, null).asInstanceOf[ConcatIteratorCell[A]] + if(tail eq null) { + tail = c + last = c + } else { + last.tail = c + last = c + } + if(current eq null) current = Iterator.empty + this + } } - private[scala] final class JoinIterator[+A](lhs: Iterator[A], that: => GenTraversableOnce[A]) extends Iterator[A] { - private[this] var state = 0 // 0: lhs not checked, 1: lhs has next, 2: switched to rhs - private[this] lazy val rhs: Iterator[A] = that.toIterator - def hasNext = state match { - case 0 => - if (lhs.hasNext) { - state = 1 - true - } else { - state = 2 - rhs.hasNext - } - case 1 => true - case _ => rhs.hasNext + private[this] final class ConcatIteratorCell[A](head: => GenTraversableOnce[A], var tail: ConcatIteratorCell[A]) { + def headIterator: Iterator[A] = head.toIterator + } + + /** Creates a delegating iterator capped by a limit count. Negative limit means unbounded. + * Lazily skip to start on first evaluation. Avoids daisy-chained iterators due to slicing. + */ + private[scala] final class SliceIterator[A](val underlying: Iterator[A], start: Int, limit: Int) extends AbstractIterator[A] { + private var remaining = limit + private var dropping = start + @inline private def unbounded = remaining < 0 + private def skip(): Unit = + while (dropping > 0) { + if (underlying.hasNext) { + underlying.next() + dropping -= 1 + } else + dropping = 0 + } + def hasNext = { skip(); remaining != 0 && underlying.hasNext } + def next() = { + skip() + if (remaining > 0) { + remaining -= 1 + underlying.next() + } + else if (unbounded) underlying.next() + else empty.next() } - def next() = state match { - case 0 => - if (lhs.hasNext) lhs.next() - else { - state = 2 - rhs.next() - } - case 1 => - state = 0 - lhs.next() - case _ => - rhs.next() + override protected def sliceIterator(from: Int, until: Int): Iterator[A] = { + val lo = from max 0 + def adjustedBound = + if (unbounded) -1 + else 0 max (remaining - lo) + val rest = + if (until < 0) adjustedBound // respect current bound, if any + else if (until <= lo) 0 // empty + else if (unbounded) until - lo // now finite + else adjustedBound min (until - lo) // keep lesser bound + if (rest == 0) empty + else { + dropping += lo + remaining = rest + this + } } - - override def ++[B >: A](that: => GenTraversableOnce[B]) = - new ConcatIterator(this, Vector(() => that.toIterator)) } } @@ -346,11 +390,11 @@ trait Iterator[+A] extends TraversableOnce[A] { /** Selects first ''n'' values of this iterator. * * @param n the number of values to take - * @return an iterator producing only of the first `n` values of this iterator, or else the + * @return an iterator producing only the first `n` values of this iterator, or else the * whole iterator, if it produces fewer than `n` values. * @note Reuse: $consumesAndProducesIterator */ - def take(n: Int): Iterator[A] = slice(0, n) + def take(n: Int): Iterator[A] = sliceIterator(0, n max 0) /** Advances this iterator past the first ''n'' elements, or the length of the iterator, whichever is smaller. * @@ -371,29 +415,24 @@ trait Iterator[+A] extends TraversableOnce[A] { /** Creates an iterator returning an interval of the values produced by this iterator. * * @param from the index of the first element in this iterator which forms part of the slice. - * @param until the index of the first element following the slice. + * If negative, the slice starts at zero. + * @param until the index of the first element following the slice. If negative, the slice is empty. * @return an iterator which advances this iterator past the first `from` elements using `drop`, * and then takes `until - from` elements, using `take`. * @note Reuse: $consumesAndProducesIterator */ - def slice(from: Int, until: Int): Iterator[A] = { + def slice(from: Int, until: Int): Iterator[A] = sliceIterator(from, until max 0) + + /** Creates an optionally bounded slice, unbounded if `until` is negative. */ + protected def sliceIterator(from: Int, until: Int): Iterator[A] = { val lo = from max 0 - var toDrop = lo - while (toDrop > 0 && self.hasNext) { - self.next() - toDrop -= 1 - } + val rest = + if (until < 0) -1 // unbounded + else if (until <= lo) 0 // empty + else until - lo // finite - new AbstractIterator[A] { - private var remaining = until - lo - def hasNext = remaining > 0 && self.hasNext - def next(): A = - if (remaining > 0) { - remaining -= 1 - self.next() - } - else empty.next() - } + if (rest == 0) empty + else new Iterator.SliceIterator(this, lo, rest) } /** Creates a new iterator that maps all produced values of this iterator @@ -419,7 +458,7 @@ trait Iterator[+A] extends TraversableOnce[A] { * @usecase def ++(that: => Iterator[A]): Iterator[A] * @inheritdoc */ - def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] = new Iterator.JoinIterator(self, that) + def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] = new Iterator.ConcatIterator(self) ++ that /** Creates a new iterator by applying a function to all values produced by this iterator * and concatenating the results. @@ -521,13 +560,13 @@ trait Iterator[+A] extends TraversableOnce[A] { def collect[B](pf: PartialFunction[A, B]): Iterator[B] = new AbstractIterator[B] { // Manually buffer to avoid extra layer of wrapping with buffered private[this] var hd: A = _ - + // Little state machine to keep track of where we are // Seek = 0; Found = 1; Empty = -1 // Not in vals because scalac won't make them static (@inline def only works with -optimize) // BE REALLY CAREFUL TO KEEP COMMENTS AND NUMBERS IN SYNC! private[this] var status = 0/*Seek*/ - + def hasNext = { while (status == 0/*Seek*/) { if (self.hasNext) { @@ -700,9 +739,9 @@ trait Iterator[+A] extends TraversableOnce[A] { } } } - + val leading = new Leading - + val trailing = new AbstractIterator[A] { private[this] var myLeading = leading /* Status flags meanings: @@ -738,7 +777,7 @@ trait Iterator[+A] extends TraversableOnce[A] { } else Iterator.empty.next() } - + override def toString = "unknown-if-empty iterator" } @@ -772,7 +811,7 @@ trait Iterator[+A] extends TraversableOnce[A] { status = 1 false } - def next() = + def next() = if (hasNext) { if (status == 1) self.next() else { @@ -955,8 +994,25 @@ trait Iterator[+A] extends TraversableOnce[A] { * or -1 if such an element does not exist until the end of the iterator is reached. * @note Reuse: $consumesIterator */ - def indexWhere(p: A => Boolean): Int = { + def indexWhere(p: A => Boolean): Int = indexWhere(p, 0) + + /** Returns the index of the first produced value satisfying a predicate, or -1, after or at + * some start index. + * $mayNotTerminateInf + * + * @param p the predicate to test values + * @param from the start index + * @return the index `>= from` of the first produced value satisfying `p`, + * or -1 if such an element does not exist until the end of the iterator is reached. + * @note Reuse: $consumesIterator + */ + def indexWhere(p: A => Boolean, from: Int): Int = { var i = 0 + while (i < from && hasNext) { + next() + i += 1 + } + while (hasNext) { if (p(next())) return i i += 1 @@ -973,8 +1029,26 @@ trait Iterator[+A] extends TraversableOnce[A] { * or -1 if such an element does not exist until the end of the iterator is reached. * @note Reuse: $consumesIterator */ - def indexOf[B >: A](elem: B): Int = { + def indexOf[B >: A](elem: B): Int = indexOf(elem, 0) + + /** Returns the index of the first occurrence of the specified object in this iterable object + * after or at some start index. + * $mayNotTerminateInf + * + * @param elem element to search for. + * @param from the start index + * @return the index `>= from` of the first occurrence of `elem` in the values produced by this + * iterator, or -1 if such an element does not exist until the end of the iterator is + * reached. + * @note Reuse: $consumesIterator + */ + def indexOf[B >: A](elem: B, from: Int): Int = { var i = 0 + while (i < from && hasNext) { + next() + i += 1 + } + while (hasNext) { if (next() == elem) return i i += 1 @@ -1289,7 +1363,6 @@ trait Iterator[+A] extends TraversableOnce[A] { * $willNotTerminateInf */ def copyToArray[B >: A](xs: Array[B], start: Int, len: Int): Unit = { - require(start >= 0 && (start < xs.length || xs.length == 0), s"start $start out of range ${xs.length}") var i = start val end = start + math.min(len, xs.length - start) while (i < end && hasNext) { |