list.scala

JAVA 语言的函数式编程扩展

   *    List("Bob", "John", "Steve", "Tom")</pre>
   */
  def sort(lt : (A,A) => Boolean): List[A] = {
    /** Merge two already-sorted lists */
    def merge(l1: List[A], l2: List[A]): List[A] = {
      val res = new ListBuffer[A]
      var left1 = l1
      var left2 = l2

      while (!left1.isEmpty && !left2.isEmpty) {
	if(lt(left1.head, left2.head)) {
	  res += left1.head
	  left1 = left1.tail
	} else {
	  res += left2.head
	  left2 = left2.tail
	}
      }

      res ++= left1
      res ++= left2

      res.toList
    }

    /** Split a list into two lists of about the same size */
    def split(lst: List[A]) = {
      val res1 = new ListBuffer[A]
      val res2 = new ListBuffer[A]
      var left = lst

      while (!left.isEmpty) {
	res1 += left.head
	left = left.tail
	if (!left.isEmpty) {
	  res2 += left.head
	  left = left.tail
	}
      }

      (res1.toList, res2.toList)
    }


    /** Merge-sort the specified list */
    def ms(lst: List[A]): List[A] =
      lst match {
	case Nil => lst
	case x :: Nil => lst
	case x :: y :: Nil =>
	  if (lt(x,y))
	    lst
	  else
	    y :: x :: Nil

	case lst =>
          val (l1, l2) = split(lst)
          val l1s = ms(l1)
          val l2s = ms(l2)
          merge(l1s, l2s)
      }

    ms(this)
  }


  /** Count the number of elements in the list 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
    var these = this
    while (!these.isEmpty) {
      if (p(these.head)) cnt += 1
      these = these.tail
    }
    cnt
  }

  /** Tests if the predicate <code>p</code> is satisfied by all elements
   *  in this list.
   *
   *  @param p the test predicate.
   *  @return  <code>true</code> iff all elements of this list satisfy the
   *           predicate <code>p</code>.
   */
  override def forall(p: A => Boolean): Boolean = {
    var these = this
    while (!these.isEmpty) {
      if (!p(these.head)) return false
      these = these.tail
    }
    true
  }

  /** Tests the existence in this list of an element that satisfies the
   *  predicate <code>p</code>.
   *
   *  @param p the test predicate.
   *  @return  <code>true</code> iff there exists an element in this list that
   *           satisfies the predicate <code>p</code>.
   */
  override def exists(p: A => Boolean): Boolean = {
    var these = this
    while (!these.isEmpty) {
      if (p(these.head)) return true
      these = these.tail
    }
    false
  }

  /** Find and return the first element of the list satisfying a
   *  predicate, if any.
   *
   *  @param p the predicate
   *  @return the first element in the list satisfying <code>p</code>,
   *  or <code>None</code> if none exists.
   */
  override def find(p: A => Boolean): Option[A] = {
    var these = this
    while (!these.isEmpty) {
      if (p(these.head)) return Some(these.head)
      these = these.tail
    }
    None
  }

  /** Combines the elements of this list together using the binary
   *  function <code>f</code>, from left to right, and starting with
   *  the value <code>z</code>.
   *
   *  @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...),
   *          a<sub>n</sub>)</code> if the list is
   *          <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>.
   */
  override def foldLeft[B](z: B)(f: (B, A) => B): B = {
    var acc = z
    var these = this
    while (!these.isEmpty) {
      acc = f(acc, these.head)
      these = these.tail
    }
    acc
  }

  /** Combines the elements of this list together using the binary
   *  function <code>f</code>, from right to left, and starting with
   *  the value <code>z</code>.
   *
   *  @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code>
   *          if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>.
   */
  override def foldRight[B](z: B)(f: (A, B) => B): B = this match {
    case Nil => z
    case x :: xs => f(x, xs.foldRight(z)(f))
  }

  /** Combines the elements of this list together using the binary
   *  operator <code>op</code>, from left to right
   *  @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 list has elements
   *          <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>.
   *  @throws Predef.UnsupportedOperationException if the list is empty.
   */
  override def reduceLeft[B >: A](f: (B, B) => B): B = this match {
    case Nil => throw new UnsupportedOperationException("Nil.reduceLeft")
    case x :: xs => ((xs: List[B]) foldLeft (x: B))(f)
  }

  /** Combines the elements of this list together using the binary
   *  operator <code>op</code>, from right to left
   *  @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 list has elements <code>a<sub>0</sub>, a<sub>1</sub>, ...,
   *          a<sub>n</sub></code>.
   *
   *  @throws Predef.UnsupportedOperationException if the list is empty.
   */
  override def reduceRight[B >: A](f: (B, B) => B): B = this match {
    case Nil => throw new UnsupportedOperationException("Nil.reduceRight")
    case x :: Nil => x: B
    case x :: xs => f(x, xs reduceRight f)
  }

  /** Applies the given function <code>f</code> to each element of
   *  this list, 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 list is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>.
   */
  final override def flatMap[B](f: A => Iterable[B]): List[B] = {
    val b = new ListBuffer[B]
    var these = this
    while (!these.isEmpty) {
      var those = f(these.head).elements
      while (those.hasNext) {
        b += those.next
      }
      these = these.tail
    }
    b.toList
  }

  /** A list consisting of all elements of this list in reverse order.
   */
  override def reverse: List[A] = {
    var result: List[A] = Nil
    var these = this
    while (!these.isEmpty) {
      result = these.head :: result
      these = these.tail
    }
    result
  }

  /** Returns a list formed from this list and the specified list
   *  <code>that</code> by associating each element of the former with
   *  the element at the same position in the latter.
   *  If one of the two lists is longer than the other, its remaining elements are ignored.
   *
   *  @return     <code>List((a<sub>0</sub>,b<sub>0</sub>), ...,
   *              (a<sub>min(m,n)</sub>,b<sub>min(m,n)</sub>))</code> when
   *              <code>List(a<sub>0</sub>, ..., a<sub>m</sub>)
   *              zip List(b<sub>0</sub>, ..., b<sub>n</sub>)</code> is invoked.
   */
  def zip[B](that: List[B]): List[(A, B)] = {
    val b = new ListBuffer[(A, B)]
    var these = this
    var those = that
    while (!these.isEmpty && !those.isEmpty) {
      b += (these.head, those.head)
      these = these.tail
      those = those.tail
    }
    b.toList
  }

  /** Returns a list that pairs each element of this list
   *  with its index, counting from 0.
   *
   *  @return      the list <code>List((a<sub>0</sub>,0), (a<sub>1</sub>,1), ...)</code>
   *               where <code>a<sub>i</sub></code> are the elements of this list.
   */
  def zipWithIndex: List[(A, Int)] = {
    val b = new ListBuffer[(A, Int)]
    var these = this
    var idx = 0

    while(!these.isEmpty) {
      b += (these.head, idx)
      these = these.tail
      idx += 1
    }

    b.toList
  }

  /** Returns a list formed from this list and the specified list
   *  <code>that</code> by associating each element of the former with
   *  the element at the same position in the latter.
   *
   *  @param that     list <code>that</code> may have a different length
   *                  as the self list.
   *  @param thisElem element <code>thisElem</code> is used to fill up the
   *                  resulting list if the self list is shorter than
   *                  <code>that</code>
   *  @param thatElem element <code>thatElem</code> is used to fill up the
   *                  resulting list if <code>that</code> is shorter than
   *                  the self list
   *  @return         <code>List((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, C >: A, D >: B](that: List[B], thisElem: C, thatElem: D): List[(C, D)] = {
    val b = new ListBuffer[(C, D)]
    var these = this
    var those = that
    while (!these.isEmpty && !those.isEmpty) {
      b += (these.head, those.head)
      these = these.tail
      those = those.tail
    }
    while (!these.isEmpty) {
      b += (these.head, thatElem)
      these = these.tail
    }
    while (!those.isEmpty) {
      b += (thisElem, those.head)
      those = those.tail
    }
    b.toList
  }

  /** Computes the union of this list and the given list
   *  <code>that</code>.
   *
   *  @param that the list of elements to add to the list.
   *  @return     a list without doubles containing the elements of this
   *              list and those of the given list <code>that</code>.
   */
  def union[B >: A](that: List[B]): List[B] = {
    val b = new ListBuffer[B]
    var these = this
    while (!these.isEmpty) {
      if (!that.contains(these.head)) b += these.head
      these = these.tail
    }
    b.prependToList(that)
  }

  /** Computes the difference between this list and the given list
   *  <code>that</code>.
   *
   *  @param that the list of elements to remove from this list.
   *  @return     this list without the elements of the given list
   *              <code>that</code>.
   */
  def diff[B >: A](that: List[B]): List[B] = {
    val b = new ListBuffer[B]
    var these = this
    while (!these.isEmpty) {
      if (!that.contains(these.head)) b += these.head
      these = these.tail
    }
    b.toList
  }
   
  def flatten[B](implicit f : A => Iterable[B]) : List[B] = {
    val buf = new ListBuffer[B]
    foreach(f(_).foreach(buf += _))
    buf.toList
  }
 

  /** Computes the intersection between this list and the given list
   *  <code>that</code>.
   *
   *  @param that the list to intersect.
   *  @return     the list of elements contained both in this list and
   *              in the given list <code>that</code>.
   */
  def intersect[B >: A](that: List[B]): List[B] = filter(x => that contains x)

  /** Removes redundant elements from the list. Uses the method <code>==</code>
   *  to decide if two elements are identical.
   *
   *  @return the list without doubles.
   */
  def removeDuplicates: List[A] = {
    val b = new ListBuffer[A]
    var these = this
    while (!these.isEmpty) {
      if (!these.tail.contains(these.head)) b += these.head
      these = these.tail
    }
    b.toList
  }
   
  override protected def stringPrefix = "List"
  override def projection = toStream
  override def toStream : Stream[A] = new Stream.Definite[A] {
    override def force : List[A] = List.this
    override def isEmpty = List.this.isEmpty
    override def head = List.this.head
    override def tail = List.this.tail.toStream
    protected def addDefinedElems(buf: StringBuilder, prefix: String): StringBuilder = if (!isEmpty) {
      var prefix0 = prefix
      var buf1 = buf.append(prefix0).append(head)
      prefix0 = ", "
      var tail0 = tail
      while (!tail0.isEmpty) {
        buf1 = buf.append(prefix0).append(tail0.head)
        tail0 = tail0.tail
      }
      buf1
    } else buf
  }

}

/** The empty list.
 *
 *  @author  Martin Odersky
 *  @version 1.0, 15/07/2003
 */
@SerialVersionUID(0 - 8256821097970055419L)
case object Nil extends List[Nothing] {
  override def isEmpty = true
  def head: Nothing =
    throw new NoSuchElementException("head of empty list")
  def tail: List[Nothing] =
    throw new NoSuchElementException("tail of empty list")
}

/** A non empty list characterized by a head and a tail.
 *
 *  @author  Martin Odersky
 *  @version 1.0, 15/07/2003
 */
@SerialVersionUID(0L - 8476791151983527571L)
final case class ::[B](private var hd: B, private[scala] var tl: List[B]) extends List[B] {
  def head : B = hd
  def tail : List[B] = tl
  override def isEmpty: Boolean = false
}