From 21e90dfb5958bd5a8030a6edf16b38518e2d69e5 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Fri, 10 Jun 2011 18:42:56 +0000 Subject: Compilation of spec-List enters an infinite loo... Compilation of spec-List enters an infinite loop under -optimise, disabling in the hopes of seeing a new build before I die. I'll put it back. No review. --- test/disabled/pos/spec-List.scala | 869 ++++++++++++++++++++++++++++++++++++++ test/files/pos/spec-List.scala | 869 -------------------------------------- 2 files changed, 869 insertions(+), 869 deletions(-) create mode 100644 test/disabled/pos/spec-List.scala delete mode 100644 test/files/pos/spec-List.scala diff --git a/test/disabled/pos/spec-List.scala b/test/disabled/pos/spec-List.scala new file mode 100644 index 0000000000..04ab7d1543 --- /dev/null +++ b/test/disabled/pos/spec-List.scala @@ -0,0 +1,869 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + + +package scala.collection +package immutable + +import generic._ +import mutable.{Builder, ListBuffer} +import annotation.tailrec + +/** 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 trait List[@specialized +A] extends LinearSeq[A] + with Product + with GenericTraversableTemplate[A, List] + with LinearSeqOptimized[A, List[A]] { + override def companion: GenericCompanion[List] = List + + import scala.collection.{Iterable, Traversable, Seq} + + /** 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. + *

+ * + * @param x the element to prepend. + * @return the list with 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. + *

+ * + * @param prefix the list to concatenate at the beginning of this list. + * @return the concatenation of the two lists. + * @ex 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] = { + @tailrec + 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 IterableLike 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](xs: GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That = { + val b = bf(this) + if (b.isInstanceOf[ListBuffer[_]]) (this ::: xs.toList).asInstanceOf[That] + else super.++(xs) + } + + /** 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] = { + @tailrec + 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] = { + @tailrec + def loop(xs: List[A]): List[A] = + if (xs.isEmpty || !p(xs.head)) xs + else loop(xs.tail) + + loop(this) + } + + /** 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 IterableLike + *

+ * + * @param lt the comparison function + * @return a list sorted according to the comparison function + * <(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") + // Removal of equals method here might lead to an infinite recusion similar to IntMap.equals. + override def equals(that: Any) = that match { + case that1: Seq[_] => 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 SeqFactory[List] { + + import collection.{Iterable, Seq} + + implicit def builderFactory[A]: CanBuildFrom[Coll, A, List[A]] = + new GenericCanBuildFrom[A] { + override def apply() = newBuilder[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 Eithers. + */ + @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 Eithers. + */ + @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 length 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 + diff --git a/test/files/pos/spec-List.scala b/test/files/pos/spec-List.scala deleted file mode 100644 index 04ab7d1543..0000000000 --- a/test/files/pos/spec-List.scala +++ /dev/null @@ -1,869 +0,0 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - - -package scala.collection -package immutable - -import generic._ -import mutable.{Builder, ListBuffer} -import annotation.tailrec - -/** 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 trait List[@specialized +A] extends LinearSeq[A] - with Product - with GenericTraversableTemplate[A, List] - with LinearSeqOptimized[A, List[A]] { - override def companion: GenericCompanion[List] = List - - import scala.collection.{Iterable, Traversable, Seq} - - /** 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. - *

- * - * @param x the element to prepend. - * @return the list with 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. - *

- * - * @param prefix the list to concatenate at the beginning of this list. - * @return the concatenation of the two lists. - * @ex 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] = { - @tailrec - 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 IterableLike 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](xs: GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That = { - val b = bf(this) - if (b.isInstanceOf[ListBuffer[_]]) (this ::: xs.toList).asInstanceOf[That] - else super.++(xs) - } - - /** 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] = { - @tailrec - 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] = { - @tailrec - def loop(xs: List[A]): List[A] = - if (xs.isEmpty || !p(xs.head)) xs - else loop(xs.tail) - - loop(this) - } - - /** 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 IterableLike - *

- * - * @param lt the comparison function - * @return a list sorted according to the comparison function - * <(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") - // Removal of equals method here might lead to an infinite recusion similar to IntMap.equals. - override def equals(that: Any) = that match { - case that1: Seq[_] => 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 SeqFactory[List] { - - import collection.{Iterable, Seq} - - implicit def builderFactory[A]: CanBuildFrom[Coll, A, List[A]] = - new GenericCanBuildFrom[A] { - override def apply() = newBuilder[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 Eithers. - */ - @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 Eithers. - */ - @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 length 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 - -- cgit v1.2.3