summaryrefslogtreecommitdiff
path: root/src/library/scala/collection/Iterator.scala
diff options
context:
space:
mode:
Diffstat (limited to 'src/library/scala/collection/Iterator.scala')
-rw-r--r--src/library/scala/collection/Iterator.scala135
1 files changed, 103 insertions, 32 deletions
diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala
index ed536f10a8..17bb83e52e 100644
--- a/src/library/scala/collection/Iterator.scala
+++ b/src/library/scala/collection/Iterator.scala
@@ -12,8 +12,6 @@ package collection
import mutable.ArrayBuffer
import scala.annotation.migration
import immutable.Stream
-import scala.collection.generic.CanBuildFrom
-import scala.annotation.unchecked.{ uncheckedVariance => uV }
/** The `Iterator` object provides various functions for creating specialized iterators.
*
@@ -182,7 +180,7 @@ object Iterator {
}
}
def hasNext = (current ne null) && (current.hasNext || advance())
- def next() = if (hasNext) current.next else Iterator.empty.next
+ def next() = if (hasNext) current.next() else Iterator.empty.next()
override def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] =
new ConcatIterator(current, queue :+ (() => that.toIterator))
@@ -191,11 +189,55 @@ object Iterator {
private[scala] final class JoinIterator[+A](lhs: Iterator[A], that: => GenTraversableOnce[A]) extends Iterator[A] {
private[this] lazy val rhs: Iterator[A] = that.toIterator
def hasNext = lhs.hasNext || rhs.hasNext
- def next = if (lhs.hasNext) lhs.next else rhs.next
+ def next() = if (lhs.hasNext) lhs.next() else rhs.next()
override def ++[B >: A](that: => GenTraversableOnce[B]) =
new ConcatIterator(this, Vector(() => that.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()
+ }
+ 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
+ }
+ }
+ }
}
import Iterator.empty
@@ -307,11 +349,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.
*
@@ -332,29 +374,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
@@ -482,13 +519,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) {
@@ -661,9 +698,9 @@ trait Iterator[+A] extends TraversableOnce[A] {
}
}
}
-
+
val leading = new Leading
-
+
val trailing = new AbstractIterator[A] {
private[this] var myLeading = leading
/* Status flags meanings:
@@ -699,7 +736,7 @@ trait Iterator[+A] extends TraversableOnce[A] {
}
else Iterator.empty.next()
}
-
+
override def toString = "unknown-if-empty iterator"
}
@@ -733,7 +770,7 @@ trait Iterator[+A] extends TraversableOnce[A] {
status = 1
false
}
- def next() =
+ def next() =
if (hasNext) {
if (status == 1) self.next()
else {
@@ -916,8 +953,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
@@ -934,8 +988,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
@@ -1250,7 +1322,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) {