/*

* Scala (https://www.scala-lang.org)

*

* Copyright EPFL and Lightbend, Inc. dba Akka

*

* Licensed under Apache License 2.0

* (http://www.apache.org/licenses/LICENSE-2.0).

*

* See the NOTICE file distributed with this work for

* additional information regarding copyright ownership.

*/

package scala

package collection

import scala.annotation.tailrec

import scala.annotation.unchecked.uncheckedVariance

import scala.collection.mutable.StringBuilder

import scala.language.implicitConversions

import scala.math.{Numeric, Ordering}

import scala.reflect.ClassTag

import scala.runtime.{AbstractFunction1, AbstractFunction2}

import IterableOnce.elemsToCopyToArray

/**

* A template trait for collections which can be traversed either once only

* or one or more times.

*

* Note: `IterableOnce` does not extend [[IterableOnceOps]]. This is different than the general

* design of the collections library, which uses the following pattern:

* {{{

* trait Seq extends Iterable with SeqOps

* trait SeqOps extends IterableOps

*

* trait IndexedSeq extends Seq with IndexedSeqOps

* trait IndexedSeqOps extends SeqOps

* }}}

*

* The goal is to provide a minimal interface without any sequential operations. This allows

* third-party extension like Scala parallel collections to integrate at the level of IterableOnce

* without inheriting unwanted implementations.

*

* @define coll collection

* @define ccoll $coll

*/

trait IterableOnce[+A] extends Any {

/** An [[scala.collection.Iterator]] over the elements of this $coll.

*

* If an `IterableOnce` object is in fact an [[scala.collection.Iterator]], this method always returns itself,

* in its current state, but if it is an [[scala.collection.Iterable]], this method always returns a new

* [[scala.collection.Iterator]].

*/

def iterator: Iterator[A]

/** Returns a [[scala.collection.Stepper]] for the elements of this collection.

*

* The Stepper enables creating a Java stream to operate on the collection, see

* [[scala.jdk.StreamConverters]]. For collections holding primitive values, the Stepper can be

* used as an iterator which doesn't box the elements.

*

* The implicit [[scala.collection.StepperShape]] parameter defines the resulting Stepper type according to the

* element type of this collection.

*

* - For collections of `Int`, `Short`, `Byte` or `Char`, an [[scala.collection.IntStepper]] is returned

* - For collections of `Double` or `Float`, a [[scala.collection.DoubleStepper]] is returned

* - For collections of `Long` a [[scala.collection.LongStepper]] is returned

* - For any other element type, an [[scala.collection.AnyStepper]] is returned

*

* Note that this method is overridden in subclasses and the return type is refined to

* `S with EfficientSplit`, for example [[scala.collection.IndexedSeqOps.stepper]]. For Steppers marked with

* [[scala.collection.Stepper.EfficientSplit]], the converters in [[scala.jdk.StreamConverters]]

* allow creating parallel streams, whereas bare Steppers can be converted only to sequential

* streams.

*/

def stepper[S <: Stepper[_]](implicit shape: StepperShape[A, S]): S = {

import convert.impl._

val s = shape.shape match {

case StepperShape.IntShape => new IntIteratorStepper (iterator.asInstanceOf[Iterator[Int]])

case StepperShape.LongShape => new LongIteratorStepper (iterator.asInstanceOf[Iterator[Long]])

case StepperShape.DoubleShape => new DoubleIteratorStepper(iterator.asInstanceOf[Iterator[Double]])

case _ => shape.seqUnbox(new AnyIteratorStepper[A](iterator))

}

s.asInstanceOf[S]

}

/** The number of elements in this $coll, if it can be cheaply computed,

* -1 otherwise. Cheaply usually means: Not requiring a collection traversal.

*/

def knownSize: Int = -1

}

