iterator.scala

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

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

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


package scala


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

/** The <code>Iterator</code> object provides various functions for
 *  creating specialized iterators.
 *
 *  @author  Martin Odersky
 *  @author  Matthias Zenger
 *  @version 1.2, 10/02/2007
 */
object Iterator {

  val empty = new Iterator[Nothing] {
    def hasNext: Boolean = false
    def next(): Nothing = throw new NoSuchElementException("next on empty iterator")
  }

  /**
   *  @param x the element
   *  @return  the iterator with one single element
   */
  def single[a](x: a) = new Iterator[a] {
    private var hasnext = true
    def hasNext: Boolean = hasnext
    def next(): a =
      if (hasnext) { hasnext = false; x }
      else throw new NoSuchElementException("next on empty iterator")
  }

  def fromValues[a](xs: a*) = xs.elements

  /**
   *  @param xs the array of elements
   *  @see also: RandomAccessSeq.elements and slice
   */
  def fromArray[a](xs: Array[a]): Iterator[a] =
    fromArray(xs, 0, xs.length)

  /**
   *  @param xs     the array of elements
   *  @param start  the start index
   *  @param length  the length
   *  @see also: RandomAccessSeq.elements and slice
   */
  @throws(classOf[NoSuchElementException])
  def fromArray[a](xs: Array[a], start: Int, length: Int): Iterator[a] =
    new BufferedIterator.Advanced[a] {
      private var i = start
      val end = if (start + length < xs.length) start + length else xs.length
      override def hasNext: Boolean = i < end
      def next: a =
        if (hasNext) { val x = xs(i) ; i += 1 ; x }
        else throw new NoSuchElementException("next on empty iterator")
        
      override protected def defaultPeek : a = throw new NoSuchElementException("no lookahead")
      override def peekList(sz: Int): Seq[a] = 
        xs.slice(i, if (i + sz > xs.length) xs.length else i + sz)
  }

  /**
   *  @param str the given string
   *  @return    the iterator on <code>str</code>
   *  @deprecated replaced by <code>str.elements</code>
   */
  @deprecated def fromString(str: String): Iterator[Char] =
    new BufferedIterator.Advanced[Char] {
      private var i = 0
      private val len = str.length()
      override def hasNext = i < len
      def next = { val c = str charAt i; i += 1; c }
      
      override protected def defaultPeek : Char = throw new NoSuchElementException
      override def peekList(sz: Int): Seq[Char] =
        str.substring(i, if (i + sz > str.length) str.length else i + sz)
    }

  /**
   *  @param n the product arity
   *  @return  the iterator on <code>Product&lt;n&gt;</code>.
   */
  def fromProduct(n: Product): Iterator[Any] = new Iterator[Any] {
    private var c: Int = 0
    private val cmax = n.productArity
    def hasNext = c < cmax
    def next() = { val a = n productElement c; c += 1; a }
  }

  /**
   * @deprecated use <code>fromProduct</code> instead.
   */
  @deprecated
  def fromCaseClass(n: Product) = fromProduct(n)

  /** Create an iterator with elements
   *  <code>e<sub>n+1</sub> = e<sub>n</sub> + 1</code>
   *  where <code>e<sub>0</sub> = start</code>
   *  and <code>e<sub>i</sub> &lt; end</code>. However, 
   *  if <code>start &ge; end</code>, then it will return an empty range.
   *
   *  @param start the start value of the iterator
   *  @param end   the end value of the iterator
   *  @return      the iterator with values in range <code>[start;end)</code>.
   */
  def range(start: Int, end: Int): Iterator[Int] = range(start, end, 1)

