Merged revisions 22114,22141-22142,22196,22486-...

Merged revisions
22114,22141-22142,22196,22486-22487,22526-22527,22869,22871 via svnmerge
from https://lampsvn.epfl.ch/svn-repos/scala/scala/trunk

........
  r22114 | prokopec | 2010-06-01 18:15:40 +0200 (Tue, 01 Jun 2010) | 1 line

  Fixes #3496. No review.
........
  r22141 | prokopec | 2010-06-02 18:31:56 +0200 (Wed, 02 Jun 2010) | 4 lines

  Partially solves the problem for #3502. review by extempore

  This commit reimplements filter for Streams, but does not reimplement
map in StreamWithFilter.

  The problem is that GC can't collect instances of Streams residing on the stack if there are multiple references to the Stream (more than a single one on the stack on which a Stream method is invoked). In the case of a StreamWithFilter, being an inner class, there is always an `$outer` reference to the outer object, so there is little GC can do. Possible solution - change the return type of WithFilter to something else (in TraversableLike) to allow it to return objects that don't have to subclass TraversableLike.WithFilter, and reimplement the withFilter method in Stream to simply call `filter` method - in the case of Streams, `withFilter` has little sense in either case...
........
  r22142 | prokopec | 2010-06-02 19:09:39 +0200 (Wed, 02 Jun 2010) | 1 line

  Fixes #3508. No review is necessary.
........
  r22196 | prokopec | 2010-06-08 18:17:58 +0200 (Tue, 08 Jun 2010) | 1 line

  Fixes #3461. No review.p
........
  r22486 | prokopec | 2010-07-05 11:25:39 +0200 (Mon, 05 Jul 2010) | 1 line

  Fixes #3580. Review by extempore.
........
  r22487 | prokopec | 2010-07-05 12:08:32 +0200 (Mon, 05 Jul 2010) | 1 line

  Fixes #3584. No review.
........
  r22526 | prokopec | 2010-07-09 13:31:34 +0200 (Fri, 09 Jul 2010) | 1 line

  closes #3603. no review
........
  r22527 | prokopec | 2010-07-09 17:06:01 +0200 (Fri, 09 Jul 2010) | 1 line

  Closes #3493. Review by extempore.
........
  r22869 | prokopec | 2010-08-31 12:29:42 +0200 (Tue, 31 Aug 2010) | 1 line

  Fixes #3684. Closes #3684. No review.
........
  r22871 | prokopec | 2010-08-31 13:27:46 +0200 (Tue, 31 Aug 2010) | 1 line

  Fix for #3684. No review
........

8 files changed, 110 insertions, 62 deletions

diff --git a/src/library/scala/collection/IterableLike.scala b/src/library/scala/collection/IterableLike.scala
index da18c712f5..538fd09c0e 100644
--- a/src/library/scala/collection/IterableLike.scala
+++ b/src/library/scala/collection/IterableLike.scala
@@ -158,7 +158,8 @@ self =>
    *  @param step the distance between the first elements of successive
    *         groups (defaults to 1)
    *  @return An iterator producing ${coll}s of size `size`, except the
-   *          last will be truncated if the elements don't divide evenly.
+   *          last and the only element will be truncated if there are
+   *          fewer elements than size.
    */
   def sliding[B >: A](size: Int): Iterator[Repr] = sliding(size, 1)
   def sliding[B >: A](size: Int, step: Int): Iterator[Repr] =
diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala
index 2169dcdd02..6f851fb5e7 100644
--- a/src/library/scala/collection/TraversableLike.scala
+++ b/src/library/scala/collection/TraversableLike.scala
@@ -698,7 +698,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr]
 
   def toTraversable: Traversable[A] = thisCollection
   def toIterator: Iterator[A] = toStream.iterator
-  def toStream: Stream[A] = Stream.empty[A] ++ thisCollection
+  def toStream: Stream[A] = toBuffer.toStream
 
   /** Converts this $coll to a string.
    *  @return   a string representation of this collection. By default this
diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala
index ba5cd896ac..d4605d3e1f 100644
--- a/src/library/scala/collection/immutable/IntMap.scala
+++ b/src/library/scala/collection/immutable/IntMap.scala
@@ -11,6 +11,14 @@
 package scala.collection
 package immutable;
 
+
+
+import scala.collection.generic.CanBuildFrom
+import scala.collection.mutable.Builder
+import scala.collection.mutable.MapBuilder
+
+
+
 /** Utility class for integer maps.
  *  @author David MacIver
  */
