/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id: List.scala 16287 2008-10-18 13:41:36Z nielsen $
package scala.collection.immutable
import mutable.ListBuffer
import generic._
/** A class representing an ordered collection of elements of type
* a
. This class comes with two implementing case
* classes scala.Nil
and scala.::
that
* implement the abstract members isEmpty
,
* head
and tail
.
*
* @author Martin Odersky and others
* @version 2.8
*/
sealed abstract class List[@specialized +A] extends LinearSequence[A]
with Product
with TraversableClass[A, List]
with LinearSequenceTemplate[A, List[A]] {
override def companion: Companion[List] = List
import collection.{Iterable, Traversable, Sequence, Vector}
/** Returns true if the list does not contain any elements.
* @return true
, iff the list is empty.
*/
def isEmpty: Boolean
/** Returns this first element of the list.
*
* @return the first element of this list.
* @throws Predef.NoSuchElementException if the list is empty.
*/
def head: A
/** Returns this list without its first element.
*
* @return this list without its first element.
* @throws Predef.NoSuchElementException if the list is empty.
*/
def tail: List[A]
// New methods in List
/**
* Add an element x
at the beginning of this list.
*
x
added at the beginning.
* @ex 1 :: List(2, 3) = List(2, 3).::(1) = List(1, 2, 3)
*/
def ::[@specialized B >: A] (x: B): List[B] =
new scala.collection.immutable.::(x, this)
/**
* Returns a list resulting from the concatenation of the given
* list prefix
and this list.
*
List(1, 2) ::: List(3, 4) = List(3, 4).:::(List(1, 2)) = List(1, 2, 3, 4)
*/
def :::[B >: A](prefix: List[B]): List[B] =
if (isEmpty) prefix
else (new ListBuffer[B] ++= prefix).prependToList(this)
/** Reverse the given prefix and append the current list to that.
* This function is equivalent to an application of reverse
* on the prefix followed by a call to :::
, but is more
* efficient.
*
* @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
}
/** Apply a function to all the elements of the list, and return the
* reversed list of results. This is equivalent to a call to map
* followed by a call to reverse
, but more efficient.
* !!! should we deprecate this? Why have reverseMap, but not filterMap or reverseFilter, say?
* @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)
}
/** Like xs map f, but returns xs
unchanged if function
* f
maps all elements to themselves (wrt ==).
* @note Unlike `map`, `mapConserve` is not tail-recursive.
*/
def mapConserve[B >: A] (f: A => B): List[B] = {
def loop(ys: List[A]): List[B] =
if (ys.isEmpty) this
else {
val head0 = ys.head
val head1 = f(head0)
if (head1 == head0) {
loop(ys.tail)
} else {
val ys1 = head1 :: ys.tail.mapConserve(f)
if (this eq ys) ys1
else {
val b = new ListBuffer[B]
var xc = this
while (xc ne ys) {
b += xc.head
xc = xc.tail
}
b.prependToList(ys1)
}
}
}
loop(this)
}
// Overridden methods from IterableTemplate or overloaded variants of such methods
/** Create a new list which contains all elements of this list
* followed by all elements of Traversable `that'
*/
override def ++[B >: A, That](that: Traversable[B])(implicit bf: BuilderFactory[B, That, List[A]]): That = {
val b = bf(this)
if (b.isInstanceOf[ListBuffer[_]]) (this ::: that.toList).asInstanceOf[That]
else super.++(that)
}
/** Create a new list which contains all elements of this list
* followed by all elements of Iterator `that'
*/
override def ++[B >: A, That](that: Iterator[B])(implicit bf: BuilderFactory[B, That, List[A]]): That =
this ++ that.toList
/** Overrides the method in Iterable for efficiency.
*
* @return the list itself
*/
override def toList: List[A] = this
/** Returns the n
first elements of this list, or else the whole
* list, if it has less than n
elements.
* @param n the number of elements to take.
* @return the n
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 without its n
first elements.
* If this list has less than n
elements, the empty list is returned.
*
* @param n the number of elements to drop.
* @return the list without its n
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 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] = {
var len = end
if (start > 0) len -= start
drop(start) take len
}
/** Returns the rightmost n
elements from this list.
*
* @param n the number of elements to take
* @return the suffix of length n
of the list
*/
override 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)
}
// dropRight is inherited from Stream
/** 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 n
* elements, and the other elements.
*/
override 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 p
.
*
* @param p the test predicate.
* @return the longest prefix of this list whose elements satisfy
* the predicate p
.
*/
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 p
.
*
* @param p the test predicate.
* @return the longest suffix of the list whose first element
* does not satisfy the predicate p
.
*/
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 p
, and the rest of the list.
*/
override 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)
}
/** 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
}
override def stringPrefix = "List"
override def toStream : Stream[A] =
if (isEmpty) Stream.Empty
else new Stream.Cons(head, tail.toStream)
// !!! todo: work in patch
/** Computes the difference between this list and the given list
* that
.
*
* @param that the list of elements to remove from this list.
* @return this list without the elements of the given list
* that
.
*/
@deprecated("use `diff' instead")
def -- [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
}
/** Computes the difference between this list and the given object
* x
.
*
* @param x the object to remove from this list.
* @return this list without occurrences of the given object
* x
.
*/
@deprecated("use `diff' instead")
def - [B >: A](x: B): List[B] = {
val b = new ListBuffer[B]
var these = this
while (!these.isEmpty) {
if (these.head != x) b += these.head
these = these.tail
}
b.toList
}
/**
* Sort the list according to the comparison function
* <(e1: a, e2: a) => Boolean
,
* which should be true iff e1
is smaller than
* e2
.
* !!! todo: move sorting to IterableTemplate
*
<(e1: a, e2: a) => Boolean
.
* @ex * List("Steve", "Tom", "John", "Bob") * .sort((e1, e2) => (e1 compareTo e2) < 0) = * List("Bob", "John", "Steve", "Tom")*/ @deprecated("use `sortWith' instead") 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) } } /** 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 override def head: Nothing = throw new NoSuchElementException("head of empty list") override def tail: List[Nothing] = throw new NoSuchElementException("tail of empty list") override def equals(that: Any) = that match { case that1: Sequence[_] => that1.isEmpty case _ => false } } /** 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 ::[@specialized B](private var hd: B, private[scala] var tl: List[B]) extends List[B] { override def head : B = hd override def tail : List[B] = tl override def isEmpty: Boolean = false import java.io._ private def writeObject(out: ObjectOutputStream) { var xs: List[B] = this while (!xs.isEmpty) { out.writeObject(xs.head); xs = xs.tail } out.writeObject(ListSerializeEnd) } private def readObject(in: ObjectInputStream) { hd = in.readObject.asInstanceOf[B] assert(hd != ListSerializeEnd) var current: ::[B] = this while (true) in.readObject match { case ListSerializeEnd => current.tl = Nil return case a : Any => val list : ::[B] = new ::(a.asInstanceOf[B], Nil) current.tl = list current = list } } } /** This object provides methods for creating specialized lists, and for * transforming special kinds of lists (e.g. lists of lists). * * @author Martin Odersky * @version 2.8 */ object List extends SequenceFactory[List] { import collection.{Iterable, Sequence, Vector} implicit def builderFactory[A]: BuilderFactory[A, List[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, List[A]] = new ListBuffer[A] override def empty[A]: List[A] = Nil override def apply[A](xs: A*): List[A] = xs.toList /** Create a sorted list with element values *
vn+1 = step(vn)
* where v0 = start
* and elements are in the range between start
(inclusive)
* and end
(exclusive)
*
* @param start the start value of the list
* @param end the end value of the list
* @param step the increment function of the list, which given vn
,
* computes vn+1
. Must be monotonically increasing
* or decreasing.
* @return the sorted list of all integers in range [start;end).
*/
@deprecated("use `iterate' instead")
def range(start: Int, end: Int, step: Int => Int): List[Int] = {
val up = step(start) > start
val down = step(start) < start
val b = new ListBuffer[Int]
var i = start
while ((!up || i < end) && (!down || i > end)) {
b += i
val next = step(i)
if (i == next)
throw new IllegalArgumentException("the step function did not make any progress on "+ i)
i = next
}
b.toList
}
/** Create a list containing several copies of an element.
*
* @param n the length of the resulting list
* @param elem the element composing the resulting list
* @return a list composed of n elements all equal to elem
*/
@deprecated("use `fill' instead")
def make[A](n: Int, elem: A): List[A] = {
val b = new ListBuffer[A]
var i = 0
while (i < n) {
b += elem
i += 1
}
b.toList
}
/** Concatenate all the elements of a given list of lists.
*
* @param xss the list of lists that are to be concatenated
* @return the concatenation of all the lists
*/
@deprecated("use `xss.flatten' instead")
def flatten[A](xss: List[List[A]]): List[A] = {
val b = new ListBuffer[A]
for (xs <- xss) {
var xc = xs
while (!xc.isEmpty) {
b += xc.head
xc = xc.tail
}
}
b.toList
}
/** Transforms a list of pairs into a pair of lists.
*
* @param xs the list of pairs to unzip
* @return a pair of lists.
*/
@deprecated("use `xs.unzip' instead")
def unzip[A,B](xs: List[(A,B)]): (List[A], List[B]) = {
val b1 = new ListBuffer[A]
val b2 = new ListBuffer[B]
var xc = xs
while (!xc.isEmpty) {
b1 += xc.head._1
b2 += xc.head._2
xc = xc.tail
}
(b1.toList, b2.toList)
}
/** Transforms an iterable of pairs into a pair of lists.
*
* @param xs the iterable of pairs to unzip
* @return a pair of lists.
*/
@deprecated("use `xs.unzip' instead")
def unzip[A,B](xs: Iterable[(A,B)]): (List[A], List[B]) =
xs.foldRight[(List[A], List[B])]((Nil, Nil)) {
case ((x, y), (xs, ys)) => (x :: xs, y :: ys)
}
/**
* Returns the Left
values in the given Iterable
* of Either
s.
*/
@deprecated("use `Either.lefts' instead")
def lefts[A, B](es: Iterable[Either[A, B]]) =
es.foldRight[List[A]](Nil)((e, as) => e match {
case Left(a) => a :: as
case Right(_) => as
})
/**
* Returns the Right
values in the givenIterable
of Either
s.
*/
@deprecated("use `Either.rights' instead")
def rights[A, B](es: Iterable[Either[A, B]]) =
es.foldRight[List[B]](Nil)((e, bs) => e match {
case Left(_) => bs
case Right(b) => b :: bs
})
/** Transforms an Iterable of Eithers into a pair of lists.
*
* @param xs the iterable of Eithers to separate
* @return a pair of lists.
*/
@deprecated("use `Either.separate' instead")
def separate[A,B](es: Iterable[Either[A,B]]): (List[A], List[B]) =
es.foldRight[(List[A], List[B])]((Nil, Nil)) {
case (Left(a), (lefts, rights)) => (a :: lefts, rights)
case (Right(b), (lefts, rights)) => (lefts, b :: rights)
}
/** Converts an iterator to a list.
*
* @param it the iterator to convert
* @return a list that contains the elements returned by successive
* calls to it.next
*/
@deprecated("use `it.toList' instead")
def fromIterator[A](it: Iterator[A]): List[A] = it.toList
/** Converts an array into a list.
*
* @param arr the array to convert
* @return a list that contains the same elements than arr
* in the same order
*/
@deprecated("use `array.toList' instead")
def fromArray[A](arr: Array[A]): List[A] = fromArray(arr, 0, arr.length)
/** Converts a range of an array into a list.
*
* @param arr the array to convert
* @param start the first index to consider
* @param len the lenght of the range to convert
* @return a list that contains the same elements than arr
* in the same order
*/
@deprecated("use `array.view(start, end).toList' instead")
def fromArray[A](arr: Array[A], start: Int, len: Int): List[A] = {
var res: List[A] = Nil
var i = start + len
while (i > start) {
i -= 1
res = arr(i) :: res
}
res
}
/** Parses a string which contains substrings separated by a
* separator character and returns a list of all substrings.
*
* @param str the string to parse
* @param separator the separator character
* @return the list of substrings
*/
@deprecated("use `str.split(separator).toList' instead")
def fromString(str: String, separator: Char): List[String] = {
var words: List[String] = Nil
var pos = str.length()
while (pos > 0) {
val pos1 = str.lastIndexOf(separator, pos - 1)
if (pos1 + 1 < pos)
words = str.substring(pos1 + 1, pos) :: words
pos = pos1
}
words
}
/** Returns the given string as a list of characters.
*
* @param str the string to convert.
* @return the string as a list of characters.
*/
@deprecated("use `str.toList' instead")
def fromString(str: String): List[Char] = str.toList
/** Returns the given list of characters as a string.
*
* @param xs the list to convert.
* @return the list in form of a string.
*/
@deprecated("use `xs.mkString' instead")
def toString(xs: List[Char]): String = {
val sb = new StringBuilder()
var xc = xs
while (!xc.isEmpty) {
sb.append(xc.head)
xc = xc.tail
}
sb.toString()
}
/** Like xs map f, but returns xs
unchanged if function
* f
maps all elements to themselves.
*/
@deprecated("use `xs.mapConserve(f)' instead")
def mapConserve[A <: AnyRef](xs: List[A])(f: A => A): List[A] = {
def loop(ys: List[A]): List[A] =
if (ys.isEmpty) xs
else {
val head0 = ys.head
val head1 = f(head0)
if (head1 eq head0) {
loop(ys.tail)
} else {
val ys1 = head1 :: mapConserve(ys.tail)(f)
if (xs eq ys) ys1
else {
val b = new ListBuffer[A]
var xc = xs
while (xc ne ys) {
b += xc.head
xc = xc.tail
}
b.prependToList(ys1)
}
}
}
loop(xs)
}
/** Returns the list resulting from applying the given function f
* to corresponding elements of the argument lists.
* @param f function to apply to each pair of elements.
* @return [f(a0,b0), ..., f(an,bn)]
if the lists are
* [a0, ..., ak]
, [b0, ..., bl]
and
* n = min(k,l)
*/
@deprecated("use `(xs, ys).map(f)' instead")
def map2[A,B,C](xs: List[A], ys: List[B])(f: (A, B) => C): List[C] = {
val b = new ListBuffer[C]
var xc = xs
var yc = ys
while (!xc.isEmpty && !yc.isEmpty) {
b += f(xc.head, yc.head)
xc = xc.tail
yc = yc.tail
}
b.toList
}
/** Returns the list resulting from applying the given function
* f
to corresponding elements of the argument lists.
*
* @param f function to apply to each pair of elements.
* @return [f(a0,b0,c0),
* ..., f(an,bn,cn)]
* if the lists are [a0, ..., ak]
,
* [b0, ..., bl]
,
* [c0, ..., cm]
and
* n = min(k,l,m)
*/
@deprecated("use `(xs, ys, zs).map(f)' instead")
def map3[A,B,C,D](xs: List[A], ys: List[B], zs: List[C])(f: (A, B, C) => D): List[D] = {
val b = new ListBuffer[D]
var xc = xs
var yc = ys
var zc = zs
while (!xc.isEmpty && !yc.isEmpty && !zc.isEmpty) {
b += f(xc.head, yc.head, zc.head)
xc = xc.tail
yc = yc.tail
zc = zc.tail
}
b.toList
}
/** Tests whether the given predicate p
holds
* for all corresponding elements of the argument lists.
*
* @param p function to apply to each pair of elements.
* @return (p(a0,b0) &&
* ... && p(an,bn))]
* if the lists are [a0, ..., ak]
;
* [b0, ..., bl]
* and n = min(k,l)
*/
@deprecated("use `(xs, ys).forall(f)' instead")
def forall2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = {
var xc = xs
var yc = ys
while (!xc.isEmpty && !yc.isEmpty) {
if (!f(xc.head, yc.head)) return false
xc = xc.tail
yc = yc.tail
}
true
}
/** Tests whether the given predicate p
holds
* for some corresponding elements of the argument lists.
*
* @param p function to apply to each pair of elements.
* @return n != 0 && (p(a0,b0) ||
* ... || p(an,bn))]
if the lists are
* [a0, ..., ak]
,
* [b0, ..., bl]
and
* n = min(k,l)
*/
@deprecated("use `(xs, ys).exists(f)' instead")
def exists2[A,B](xs: List[A], ys: List[B])(f: (A, B) => Boolean): Boolean = {
var xc = xs
var yc = ys
while (!xc.isEmpty && !yc.isEmpty) {
if (f(xc.head, yc.head)) return true
xc = xc.tail
yc = yc.tail
}
false
}
/** Transposes a list of lists.
* pre: All element lists have the same length.
*
* @param xss the list of lists
* @return the transposed list of lists
*/
@deprecated("use p`xss.transpose' instead")
def transpose[A](xss: List[List[A]]): List[List[A]] = {
val buf = new ListBuffer[List[A]]
var yss = xss
while (!yss.head.isEmpty) {
buf += (yss map (_.head))
yss = (yss map (_.tail))
}
buf.toList
}
/** Lists with ordered elements are ordered
implicit def list2ordered[a <% Ordered[a]](x: List[a]): Ordered[List[a]] = new Ordered[List[a]] {
def compare [b >: List[a] <% Ordered[b]](y: b): Int = y match {
case y1: List[a] => compareLists(x, y1);
case _ => -(y compare x)
}
private def compareLists(xs: List[a], ys: List[a]): Int = {
if (xs.isEmpty && ys.isEmpty) 0
else if (xs.isEmpty) -1
else if (ys.isEmpty) 1
else {
val s = xs.head compare ys.head;
if (s != 0) s
else compareLists(xs.tail, ys.tail)
}
}
}
*/
}
/** Only used for list serialization */
@SerialVersionUID(0L - 8476791151975527571L)
private[scala] case object ListSerializeEnd