  /** Create an iterator with elements
   *  <code>e<sub>n+1</sub> = e<sub>n</sub> + step</code>
   *  where <code>e<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 iterator
   *  @param end   the end value of the iterator
   *  @param step  the increment value of the iterator (must be positive or negative)
   *  @return      the iterator with values in range <code>[start;end)</code>.
   */
  @throws(classOf[NoSuchElementException])
  def range(start: Int, end: Int, step: Int) = new Iterator[Int] {
    private var i = start
    def hasNext: Boolean = (step <= 0 || i < end) && (step >= 0 || i > end)
    def next(): Int =
      if (hasNext) { val j = i; i += step; j }
      else throw new NoSuchElementException("next on empty iterator")
  }

  /** Create an iterator with elements
   *  <code>e<sub>n+1</sub> = step(e<sub>n</sub>)</code>
   *  where <code>e<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 iterator
   *  @param end   the end value of the iterator
   *  @param step  the increment function of the iterator, must be monotonically increasing or decreasing
   *  @return      the iterator with values in range <code>[start;end)</code>.
   */
  @throws(classOf[NoSuchElementException])
  def range(start: Int, end: Int, step: Int => Int) = new Iterator[Int] {
    private val up = step(start) > start
    private val down = step(start) < start
    private var i = start
    def hasNext: Boolean = (!up || i < end) && (!down || i > end)
    def next(): Int =
      if (hasNext) { val j = i; i = step(i); j }
      else throw new NoSuchElementException("next on empty iterator")
  }

  /** Create an iterator with elements
   *  <code>e<sub>n+1</sub> = e<sub>n</sub> + 1</code>
   *  where <code>e<sub>0</sub> = start</code>.
   *
   *  @param start the start value of the iterator
   *  @return      the iterator starting at value <code>start</code>.
   */
  def from(start: Int): Iterator[Int] = from(start, 1)

  /** Create an iterator with elements
   * <code>e<sub>n+1</sub> = e<sub>n</sub> + step</code>
   *  where <code>e<sub>0</sub> = start</code>.
   *
   *  @param start the start value of the iterator
   *  @param step  the increment value of the iterator
   *  @return      the iterator starting at value <code>start</code>.
   */
  def from(start: Int, step: Int): Iterator[Int] = from(start, {x:Int => x + step})

  /** Create an iterator with elements
   *  <code>e<sub>n+1</sub> = step(e<sub>n</sub>)</code>
   *  where <code>e<sub>0</sub> = start</code>.
   *
   *  @param start the start value of the iterator
   *  @param step  the increment function of the iterator
   *  @return      the iterator starting at value <code>start</code>.
   */
  def from(start: Int, step: Int => Int): Iterator[Int] = new Iterator[Int] {
    private var i = start
    override def hasNext: Boolean = true
    def next: Int = { val j = i; i = step(i); j }
  }
}

/** Iterators are data structures that allow to iterate over a sequence
 *  of elements. They have a <code>hasNext</code> method for checking
 *  if there is a next element available, and a <code>next</code> method
 *  which returns the next element and discards it from the iterator.
 *
 *  @author  Martin Odersky, Matthias Zenger
 *  @version 1.2, 15/03/2004
 */
trait Iterator[+A] {

  /** Does this iterator provide another element?
   */
  def hasNext: Boolean

  /** Returns the next element.
   */
  def next(): A
  

  /** Returns a new iterator that iterates only over the first <code>n</code>
   *  elements.
   *
   *  @param n the number of elements to take
   *  @return  the new iterator
   */
  @throws(classOf[NoSuchElementException])
  def take(n: Int) = new Iterator[A] {
    var remaining = n
    def hasNext = remaining > 0 && Iterator.this.hasNext
    def next(): A =
      if (hasNext) { remaining -= 1; Iterator.this.next }
      else throw new NoSuchElementException("next on empty iterator")
  }

  /** Removes the first <code>n</code> elements from this iterator.
   *
   *  @param n the number of elements to drop
   *  @return  the new iterator
   */
  def drop(n: Int): Iterator[A] =
    if (n > 0 && hasNext) { next; drop(n - 1) } else this

