Created Mutable and Immutable SetFactories to d...

Created Mutable and Immutable SetFactories to deal with the spectacular
performance regression which accompanies the use of AddingBuilder on
mutable Sets. Because '+' now creates a new collection even on mutable
sets, AddingBuilder on a 100K element collection will create garbage
sets of size 1,2,3...,99,999 before finishing. Thankfully there is
already GrowingBuilder.

See test/files/run/adding-growing-set.scala for a demonstration.

This patch is not complete: in particular, SortedSet and SetBuilder need
attention. Unfortunately there is a combinatorial jump in the number of
Addable/Growable divisions which arises once one tries to accomodate
both Sorted signatures (taking an Ordering) and unsorted signatures, so
will come back to it after receiving counsel.

Review by odersky.

18 files changed, 80 insertions, 15 deletions

diff --git a/src/library/scala/collection/BitSet.scala b/src/library/scala/collection/BitSet.scala
index b43b681888..e362271f70 100644
--- a/src/library/scala/collection/BitSet.scala
+++ b/src/library/scala/collection/BitSet.scala
@@ -27,6 +27,8 @@ trait BitSet extends Set[Int]
  */
 object BitSet extends BitSetFactory[BitSet] {
   val empty: BitSet = immutable.BitSet.empty
+  def newBuilder = immutable.BitSet.newBuilder
+
   /** $canBuildFromInfo */
   implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom
 }
diff --git a/src/library/scala/collection/Set.scala b/src/library/scala/collection/Set.scala
index 034d9f1705..f1c1e43731 100644
--- a/src/library/scala/collection/Set.scala
+++ b/src/library/scala/collection/Set.scala
@@ -37,6 +37,7 @@ trait Set[A] extends (A => Boolean)
  *  @define Coll Set
  */
 object Set extends SetFactory[Set] {
+  def newBuilder[A] = immutable.Set.newBuilder[A]
   override def empty[A]: Set[A] = immutable.Set.empty[A]
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Set[A]] = setCanBuildFrom[A]
 }
diff --git a/src/library/scala/collection/generic/BitSetFactory.scala b/src/library/scala/collection/generic/BitSetFactory.scala
index 5679b25351..08cf7bd0e0 100644
--- a/src/library/scala/collection/generic/BitSetFactory.scala
+++ b/src/library/scala/collection/generic/BitSetFactory.scala
@@ -13,7 +13,7 @@ package scala.collection
 package generic
 
 import scala.collection._
