list.scala

JAVA 语言的函数式编程扩展

   */
  def tail: List[A]

  /** <p>
   *    Add an element <code>x</code> at the beginning of this list.
   *  </p>
   *
   *  @param x the element to append.
   *  @return  the list with <code>x</code> appended at the beginning.
   *  @ex <code>1 :: List(2, 3) = List(2, 3).::(1) = List(1, 2, 3)</code>
   */
  def ::[B >: A] (x: B): List[B] =
    new scala.::(x, this)

  /** <p>
   *    Returns a list resulting from the concatenation of the given
   *    list <code>prefix</code> and this list. 
   *  </p>
   *
   *  @param prefix the list to concatenate at the beginning of this list.
   *  @return the concatenation of the two lists.
   *  @ex <code>List(1, 2) ::: List(3, 4) = List(3, 4).:::(List(1, 2)) = List(1, 2, 3, 4)</code>
   */
  def :::[B >: A](prefix: List[B]): List[B] =
    if (isEmpty) prefix
    else {
      val b = new ListBuffer[B]
      var those = prefix
      while (!those.isEmpty) {
        b += those.head
        those = those.tail
      }
      b.prependToList(this)
    }

  /** Reverse the given prefix and append the current list to that.
   *  This function is equivalent to an application of <code>reverse</code>
   *  on the prefix followed by a call to <code>:::</code>, but more
   *  efficient (and tail recursive).
   *
   *  @param prefix the prefix to reverse and then prepend
   *  @return       the concatenation of the reversed prefix and the current list.
   */
  def reverse_:::[B >: A](prefix: List[B]): List[B] = {
    var these: List[B] = this
    var pres = prefix
    while (!pres.isEmpty) {
      these = pres.head :: these
      pres = pres.tail
    }
    these
  }

  /** Returns the number of elements in the list.
   *
   *  @return the number of elements in the list.
   */
  def length: Int = {
    var these = this
    var len = 0
    while (!these.isEmpty) {
      len += 1
      these = these.tail
    }
    len
  }

  /** Creates a list with all indices in the list. This is
   *  equivalent to a call to <code>List.range(0, xs.length)</code>.
   *
   *  @return a list of all indices in the list.
   */
  def indices: List[Int] = {
    val b = new ListBuffer[Int]
    var i = 0
    var these = this
    while (!these.isEmpty) {
      b += i
      i += 1
      these = these.tail
    }
    b.toList
  }
 
  /** Returns the elements in the list as an iterator
   *
   *  @return an iterator on the list elements.
   */
  override def elements: Iterator[A] = new Iterator[A] {
    var these = List.this
    def hasNext: Boolean = !these.isEmpty
    def next: A =
      if (!hasNext)
        throw new NoSuchElementException("next on empty Iterator")
      else {
        val result = these.head; these = these.tail; result
      }
    override def toList: List[A] = these
  }

  /** Overrides the method in Iterable for efficiency.
   *
   *  @return  the list itself
   */
  override def toList: List[A] = this

  /** Returns the list without its last element.
   *
   *  @return the list without its last element.
   *  @throws Predef.UnsupportedOperationException if the list is empty.
   */
  def init: List[A] =
    if (isEmpty) throw new UnsupportedOperationException("Nil.init")
    else {
      val b = new ListBuffer[A]
      var elem = head
      var next = tail
      while (!next.isEmpty) {
        b += elem
        elem = next.head
        next = next.tail
      }
      b.toList
    }

  /** Returns the last element of this list.
   *
   *  @return the last element of the list.
   *  @throws Predef.UnsupportedOperationException if the list is empty.
   */
  override def last: A =
    if (isEmpty) throw new Predef.NoSuchElementException("Nil.last")
    else {
      var cur = this
      var next = this.tail
      while (!next.isEmpty) {
        cur = next
        next = next.tail
      }
      cur.head
    }

  /** Returns the <code>n</code> first elements of this list, or else the whole 
   *  list, if it has less than <code>n</code> elements.
   *
   *  @param n the number of elements to take.
   *  @return the <code>n</code> first elements of this list.
   */
  override def take(n: Int): List[A] = {
    val b = new ListBuffer[A]
    var i = 0
    var these = this
    while (!these.isEmpty && i < n) {
      i += 1
      b += these.head
      these = these.tail
    }
    if (these.isEmpty) this
    else b.toList
  }

  /** Returns the list with elements belonging to the given index range.
   *
   *  @param start the start position of the list slice.
   *  @param end   the end position (exclusive) of the list slice.
   *  @return the list with elements belonging to the given index range.
   */
  override def slice(start: Int, end: Int): List[A] = {
    val s = start max 0
    val e = end min this.length
    drop(s) take (e - s)
  }

  /** Returns the list without its <code>n</code> first elements.
   *  If this list has less than <code>n</code> elements, the empty list is returned.
   *
   *  @param n the number of elements to drop.
   *  @return the list without its <code>n</code> first elements.
   */
  override def drop(n: Int): List[A] = {
    var these = this
    var count = n
    while (!these.isEmpty && count > 0) {
      these = these.tail
      count -= 1
    }
    these
  }

  /** Returns the rightmost <code>n</code> elements from this list.
   *
   *  @param n the number of elements to take
   *  @return the suffix of length <code>n</code> of the list
   */
  def takeRight(n: Int): List[A] = {
    def loop(lead: List[A], lag: List[A]): List[A] = lead match {
      case Nil => lag
      case _ :: tail => loop(tail, lag.tail)
    }
    loop(drop(n), this)
  }

  /** Returns the list wihout its rightmost <code>n</code> elements.
   *
   *  @param n the number of elements to take
   *  @return the suffix of length <code>n</code> of the list
   */
  def dropRight(n: Int): List[A] = {
    def loop(lead: List[A], lag: List[A]): List[A] = lead match {
      case Nil => Nil
      case _ :: tail => lag.head :: loop(tail, lag.tail)
    }
    loop(drop(n), this)
  }

  /** Split the list at a given point and return the two parts thus
   *  created.
   *
   *  @param n the position at which to split
   *  @return  a pair of lists composed of the first <code>n</code>
   *           elements, and the other elements.
   */
  def splitAt(n: Int): (List[A], List[A]) = {
    val b = new ListBuffer[A]
    var i = 0
    var these = this
    while (!these.isEmpty && i < n) {
      i += 1
      b += these.head
      these = these.tail
    }
    (b.toList, these)
  }

  /** Returns the longest prefix of this list whose elements satisfy
   *  the predicate <code>p</code>.
   *
   *  @param p the test predicate.
   *  @return  the longest prefix of this list whose elements satisfy
   *           the predicate <code>p</code>.
   */
  override def takeWhile(p: A => Boolean): List[A] = {
    val b = new ListBuffer[A]
    var these = this
    while (!these.isEmpty && p(these.head)) {
      b += these.head
      these = these.tail
    }
    b.toList
  }

  /** Returns the longest suffix of this list whose first element
   *  does not satisfy the predicate <code>p</code>.
   *
   *  @param p the test predicate.
   *  @return  the longest suffix of the list whose first element
   *           does not satisfy the predicate <code>p</code>.
   */
  override def dropWhile(p: A => Boolean): List[A] =
    if (isEmpty || !p(head)) this
    else tail dropWhile p

  /** Returns the longest prefix of the list whose elements all satisfy
   *  the given predicate, and the rest of the list.
   *
   *  @param p the test predicate
   *  @return  a pair consisting of the longest prefix of the list whose
   *           elements all satisfy <code>p</code>, and the rest of the list.
   */
  def span(p: A => Boolean): (List[A], List[A]) = {
    val b = new ListBuffer[A]
    var these = this
    while (!these.isEmpty && p(these.head)) {
      b += these.head
      these = these.tail
    }
    (b.toList, these)
  }

  /** Like <code>span</code> but with the predicate inverted.
   */
  def break(p: A => Boolean): (List[A], List[A]) = span { x => !p(x) }

  /** Returns the <code>n</code>-th element of this list. The first element
   *  (head of the list) is at position 0.
   *
   *  @param n index of the element to return
   *  @return  the element at position <code>n</code> in this list.
   *  @throws Predef.NoSuchElementException if the list is too short.
   */
  def apply(n: Int): A = drop(n).head

  /** Returns the list resulting from applying the given function <code>f</code> to each
   *  element of this list.
   *
   *  @param f function to apply to each element.
   *  @return <code>[f(a0), ..., f(an)]</code> if this list is <code>[a0, ..., an]</code>.
   */
  final override def map[B](f: A => B): List[B] = {
    val b = new ListBuffer[B]
    var these = this
    while (!these.isEmpty) {
      b += f(these.head)
      these = these.tail
    }
    b.toList
  }

  /** Apply a function to all the elements of the list, and return the
   *  reversed list of results. This is equivalent to a call to <code>map</code>
   *  followed by a call to <code>reverse</code>, but more efficient.
   *
   *  @param f the function to apply to each elements.
   *  @return  the reversed list of results.
   */
  def reverseMap[B](f: A => B): List[B] = {
    def loop(l: List[A], res: List[B]): List[B] = l match {
      case Nil => res
      case head :: tail => loop(tail, f(head) :: res)
    }
    loop(this, Nil)
  }

  /** Apply the given function <code>f</code> to each element of this list
   *  (while respecting the order of the elements).
   *
   *  @param f the treatment to apply to each element.
   */
  final override def foreach(f: A => Unit) {
    var these = this
    while (!these.isEmpty) {
      f(these.head)
      these = these.tail
    }
  }

  /** Returns all the elements of this list that satisfy the
   *  predicate <code>p</code>. The order of the elements is preserved.
   *  It is guarenteed that the receiver list itself is returned iff all its
   *  elements satisfy the predicate `p'. Hence the following equality is valid:
   *
   *  (xs filter p) eq xs  ==  xs forall p
   *
   *  @param p the predicate used to filter the list.
   *  @return the elements of this list satisfying <code>p</code>.
   */
  final override def filter(p: A => Boolean): List[A] = {
    // return same list if all elements satisfy p
    var these = this
    while (!these.isEmpty && p(these.head)) {
      these = these.tail
    }
    if (these.isEmpty) this
    else {
      val b = new ListBuffer[A]
      var these1 = this
      while (these1 ne these) {
        b += these1.head
        these1 = these1.tail
      }

      these = these.tail // prevent the second evaluation of the predicate
                         // on the element on which it first failed
      while (!these.isEmpty) {
        if (p(these.head)) b += these.head
        these = these.tail
      }
      b.toList
    }
  }

//  final def filterMap[B](f: PartialFunction[A, B]): List[B] = 
//    this filter f.isDefinedAt map f

  /** Removes all elements of the list 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 list without all elements which satisfy <code>p</code>
   */
  def remove(p: A => Boolean): List[A] = filter (x => !p(x))

  /** Partition the list in two sub-lists according to a predicate.
   *
   *  @param p the predicate on which to partition
   *  @return  a pair of lists: the list of all elements which satisfy
   *           <code>p</code> and the list of all elements which do not.
   *           The relative order of the elements in the sub-lists is the
   *           same as in the original list.
   */
  override def partition(p: A => Boolean): (List[A], List[A]) = {
    val btrue = new ListBuffer[A]
    val bfalse = new ListBuffer[A]
    var these = this
    while (!these.isEmpty) {
      (if (p(these.head)) btrue else bfalse) += these.head
      these = these.tail
    }
    (btrue.toList, bfalse.toList)
  }

  /** <p>
   *    Sort the list 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>. 
   *  </p>
   *
   *  @param lt the comparison function
   *  @return   a list 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) =