  /** A sub-iterator of <code>until - from elements 
   *  starting at index <code>from</code>
   *
   *  @param from   The index of the first element of the slice
   *  @param until    The index of the element following the slice
   */
  def slice(from: Int, until: Int): Iterator[A] = drop(from).take(until - from)

  /** Returns a new iterator that maps all elements of this iterator
   *  to new elements using function <code>f</code>.
   */
  def map[B](f: A => B): Iterator[B] = new Iterator[B] {
    def hasNext = Iterator.this.hasNext
    def next() = f(Iterator.this.next)
  }

  /** Returns a new iterator that first yields the elements of this
   *  iterator followed by the elements provided by iterator <code>that</code>.
   *  @deprecated  use <code>++</code>
   */
  def append[B >: A](that: Iterator[B]) = new Iterator[B] {
    def hasNext = Iterator.this.hasNext || that.hasNext
    def next() = if (Iterator.this.hasNext) Iterator.this.next else that.next
  }

  /** Returns a new iterator that first yields the elements of this
   *  iterator followed by the elements provided by iterator <code>that</code>.
   */
  def ++[B >: A](that: => Iterator[B]) = new Iterator[B] {
    // optimize a little bit to prevent n log n behavior.
    var what : Iterator[B] = Iterator.this 
    def hasNext = if (what.hasNext) true
                  else if (what eq Iterator.this) {
                    what = that
                    what.hasNext
                  } else false
                  
    def next = { hasNext; what.next }
  }

  /** Applies the given function <code>f</code> to each element of
   *  this iterator, then concatenates the results.
   *
   *  @param f the function to apply on each element.
   *  @return  an iterator over <code>f(a<sub>0</sub>), ... ,
   *           f(a<sub>n</sub>)</code> if this iterator yields the
   *           elements <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
   */
  @throws(classOf[NoSuchElementException])
  def flatMap[B](f: A => Iterator[B]): Iterator[B] = new Iterator[B] {
    private var cur: Iterator[B] = Iterator.empty
    def hasNext: Boolean =
      if (cur.hasNext) true
      else if (Iterator.this.hasNext) {
        cur = f(Iterator.this.next)
        hasNext
      } else false
    def next(): B = 
      if (cur.hasNext) cur.next
      else if (Iterator.this.hasNext) {
        cur = f(Iterator.this.next)
        next
      } else throw new NoSuchElementException("next on empty iterator")
  }

  protected class PredicatedIterator(p : A => Boolean) extends BufferedIterator.Default[A] {
    protected def doEnd : Boolean = false
    protected override def fill(sz: Int): Seq[A] = {
      while (true) {
        if (!Iterator.this.hasNext) return Nil
        val ret = Iterator.this.next
        if (p(ret)) return ret :: Nil
        if (doEnd) return Nil
      }
      throw new Error
    }
  }
  protected class TakeWhileIterator(p : A => Boolean) extends PredicatedIterator(p) {
    private var ended = false
    override protected def doEnd = {
      ended = true; true
    }
    override protected def fill(sz : Int) : Seq[A] = 
      if (ended) Nil else super.fill(sz)
  }
  

  /** Returns an iterator over all the elements of this iterator that
   *  satisfy the predicate <code>p</code>. The order of the elements
   *  is preserved.
   *
   *  @param p the predicate used to filter the iterator.
   *  @return  the elements of this iterator satisfying <code>p</code>.
   */
  def filter(p: A => Boolean): Iterator[A] = new PredicatedIterator(p)

  /** Returns an iterator over the longest prefix of this iterator such that
   *  all elements of the result satisfy the predicate <code>p</code>. 
   *  The order of the elements is preserved.
   *
   *  @param p the predicate used to filter the iterator.
   *  @return  the longest prefix of this iterator satisfying <code>p</code>.
   */
  def takeWhile(p: A => Boolean): Iterator[A] = new TakeWhileIterator(p)

  /** Skips longest sequence of elements of this iterator which satisfy given