Improved BitSet implementations

- Mutable and immutable BitSets now extend SortedSet, using a fixed
  Ordering.Int and an efficient bit mask based rangeImpl()
- fromArray methods in both implementations are deprecated in favor of
  new fromBitMask and fromBitMaskNoCopy methods
- New toBitMask method for converting bit sets back to Array[Long] bit
  masks
- immutable.BitSet uses a more efficient Builder, based on
  mutable.BitSet (closes SI-4647)
- Delete scala.tools.nsc.util.BitSet (not used anywhere)

Review by @odersky

6 files changed, 111 insertions, 20 deletions

diff --git a/src/library/scala/collection/BitSet.scala b/src/library/scala/collection/BitSet.scala
index 2f411f976f..59b53faf7e 100644
--- a/src/library/scala/collection/BitSet.scala
+++ b/src/library/scala/collection/BitSet.scala
@@ -15,7 +15,7 @@ import generic._
 /** A common base class for mutable and immutable bitsets.
  *  $bitsetinfo
  */
-trait BitSet extends Set[Int]
+trait BitSet extends SortedSet[Int]
                 with BitSetLike[BitSet] {
   override def empty: BitSet = BitSet.empty
 }
diff --git a/src/library/scala/collection/BitSetLike.scala b/src/library/scala/collection/BitSetLike.scala
index b96e8f6a91..7d9f48f299 100644
--- a/src/library/scala/collection/BitSetLike.scala
+++ b/src/library/scala/collection/BitSetLike.scala
@@ -32,7 +32,7 @@ import mutable.StringBuilder
  *  @define coll bitset
  *  @define Coll BitSet
  */
-trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, This] { self =>
+trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSetLike[Int, This] { self =>
 
   def empty: This
 
@@ -46,7 +46,19 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T
 
   /** Creates a new set of this kind from an array of longs
    */
-  protected def fromArray(elems: Array[Long]): This
+  protected def fromBitMaskNoCopy(elems: Array[Long]): This
+
+  /** Creates a bit mask for this set as a new array of longs
+   */
+  def toBitMask: Array[Long] = {
+    val a = new Array[Long](nwords)
+    var i = a.length
+    while(i > 0) {
+      i -= 1
+      a(i) = word(i)
+    }
+    a
+  }
 
   override def size: Int = {
     var s = 0
@@ -58,6 +70,35 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T
     s
   }
 
+  implicit def ordering: Ordering[Int] = Ordering.Int
+
+  def rangeImpl(from: Option[Int], until: Option[Int]): This = {
+    val a = toBitMask
+    val len = a.length
+    if(from.isDefined) {
+      var f = from.get
+      var pos = 0
+      while(f >= 64 && pos < len) {
+        f -= 64
+        a(pos) = 0
+        pos += 1
+      }
+      if(f > 0 && pos < len) a(pos) &= ~((1L << f)-1)
+    }
+    if(until.isDefined) {
+      val u = until.get
+      val w = u / 64
+      val b = u % 64
+      var clearw = w+1
+      while(clearw < len) {
+        a(clearw) = 0
+        clearw += 1
+      }
+      if(w < len) a(w) &= (1L << b)-1
+    }
+    fromBitMaskNoCopy(a)
+  }
+
   def iterator: Iterator[Int] = new AbstractIterator[Int] {
     private var current = 0
     private val end = nwords * WordLength
@@ -91,7 +132,7 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T
     val words = new Array[Long](len)
     for (idx <- 0 until len)
       words(idx) = this.word(idx) | other.word(idx)
-    fromArray(words)
+    fromBitMaskNoCopy(words)
   }
 
   /** Computes the intersection between this bitset and another bitset by performing
@@ -105,7 +146,7 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T
     val words = new Array[Long](len)
     for (idx <- 0 until len)
       words(idx) = this.word(idx) & other.word(idx)
-    fromArray(words)
+    fromBitMaskNoCopy(words)
   }
 
   /** Computes the difference of this bitset and another bitset by performing
@@ -120,7 +161,7 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T
     val words = new Array[Long](len)
     for (idx <- 0 until len)
       words(idx) = this.word(idx) & ~other.word(idx)
-    fromArray(words)
+    fromBitMaskNoCopy(words)
   }
 
   /** Computes the symmetric difference of this bitset and another bitset by performing
@@ -135,7 +176,7 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T
     val words = new Array[Long](len)
     for (idx <- 0 until len)
       words(idx) = this.word(idx) ^ other.word(idx)
-    fromArray(words)
+    fromBitMaskNoCopy(words)
   }
 
   def contains(elem: Int): Boolean =
diff --git a/src/library/scala/collection/SortedSet.scala b/src/library/scala/collection/SortedSet.scala
index a1d1cd3fc3..f29b6d8aa3 100644
--- a/src/library/scala/collection/SortedSet.scala
+++ b/src/library/scala/collection/SortedSet.scala
@@ -27,5 +27,7 @@ trait SortedSet[A] extends Set[A] with SortedSetLike[A, SortedSet[A]] {
  */
 object SortedSet extends SortedSetFactory[SortedSet] {
   def empty[A](implicit ord: Ordering[A]): immutable.SortedSet[A] = immutable.SortedSet.empty[A](ord)
-  implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = new SortedSetCanBuildFrom[A]
+  def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = newCanBuildFrom[A]
+  // Force a declaration here so that BitSet's (which does not inherit from SortedSetFactory) can be more specific
+  override implicit def newCanBuildFrom[A](implicit ord : Ordering[A]) : CanBuildFrom[Coll, A, SortedSet[A]] = super.newCanBuildFrom
 }
diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala
index 36aa087dd0..ce4d688707 100644
--- a/src/library/scala/collection/immutable/BitSet.scala
+++ b/src/library/scala/collection/immutable/BitSet.scala
@@ -22,13 +22,16 @@ import mutable.{ Builder, SetBuilder }
  */
 @SerialVersionUID(1611436763290191562L)
 abstract class BitSet extends scala.collection.AbstractSet[Int]
-                         with Set[Int]
+                         with SortedSet[Int]
                          with scala.collection.BitSet
                          with BitSetLike[BitSet]
                          with Serializable {
   override def empty = BitSet.empty
 
-  def fromArray(elems: Array[Long]): BitSet = BitSet.fromArray(elems)
+  @deprecated("Use BitSet.fromBitMask[NoCopy] instead of fromArray", "2.10")
+  def fromArray(elems: Array[Long]): BitSet = fromBitMaskNoCopy(elems)
+
+  protected def fromBitMaskNoCopy(elems: Array[Long]): BitSet = BitSet.fromBitMaskNoCopy(elems)
 
   /** Update word at index `idx`; enlarge set if `idx` outside range of set.
    */
@@ -64,14 +67,38 @@ 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 SetBuilder[Int, BitSet](empty)
+  /** A builder that takes advantage of mutable BitSets. */
+  def newBuilder: Builder[Int, BitSet] = new Builder[Int, BitSet] {
+    private[this] val b = new mutable.BitSet
+    def += (x: Int) = { b += x; this }
+    def clear() = b.clear
+    def result() = b.toImmutable
+  }
 
   /** $bitsetCanBuildFrom */
   implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom
 
   /** A bitset containing all the bits in an array */
-  def fromArray(elems: Array[Long]): BitSet = {
+  @deprecated("Use fromBitMask[NoCopy] instead of fromArray", "2.10")
+  def fromArray(elems: Array[Long]): BitSet = fromBitMaskNoCopy(elems)
+
+  /** A bitset containing all the bits in an array */
+  def fromBitMask(elems: Array[Long]): BitSet = {
+    val len = elems.length
+    if (len == 0) empty
+    else if (len == 1) new BitSet1(elems(0))
+    else if (len == 2) new BitSet2(elems(0), elems(1))
+    else {
+      val a = new Array[Long](len)
+      Array.copy(elems, 0, a, 0, len)
+      new BitSetN(a)
+    }
+  }
+
+  /** A bitset containing all the bits in an array, wrapping the existing
+   *  array without copying.
+   */
+  def fromBitMaskNoCopy(elems: Array[Long]): BitSet = {
     val len = elems.length
     if (len == 0) empty
     else if (len == 1) new BitSet1(elems(0))
@@ -85,7 +112,7 @@ object BitSet extends BitSetFactory[BitSet] {
     protected def updateWord(idx: Int, w: Long): BitSet =
       if (idx == 0) new BitSet1(w)
       else if (idx == 1) new BitSet2(elems, w)
-      else fromArray(updateArray(Array(elems), idx, w))
+      else fromBitMaskNoCopy(updateArray(Array(elems), idx, w))
   }
 
   class BitSet2(val elems0: Long, elems1: Long) extends BitSet {
@@ -94,12 +121,18 @@ object BitSet extends BitSetFactory[BitSet] {
     protected def updateWord(idx: Int, w: Long): BitSet =
       if (idx == 0) new BitSet2(w, elems1)
       else if (idx == 1) new BitSet2(elems0, w)
-      else fromArray(updateArray(Array(elems0, elems1), idx, w))
+      else fromBitMaskNoCopy(updateArray(Array(elems0, elems1), idx, w))
   }
 
+  /** The implementing class for bit sets with elements >= 128 (exceeding
+   *  the capacity of two long values). The constructor wraps an existing
+   *  bit mask without copying, thus exposing a mutable part of the internal
+   *  implementation. Care needs to be taken not to modify the exposed
+   *  array.  
+   */
   class BitSetN(val elems: Array[Long]) extends BitSet {
     protected def nwords = elems.length
     protected def word(idx: Int) = if (idx < nwords) elems(idx) else 0L
-    protected def updateWord(idx: Int, w: Long): BitSet = fromArray(updateArray(elems, idx, w))
+    protected def updateWord(idx: Int, w: Long): BitSet = fromBitMaskNoCopy(updateArray(elems, idx, w))
   }
 }
diff --git a/src/library/scala/collection/immutable/SortedSet.scala b/src/library/scala/collection/immutable/SortedSet.scala
index 50cd5445b9..e1637ce78b 100644
--- a/src/library/scala/collection/immutable/SortedSet.scala
+++ b/src/library/scala/collection/immutable/SortedSet.scala
@@ -35,6 +35,8 @@ trait SortedSet[A] extends Set[A] with scala.collection.SortedSet[A] with Sorted
  */
 object SortedSet extends ImmutableSortedSetFactory[SortedSet] {
   /** $sortedSetCanBuildFromInfo */
-  implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = new SortedSetCanBuildFrom[A]
+  def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = newCanBuildFrom[A]
   def empty[A](implicit ord: Ordering[A]): SortedSet[A] = TreeSet.empty[A]
+  // Force a declaration here so that BitSet's (which does not inherit from SortedSetFactory) can be more specific
+  override implicit def newCanBuildFrom[A](implicit ord : Ordering[A]) : CanBuildFrom[Coll, A, SortedSet[A]] = super.newCanBuildFrom
 }
diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala
index 0cff9f970f..9dce3ff9e2 100644
--- a/src/library/scala/collection/mutable/BitSet.scala
+++ b/src/library/scala/collection/mutable/BitSet.scala
@@ -34,7 +34,7 @@ import BitSetLike.{LogWL, updateArray}
  */
 @SerialVersionUID(8483111450368547763L)
 class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int]
-                                                  with Set[Int]
+                                                  with SortedSet[Int]
                                                   with scala.collection.BitSet
                                                   with BitSetLike[BitSet]
                                                   with SetLike[Int, BitSet]
@@ -65,7 +65,7 @@ class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int]
     elems(idx) = w
   }
 
-  protected def fromArray(words: Array[Long]): BitSet = new BitSet(words)
+  protected def fromBitMaskNoCopy(words: Array[Long]): BitSet = new BitSet(words)
 
   override def add(elem: Int): Boolean = {
     require(elem >= 0)
@@ -100,7 +100,7 @@ class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int]
    *
    *  @return an immutable set containing all the elements of this set.
    */
-  def toImmutable = immutable.BitSet.fromArray(elems)
+  def toImmutable = immutable.BitSet.fromBitMaskNoCopy(elems)
 
   override def clone(): BitSet = {
     val elems1 = new Array[Long](elems.length)
@@ -121,4 +121,17 @@ object BitSet extends BitSetFactory[BitSet] {
 
   /** $bitsetCanBuildFrom */
   implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom
+
+  /** A bitset containing all the bits in an array */
+  def fromBitMask(elems: Array[Long]): BitSet = {
+    val len = elems.length
+    val a = new Array[Long](len)
+    Array.copy(elems, 0, a, 0, len)
+    new BitSet(a)
+  }
+
+  /** A bitset containing all the bits in an array, wrapping the existing
+   *  array without copying.
+   */
+  def fromBitMaskNoCopy(elems: Array[Long]): BitSet = new BitSet(elems)
 }