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

2 files changed, 131 insertions, 0 deletions

diff --git a/test/files/run/bitsets.check b/test/files/run/bitsets.check
index 478de261af..3f01d2a400 100644
--- a/test/files/run/bitsets.check
+++ b/test/files/run/bitsets.check
@@ -14,6 +14,29 @@ mi0 = BitSet(2)
 mi1 = BitSet(2)
 mi2 = BitSet(2)
 
+m2_m0 = List(1010101010101010101010101)
+m2_m2 = List(ffffffffffffffff, ffffffffffffffff, ffffffffffffffff, ffffffffffffffff, 1, 0, 0, 0)
+m2_m0c = true
+m2_m1c = true
+m2_m2c = true
+m2_m3c = true
+m2_i0 = true
+m2_i1 = true
+m2_i2 = true
+m2_i3 = true
+m2_f0 = true
+m2_f1 = true
+m2_f2 = true
+m2_f3 = true
+m2_t0 = true
+m2_t1 = true
+m2_t2 = true
+m2_t3 = true
+m2_r0 = true
+m2_r1 = true
+m2_r2 = true
+m2_r3 = true
+
 is0 = BitSet()
 is1 = BitSet()
 is2 = BitSet(2)
@@ -31,3 +54,26 @@ ia1 = List()
 ia2 = List(2)
 ia3 = List()
 
+i2_m0 = List(1010101010101010101010101)
+i2_m2 = List(ffffffffffffffff, ffffffffffffffff, ffffffffffffffff, ffffffffffffffff, 1)
+i2_m0c = true
+i2_m1c = true
+i2_m2c = true
+i2_m3c = true
+i2_i0 = true
+i2_i1 = true
+i2_i2 = true
+i2_i3 = true
+i2_f0 = true
+i2_f1 = true
+i2_f2 = true
+i2_f3 = true
+i2_t0 = true
+i2_t1 = true
+i2_t2 = true
+i2_t3 = true
+i2_r0 = true
+i2_r1 = true
+i2_r2 = true
+i2_r3 = true
+
diff --git a/test/files/run/bitsets.scala b/test/files/run/bitsets.scala
index a847c9940d..27395683b4 100644
--- a/test/files/run/bitsets.scala
+++ b/test/files/run/bitsets.scala
@@ -39,6 +39,48 @@ object TestMutable {
   Console.println
 }
 
+object TestMutable2 {
+  import scala.collection.mutable.BitSet
+  import scala.collection.immutable.TreeSet
+
+  val l0 = 0 to 24 by 2 toList
+  val l1 = (190 to 255 toList) reverse
+  val l2 = (0 to 256 toList)
+  val l3 = (1 to 200 by 2 toList) reverse
+  val t0 = TreeSet(l0: _*)
+  val t1 = TreeSet(l1: _*)
+  val t2 = TreeSet(l2: _*)
+  val t3 = TreeSet(l3: _*)
+  val b0 = BitSet(l0: _*)
+  val b1 = BitSet(l1: _*)
+  val b2 = BitSet(l2: _*)
+  val b3 = BitSet(l3: _*)
+
+  println("m2_m0 = " + b0.toBitMask.toList.map(_.toBinaryString))
+  println("m2_m2 = " + b2.toBitMask.toList.map(_.toHexString))
+  println("m2_m0c = " + (BitSet.fromBitMask(b0.toBitMask) == b0))
+  println("m2_m1c = " + (BitSet.fromBitMask(b1.toBitMask) == b1))
+  println("m2_m2c = " + (BitSet.fromBitMask(b2.toBitMask) == b2))
+  println("m2_m3c = " + (BitSet.fromBitMask(b3.toBitMask) == b3))
+  println("m2_i0 = " + (t0 == b0))
+  println("m2_i1 = " + (t1 == b1))
+  println("m2_i2 = " + (t2 == b2))
+  println("m2_i3 = " + (t3 == b3))
+  println("m2_f0 = " + (t0.from(42) == b0.from(42)))
+  println("m2_f1 = " + (t1.from(42) == b1.from(42)))
+  println("m2_f2 = " + (t2.from(42) == b2.from(42)))
+  println("m2_f3 = " + (t3.from(42) == b3.from(42)))
+  println("m2_t0 = " + (t0.to(195) == b0.to(195)))
+  println("m2_t1 = " + (t1.to(195) == b1.to(195)))
+  println("m2_t2 = " + (t2.to(195) == b2.to(195)))
+  println("m2_t3 = " + (t3.to(195) == b3.to(195)))
+  println("m2_r0 = " + (t0.range(43,194) == b0.range(43,194)))
+  println("m2_r1 = " + (t1.range(43,194) == b1.range(43,194)))
+  println("m2_r2 = " + (t2.range(43,194) == b2.range(43,194)))
+  println("m2_r3 = " + (t3.range(43,194) == b3.range(43,194)))
+  println
+}
+
 object TestImmutable {
   import scala.collection.immutable.BitSet
 
@@ -69,9 +111,52 @@ object TestImmutable {
   Console.println
 }
 
+object TestImmutable2 {
+  import scala.collection.immutable.{BitSet, TreeSet}
+
+  val l0 = 0 to 24 by 2 toList
+  val l1 = (190 to 255 toList) reverse
+  val l2 = (0 to 256 toList)
+  val l3 = (1 to 200 by 2 toList) reverse
+  val t0 = TreeSet(l0: _*)
+  val t1 = TreeSet(l1: _*)
+  val t2 = TreeSet(l2: _*)
+  val t3 = TreeSet(l3: _*)
+  val b0 = BitSet(l0: _*)
+  val b1 = BitSet(l1: _*)
+  val b2 = BitSet(l2: _*)
+  val b3 = BitSet(l3: _*)
+
+  println("i2_m0 = " + b0.toBitMask.toList.map(_.toBinaryString))
+  println("i2_m2 = " + b2.toBitMask.toList.map(_.toHexString))
+  println("i2_m0c = " + (BitSet.fromBitMask(b0.toBitMask) == b0))
+  println("i2_m1c = " + (BitSet.fromBitMask(b1.toBitMask) == b1))
+  println("i2_m2c = " + (BitSet.fromBitMask(b2.toBitMask) == b2))
+  println("i2_m3c = " + (BitSet.fromBitMask(b3.toBitMask) == b3))
+  println("i2_i0 = " + (t0 == b0))
+  println("i2_i1 = " + (t1 == b1))
+  println("i2_i2 = " + (t2 == b2))
+  println("i2_i3 = " + (t3 == b3))
+  println("i2_f0 = " + (t0.from(42) == b0.from(42)))
+  println("i2_f1 = " + (t1.from(42) == b1.from(42)))
+  println("i2_f2 = " + (t2.from(42) == b2.from(42)))
+  println("i2_f3 = " + (t3.from(42) == b3.from(42)))
+  println("i2_t0 = " + (t0.to(195) == b0.to(195)))
+  println("i2_t1 = " + (t1.to(195) == b1.to(195)))
+  println("i2_t2 = " + (t2.to(195) == b2.to(195)))
+  println("i2_t3 = " + (t3.to(195) == b3.to(195)))
+  println("i2_r0 = " + (t0.range(77,194) == b0.range(77,194)))
+  println("i2_r1 = " + (t1.range(77,194) == b1.range(77,194)))
+  println("i2_r2 = " + (t2.range(77,194) == b2.range(77,194)))
+  println("i2_r3 = " + (t3.range(77,194) == b3.range(77,194)))
+  println
+}
+
 object Test extends App {
   TestMutable
+  TestMutable2
   TestImmutable
+  TestImmutable2
 }
 
 //############################################################################