final class IterableOnceExtensionMethods[A](private val it: IterableOnce[A]) extends AnyVal {

@deprecated("Use .iterator.withFilter(...) instead", "2.13.0")

def withFilter(f: A => Boolean): Iterator[A] = it.iterator.withFilter(f)

@deprecated("Use .iterator.reduceLeftOption(...) instead", "2.13.0")

def reduceLeftOption(f: (A, A) => A): Option[A] = it.iterator.reduceLeftOption(f)

@deprecated("Use .iterator.min instead", "2.13.0")

def min(implicit ord: Ordering[A]): A = it.iterator.min

@deprecated("Use .iterator.nonEmpty instead", "2.13.0")

def nonEmpty: Boolean = it.iterator.nonEmpty

@deprecated("Use .iterator.max instead", "2.13.0")

def max(implicit ord: Ordering[A]): A = it.iterator.max

@deprecated("Use .iterator.reduceRight(...) instead", "2.13.0")

def reduceRight(f: (A, A) => A): A = it.iterator.reduceRight(f)

@deprecated("Use .iterator.maxBy(...) instead", "2.13.0")

def maxBy[B](f: A => B)(implicit cmp: Ordering[B]): A = it.iterator.maxBy(f)

@deprecated("Use .iterator.reduceLeft(...) instead", "2.13.0")

def reduceLeft(f: (A, A) => A): A = it.iterator.reduceLeft(f)

@deprecated("Use .iterator.sum instead", "2.13.0")

def sum(implicit num: Numeric[A]): A = it.iterator.sum

@deprecated("Use .iterator.product instead", "2.13.0")

def product(implicit num: Numeric[A]): A = it.iterator.product

@deprecated("Use .iterator.count(...) instead", "2.13.0")

def count(f: A => Boolean): Int = it.iterator.count(f)

@deprecated("Use .iterator.reduceOption(...) instead", "2.13.0")

def reduceOption(f: (A, A) => A): Option[A] = it.iterator.reduceOption(f)

@deprecated("Use .iterator.minBy(...) instead", "2.13.0")

def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A = it.iterator.minBy(f)

@deprecated("Use .iterator.size instead", "2.13.0")

def size: Int = it.iterator.size

@deprecated("Use .iterator.forall(...) instead", "2.13.0")

def forall(f: A => Boolean): Boolean = it.iterator.forall(f)

@deprecated("Use .iterator.collectFirst(...) instead", "2.13.0")

def collectFirst[B](f: PartialFunction[A, B]): Option[B] = it.iterator.collectFirst(f)

@deprecated("Use .iterator.filter(...) instead", "2.13.0")

def filter(f: A => Boolean): Iterator[A] = it.iterator.filter(f)

@deprecated("Use .iterator.exists(...) instead", "2.13.0")

def exists(f: A => Boolean): Boolean = it.iterator.exists(f)

@deprecated("Use .iterator.copyToBuffer(...) instead", "2.13.0")

def copyToBuffer(dest: mutable.Buffer[A]): Unit = it.iterator.copyToBuffer(dest)

@deprecated("Use .iterator.reduce(...) instead", "2.13.0")

def reduce(f: (A, A) => A): A = it.iterator.reduce(f)

@deprecated("Use .iterator.reduceRightOption(...) instead", "2.13.0")

def reduceRightOption(f: (A, A) => A): Option[A] = it.iterator.reduceRightOption(f)

@deprecated("Use .iterator.toIndexedSeq instead", "2.13.0")

def toIndexedSeq: IndexedSeq[A] = it.iterator.toIndexedSeq

@deprecated("Use .iterator.foreach(...) instead", "2.13.0")

@`inline` def foreach[U](f: A => U): Unit = it match {

case it: Iterable[A] => it.foreach(f)

case _ => it.iterator.foreach(f)

}

@deprecated("Use .iterator.to(factory) instead", "2.13.0")

def to[C1](factory: Factory[A, C1]): C1 = factory.fromSpecific(it)

@deprecated("Use .iterator.to(ArrayBuffer) instead", "2.13.0")

def toBuffer[B >: A]: mutable.Buffer[B] = mutable.ArrayBuffer.from(it)

@deprecated("Use .iterator.toArray", "2.13.0")

def toArray[B >: A: ClassTag]: Array[B] = it match {

case it: Iterable[B] => it.toArray[B]

case _ => it.iterator.toArray[B]

}

@deprecated("Use .iterator.to(List) instead", "2.13.0")

def toList: immutable.List[A] = immutable.List.from(it)

@deprecated("Use .iterator.to(Set) instead", "2.13.0")

@`inline` def toSet[B >: A]: immutable.Set[B] = immutable.Set.from(it)

@deprecated("Use .iterator.to(Iterable) instead", "2.13.0")

@`inline` final def toTraversable: Traversable[A] = toIterable

@deprecated("Use .iterator.to(Iterable) instead", "2.13.0")

@`inline` final def toIterable: Iterable[A] = Iterable.from(it)

@deprecated("Use .iterator.to(Seq) instead", "2.13.0")

@`inline` def toSeq: immutable.Seq[A] = immutable.Seq.from(it)

@deprecated("Use .iterator.to(LazyList) instead", "2.13.0")

@`inline` def toStream: immutable.Stream[A] = immutable.Stream.from(it)

@deprecated("Use .iterator.to(Vector) instead", "2.13.0")

@`inline` def toVector: immutable.Vector[A] = immutable.Vector.from(it)

@deprecated("Use .iterator.to(Map) instead", "2.13.0")

def toMap[K, V](implicit ev: A <:< (K, V)): immutable.Map[K, V] =

immutable.Map.from(it.asInstanceOf[IterableOnce[(K, V)]])

@deprecated("Use .iterator instead", "2.13.0")

@`inline` def toIterator: Iterator[A] = it.iterator

@deprecated("Use .iterator.isEmpty instead", "2.13.0")

def isEmpty: Boolean = it match {

case it: Iterable[A] => it.isEmpty

case _ => it.iterator.isEmpty

}

@deprecated("Use .iterator.mkString instead", "2.13.0")

def mkString(start: String, sep: String, end: String): String = it match {

case it: Iterable[A] => it.mkString(start, sep, end)

case _ => it.iterator.mkString(start, sep, end)

}

@deprecated("Use .iterator.mkString instead", "2.13.0")

def mkString(sep: String): String = it match {

case it: Iterable[A] => it.mkString(sep)

case _ => it.iterator.mkString(sep)

}

@deprecated("Use .iterator.mkString instead", "2.13.0")

def mkString: String = it match {

case it: Iterable[A] => it.mkString

case _ => it.iterator.mkString

}

@deprecated("Use .iterator.find instead", "2.13.0")

def find(p: A => Boolean): Option[A] = it.iterator.find(p)

@deprecated("Use .iterator.foldLeft instead", "2.13.0")

@`inline` def foldLeft[B](z: B)(op: (B, A) => B): B = it.iterator.foldLeft(z)(op)

@deprecated("Use .iterator.foldRight instead", "2.13.0")

@`inline` def foldRight[B](z: B)(op: (A, B) => B): B = it.iterator.foldRight(z)(op)

@deprecated("Use .iterator.fold instead", "2.13.0")

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 = it.iterator.fold(z)(op)

@deprecated("Use .iterator.foldLeft instead", "2.13.0")

@`inline` def /: [B](z: B)(op: (B, A) => B): B = foldLeft[B](z)(op)

@deprecated("Use .iterator.foldRight instead", "2.13.0")

@`inline` def :\ [B](z: B)(op: (A, B) => B): B = foldRight[B](z)(op)

@deprecated("Use .iterator.map instead or consider requiring an Iterable", "2.13.0")

def map[B](f: A => B): IterableOnce[B] = it match {

case it: Iterable[A] => it.map(f)

case _ => it.iterator.map(f)

}

@deprecated("Use .iterator.flatMap instead or consider requiring an Iterable", "2.13.0")

def flatMap[B](f: A => IterableOnce[B]): IterableOnce[B] = it match {

case it: Iterable[A] => it.flatMap(f)

case _ => it.iterator.flatMap(f)

}

@deprecated("Use .iterator.sameElements instead", "2.13.0")

def sameElements[B >: A](that: IterableOnce[B]): Boolean = it.iterator.sameElements(that)

}

