diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/Tuple2.scala | 4 | ||||
-rw-r--r-- | src/library/scala/collection/IterableLike.scala | 4 | ||||
-rw-r--r-- | src/library/scala/collection/SeqLike.scala | 2 | ||||
-rw-r--r-- | src/library/scala/collection/TraversableLike.scala | 10 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/Builder.scala | 36 |
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. |