path: root/src/library/scalax/collection/generic/IterableTemplate.scala

/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2003-2009, 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, ::, Stream}
import util.control.Breaks._
import Iterable._

/** Collection classes mixing in this class provide a method
 *  <code>elements</code> which returns an iterator over all the
 *  elements contained in the collection.
 *
 *  @note If a collection has a known <code>size</code>, it should also sub-type <code>Collection</code>.
 *        Only potentially unbounded collections should directly sub-class <code>Iterable</code>.
 *  @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]

  /** Create a new builder for this IterableType
   *  with a hint what that its size should be size `sizeHint`
   */
  def newBuilder[B](sizeHint: Int): Builder[CC, B] = newBuilder[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 iterable of type CC which contains all elements of this iterable
   *  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 iterable of type CC which contains all elements of this iterable
   *  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 iterable resulting from applying the given function
   *  <code>f</code> to each element of this iterable.
   *
   *  @param f function to apply to each element.
   *  @return  <code>f(a<sub>0</sub>), ..., f(a<sub>n</sub>)</code> if this
   *           iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
   */
  def map[B](f: A => B): CC[B] = {
    val b = newBuilder[B]
    for (x <- this) b += f(x)
    b.result
  }

  /** Applies the given function <code>f</code> to each element of
   *  this iterable, then concatenates the results.
   *
   *  @param f the function to apply on each element.
   *  @return  <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
   *           this iterable is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
   */
  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 iterable that satisfy the
   *  predicate <code>p</code>. The order of the elements is preserved.
   *  @param p the predicate used to filter the iterable.
   *  @return the elements of this iterable satisfying <code>p</code>.
   */
  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
   *  <code>p</code>. This is like <code>filter</code> with the
   *  predicate inversed.
   *
   *  @param p the predicate to use to test elements
   *  @return  the iterable without all elements which satisfy <code>p</code>
   */
  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
   *           <code>p</code> 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 <code>f</code> 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 <code>p</code>.
   */
  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.
   *  @note Might return different results for different runs, unless this iterable is ordered, or
   *        the operator is associative and commutative.
   *  @param p the predicate
   *  @return an option containing the first element in the iterable object
   *  satisfying <code>p</code>, or <code>None</code> 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 <code>f</code>, from left to right, and starting with
   *  the value <code>z</code>.
   *
   *  @note Will not terminate for infinite-sized collections.
   *  @note Might return different results for different runs, unless this iterable is ordered, or
   *        the operator is associative and commutative.
   *  @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...),
   *          a<sub>n</sub>)</code> if the iterable is
   *          <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>.
   */
  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 iterable together using the binary
   *  function <code>f</code>, from right to left, and starting with
   *  the value <code>z</code>.
   *
   *  @note Will not terminate for infinite-sized collections.
   *  @note Might return different results for different runs, unless this iterable is ordered, or
   *        the operator is associative and commutative.
   *  @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code>
   *          if the iterable is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>.
   */
  def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op)

  /** Similar to <code>foldLeft</code> but can be used as
   *  an operator with the order of iterable and zero arguments reversed.
   *  That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code>
   *  @note Will not terminate for infinite-sized collections.
   *  @note Might return different results for different runs, unless this iterable is ordered, or
   *        the operator is associative and commutative.
   */
  def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op)

  /** An alias for <code>foldRight</code>.
   *  That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code>
   *  @note Will not terminate for infinite-sized collections.
   *  @note Might return different results for different runs, unless this iterable is ordered, or
   *        the operator is associative and commutative.
   */
  def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op)

  /** Combines the elements of this iterable object together using the binary
   *  operator <code>op</code>, from left to right
   *  @note Will not terminate for infinite-sized collections.
   *  @note Might return different results for different runs, unless this iterable is ordered, or
   *        the operator is associative and commutative.
   *  @param op  The operator to apply
   *  @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code>
      if the iterable object has elements
   *          <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>.
   *  @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 <code>op</code>, from right to left
   *  @note Will not terminate for infinite-sized collections.
   *  @note Might return different results for different runs, unless this iterable is ordered, or
   *        the operator is associative and commutative.
   *  @param op  The operator to apply
   *
   *  @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code>
   *          if the iterable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ...,
   *          a<sub>n</sub></code>.
   *
   *  @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 iterable
   *  `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
   *  <code>that</code> by associating each element of the former with
   *  the element at the same position in the latter.
   *
   *  @param that     iterable <code>that</code> may have a different length
   *                  as the self iterable.
   *  @param thisElem element <code>thisElem</code> is used to fill up the
   *                  resulting iterable if the self iterable is shorter than
   *                  <code>that</code>
b   *  @param thatElem element <code>thatElem</code> is used to fill up the
   *                  resulting iterable if <code>that</code> is shorter than
   *                  the self iterable
   *  @return         <code>Iterable((a<sub>0</sub>,b<sub>0</sub>), ...,
   *                  (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>),
   *                  ..., {elem,b<sub>m</sub>})</code>
   *                  when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip
   *                  [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is
   *                  invoked where <code>m &gt; n</code>.
   */
  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 <code>xs</code> with at most `len` elements of
   *  this iterable 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 <code>xs</code> with the elements of
   *  this iterable starting at position <code>start</code>
   *  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

  /** @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 <code>projection</code> for lazy behavior.
   */
  def toStream: Stream[A] = elements.toStream

  /** Sort the iterable according to the comparison function
   *  <code>&lt;(e1: a, e2: a) =&gt; Boolean</code>,
   *  which should be true iff <code>e1</code> is smaller than
   *  <code>e2</code>.
   *  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 iterable sorted according to the comparison function
   *            <code>&lt;(e1: a, e2: a) =&gt; Boolean</code>.
   *  @ex <pre>
   *    List("Steve", "Tom", "John", "Bob")
   *      .sort((e1, e2) => (e1 compareTo e2) &lt; 0) =
   *    List("Bob", "John", "Steve", "Tom")</pre>
   *  !!!
  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 <code>start</code> and is finished by the string
   *  <code>end</code>. Inside, the string representations of elements (w.r.t.
   *  the method <code>toString()</code>) are separated by the string
   *  <code>sep</code>.
   *
   *  @ex  <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code>
   *  @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 <code>toString()</code>)
   *  are separated by the string <code>sep</code>.
   *
   *  @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 <code>String</code> by each element's toString method.
   */
  def mkString =
    addString(new StringBuilder()).toString

  /** Write all elements of this iterable into given string builder.
   *  The written text begins with the string <code>start</code> and is finished by the string
   *  <code>end</code>. Inside, the string representations of elements (w.r.t.
   *  the method <code>toString()</code>) are separated by the string
   *  <code>sep</code>.
   */
  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 <code>toString()</code>)
   *  are separated by the string <code>sep</code>.
   */
  def addString(b: StringBuilder, sep: String): StringBuilder = addString(b, "", sep, "")

  /** Write all elements of this string into given string builder without using
   *  any separator between consecutive elements.
   */
  def addString(b: StringBuilder): StringBuilder = addString(b, "")

  /**
   * returns a projection that can be used to call non-strict <code>filter</code>,
   * <code>map</code>, and <code>flatMap</code> 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 <code>toString</code> 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 iterable.
   *
   *  @note  Might return different results for different runs, unless this iterable is ordered
   *  @throws Predef.NoSuchElementException if the iterable 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 <code>None</code> 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
   *  <code>None</code> if iterable 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 <code>n</code>
   *  elements of this iterable, or else the whole iterable, if it has less
   *  than <code>n</code> elements.
   *
   *  @param n the number of elements to take
   *  @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 <code>n</code> first elements
   *  If this iterable has less than <code>n</code> 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 <code>from &lt; 0</code>
   *          or <code>length &lt; from + len<code>
   *  @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
  }

  /** 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 <code>n</code>
   *           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)
  }

  /** A sub-iterable 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 iterable, whereas `slice` produces a new iterable.
   *
   *  @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)
}