Added sizeHints to operations where it made sense.

5 files changed, 54 insertions, 2 deletions

diff --git a/src/library/scala/Tuple2.scala b/src/library/scala/Tuple2.scala
index 5dec39a79b..fb685096a3 100644
--- a/src/library/scala/Tuple2.scala
+++ b/src/library/scala/Tuple2.scala
@@ -12,7 +12,7 @@
 
 package scala
 
-import scala.collection.{TraversableLike, IterableLike}
+import scala.collection.{TraversableLike, IterableLike, IndexedSeqLike}
 import scala.collection.generic.CanBuildFrom
 
 
@@ -55,8 +55,8 @@ case class Tuple2[@specialized(Int, Long, Double) +T1, @specialized(Int, Long, D
   class Zipped[+Repr1, +El1, +Repr2, +El2](coll1: TraversableLike[El1, Repr1], coll2: IterableLike[El2, Repr2]) { // coll2: IterableLike for filter
     def map[B, To](f: (El1, El2) => B)(implicit cbf: CanBuildFrom[Repr1, B, To]): To = {
       val b = cbf(coll1.repr)
+      b.sizeHint(coll1)
       val elems2 = coll2.iterator
-
       for(el1 <- coll1)
        if(elems2.hasNext)
          b += f(el1, elems2.next)
diff --git a/src/library/scala/collection/IterableLike.scala b/src/library/scala/collection/IterableLike.scala
index 0efc756b10..06909961ce 100644
--- a/src/library/scala/collection/IterableLike.scala
+++ b/src/library/scala/collection/IterableLike.scala
@@ -104,6 +104,7 @@ self =>
 
   override /*TraversableLike*/ def take(n: Int): Repr = {
     val b = newBuilder
+    b.sizeHintBounded(n, this)
     var i = 0
     val it = iterator
     while (i < n && it.hasNext) {
@@ -115,6 +116,7 @@ self =>
 
   override /*TraversableLike*/ def slice(from: Int, until: Int): Repr = {
     val b = newBuilder
+    b.sizeHintBounded(until - from, this)
     var i = from
     val it = iterator drop from
     while (i < until && it.hasNext) {
@@ -176,6 +178,7 @@ self =>
    */
   def takeRight(n: Int): Repr = {
     val b = newBuilder
+    b.sizeHintBounded(n, this)
     val lead = this.iterator drop n
     var go = false
     for (x <- this) {
@@ -195,6 +198,7 @@ self =>
    */
   def dropRight(n: Int): Repr = {
     val b = newBuilder
+    if (n >= 0) b.sizeHint(this, -n)
     val lead = iterator drop n
     val it = iterator
     while (lead.hasNext) {
diff --git a/src/library/scala/collection/SeqLike.scala b/src/library/scala/collection/SeqLike.scala
index d80539d0b0..2774536886 100644
--- a/src/library/scala/collection/SeqLike.scala
+++ b/src/library/scala/collection/SeqLike.scala
@@ -378,6 +378,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self =>
     for (x <- this)
       xs = x :: xs
     val b = newBuilder
+    b.sizeHint(this)
     for (x <- xs)
       b += x
     b.result
@@ -827,6 +828,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self =>
     }
     java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]])
     val b = newBuilder
+    b.sizeHint(this)
     for (x <- arr) b += x
     b.result
   }
diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala
index 4c8d34622e..02777a5daa 100644
--- a/src/library/scala/collection/TraversableLike.scala
+++ b/src/library/scala/collection/TraversableLike.scala
@@ -179,6 +179,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with Traversable
    */
   def ++[B >: A, That](that: TraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
     val b = bf(repr)
+    if (that.isInstanceOf[IndexedSeqLike[_, _]]) b.sizeHint(this, that.size)
     b ++= thisCollection
     b ++= that
     b.result
@@ -200,6 +201,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with Traversable
    */
   def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
     val b = bf(repr)
+    b.sizeHint(this)
     for (x <- this) b += f(x)
     b.result
   }
@@ -428,6 +430,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with Traversable
    */
   def scanLeft[B, That](z: B)(op: (B, A) => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
     val b = bf(repr)
+    b.sizeHint(this)
     var acc = z
     b += acc
     for (x <- this) { acc = op(acc, x); b += acc }
@@ -448,6 +451,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with Traversable
    */
   def scanRight[B, That](z: B)(op: (A, B) => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
     val b = bf(repr)
+    b.sizeHint(this)
     var acc = z
     b += acc
     for (x <- reversed) { acc = op(x, acc); b += acc }
@@ -516,6 +520,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with Traversable
     var lst = head
     var follow = false
     val b = newBuilder
+    b.sizeHint(this, -1)
     for (x <- this) {
       if (follow) b += lst
       else follow = true
@@ -532,6 +537,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with Traversable
    */
   def take(n: Int): Repr = {
     val b = newBuilder
+    b.sizeHintBounded(n, this)
     var i = 0
     breakable {
       for (x <- this) {
@@ -551,6 +557,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with Traversable
    */
   def drop(n: Int): Repr = {
     val b = newBuilder
+    if (n >= 0) b.sizeHint(this, -n)
     var i = 0
     for (x <- this) {
       if (i >= n) b += x
@@ -572,6 +579,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with Traversable
    */
   def slice(from: Int, until: Int): Repr = {
     val b = newBuilder
+    b.sizeHintBounded(until - from, this)
     var i = 0
     breakable {
       for (x <- this) {
@@ -648,6 +656,8 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] with Traversable
    */
   def splitAt(n: Int): (Repr, Repr) = {
     val l, r = newBuilder
+    l.sizeHintBounded(n, this)
+    if (n >= 0) r.sizeHint(this, -n)
     var i = 0
     for (x <- this) {
       (if (i < n) l else r) += x
diff --git a/src/library/scala/collection/mutable/Builder.scala b/src/library/scala/collection/mutable/Builder.scala
index a930c29948..0c8bb79f83 100644
--- a/src/library/scala/collection/mutable/Builder.scala
+++ b/src/library/scala/collection/mutable/Builder.scala
@@ -52,6 +52,42 @@ trait Builder[-Elem, +To] extends Growable[Elem] {
    */
   def sizeHint(size: Int) {}
 
+  /** Gives a hint that one expects the `result` of this builder
+   *  to have the same size as the given collection, plus some delta. This will
+   *  provide a hint only if the collection is known to have a cheap
+   *  `size` method. Currently this is assumed ot be the case if and only if
+   *  the collection is of type `IndexedSeqLike`.
+   *  Some builder classes
+   *  will optimize their representation based on the hint. However,
+   *  builder implementations are still required to work correctly even if the hint is
+   *  wrong, i.e. a different number of elements is added.
+   *
+   *  @param coll  the collection which serves as a hint for the result's size.
+   *  @param delta a correction to add to the `coll.size` to produce the size hint.
+   */
+  def sizeHint(coll: TraversableLike[_, _], delta: Int = 0) {
+    if (coll.isInstanceOf[IndexedSeqLike[_,_]]) {
+      sizeHint(coll.size + delta)
+    }
+  }
+
+  /** Gives a hint how many elements are expected to be added
+   *  when the next `result` is called, together with an upper bound
+   *  given by the size of some other collection. Some builder classes
+   *  will optimize their representation based on the hint. However,
+   *  builder implementations are still required to work correctly even if the hint is
+   *  wrong, i.e. a different number of elements is added.
+   *
+   *  @param size  the hint how many elements will be added.
+   *  @param boundingColl  the bounding collection. If it is
+   *                       an IndexedSeqLike, then sizes larger
+   *                       than collection's size are reduced.
+   */
+  def sizeHintBounded(size: Int, boundingColl: TraversableLike[_, _]) {
+    if (boundingColl.isInstanceOf[IndexedSeqLike[_,_]])
+      sizeHint(size min boundingColl.size)
+  }
+
   /** Creates a new builder by applying a transformation function to
    *  the results of this builder.
    *  @param  f     the transformation function.