diff options
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) + } +} |