object IterableOnce {

@inline implicit def iterableOnceExtensionMethods[A](it: IterableOnce[A]): IterableOnceExtensionMethods[A] =

new IterableOnceExtensionMethods[A](it)

/** Computes the number of elements to copy to an array from a source IterableOnce.

*

* If `start` is less than zero, it is taken as zero.

* If any of the length inputs is less than zero, the computed result is zero.

*

* The result is the smaller of the remaining capacity in the destination and the requested count.

*

* @param srcLen the length of the source collection

* @param destLen the length of the destination array

* @param start the index in the destination array at which to start copying elements

* @param len the requested number of elements to copy (we may only be able to copy less than this)

* @return the number of elements that will be copied to the destination array

*/

@inline private[collection] def elemsToCopyToArray(srcLen: Int, destLen: Int, start: Int, len: Int): Int = {

val limit = math.min(len, srcLen)

val capacity = if (start < 0) destLen else destLen - start

val total = math.min(capacity, limit)

math.max(0, total)

}

/** Calls `copyToArray` on the given collection, regardless of whether or not it is an `Iterable`. */

@inline private[collection] def copyElemsToArray[A, B >: A](elems: IterableOnce[A],

xs: Array[B],

start: Int = 0,

len: Int = Int.MaxValue): Int =

elems match {

case src: Iterable[A] => src.copyToArray[B](xs, start, len)

case src => src.iterator.copyToArray[B](xs, start, len)

}

}

/** This implementation trait can be mixed into an `IterableOnce` to get the basic methods that are shared between

* `Iterator` and `Iterable`. The `IterableOnce` must support multiple calls to `iterator` but may or may not

* return the same `Iterator` every time.

*

* @define orderDependent

*

* Note: might return different results for different runs, unless the underlying collection type is ordered.

* @define orderDependentReduce

*

* Note: might return different results for different runs, unless the

* underlying collection type is ordered or the operator is associative

* and commutative.

* @define orderIndependentReduce

*

* Note: might return different results for different runs, unless either

* of the following conditions is met: (1) the operator is associative,

* and the underlying collection type is ordered; or (2) the operator is

* associative and commutative.

* @define mayNotTerminateInf

*

* Note: may not terminate for infinite-sized collections.

* @define willNotTerminateInf

*

* Note: will not terminate for infinite-sized collections.

* @define willForceEvaluation

* Note: Even when applied to a view or a lazy collection it will always force the elements.

* @define consumesIterator

* After calling this method, one should discard the iterator it was called

* on. Using it is undefined and subject to change.

* @define undefinedOrder

* The order of applications of the operator is unspecified and may be nondeterministic.

* @define exactlyOnce

* Each element appears exactly once in the computation.

*/

