/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $
package scalax.collection.generic
import scalax.collection.mutable.{Buffer, ArrayBuffer, ListBuffer}
import scalax.collection.immutable.{List, Nil, ::}
import util.control.Break._
import Iterable._
/** Collection classes mixing in this class provide a method
* elements
which returns an iterator over all the
* elements contained in the collection.
*
* @note If a collection has a known size
, it should also sub-type Collection
.
* Only potentially unbounded collections should directly sub-class Iterable
.
* @author Matthias Zenger
* @author Martin Odersky
* @version 2.8
*/
trait IterableTemplate[+CC[/*+*/B] <: IterableTemplate[CC, B] with Iterable[B], /*+*/A] { self/*: CC[A]*/ =>
/** The template itself seen as an instance of `CC[A]`.
* @note: It would be logical to have a self type `CC[A]` instead, then we would not need
* this method. Unfortunately, tyis runs afoul some pecularities in Scala's member resolution
* algorithm: If the self type is a CC, then Iterable is one of its supertypes. Iterable
* defines a number of concrete methods such as newBuilder which are abstract here.
* The newBuilder method in Iterable[A] has type Builder[Iterable, A]. Because Scala
* prefers concrete over abstract members, it is this newBuilder which is chosen, instead of
* the abstract newBuilder in class IterableTemplate of type Builder[CC, A].
* Even for concrete methods we have a problem because the last mixin in the parents of CC is
* Iterable, not IterableTemplate. So resolution picks the version in Iterable, which returns
* again an Iterable, not a CC, as would be required.
* These problems would be avoided if Scala computed the type of a member as the glb of the types
* all members in the class and its superclasses types.
* I think overall this would be a better design.
*/
protected[this] def thisCC: CC[A] = this.asInstanceOf[CC[A]]
/** Creates a new iterator over all elements contained in this
* object.
*
* @return the new iterator
*/
def elements: Iterator[A]
/** Create a new builder for this IterableType
*/
def newBuilder[B]: Builder[CC, B]
/** Is this collection empty? */
def isEmpty: Boolean = !elements.hasNext
/** returns true iff this collection has a bound size.
* Many APIs in this trait will not work on collections of
* unbound sizes.
*/
def hasDefiniteSize = true
/** Create a new sequence of type CC which contains all elements of this sequence
* followed by all elements of Iterable `that'
*/
def ++[B >: A](that: Iterable[B]): CC[B] = {
val b: Builder[CC, B] = (this: IterableTemplate[CC, A]).newBuilder[B]
b ++= thisCC
b ++= that
b.result
}
/** Create a new sequence of type IterableType which contains all elements of this sequence
* followed by all elements of Iterator `that'
*/
def ++[B >: A](that: Iterator[B]): CC[B] = {
val b = newBuilder[B]
b ++= thisCC
b ++= that
b.result
}
/** Returns the sequence resulting from applying the given function
* f
to each element of this sequence.
*
* @param f function to apply to each element.
* @return f(a0), ..., f(an)
if this
* sequence is a0, ..., an
.
*/
def map[B](f: A => B): CC[B] = {
val b = newBuilder[B]
for (x <- this) b += f(x)
b.result
}
/** Applies the given function f
to each element of
* this sequence, then concatenates the results.
*
* @param f the function to apply on each element.
* @return f(a0) ::: ... ::: f(an)
if
* this sequence is a0, ..., an
.
*/
def flatMap[B](f: A => Iterable[B]): CC[B] = {
val b = newBuilder[B]
for (x <- this) b ++= f(x)
b.result
}
/** Returns all the elements of this sequence that satisfy the
* predicate p
. The order of the elements is preserved.
* @param p the predicate used to filter the list.
* @return the elements of this list satisfying p
.
*/
def filter(p: A => Boolean): CC[A] = {
val b = newBuilder[A]
for (x <- this)
if (p(x)) b += x
b.result
}
/** Removes all elements of the iterable which satisfy the predicate
* p
. This is like filter
with the
* predicate inversed.
*
* @param p the predicate to use to test elements
* @return the list without all elements which satisfy p
*/
def remove(p: A => Boolean): CC[A] = filter(!p(_))
/** Partitions this iterable in two iterables according to a predicate.
*
* @param p the predicate on which to partition
* @return a pair of iterables: the iterable that satisfies the predicate
* p
and the iterable that does not.
* The relative order of the elements in the resulting iterables
* is the same as in the original iterable.
*/
def partition(p: A => Boolean): (CC[A], CC[A]) = {
val l, r = newBuilder[A]
for (x <- this) (if (p(x)) l else r) += x
(l.result, r.result)
}
/** Apply a function f
to all elements of this
* iterable object.
*
* @note Will not terminate for infinite-sized collections.
* @param f a function that is applied to every element.
* Note this function underlies the implementation of most other bulk operations.
* It should be overridden in concrete collectionc classes with efficient implementations.
*/
def foreach(f: A => Unit): Unit = elements.foreach(f)
/** Return true iff the given predicate `p` yields true for all elements
* of this iterable.
*
* @note May not terminate for infinite-sized collections.
* @param p the predicate
*/
def forall(p: A => Boolean): Boolean = {
var result = true
breakable {
for (x <- this)
if (!p(x)) { result = false; break }
}
result
}
/** Return true iff there is an element in this iterable for which the
* given predicate `p` yields true.
*
* @note May not terminate for infinite-sized collections.
* @param p the predicate
*/
def exists(p: A => Boolean): Boolean = {
var result = false
breakable {
for (x <- this)
if (p(x)) { result = true; break }
}
result
}
/** Count the number of elements in the iterable which satisfy a predicate.
*
* @param p the predicate for which to count
* @return the number of elements satisfying the predicate p
.
*/
def count(p: A => Boolean): Int = {
var cnt = 0
for (x <- this) {
if (p(x)) cnt += 1
}
cnt
}
/** Find and return the first element of the iterable object satisfying a
* predicate, if any.
*
* @note may not terminate for infinite-sized collections.
* @param p the predicate
* @return an option containing the first element in the iterable object
* satisfying p
, or None
if none exists.
*/
def find(p: A => Boolean): Option[A] = {
var result: Option[A] = None
breakable {
for (x <- this)
if (p(x)) { result = Some(x); break }
}
result
}
/** Combines the elements of this iterable object together using the binary
* function f
, from left to right, and starting with
* the value z
.
*
* @note Will not terminate for infinite-sized collections.
* @return f(... (f(f(z, a0), a1) ...),
* an)
if the list is
* [a0, a1, ..., an]
.
*/
def foldLeft[B](z: B)(op: (B, A) => B): B = {
var result = z
for (x <- this)
result = op(result, x)
result
}
/** Combines the elements of this list together using the binary
* function f
, from right to left, and starting with
* the value z
.
*
* @note Will not terminate for infinite-sized collections.
* @return f(a0, f(a1, f(..., f(an, z)...)))
* if the list is [a0, a1, ..., an]
.
*/
def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op)
/** Similar to foldLeft
but can be used as
* an operator with the order of list and zero arguments reversed.
* That is, z /: xs
is the same as xs foldLeft z
* @note Will not terminate for infinite-sized collections.
*/
def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op)
/** An alias for foldRight
.
* That is, xs :\ z
is the same as xs foldRight z
* @note Will not terminate for infinite-sized collections.
*/
def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op)
/** Combines the elements of this iterable object together using the binary
* operator op
, from left to right
* @note Will not terminate for infinite-sized collections.
* @param op The operator to apply
* @return op(... op(a0,a1), ..., an)
if the iterable object has elements
* a0, a1, ..., an
.
* @throws Predef.UnsupportedOperationException if the iterable object is empty.
*/
def reduceLeft[B >: A](op: (B, A) => B): B = {
if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft")
var result: B = elements.next
var first = true
for (x <- this)
if (first) first = false
else result = op(result, x)
result
}
/** Combines the elements of this iterable object together using the binary
* operator op
, from right to left
* @note Will not terminate for infinite-sized collections.
* @param op The operator to apply
*
* @return a0 op (... op (an-1 op an)...)
* if the iterable object has elements a0, a1, ...,
* an
.
*
* @throws Predef.UnsupportedOperationException if the iterator is empty.
*/
def reduceRight[B >: A](op: (A, B) => B): B =
elements.reduceRight(op)
/** Returns an iterable formed from this iterable and the specified list
* `other` by associating each element of the former with
* the element at the same position in the latter.
* If one of the two iterables is longer than the other, its remaining elements are ignored.
*/
def zip[B](that: Iterable[B]): CC[(A, B)] = {
val these = this.elements
val those = that.elements
val b = this.newBuilder[(A, B)]
while (these.hasNext && those.hasNext)
b += ((these.next, those.next))
b.result
}
/** Returns a iterable formed from this iterable and the specified iterable
* that
by associating each element of the former with
* the element at the same position in the latter.
*
* @param that iterable that
may have a different length
* as the self iterable.
* @param thisElem element thisElem
is used to fill up the
* resulting iterable if the self iterable is shorter than
* that
b * @param thatElem element thatElem
is used to fill up the
* resulting iterable if that
is shorter than
* the self iterable
* @return Iterable((a0,b0), ...,
* (an,bn), (elem,bn+1),
* ..., {elem,bm})
* when [a0, ..., an] zip
* [b0, ..., bm]
is
* invoked where m > n
.
*/
def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): CC[(A1, B1)] = {
val these = this.elements
val those = that.elements
val b = newBuilder[(A1, B1)]
while (these.hasNext && those.hasNext)
b += ((these.next, those.next))
while (these.hasNext)
b += ((these.next, thatElem))
while (those.hasNext)
b += ((thisElem, those.next))
b.result
}
/** Zips this iterable with its indices. `s.zipWithIndex` is equivalent to
* `s zip s.indices`, but is usually more efficient.
*/
def zipWithIndex: CC[(A, Int)] = {
val b = newBuilder[(A, Int)]
var i = 0
for (x <- this) {
b += ((x, i))
i +=1
}
b.result
}
/** Copy all elements to a given buffer
* @note Will not terminate for infinite-sized collections.
* @param dest The buffer to which elements are copied
*/
def copyToBuffer[B >: A](dest: Buffer[B]) {
for (x <- this) dest += x
}
/** Fills the given array xs
with at most `len` elements of
* this sequence starting at position `start`.
* Copying will stop oce either the end of the current iterable is reached or
* `len` elements have been copied.
*
* @note Will not terminate for infinite-sized collections.
* @param xs the array to fill.
* @param start starting index.
* @param len number of elements to copy
* @pre the array must be large enough to hold all elements.
*/
def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) {
var i = start
val end = (start + len) min xs.length
for (x <- this) {
if (i < end) {
xs(i) = x
i += 1
}
}
}
/** Fills the given array xs
with the elements of
* this sequence starting at position start
* until either the end of the current iterable or the end of array `xs` is reached.
*
* @note Will not terminate for infinite-sized collections.
* @param xs the array to fill.
* @param start starting index.
* @pre the array must be large enough to hold all elements.
*/
def copyToArray[B >: A](xs: Array[B], start: Int) {
copyToArray(xs, start, xs.length - start)
}
/** Converts this collection to a fresh Array elements.
* @note Will not terminate for infinite-sized collections.
*/
def toArray[B >: A]: Array[B] = {
var size = 0
for (x <- this) size += 1
val result = new Array[B](size)
copyToArray(result, 0)
result
}
/**
* Create a fresh list with all the elements of this iterable object.
* @note Will not terminate for infinite-sized collections.
*/
def toList: List[A] = (new ListBuffer[A] ++ thisCC).toList
/**
* Returns a sequence containing all of the elements in this iterable object.
* @note Will not terminate for infinite-sized collections.
*/
def toSequence: Sequence[A] = toList.asInstanceOf[Sequence[A]] // !!!
/** @deprecated use toSequence instead
*/
@deprecated def toSeq: Sequence[A] = toSequence
/**
* Create a stream which contains all the elements of this iterable object.
* @note consider using projection
for lazy behavior.
*/
def toStream: Stream[A] = elements.toStream
/** Sort the iterable according to the comparison function
* <(e1: a, e2: a) => Boolean
,
* which should be true iff e1
is smaller than
* e2
.
* The sort is stable. That is elements that are equal wrt `lt` appear in the
* same order in the sorted iterable as in the original.
*
* @param lt the comparison function
* @return a list sorted according to the comparison function
* <(e1: a, e2: a) => Boolean
.
* @ex
* List("Steve", "Tom", "John", "Bob") * .sort((e1, e2) => (e1 compareTo e2) < 0) = * List("Bob", "John", "Steve", "Tom")* !!! def sortWith(lt : (A,A) => Boolean): CC[A] = { val arr = toArray Array.sortWith(arr, lt) val b = newBuilder[A] for (x <- arr) b += x b.result } */ /** Returns a string representation of this iterable object. The resulting string * begins with the string
start
and is finished by the string
* end
. Inside, the string representations of elements (w.r.t.
* the method toString()
) are separated by the string
* sep
.
*
* @ex List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"
* @note Will not terminate for infinite-sized collections.
* @param start starting string.
* @param sep separator string.
* @param end ending string.
* @return a string representation of this iterable object.
*/
def mkString(start: String, sep: String, end: String): String =
addString(new StringBuilder(), start, sep, end).toString
/** Returns a string representation of this iterable object. The string
* representations of elements (w.r.t. the method toString()
)
* are separated by the string sep
.
*
* @note Will not terminate for infinite-sized collections.
* @param sep separator string.
* @return a string representation of this iterable object.
*/
def mkString(sep: String): String =
addString(new StringBuilder(), sep).toString
/** Converts a collection into a flat String
by each element's toString method.
* @note Will not terminate for infinite-sized collections.
*/
def mkString =
addString(new StringBuilder()).toString
/** Write all elements of this iterable into given string builder.
* The written text begins with the string start
and is finished by the string
* end
. Inside, the string representations of elements (w.r.t.
* the method toString()
) are separated by the string
* sep
.
* @note Will not terminate for infinite-sized collections.
*/
def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
b append start
var first = true
for (x <- this) {
if (first) first = false
else b append sep
b append x
}
b append end
}
/** Write all elements of this string into given string builder.
* The string representations of elements (w.r.t. the method toString()
)
* are separated by the string sep
.
* @note Will not terminate for infinite-sized collections.
*/
def addString(b: StringBuilder, sep: String): StringBuilder = {
var first = true
for (x <- this) {
if (first) first = false
else b append sep
b append x
}
b
}
/** Write all elements of this string into given string builder without using
* any separator between consecutive elements.
* @note Will not terminate for infinite-sized collections.
*/
def addString(b: StringBuilder): StringBuilder = {
for (x <- this) {
b append x
}
b
}
/**
* returns a projection that can be used to call non-strict filter
,
* map
, and flatMap
methods that build projections
* of the collection.
def projection : Iterable.Projection[A] = new Iterable.Projection[A] {
def elements = Iterable.this.elements
override def force = Iterable.this
}
*/
override def toString = mkString(stringPrefix + "(", ", ", ")")
/** Defines the prefix of this object's toString
representation.
*/
def stringPrefix : String = {
var string = this.getClass.getName
val idx1 = string.lastIndexOf('.' : Int)
if (idx1 != -1) string = string.substring(idx1 + 1)
val idx2 = string.indexOf('$')
if (idx2 != -1) string = string.substring(0, idx2)
string
}
/** Creates a view of this iterable @see IterableView
*/
def view: IterableView[CC, A] = new IterableView[CC, A] { // !!! Martin: We should maybe infer the type parameters here?
val origin = thisCC
val elements: Iterator[A] = self.elements
}
// The following methods return non-deterministic results, unless this iterable is an OrderedIterable
/** The first element of this sequence.
*
* @note Might return different results for different runs, unless this iterable is ordered
* @throws Predef.NoSuchAentException if the sequence is empty.
*/
def head: A = if (isEmpty) throw new NoSuchElementException else elements.next
/** @deprecated use head instead */
@deprecated def first: A = head
/** Returns as an option the first element of this iterable
* or None
if iterable is empty.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def headOption: Option[A] = if (isEmpty) None else Some(head)
/** @deprecated use headOption instead
* None
if list is empty.
*/
@deprecated def firstOption: Option[A] = headOption
/** An iterable consisting of all elements of this iterable
* except the first one.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def tail: CC[A] = drop(1)
/** Return an iterable consisting only of the first n
* elements of this iterable, or else the whole iterable, if it has less
* than n
elements.
*
* @param n the number of elements to take
* @return a possibly projected sequence
* @note Might return different results for different runs, unless this iterable is ordered
*/
def take(n: Int): CC[A] = {
val b = newBuilder[A]
var i = 0
breakable {
for (x <- this) {
b += x
i += 1
if (i == n) break
}
}
b.result
}
/** Returns this iterable without its n
first elements
* If this iterable has less than n
elements, the empty
* iterable is returned.
*
* @param n the number of elements to drop
* @return the new iterable
* @note Might return different results for different runs, unless this iterable is ordered
*/
def drop(n: Int): CC[A] = {
val b = newBuilder[A]
var i = 0
for (x <- this) {
if (i >= n) b += x
i += 1
}
b.result
}
/** A sub-iterable starting at index `from`
* and extending up to (but not including) index `until`.
*
* @note c.slice(from, to) is equivalent to (but possibly more efficient than)
* c.drop(from).take(to - from)
*
* @param from The index of the first element of the returned subsequence
* @param until The index of the element following the returned subsequence
* @throws IndexOutOfBoundsException if from < 0
* or length < from + len
* @note Might return different results for different runs, unless this iterable is ordered
*/
def slice(from: Int, until: Int): CC[A] = {
val b = newBuilder[A]
var i = 0
breakable {
for (x <- this) {
if (i >= from) b += x
i += 1
if (i == until) break
}
}
b.result
}
/** The last element of this iterable.
*
* @throws Predef.NoSuchElementException if the sequence is empty.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def last: A = {
var lst = head
for (x <- this)
lst = x
lst
}
/** Returns as an option the last element of this iterable or
* None
if iterable is empty.
*
* @return the last element as an option.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def lastOption: Option[A] = if (isEmpty) None else Some(last)
/** An iterable consisting of all elements of this iterable except the last one.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def init: CC[A] = {
var lst = head
val b = newBuilder[A]
for (x <- this) {
b += lst
lst = x
}
b.result
}
/** Returns the rightmost n
elements from this iterable.
*
* @param n the number of elements to take
* @note Might return different results for different runs, unless this iterable is ordered
*/
def takeRight(n: Int): CC[A] = {
val b = newBuilder[A]
val lead = elements drop n
var go = false
for (x <- this) {
if (go) b += x
else if (lead.hasNext) lead.next
else go = true
}
b.result
}
/** Returns the iterable wihtout its rightmost n
elements.
*
* @param n the number of elements to take
* @note Might return different results for different runs, unless this iterable is ordered
*/
def dropRight(n: Int): CC[A] = {
val b = newBuilder[A]
val lead = elements drop n
breakable {
for (x <- this) {
if (!lead.hasNext) break
lead.next
b += x
}
}
b.result
}
/** Split the iterable at a given point and return the two parts thus
* created.
*
* @param n the position at which to split
* @return a pair of iterables composed of the first n
* elements, and the other elements.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def splitAt(n: Int): (CC[A], CC[A]) = {
val l, r = newBuilder[A]
var i = 0
for (x <- this)
(if (i < n) l else r) += x
(l.result, r.result)
}
/** Returns the longest prefix of this sequence whose elements satisfy
* the predicate p
.
*
* @param p the test predicate.
* @return the longest prefix of this sequence whose elements satisfy
* the predicate p
.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def takeWhile(p: A => Boolean): CC[A] = {
val b = newBuilder[A]
breakable {
for (x <- this) {
if (!p(x)) break
b += x
}
}
b.result
}
/** Returns the longest suffix of this sequence whose first element
* does not satisfy the predicate p
.
*
* @param p the test predicate.
* @return the longest suffix of the sequence whose first element
* does not satisfy the predicate p
.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def dropWhile(p: A => Boolean): CC[A] = {
val b = newBuilder[A]
var go = false
for (x <- this) {
if (go) b += x
else if (!p(x)) { go = true; b += x }
}
b.result
}
/** Returns a pair consisting of the longest prefix of the list whose
* elements all satisfy the given predicate, and the rest of the list.
*
* @param p the test predicate
* @return a pair consisting of the longest prefix of the list whose
* elements all satisfy p
, and the rest of the list.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def span(p: A => Boolean): (CC[A], CC[A]) = {
val l, r = newBuilder[A]
var toLeft = true
for (x <- this) {
toLeft = toLeft && p(x)
(if (toLeft) l else r) += x
}
(l.result, r.result)
}
/** Checks if the other iterable object contains the same elements as this one.
*
* @note will not terminate for infinite-sized iterables.
* @param that the other iterable
* @return true, iff both iterables contain the same elements.
* @note Might return different results for different runs, unless this iterable is ordered
*/
def sameElements[B >: A](that: OrderedIterable[B]): Boolean = {
val these = this.elements
val those = that.elements
while (these.hasNext && those.hasNext && these.next() == those.next()) {}
!these.hasNext && !those.hasNext
}
/** A sub-sequence view starting at index `from`
* and extending up to (but not including) index `until`.
*
* @param from The index of the first element of the slice
* @param until The index of the element following the slice
* @note The difference between `view` and `slice` is that `view` produces
* a view of the current sequence, whereas `slice` produces a new sequence.
*
* @note Might return different results for different runs, unless this iterable is ordered
* @note view(from, to) is equivalent to view.slice(from, to)
*/
def view(from: Int, until: Int): IterableView[CC, A] = view.slice(from, until)
}