-import mutable.{Builder, AddingBuilder}
+import mutable.Builder
 
 /** @define coll collection
  *  @define Coll Traversable
@@ -28,8 +28,8 @@ import mutable.{Builder, AddingBuilder}
  *    The standard `CanBuildFrom` instance for bitsets.
  */
 trait BitSetFactory[Coll <: BitSet with BitSetLike[Coll]] {
-  def newBuilder: Builder[Int, Coll] = new AddingBuilder[Int, Coll](empty)
   def empty: Coll
+  def newBuilder: Builder[Int, Coll]
   def apply(elems: Int*): Coll = (empty /: elems) (_ + _)
   def bitsetCanBuildFrom = new CanBuildFrom[Coll, Int, Coll] {
     def apply(from: Coll) = newBuilder
diff --git a/src/library/scala/collection/generic/ImmutableSetFactory.scala b/src/library/scala/collection/generic/ImmutableSetFactory.scala
new file mode 100644
index 0000000000..a551786f25
--- /dev/null
+++ b/src/library/scala/collection/generic/ImmutableSetFactory.scala
@@ -0,0 +1,18 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2010, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+package scala.collection
+package generic
+
+import mutable.{ Builder, AddingBuilder }
+
+abstract class ImmutableSetFactory[CC[X] <: immutable.Set[X] with SetLike[X, CC[X]]]
+  extends SetFactory[CC] {
+
+  def newBuilder[A]: Builder[A, CC[A]] = new AddingBuilder[A, CC[A]](empty[A])
+}
diff --git a/src/library/scala/collection/generic/MutableSetFactory.scala b/src/library/scala/collection/generic/MutableSetFactory.scala
new file mode 100644
index 0000000000..28b5fdd897
--- /dev/null
+++ b/src/library/scala/collection/generic/MutableSetFactory.scala
@@ -0,0 +1,18 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2010, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+package scala.collection
+package generic
+
+import mutable.{ Builder, GrowingBuilder }
+
+abstract class MutableSetFactory[CC[X] <: mutable.Set[X] with mutable.SetLike[X, CC[X]]]
+  extends SetFactory[CC] {
+
+  def newBuilder[A]: Builder[A, CC[A]] = new GrowingBuilder[A, CC[A]](empty[A])
+}
diff --git a/src/library/scala/collection/generic/SetFactory.scala b/src/library/scala/collection/generic/SetFactory.scala
index 1c4ec3e7e3..d43664bd39 100644
--- a/src/library/scala/collection/generic/SetFactory.scala
+++ b/src/library/scala/collection/generic/SetFactory.scala
@@ -12,7 +12,7 @@
 package scala.collection
 package generic
 
-import mutable.{Builder, AddingBuilder}
+import mutable.Builder
 
 /** A template for companion objects of `Set` and subclasses thereof.
  *
@@ -34,7 +34,7 @@ import mutable.{Builder, AddingBuilder}
 abstract class SetFactory[CC[X] <: Set[X] with SetLike[X, CC[X]]]
   extends GenericCompanion[CC] {
 
-  def newBuilder[A]: Builder[A, CC[A]] = new AddingBuilder[A, CC[A]](empty[A])
+  def newBuilder[A]: Builder[A, CC[A]]
 
   /** $setCanBuildFromInfo
    */
diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala
index 9b801f26cb..8fa23c3ddf 100644
--- a/src/library/scala/collection/immutable/BitSet.scala
+++ b/src/library/scala/collection/immutable/BitSet.scala
@@ -14,6 +14,7 @@ package immutable
 
 import generic._
 import BitSetLike.{LogWL, updateArray}
+import mutable.{ Builder, AddingBuilder }
 
 /** A class for immutable bitsets.
  *  $bitsetinfo
@@ -60,10 +61,12 @@ abstract class BitSet extends Set[Int]
  *  @define coll immutable bitset
  */
 object BitSet extends BitSetFactory[BitSet] {
-
   /** The empty bitset */
   val empty: BitSet = new BitSet1(0L)
 
+  /** An adding builder for immutable Sets. */
+  def newBuilder: Builder[Int, BitSet] = new AddingBuilder[Int, BitSet](empty)
+
   /** $bitsetCanBuildFrom */
   implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom
 
diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala
index 68da0cef50..481b1c3204 100644
--- a/src/library/scala/collection/immutable/HashSet.scala
+++ b/src/library/scala/collection/immutable/HashSet.scala
@@ -88,7 +88,7 @@ class HashSet[A] extends Set[A]
  *  @define mayNotTerminateInf
  *  @define willNotTerminateInf
  */
-object HashSet extends SetFactory[HashSet] {
+object HashSet extends ImmutableSetFactory[HashSet] {
   /** $setCanBuildFromInfo */
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, HashSet[A]] = setCanBuildFrom[A]
   override def empty[A]: HashSet[A] = EmptyHashSet.asInstanceOf[HashSet[A]]
diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala
index 2a202df9ef..979fdff552 100644
--- a/src/library/scala/collection/immutable/ListSet.scala
+++ b/src/library/scala/collection/immutable/ListSet.scala
@@ -19,7 +19,7 @@ import generic._
  *  @define coll immutable list set
  *  @since 1
  */
-object ListSet extends SetFactory[ListSet] {
+object ListSet extends ImmutableSetFactory[ListSet] {
   /** setCanBuildFromInfo */
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] = setCanBuildFrom[A]
   override def empty[A] = new ListSet[A]
diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala
index 769ee37f6b..745b0034e8 100644
--- a/src/library/scala/collection/immutable/Set.scala
+++ b/src/library/scala/collection/immutable/Set.scala
@@ -36,7 +36,7 @@ trait Set[A] extends Iterable[A]
  *  @define Coll immutable.Set
  *  @define coll immutable set
  */
-object Set extends SetFactory[Set] {
+object Set extends ImmutableSetFactory[Set] {
   /** $setCanBuildFromInfo */
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Set[A]] = setCanBuildFrom[A]
   override def empty[A]: Set[A] = EmptySet.asInstanceOf[Set[A]]
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 7b1f71df5b..18c65dd373 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -13,7 +13,7 @@ package scala.collection
 package immutable
 
 import generic._
-import mutable.{Builder, AddingBuilder}
+import mutable.{ Builder, AddingBuilder }
 
 /** $factoryInfo
  *  @define Coll immutable.TreeSet
diff --git a/src/library/scala/collection/mutable/AddingBuilder.scala b/src/library/scala/collection/mutable/AddingBuilder.scala
index 14636c9feb..54137b6a26 100644
--- a/src/library/scala/collection/mutable/AddingBuilder.scala
+++ b/src/library/scala/collection/mutable/AddingBuilder.scala
@@ -17,9 +17,12 @@ import generic._
  *  which adds an element to the collection.
  *
  *  Collections are built from their empty element using this `+` method.
- *  @param empty  the empty element of the collection.
- *  @tparam Elem  the type of elements that get added to the builder.
- *  @tparam To    the type of the built collection.
+ *  @param  empty   the empty element of the collection.
+ *  @tparam Elem    the type of elements that get added to the builder.
+ *  @tparam To      the type of the built collection.
+ *
+ *  @note   "efficient `+`" is not idle talk.  Do not use this on mutable collections or any others
+ *  for which `+` may perform an unshared copy! See GrowingBuilder comments for more.
  *
  *  @author Martin Odersky
  *  @version 2.8
diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala
index 5d0f5863ca..da3e95fce7 100644
--- a/src/library/scala/collection/mutable/BitSet.scala
+++ b/src/library/scala/collection/mutable/BitSet.scala
@@ -114,6 +114,10 @@ class BitSet(protected var elems: Array[Long]) extends Set[Int]
  */
 object BitSet extends BitSetFactory[BitSet] {
   def empty: BitSet = new BitSet
+
+  /** A growing builder for mutable Sets. */
+  def newBuilder: Builder[Int, BitSet] = new GrowingBuilder[Int, BitSet](empty)
+
   /** $bitsetCanBuildFrom */
   implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom
 }
diff --git a/src/library/scala/collection/mutable/GrowingBuilder.scala b/src/library/scala/collection/mutable/GrowingBuilder.scala
index cd1c8bec8c..781753c24d 100644
--- a/src/library/scala/collection/mutable/GrowingBuilder.scala
+++ b/src/library/scala/collection/mutable/GrowingBuilder.scala
@@ -18,6 +18,11 @@ import generic._
  *  interacting surprisingly with any2stringadd thus driving '+' out of the `Seq`
  *  hierarchy.  The tendrils of original sin should never be underestimated.
  *
+ *  Addendum: of even greater significance is that '+' on mutable collections now
+ *  creates a new collection.  This means using AddingBuilder on them will create
+ *  a new intermediate collection for every element given to the builder, taking
+ *  '+' from an O(1) to O(n) operation.
+ *
  *  @author Paul Phillips
  *  @version 2.8
  *  @since 2.8
diff --git a/src/library/scala/collection/mutable/HashSet.scala b/src/library/scala/collection/mutable/HashSet.scala
index 3d9dc3e55d..41f9a17dd6 100644
--- a/src/library/scala/collection/mutable/HashSet.scala
+++ b/src/library/scala/collection/mutable/HashSet.scala
@@ -79,7 +79,7 @@ class HashSet[A] extends Set[A]
  *  @define Coll mutable.HashSet
  *  @define coll mutable hash set
  */
-object HashSet extends SetFactory[HashSet] {
+object HashSet extends MutableSetFactory[HashSet] {
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, HashSet[A]] = setCanBuildFrom[A]
   override def empty[A]: HashSet[A] = new HashSet[A]
 }
diff --git a/src/library/scala/collection/mutable/LinkedHashSet.scala b/src/library/scala/collection/mutable/LinkedHashSet.scala
index 7ecb71e23b..e91b03048d 100644
--- a/src/library/scala/collection/mutable/LinkedHashSet.scala
+++ b/src/library/scala/collection/mutable/LinkedHashSet.scala
@@ -87,7 +87,7 @@ class LinkedHashSet[A] extends Set[A]
  *  @define Coll LinkedHashSet
  *  @define coll linked hash set
  */
-object LinkedHashSet extends SetFactory[LinkedHashSet] {
+object LinkedHashSet extends MutableSetFactory[LinkedHashSet] {
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, LinkedHashSet[A]] = setCanBuildFrom[A]
   override def empty[A]: LinkedHashSet[A] = new LinkedHashSet[A]
 }
diff --git a/src/library/scala/collection/mutable/Set.scala b/src/library/scala/collection/mutable/Set.scala
index 2e7f1cbc6b..bebf66157a 100644
--- a/src/library/scala/collection/mutable/Set.scala
+++ b/src/library/scala/collection/mutable/Set.scala
@@ -32,7 +32,7 @@ trait Set[A] extends Iterable[A]
  *  @define coll mutable set
  *  @define Coll mutable.Set
  */
-object Set extends SetFactory[Set] {
+object Set extends MutableSetFactory[Set] {
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Set[A]] = setCanBuildFrom[A]
   override def empty[A]: Set[A] = HashSet.empty[A]
 }
diff --git a/test/files/run/adding-growing-set.scala b/test/files/run/adding-growing-set.scala
new file mode 100644
index 0000000000..5903813ed1
--- /dev/null
+++ b/test/files/run/adding-growing-set.scala
@@ -0,0 +1,11 @@
+/** This will run a a loooong time if Set's builder copies a
+ *  complete new Set for every element.
+ */
+object Test {
+  def main(args: Array[String]): Unit = {
+    val a = new Array[Long](1000000)
+    (1 to 10000) foreach (i => a(i) = i)
+    val s = collection.mutable.Set(a: _*)
+    assert(s.sum > 0)
+  }
+}