stream.scala

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

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

// $Id: Stream.scala 14480 2008-04-02 14:11:46Z dragos $


package scala

import Predef._

/**
 * The object <code>Stream</code> provides helper functions
 * to manipulate streams.
 *
 * @author Martin Odersky, Matthias Zenger
 * @version 1.1 08/08/03
 */
object Stream {

  def apply[A](xs: A*) = (xs :\ (empty: Stream[A]))(cons(_, _))
    
  def unapplySeq[A](xs: Stream[A]): Option[Seq[A]] = Some(xs)

  object lazy_:: {
    def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = 
      if (xs.isEmpty) None
      else Some(xs.head, xs.tail)
  }

   /** a stream with a definite size */
  trait Definite[+A] extends Stream[A] with Function0[Stream[A]] {
     override def hasDefiniteSize = true
     override def apply = this
     override def toString = super[Stream].toString
   }
   
  /** The empty stream */
  val empty: Stream[Nothing] = new Definite[Nothing] {
    override def isEmpty = true
    def head: Nothing = throw new NoSuchElementException("head of empty stream")
    def tail: Stream[Nothing] = throw new UnsupportedOperationException("tail of empty stream")
    protected def addDefinedElems(buf: StringBuilder, prefix: String): StringBuilder = buf
  }

  object cons {

    /** A stream consisting of a given first element and remaining elements 
     *  @param hd   The first element of the result stream
     *  @param tl   The remaining elements of the result stream
     */
    def apply[A](hd: A, tl: => Stream[A]) = new Stream[A] {
      override def hasDefiniteSize = if (tlDefined) tlVal.hasDefiniteSize else super.hasDefiniteSize
      override def isEmpty = false
      def head = hd
      private var tlVal: Stream[A] = _
      private def tlDefined = tlVal ne null
      def tail: Stream[A] = {
        if (!tlDefined) { tlVal = tl }
        tlVal 
      }
      protected def addDefinedElems(buf: StringBuilder, prefix: String): StringBuilder = {
        val buf1 = buf.append(prefix).append(hd)
        if (tlDefined) tlVal.addDefinedElems(buf1, ", ") else buf1 append ", ?"
      }
    }

    def unapply[A](str: Stream[A]): Option[(A, Stream[A])] =
      if(str.isEmpty)
        None
      else
        Some((str.head, str.tail))
  }

  /** A stream containing all elements of a given iterator, in the order they are produced.
   *  @param it   The iterator producing the stream's elements
   */
  def fromIterator[A](it: Iterator[A]): Stream[A] =
    if (it.hasNext) cons(it.next, fromIterator(it)) else empty

  /** The concatenation of a sequence of streams 
   */
  def concat[A](xs: Iterable[Stream[A]]): Stream[A] = concat(xs.elements)

  /** The concatenation of all given streams 
   */
  def concat[A](s1: Stream[A], s2: Stream[A], ss: Stream[A]*): Stream[A] =
    s1 append s2 append concat(ss.elements)

  /** The concatenation of all streams returned by an iterator
   */
  def concat[A](xs: Iterator[Stream[A]]): Stream[A] =
    if (xs.hasNext) xs.next append concat(xs)
    else empty

  /**
   * Create a stream with element values
   * <code>v<sub>n+1</sub> = v<sub>n</sub> + 1</code>
   * where <code>v<sub>0</sub> = start</code>
   * and <code>v<sub>i</sub> &lt; end</code>.
   *
   * @param start the start value of the stream
   * @param end the end value of the stream
   * @return the stream starting at value <code>start</code>.
   */
  def range(start: Int, end: Int): Stream[Int] = 
    range(start, end, 1)