@@ -53,6 +61,12 @@ import IntMapUtils._
  *  @since 2.7
  */
 object IntMap {
+  /** $mapCanBuildFromInfo */
+  implicit def canBuildFrom[A, B] = new CanBuildFrom[IntMap[A], (Int, B), IntMap[B]] {
+    def apply(from: IntMap[A]): Builder[(Int, B), IntMap[B]] = apply()
+    def apply(): Builder[(Int, B), IntMap[B]] = new MapBuilder[Int, B, IntMap[B]](empty[B])
+  }
+
   def empty[T] : IntMap[T]  = IntMap.Nil;
   def singleton[T](key : Int, value : T) : IntMap[T] = IntMap.Tip(key, value);
   def apply[T](elems : (Int, T)*) : IntMap[T] =
@@ -147,7 +161,7 @@ import IntMap._
 
 /** Specialised immutable map structure for integer keys, based on
  *  <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Integer Maps</a>
- *  by Okasaki and Gill. Essentially a trie based on binary digits of the the integers.
+ *  by Okasaki and Gill. Essentially a trie based on binary digits of the integers.
  *
  *  Note: This class is as of 2.8 largely superseded by HashMap.
  *
diff --git a/src/library/scala/collection/immutable/LongMap.scala b/src/library/scala/collection/immutable/LongMap.scala
index 691a81d9f0..dcdc6e948f 100644
--- a/src/library/scala/collection/immutable/LongMap.scala
+++ b/src/library/scala/collection/immutable/LongMap.scala
@@ -1,6 +1,23 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2010, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+
+
 package scala.collection
 package immutable
 
+
+import scala.collection.generic.CanBuildFrom
+import scala.collection.mutable.Builder
+import scala.collection.mutable.MapBuilder
+
+
+
 /** Utility class for long maps.
  *  @author David MacIver
  */
@@ -44,6 +61,12 @@ import LongMapUtils._
  *  @since 2.7
  */
 object LongMap{
+  /** $mapCanBuildFromInfo */
+  implicit def canBuildFrom[A, B] = new CanBuildFrom[LongMap[A], (Long, B), LongMap[B]] {
+    def apply(from: LongMap[A]): Builder[(Long, B), LongMap[B]] = apply()
+    def apply(): Builder[(Long, B), LongMap[B]] = new MapBuilder[Long, B, LongMap[B]](empty[B])
+  }
+
   def empty[T] : LongMap[T]  = LongMap.Nil;
   def singleton[T](key : Long, value : T) : LongMap[T] = LongMap.Tip(key, value);
   def apply[T](elems : (Long, T)*) : LongMap[T] =
@@ -136,7 +159,7 @@ import LongMap._;
 /**
  *  Specialised immutable map structure for long keys, based on
  *  <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Long Maps</a>
- *  by Okasaki and Gill. Essentially a trie based on binary digits of the the integers.
+ *  by Okasaki and Gill. Essentially a trie based on binary digits of the integers.
  *
  *  Note: This class is as of 2.8 largely superseded by HashMap.
  *
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala
index 7e363a7e96..7660a1e2c8 100644
--- a/src/library/scala/collection/immutable/Stream.scala
+++ b/src/library/scala/collection/immutable/Stream.scala
@@ -15,6 +15,8 @@ import generic._
 import mutable.{Builder, StringBuilder, LazyBuilder, ListBuffer}
 import scala.annotation.tailrec
 
+
+
 /** The class `Stream` implements lazy lists where elements
  *  are only evaluated when they are needed. Here is an example:
  *
@@ -201,11 +203,14 @@ self =>
    *  @param p the predicate used to filter the stream.
    *  @return the elements of this stream satisfying <code>p</code>.
    */
-  override final def filter(p: A => Boolean): Stream[A] = {
+  override def filter(p: A => Boolean): Stream[A] = {
     // optimization: drop leading prefix of elems for which f returns false
-    var rest = this dropWhile (!p(_))
-    if (rest.isEmpty) Stream.Empty
-    else new Stream.Cons(rest.head, rest.tail filter p)
+    // var rest = this dropWhile (!p(_)) - forget DRY principle - GC can't collect otherwise
+    var rest = this
+    while (!rest.isEmpty && !p(rest.head)) rest = rest.tail
+    // private utility func to avoid `this` on stack (would be needed for the lazy arg)
+    if (rest.nonEmpty) Stream.filteredTail(rest, p)
+    else Stream.Empty
   }
 
   override final def withFilter(p: A => Boolean): StreamWithFilter = new StreamWithFilter(p)
@@ -213,6 +218,7 @@ self =>
   /** A lazier implementation of WithFilter than TraversableLike's.
    */
   final class StreamWithFilter(p: A => Boolean) extends WithFilter(p) {
+
     override def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = {
       def tailMap = asStream[B](tail withFilter p map f)
       asThat[That](
@@ -344,6 +350,8 @@ self =>
     if (n <= 0 || isEmpty) Stream.Empty
     else new Stream.Cons(head, if (n == 1) Stream.empty else tail take (n-1))
 
+  override def splitAt(n: Int): (Stream[A], Stream[A]) = (take(n), drop(n))
+
   /** A substream starting at index `from`
    *  and extending up to (but not including) index `until`.
    *
@@ -601,8 +609,8 @@ object Stream extends SeqFactory[Stream] {
     if (n <= 0) Empty else new Cons(elem, fill(n-1)(elem))
 
   override def tabulate[A](n: Int)(f: Int => A): Stream[A] = {
-    def loop(i: Int) =
-      if (i >= n) Empty else new Cons(f(i), tabulate(i+1)(f))
+    def loop(i: Int): Stream[A] =
+      if (i >= n) Empty else new Cons(f(i), loop(i+1))
     loop(0)
   }
 
@@ -610,6 +618,10 @@ object Stream extends SeqFactory[Stream] {
     if (if (step < 0) start <= end else end <= start) Empty
     else new Cons(start, range(start + step, end, step))
 
+  private[immutable] def filteredTail[A](stream: Stream[A], p: A => Boolean) = {
+    new Stream.Cons(stream.head, stream.tail filter p)
+  }
+
   /** A stream containing all elements of a given iterator, in the order they are produced.
    *  @param it   The iterator producing the stream's elements
    */
diff --git a/src/library/scala/collection/mutable/ArrayBuilder.scala b/src/library/scala/collection/mutable/ArrayBuilder.scala
index 5199fb9051..ec1351f671 100644
--- a/src/library/scala/collection/mutable/ArrayBuilder.scala
+++ b/src/library/scala/collection/mutable/ArrayBuilder.scala
@@ -63,9 +63,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
@@ -128,9 +127,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
@@ -193,9 +191,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
@@ -258,9 +255,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
@@ -323,9 +319,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
@@ -388,9 +383,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
@@ -453,9 +447,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
@@ -518,9 +511,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
@@ -583,9 +575,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
@@ -648,9 +639,8 @@ object ArrayBuilder {
     }
 
     private def ensureSize(size: Int) {
-      if (capacity == 0) resize(16)
-      if (capacity < size) {
-        var newsize = capacity * 2
+      if (capacity < size || capacity == 0) {
+        var newsize = if (capacity == 0) 16 else capacity * 2
         while (newsize < size) newsize *= 2
         resize(newsize)
       }
diff --git a/src/library/scala/runtime/ScalaRunTime.scala b/src/library/scala/runtime/ScalaRunTime.scala
index a1d15c4b7d..a8cb2340ff 100644
--- a/src/library/scala/runtime/ScalaRunTime.scala
+++ b/src/library/scala/runtime/ScalaRunTime.scala
@@ -235,6 +235,12 @@ object ScalaRunTime {
    *
    */
   def stringOf(arg: Any): String = {
+    import collection.{SortedSet, SortedMap}
+    def mapTraversable(x: Traversable[_], f: Any => String) = x match {
+      case ss: SortedSet[_] => ss.map(f)
+      case ss: SortedMap[_, _] => ss.map(f)
+      case _ => x.map(f)
+    }
     def inner(arg: Any): String = arg match {
       case null                     => "null"
       // Node extends NodeSeq extends Seq[Node] strikes again
@@ -252,7 +258,7 @@ object ScalaRunTime {
         // exception if you call iterator.  What a world.
         // And they can't be infinite either.
         if (x.getClass.getName startsWith "scala.tools.nsc.io") x.toString
-        else (x map inner) mkString (x.stringPrefix + "(", ", ", ")")
+        else (mapTraversable(x, inner)) mkString (x.stringPrefix + "(", ", ", ")")
       case x                        => x toString
     }
     val s = inner(arg)
diff --git a/src/library/scala/util/Random.scala b/src/library/scala/util/Random.scala
index 69cb4bb48d..53e721dcda 100644
--- a/src/library/scala/util/Random.scala
+++ b/src/library/scala/util/Random.scala
@@ -17,6 +17,8 @@ import collection.immutable.List
  *
  */
 class Random(val self: java.util.Random) {
+  import collection.mutable.ArrayBuffer
+  import collection.generic.CanBuildFrom
 
   /** Creates a new random number generator using a single long seed. */
   def this(seed: Long) = this(new java.util.Random(seed))
@@ -97,27 +99,6 @@ class Random(val self: java.util.Random) {
   }
 
   def setSeed(seed: Long) { self.setSeed(seed) }
-}
-
-/** The object <code>Random</code> offers a default implementation
- *  of scala.util.Random and random-related convenience methods.
- *
- *  @since 2.8
- */
-object Random extends Random {
-  import collection.mutable.ArrayBuffer
-  import collection.generic.CanBuildFrom
-
-  /** Returns a Stream of pseudorandomly chosen alphanumeric characters,
-   *  equally chosen from A-Z, a-z, and 0-9.
-   *
-   *  @since 2.8
-   */
-  def alphanumeric: Stream[Char] = {
-    def isAlphaNum(c: Char) = (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')
-
-    Stream continually nextPrintableChar filter isAlphaNum
-  }
 
   /** Returns a new collection of the same type in a randomly chosen order.
    *
@@ -140,4 +121,25 @@ object Random extends Random {
 
     bf(xs) ++= buf result
   }
+
+}
+
+/** The object <code>Random</code> offers a default implementation
+ *  of scala.util.Random and random-related convenience methods.
+ *
+ *  @since 2.8
+ */
+object Random extends Random {
+
+  /** Returns a Stream of pseudorandomly chosen alphanumeric characters,
+   *  equally chosen from A-Z, a-z, and 0-9.
+   *
+   *  @since 2.8
+   */
+  def alphanumeric: Stream[Char] = {
+    def isAlphaNum(c: Char) = (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')
+
+    Stream continually nextPrintableChar filter isAlphaNum
+  }
+
 }