trait IterableOnceOps[+A, +CC[_], +C] extends Any { this: IterableOnce[A] =>

/////////////////////////////////////////////////////////////// Abstract methods that must be implemented

/** Produces a $coll containing cumulative results of applying the

* operator going left to right, including the initial value.

*

* $willNotTerminateInf

* $orderDependent

*

* @tparam B the type of the elements in the resulting collection

* @param z the initial value

* @param op the binary operator applied to the intermediate result and the element

* @return collection with intermediate results

*/

def scanLeft[B](z: B)(op: (B, A) => B): CC[B]

/** Selects all elements of this $coll which satisfy a predicate.

*

* @param p the predicate used to test elements.

* @return a new $coll consisting of all elements of this $coll that satisfy the given

* predicate `p`. The order of the elements is preserved.

*/

def filter(p: A => Boolean): C

/** Selects all elements of this $coll which do not satisfy a predicate.

*

* @param pred the predicate used to test elements.

* @return a new $coll consisting of all elements of this $coll that do not satisfy the given

* predicate `pred`. Their order may not be preserved.

*/

def filterNot(pred: A => Boolean): C

/** Selects the first `n` elements.

* $orderDependent

* @param n the number of elements to take from this $coll.

* @return a $coll consisting only of the first `n` elements of this $coll,

* or else the whole $coll, if it has less than `n` elements.

* If `n` is negative, returns an empty $coll.

*/

def take(n: Int): C

/** Selects the longest prefix of elements that satisfy a predicate.

*

* The matching prefix starts with the first element of this $coll,

* and the element following the prefix is the first element that

* does not satisfy the predicate. The matching prefix may empty,

* so that this method returns an empty $coll.

*

* Example:

*

* {{{

* scala> List(1, 2, 3, 100, 4).takeWhile(n => n < 10)

* val res0: List[Int] = List(1, 2, 3)

*

* scala> List(1, 2, 3, 100, 4).takeWhile(n => n == 0)

* val res1: List[Int] = List()

* }}}

*

* Use [[span]] to obtain both the prefix and suffix.

* Use [[filter]] to retain only those elements from the entire $coll that satisfy the predicate.

* $orderDependent

* @param p The predicate used to test elements.

* @return the longest prefix of this $coll whose elements all satisfy

* the predicate `p`.

*/

def takeWhile(p: A => Boolean): C

/** Selects all elements except the first `n` ones.

* $orderDependent

* @param n the number of elements to drop from this $coll.

* @return a $coll consisting of all elements of this $coll except the first `n` ones, or else the

* empty $coll, if this $coll has less than `n` elements.

* If `n` is negative, don't drop any elements.

*/

def drop(n: Int): C

/** Selects all elements except the longest prefix that satisfies a predicate.

*

* The matching prefix starts with the first element of this $coll,

* and the element following the prefix is the first element that

* does not satisfy the predicate. The matching prefix may be empty,

* so that this method returns the entire $coll.

*

* Example:

*

* {{{

* scala> List(1, 2, 3, 100, 4).dropWhile(n => n < 10)

* val res0: List[Int] = List(100, 4)

*

* scala> List(1, 2, 3, 100, 4).dropWhile(n => n == 0)

* val res1: List[Int] = List(1, 2, 3, 100, 4)

* }}}

*

* Use [[span]] to obtain both the prefix and suffix.

* Use [[filterNot]] to drop all elements that satisfy the predicate.

*

* $orderDependent

* @param p The predicate used to test elements.

* @return the longest suffix of this $coll whose first element

* does not satisfy the predicate `p`.

*/

def dropWhile(p: A => Boolean): C

/** Selects an interval of elements. The returned $coll is made up

* of all elements `x` which satisfy the invariant:

* {{{

* from <= indexOf(x) < until

* }}}

* $orderDependent

*

* @param from the lowest index to include from this $coll.

* @param until the lowest index to EXCLUDE from this $coll.

* @return a $coll containing the elements greater than or equal to

* index `from` extending up to (but not including) index `until`

* of this $coll.

* @example

* `List('a', 'b', 'c', 'd', 'e').slice(1, 3) == List('b', 'c')`

*/

def slice(from: Int, until: Int): C

/** Builds a new $ccoll by applying a function to all elements of this $coll.

*

* @param f the function to apply to each element.

* @tparam B the element type of the returned $ccoll.

* @return a new $ccoll resulting from applying the given function

* `f` to each element of this $coll and collecting the results.

*/

def map[B](f: A => B): CC[B]

/** Builds a new $ccoll by applying a function to all elements of this $coll

* and using the elements of the resulting collections.

*

* For example:

*

* {{{

* def getWords(lines: Seq[String]): Seq[String] = lines.flatMap(line => line.split("\\W+"))

* }}}

*

* The type of the resulting collection is guided by the static type of this $coll. This might

* cause unexpected results sometimes. For example:

*

* {{{

* // lettersOf will return a Seq[Char] of likely repeated letters, instead of a Set

* def lettersOf(words: Seq[String]) = words.flatMap(word => word.toSet)

*

* // lettersOf will return a Set[Char], not a Seq

* def lettersOf(words: Seq[String]) = words.toSet.flatMap(word => word.toSeq)

*

* // xs will be an Iterable[Int]

* val xs = Map("a" -> List(11, 111), "b" -> List(22, 222)).flatMap(_._2)

*

* // ys will be a Map[Int, Int]

* val ys = Map("a" -> List(1 -> 11, 1 -> 111), "b" -> List(2 -> 22, 2 -> 222)).flatMap(_._2)

* }}}

*

* @param f the function to apply to each element.

* @tparam B the element type of the returned collection.

* @return a new $ccoll resulting from applying the given collection-valued function

* `f` to each element of this $coll and concatenating the results.

*/

def flatMap[B](f: A => IterableOnce[B]): CC[B]

/** Given that the elements of this collection are themselves iterable collections,

* converts this $coll into a $ccoll comprising the elements of these iterable collections.

*

* The resulting collection's type will be guided by the

* type of $coll. For example:

*

* {{{

* val xs = List(

* Set(1, 2, 3),

* Set(1, 2, 3)

* ).flatten

* // xs == List(1, 2, 3, 1, 2, 3)

*

* val ys = Set(

* List(1, 2, 3),

* List(3, 2, 1)

* ).flatten

* // ys == Set(1, 2, 3)

* }}}

*

* @tparam B the type of the elements of each iterable collection.

* @param asIterable an implicit conversion which asserts that the element

* type of this $coll is an `Iterable`.

* @return a new $ccoll resulting from concatenating all element collections.

*/

def flatten[B](implicit asIterable: A => IterableOnce[B]): CC[B]

/** Builds a new $ccoll by applying a partial function to all elements of this $coll

* on which the function is defined.

*

* @param pf the partial function which filters and maps the $coll.

* @tparam B the element type of the returned $coll.

* @return a new $ccoll resulting from applying the given partial function

* `pf` to each element on which it is defined and collecting the results.

* The order of the elements is preserved.

*/

def collect[B](pf: PartialFunction[A, B]): CC[B]

/** Zips this $coll with its indices.

*

* @return A new $ccoll containing pairs consisting of all elements of this $coll paired with their index.

* Indices start at `0`.

* @example

* `List("a", "b", "c").zipWithIndex == List(("a", 0), ("b", 1), ("c", 2))`

*/

def zipWithIndex: CC[(A @uncheckedVariance, Int)]

/** Splits this $coll into a prefix/suffix pair according to a predicate.

*

* Note: `c span p` is equivalent to (but possibly more efficient than)

* `(c takeWhile p, c dropWhile p)`, provided the evaluation of the

* predicate `p` does not cause any side effects.

* $orderDependent

*

* @param p the test predicate

* @return a pair consisting of the longest prefix of this $coll whose

* elements all satisfy `p`, and the rest of this $coll.

*/

def span(p: A => Boolean): (C, C)

/** Splits this $coll into a prefix/suffix pair at a given position.

*

* Note: `c splitAt n` is equivalent to (but possibly more efficient than)

* `(c take n, c drop n)`.

* $orderDependent

*

* @param n the position at which to split.

* @return a pair of ${coll}s consisting of the first `n`

* elements of this $coll, and the other elements.

*/

def splitAt(n: Int): (C, C) = {

class Spanner extends runtime.AbstractFunction1[A, Boolean] {

var i = 0

def apply(a: A) = i < n && { i += 1 ; true }

}

val spanner = new Spanner

span(spanner)

}

/** Applies a side-effecting function to each element in this collection.

* Strict collections will apply `f` to their elements immediately, while lazy collections

* like Views and LazyLists will only apply `f` on each element if and when that element

* is evaluated, and each time that element is evaluated.

*

* @param f a function to apply to each element in this $coll

* @tparam U the return type of f

* @return The same logical collection as this

*/

def tapEach[U](f: A => U): C

/////////////////////////////////////////////////////////////// Concrete methods based on iterator

/** Tests whether this $coll is known to have a finite size.

* All strict collections are known to have finite size. For a non-strict

* collection such as `Stream`, the predicate returns `'''true'''` if all

* elements have been computed. It returns `'''false'''` if the stream is

* not yet evaluated to the end. Non-empty Iterators usually return

* `'''false'''` even if they were created from a collection with a known

* finite size.

*

* Note: many collection methods will not work on collections of infinite sizes.

* The typical failure mode is an infinite loop. These methods always attempt a

* traversal without checking first that `hasDefiniteSize` returns `'''true'''`.

* However, checking `hasDefiniteSize` can provide an assurance that size is

* well-defined and non-termination is not a concern.

*

* @deprecated This method is deprecated in 2.13 because it does not provide any

* actionable information. As noted above, even the collection library itself

* does not use it. When there is no guarantee that a collection is finite, it

* is generally best to attempt a computation anyway and document that it will

* not terminate for infinite collections rather than backing out because this

* would prevent performing the computation on collections that are in fact

* finite even though `hasDefiniteSize` returns `false`.

*

* @see method `knownSize` for a more useful alternative

*

* @return `'''true'''` if this collection is known to have finite size,

* `'''false'''` otherwise.

*/

@deprecated("Check .knownSize instead of .hasDefiniteSize for more actionable information (see scaladoc for details)", "2.13.0")

def hasDefiniteSize: Boolean = true

/** Tests whether this $coll can be repeatedly traversed. Always

* true for Iterables and false for Iterators unless overridden.

*

* @return `true` if it is repeatedly traversable, `false` otherwise.

*/

def isTraversableAgain: Boolean = false

/** Applies `f` to each element for its side effects.

* Note: `U` parameter needed to help scalac's type inference.

*/

def foreach[U](f: A => U): Unit = {

val it = iterator

while(it.hasNext) f(it.next())

}

/** Tests whether a predicate holds for all elements of this $coll.

*

* $mayNotTerminateInf

*

* @param p the predicate used to test elements.

* @return `true` if this $coll is empty or the given predicate `p`

* holds for all elements of this $coll, otherwise `false`.

*/

def forall(p: A => Boolean): Boolean = {

var res = true

val it = iterator

while (res && it.hasNext) res = p(it.next())

res

}

/** Tests whether a predicate holds for at least one element of this $coll.

*

* $mayNotTerminateInf

*

* @param p the predicate used to test elements.

* @return `true` if the given predicate `p` is satisfied by at least one element of this $coll, otherwise `false`

*/

def exists(p: A => Boolean): Boolean = {

var res = false

val it = iterator

while (!res && it.hasNext) res = p(it.next())

res

}

/** Counts the number of elements in the $coll which satisfy a predicate.

*

* $willNotTerminateInf

*

* @param p the predicate used to test elements.

* @return the number of elements satisfying the predicate `p`.

*/

def count(p: A => Boolean): Int = {

var res = 0

val it = iterator

while (it.hasNext) if (p(it.next())) res += 1

res

}

/** Finds the first element of the $coll satisfying a predicate, if any.

*

* $mayNotTerminateInf

* $orderDependent

*

* @param p the predicate used to test elements.

* @return an option value containing the first element in the $coll

* that satisfies `p`, or `None` if none exists.

*/

def find(p: A => Boolean): Option[A] = {

val it = iterator

while (it.hasNext) {

val a = it.next()

if (p(a)) return Some(a)

}

None

}

// in future, move to IndexedSeqOps

private def foldl[X >: A, B](seq: IndexedSeq[X], start: Int, z: B, op: (B, X) => B): B = {

@tailrec def loop(at: Int, end: Int, acc: B): B =

if (at == end) acc

else loop(at + 1, end, op(acc, seq(at)))

loop(start, seq.length, z)

}

private def foldr[X >: A, B >: X](seq: IndexedSeq[X], op: (X, B) => B): B = {

@tailrec def loop(at: Int, acc: B): B =

if (at == 0) acc

else loop(at - 1, op(seq(at - 1), acc))

loop(seq.length - 1, seq(seq.length - 1))

}

/** Applies the given binary operator `op` to the given initial value `z` and all

* elements of this $coll, going left to right. Returns the initial value if this $coll

* is empty.

*

* "Going left to right" only makes sense if this collection is ordered: then if

* `x,,1,,`, `x,,2,,`, ..., `x,,n,,` are the elements of this $coll, the result is

* `op( op( ... op( op(z, x,,1,,), x,,2,,) ... ), x,,n,,)`.

*

* If this collection is not ordered, then for each application of the operator, each

* right operand is an element. In addition, the leftmost operand is the initial

* value, and each other left operand is itself an application of the operator. The

* elements of this $coll and the initial value all appear exactly once in the

* computation.

*

* $orderDependent

* $willNotTerminateInf

*

* @param z An initial value.

* @param op A binary operator.

* @tparam B The result type of the binary operator.

* @return The result of applying `op` to `z` and all elements of this $coll,

* going left to right. Returns `z` if this $coll is empty.

*/

def foldLeft[B](z: B)(op: (B, A) => B): B = this match {

case seq: IndexedSeq[A @unchecked] => foldl[A, B](seq, 0, z, op)

case _ =>

var result = z

val it = iterator

while (it.hasNext) {

result = op(result, it.next())

}

result

}

/** Applies the given binary operator `op` to all elements of this $coll and the given

* initial value `z`, going right to left. Returns the initial value if this $coll is

* empty.

*

* "Going right to left" only makes sense if this collection is ordered: then if

* `x,,1,,`, `x,,2,,`, ..., `x,,n,,` are the elements of this $coll, the result is

* `op(x,,1,,, op(x,,2,,, op( ... op(x,,n,,, z) ... )))`.

*

* If this collection is not ordered, then for each application of the operator, each

* left operand is an element. In addition, the rightmost operand is the initial

* value, and each other right operand is itself an application of the operator. The

* elements of this $coll and the initial value all appear exactly once in the

* computation.

*

* $orderDependent

* $willNotTerminateInf

*

* @param z An initial value.

* @param op A binary operator.

* @tparam B The result type of the binary operator.

* @return The result of applying `op` to all elements of this $coll and `z`,

* going right to left. Returns `z` if this $coll is empty.

*/

def foldRight[B](z: B)(op: (A, B) => B): B = reversed.foldLeft(z)((b, a) => op(a, b))

@deprecated("Use foldLeft instead of /:", "2.13.0")

@`inline` final def /: [B](z: B)(op: (B, A) => B): B = foldLeft[B](z)(op)

@deprecated("Use foldRight instead of :\\", "2.13.0")

@`inline` final def :\ [B](z: B)(op: (A, B) => B): B = foldRight[B](z)(op)

/** Applies the given binary operator `op` to the given initial value `z` and all

* elements of this $coll.

*

* For each application of the operator, each operand is either an element of this

* $coll, the initial value, or another such application of the operator.

* $undefinedOrder $exactlyOnce The initial value may be used an arbitrary number of

* times, but at least once.

*

* If this collection is ordered, then for any application of the operator, the

* element(s) appearing in the left operand will precede those in the right.

*

* $orderIndependentReduce In either case, it is also necessary that the initial value

* be a neutral value for the operator, e.g. `Nil` for `List` concatenation or `1` for

* multiplication.

*

* The default implementation in `IterableOnce` is equivalent to `foldLeft` but may be

* overridden for more efficient traversal orders.

*

* $willNotTerminateInf

*

* @tparam A1 The type parameter for the binary operator, a supertype of `A`.

* @param z An initial value; may be used an arbitrary number of times in the

* computation of the result; must be a neutral value for `op` for the

* result to always be the same across runs.

* @param op A binary operator; must be associative for the result to always be the

* same across runs.

* @return The result of applying `op` between all the elements and `z`, or `z`

* if this $coll is empty.

*/

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 = foldLeft(z)(op)

/** Applies the given binary operator `op` to all elements of this $coll.

*

* For each application of the operator, each operand is either an element of this

* $coll or another such application of the operator. $undefinedOrder $exactlyOnce

*

* If this collection is ordered, then for any application of the operator, the

* element(s) appearing in the left operand will precede those in the right.

*

* $orderIndependentReduce

* $willNotTerminateInf

*

* @tparam B The type parameter for the binary operator, a supertype of `A`.

* @param op A binary operator; must be associative for the result to always be the

* same across runs.

* @return The result of applying `op` between all the elements if the $coll is

* nonempty.

* @throws UnsupportedOperationException if this $coll is empty.

*/

def reduce[B >: A](op: (B, B) => B): B = reduceLeft(op)

/** If this $coll is nonempty, reduces it with the given binary operator `op`.

*

* The behavior is the same as [[reduce]] except that the value is `None` if the $coll

* is empty. $undefinedOrder $exactlyOnce

*

* $orderIndependentReduce

* $willNotTerminateInf

*

* @tparam B A type parameter for the binary operator, a supertype of `A`.

* @param op A binary operator; must be associative for the result to always be the

* same across runs.

* @return The result of reducing this $coll with `op` if the $coll is nonempty,

* inside a `Some`, and `None` otherwise.

*/

def reduceOption[B >: A](op: (B, B) => B): Option[B] = reduceLeftOption(op)

/** Applies the given binary operator `op` to all elements of this $coll, going left to

* right.

*

* "Going left to right" only makes sense if this collection is ordered: then if

* `x,,1,,`, `x,,2,,`, ..., `x,,n,,` are the elements of this $coll, the result is

* `op( op( op( ... op(x,,1,,, x,,2,,) ... ), x,,n-1,,), x,,n,,)`.

*

* If this collection is not ordered, then for each application of the operator, each

* right operand is an element. In addition, the leftmost operand is the first element

* of this $coll and each other left operand is itself an application of the

* operator. $exactlyOnce

*

* $orderDependentReduce

* $willNotTerminateInf

*

* @param op A binary operator.

* @tparam B The result type of the binary operator, a supertype of `A`.

* @return The result of applying `op` to all elements of this $coll, going

* left to right.

* @throws UnsupportedOperationException if this $coll is empty.

*/

def reduceLeft[B >: A](op: (B, A) => B): B = this match {

case seq: IndexedSeq[A @unchecked] if seq.length > 0 => foldl(seq, 1, seq(0), op)

case _ if knownSize == 0 => throw new UnsupportedOperationException("empty.reduceLeft")

case _ => reduceLeftIterator[B](throw new UnsupportedOperationException("empty.reduceLeft"))(op)

}

private final def reduceLeftIterator[B >: A](onEmpty: => B)(op: (B, A) => B): B = {

val it = iterator

if (it.hasNext) {

var acc: B = it.next()

while (it.hasNext)

acc = op(acc, it.next())

acc

}

else onEmpty

}

/** Applies the given binary operator `op` to all elements of this $coll, going right to

* left.

*

* "Going right to left" only makes sense if this collection is ordered: then if

* `x,,1,,`, `x,,2,,`, ..., `x,,n,,` are the elements of this $coll, the result is

* `op(x,,1,,, op(x,,2,,, op( ... op(x,,n-1,,, x,,n,,) ... )))`.

*

* If this collection is not ordered, then for each application of the operator, each

* left operand is an element. In addition, the rightmost operand is the last element

* of this $coll and each other right operand is itself an application of the

* operator. $exactlyOnce

*

* $orderDependentReduce

* $willNotTerminateInf

*

* @param op A binary operator.

* @tparam B The result type of the binary operator, a supertype of `A`.

* @return The result of applying `op` to all elements of this $coll, going

* right to left.

* @throws UnsupportedOperationException if this $coll is empty.

*/

def reduceRight[B >: A](op: (A, B) => B): B = this match {

case seq: IndexedSeq[A @unchecked] if seq.length > 0 => foldr[A, B](seq, op)

case _ if knownSize == 0 => throw new UnsupportedOperationException("empty.reduceRight")

case _ => reversed.reduceLeft[B]((x, y) => op(y, x)) // reduceLeftIterator

}

/** If this $coll is nonempty, reduces it with the given binary operator `op`, going

* left to right.

*

* The behavior is the same as [[reduceLeft]] except that the value is `None` if the

* $coll is empty. $exactlyOnce

*

* $orderDependentReduce

* $willNotTerminateInf

*

* @param op A binary operator.

* @tparam B The result type of the binary operator, a supertype of `A`.

* @return The result of reducing this $coll with `op` going left to right if

* the $coll is nonempty, inside a `Some`, and `None` otherwise.

*/

def reduceLeftOption[B >: A](op: (B, A) => B): Option[B] =

knownSize match {

case -1 => reduceLeftOptionIterator[B](op)

case 0 => None

case _ => Some(reduceLeft(op))

}

private final def reduceLeftOptionIterator[B >: A](op: (B, A) => B): Option[B] = reduceOptionIterator[A, B](iterator)(op)

private final def reduceOptionIterator[X >: A, B >: X](it: Iterator[X])(op: (B, X) => B): Option[B] = {

if (it.hasNext) {

var acc: B = it.next()

while (it.hasNext)

acc = op(acc, it.next())

Some(acc)

}

else None

}

/** If this $coll is nonempty, reduces it with the given binary operator `op`, going

* right to left.

*

* The behavior is the same as [[reduceRight]] except that the value is `None` if the

* $coll is empty. $exactlyOnce

*

* $orderDependentReduce

* $willNotTerminateInf

*

* @param op A binary operator.

* @tparam B The result type of the binary operator, a supertype of `A`.

* @return The result of reducing this $coll with `op` going right to left if

* the $coll is nonempty, inside a `Some`, and `None` otherwise.

*/

def reduceRightOption[B >: A](op: (A, B) => B): Option[B] =

knownSize match {

case -1 => reduceOptionIterator[A, B](reversed.iterator)((x, y) => op(y, x))

case 0 => None

case _ => Some(reduceRight(op))

}

/** Tests whether the $coll is empty.

*

* Note: The default implementation creates and discards an iterator.

*

* Note: Implementations in subclasses that are not repeatedly iterable must take

* care not to consume any elements when `isEmpty` is called.

*

* @return `true` if the $coll contains no elements, `false` otherwise.

*/

def isEmpty: Boolean =

knownSize match {

case -1 => !iterator.hasNext

case 0 => true

case _ => false

}

/** Tests whether the $coll is not empty.

*

* @return `true` if the $coll contains at least one element, `false` otherwise.

*/

@deprecatedOverriding("nonEmpty is defined as !isEmpty; override isEmpty instead", "2.13.0")

def nonEmpty: Boolean = !isEmpty

/** The size of this $coll.

*

* $willNotTerminateInf

*

* @return the number of elements in this $coll.

*/

def size: Int =

if (knownSize >= 0) knownSize

else {

val it = iterator

var len = 0

while (it.hasNext) { len += 1; it.next() }

len

}

@deprecated("Use `dest ++= coll` instead", "2.13.0")

@inline final def copyToBuffer[B >: A](dest: mutable.Buffer[B]): Unit = dest ++= this

/** Copies elements to an array, returning the number of elements written.

*

* Fills the given array `dest` starting at index `start` with values of this $coll.