iterable.scala

来自「JAVA 语言的函数式编程扩展」· SCALA 代码 · 共 517 行 · 第 1/2 页

/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2003-2008, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */

// $Id: Iterable.scala 14494 2008-04-04 09:40:48Z washburn $


package scala


import Predef._
import collection.mutable.{Buffer,ArrayBuffer}

/** Various utilities for instances of <a href="Iterable.html">Iterable</a>.
 *
 *  @author  Matthias Zenger
 *  @version 1.1, 04/02/2004
 */
object Iterable {
/*
  implicit def view[A <% Ordered[A]](x: Iterable[A]): Ordered[Iterable[A]] =
    new Ordered[Iterable[A]] {
      def compare[B >: Iterable[A] <% Ordered[B]](that: B): Int = that match {
        case y: Iterable[A] =>
          val xs = x.elements
          val ys = y.elements
          var res = 0
          while (xs.hasNext && ys.hasNext && (res == 0)) {
            res = xs.next compare ys.next
          }
          if (xs.hasNext) 1
          else if (ys.hasNext) -1
          else res
        case _ =>
          -(that compare x)
      }
    }
*/
  /** The minimum element of a non-empty sequence of ordered elements */
  def min[A <% Ordered[A]](seq: Iterable[A]): A = {
    val xs = seq.elements
    if (!xs.hasNext) throw new IllegalArgumentException("min(<empty>)")
    var min = xs.next
    while (xs.hasNext) {
      val x = xs.next
      if (x < min) min = x
    }
    min
  }

  /** The maximum element of a non-empty sequence of ordered elements */
  def max[A <% Ordered[A]](seq: Iterable[A]): A = {
    val xs = seq.elements
    if (!xs.hasNext) throw new IllegalArgumentException("max(<empty>)")
    var max = xs.next
    while (xs.hasNext) {
      val x = xs.next
      if (max < x) max = x
    }
    max
  }

  /** The empty iterable object */
  val empty = new Iterable[Nothing] {
    def elements = Iterator.empty
  }
  /** A non-strict projection of an iterable. 
   * @author Sean McDirmid
   */
  trait Projection[+A] extends Iterable[A] {
    override def projection = this
    /** convert to a copied strict collection */
    def force : Iterable[A] = toList
    
    /** non-strict */
    override def filter(p : A => Boolean) : Projection[A] = new Projection[A] {
      def elements = Projection.this.elements.filter(p)
    }
    /** non-strict */
    override def map[B](f: A => B) : Projection[B] = new Projection[B] {
      def elements = Projection.this.elements.map(f)
    }
    /** non-strict */
    override def flatMap[B](f: A => Iterable[B]) : Projection[B] = new Projection[B] {
      def elements = Projection.this.elements.flatMap(a => f(a).elements)
    }  
    /** non-strict */
    override def takeWhile(p: A => Boolean): Projection[A] = new Projection[A] {
      def elements = Projection.this.elements.takeWhile(p)
    }
    /** The projection resulting from the concatenation of this projection with the <code>rest</code> projection.
     *  @param rest   The projection that gets appended to this projection
     */
    def append[B >: A](rest : => Iterable[B]): Projection[B] = new Projection[B] {
      def elements = Projection.this.elements ++ rest.elements
    }
  }
}


/** 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
 *  @version 1.1, 04/02/2004
 */
trait Iterable[+A] {

  /** Creates a new iterator over all elements contained in this
   *  object.
   *  
   *  @return the new iterator
   */
  def elements: Iterator[A]

  /** Appends two iterable objects.
   *
   *  @return the new iterable object
   *  @deprecated  use <code>++</code> instead
   *  @note Will not terminate for infinite-sized collections.
   */
  @deprecated
  def concat[B >: A](that: Iterable[B]): Collection[B] =
    this ++ that