  /**
   * Create a stream with element values
   * <code>v<sub>n+1</sub> = v<sub>n</sub> + step</code>
   * where <code>v<sub>0</sub> = start</code>
   * and elements are in the range between <code>start</code> (inclusive)
   * and <code>end</code> (exclusive)
   *
   * @param start the start value of the stream
   * @param end the end value of the stream
   * @param step the increment value of the stream
   * @return the stream starting at value <code>start</code>.
   */
  final def range(start: Int, end: Int, step: Int): Stream[Int] = {
    if ((step <= 0 || start < end) && (step >= 0 || start > end)) 
      cons(start, range(start + step, end, step))
    else 
      empty
  }

  /**
   * Create a stream with element values
   * <code>v<sub>n+1</sub> = step(v<sub>n</sub>)</code>
   * where <code>v<sub>0</sub> = start</code>
   * and elements are in the range between <code>start</code> (inclusive)
   * and <code>end</code> (exclusive)
   *
   * @param start the start value of the stream
   * @param end the end value of the stream
   * @param step the increment function of the stream, must be monotonically increasing or decreasing
   * @return the stream starting at value <code>start</code>.
   */
  def range(start: Int, end: Int, step: Int => Int): Stream[Int] = {
    val up = step(start) > start
    val down = step(start) < start
    def loop(lo: Int): Stream[Int] =
      if ((!up || lo < end) && (!down || lo > end)) cons(lo, loop(step(lo)))
      else empty
    loop(start)
  }
   
  /**
   * Create an infinite stream starting at <code>start</code>
   * and incrementing by step <code>step</code>
   *
   * @param start the start value of the stream
   * @param step the increment value of the stream
   * @return the stream starting at value <code>start</code>.
   */
  def from(start: Int, step: Int): Stream[Int] =
    cons(start, from(start+step, step))

  /**
   * Create an infinite stream starting at <code>start</code>
   * and incrementing by 1.
   *
   * @param start the start value of the stream
   * @return the stream starting at value <code>start</code>.
   */
  def from(start: Int): Stream[Int] = from(start, 1)

  /**
   * Create an infinite stream containing the given element.
   *
   * @param elem the element composing the resulting stream
   * @return the stream containing an inifinite number of elem
   */
  def const[A](elem: A): Stream[A] = cons(elem, const(elem))

  /** Create a stream containing several copies of an element.
   *
   *  @param n    the length of the resulting stream
   *  @param elem the element composing the resulting stream
   *  @return     the stream composed of n elements all equal to elem
   */
  def make[A](n: Int, elem: A): Stream[A] = 
    Stream.const(elem) take n
}

/**
 * <p>The class <code>Stream</code> implements lazy lists where elements
 * are only evaluated when they are needed. Here is an example:</p>
 * <pre>
 * <b>object</b> Main <b>extends</b> Application {
 *
 *   <b>def</b> from(n: Int): Stream[Int] =
 *     Stream.cons(n, from(n + 1))
 *
 *   <b>def</b> sieve(s: Stream[Int]): Stream[Int] =
 *     Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 }))
 *
 *   <b>def</b> primes = sieve(from(2))
 *
 *   primes take 10 print
 * }
 * </pre>
 *
 * @author Martin Odersky, Matthias Zenger
 * @version 1.1 08/08/03
 */
trait Stream[+A] extends Seq.Projection[A] {

  /** is this stream empty? */
  override def isEmpty: Boolean

  override def force : List[A] = toList
  
  /** The first element of this stream 
   *  @throws Predef.NoSuchElementException if the stream is empty.
   */
  def head: A

  /** A stream consisting of the remaining elements of this stream after the first one.
   *  @throws Predef.UnsupportedOperationException if the stream is empty.
   */
  def tail: Stream[A]

  /** The length of this stream */
  override def length: Int = {
    var len = 0
    var here = this
    while (!here.isEmpty) {
      len += 1
      here = here.tail
    }
    len
  }

  /** returns length - l without calling length
   */
  override def lengthCompare(l: Int) = {
    if (isEmpty) 0 - l
    else if (l <= 0) 1
    else tail.lengthCompare(l - 1)
  }

  override def hasDefiniteSize = false