  /** Appends two iterable objects.
   *
   *  @return the new iterable object
   *  @note Will not terminate for infinite-sized collections.
   */
  def ++ [B >: A](that: Iterable[B]): Collection[B] = {
    val buf = new ArrayBuffer[B]
    this copyToBuffer buf
    that copyToBuffer buf
    buf
  }

  /** Returns the iterable resulting from applying the given function
   *  <code>f</code> to each element of this iterable.
   *
   *  @note Will not terminate for infinite-sized collections.
   *  @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>, ..., an</code>.
   */
  def map[B](f: A => B): Iterable[B] = {
    val buf = new ArrayBuffer[B]
    val elems = elements
    while (elems.hasNext) buf += f(elems.next)
    buf
  }

  /** Applies the given function <code>f</code> to each element of
   *  this iterable, then concatenates the results.
   *
   *  @note Will not terminate for infinite-sized collections.
   *  @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]): Iterable[B] = {
    val buf = new ArrayBuffer[B]
    val elems = elements
    while (elems.hasNext) f(elems.next) copyToBuffer buf
    buf
  }

  /** Returns all the elements of this iterable that satisfy the
   *  predicate <code>p</code>. The order of the elements is preserved.
   *
   *  @note Will not terminate for infinite-sized collections.
   *  @param p the predicate used to filter the list.
   *  @return the elements of this list satisfying <code>p</code>.
   */
  def filter(p: A => Boolean): Iterable[A] = {
    val buf = new ArrayBuffer[A]
    val elems = elements
    while (elems.hasNext) { val x = elems.next; if (p(x)) buf += x }
    buf
  }

  /** 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 satisfy the predicate
   *           <code>p</code> and the iterable that do not.
   *           The relative order of the elements in the resulting iterables
   *           is the same as in the original iterable.
   */
  def partition(p: A => Boolean): (Iterable[A], Iterable[A]) = {
    val matched = new ArrayBuffer[A]
    val failed = new ArrayBuffer[A]
    val elems = elements
    while (elems.hasNext) { val x = elems.next; if (p(x)) matched += x else failed += x }
    (matched, failed)
  }

  /** Returns the longest prefix of this iterable whose elements satisfy
   *  the predicate <code>p</code>.
   *
   *  @note May not terminate for infinite-sized collections.
   *  @param p the test predicate.
   *  @return  the longest prefix of this iterable whose elements satisfy
   *           the predicate <code>p</code>.
   */
  def takeWhile(p: A => Boolean): Iterable[A] = 
    (new ArrayBuffer[A] ++ elements.takeWhile(p))

  /** Returns the longest suffix of this iterable whose first element
   *  does not satisfy the predicate <code>p</code>.
   *
   *  @note May not terminate for infinite-sized collections.
   *  @param p the test predicate.
   *  @return  the longest suffix of the iterable whose first element
   *           does not satisfy the predicate <code>p</code>.
   */
  def dropWhile(p: A => Boolean): Collection[A] = 
    (new ArrayBuffer[A] ++ elements.dropWhile(p))

  /** Returns an iterable consisting only over the first <code>n</code>
   *  elements of this iterable, or else the whole iterable, if it has less
   *  than <code>n</code> elements.
   *
   *  @deprecated API does not make sense for non-ordered collections
   *  @param n the number of elements to take
   *  @return  the new iterable
   */
  @deprecated def take(n: Int): Collection[A] = 
    (new ArrayBuffer[A] ++ elements.take(n))

  /** 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.
   *
   *  @note Will not terminate for infinite-sized collections.
   *  @deprecated API does not make sense for non-ordered collections
   *  @param n the number of elements to drop
   *  @return  the new iterable
   */
  @deprecated def drop(n: Int): Collection[A] =
    (new ArrayBuffer[A] ++ elements.drop(n))

  /** 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.
   */
  def foreach(f: A => Unit): Unit = elements.foreach(f)

  /** Apply a predicate <code>p</code> to all elements of this
   *  iterable object and return true, iff the predicate yields