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

9 files changed, 242 insertions, 179 deletions

diff --git a/src/compiler/scala/tools/nsc/util/BitSet.scala b/src/compiler/scala/tools/nsc/util/BitSet.scala
deleted file mode 100644
index de0c6fd62a..0000000000
--- a/src/compiler/scala/tools/nsc/util/BitSet.scala
+++ /dev/null
@@ -1,159 +0,0 @@
-package scala.tools.nsc
-package util
-
-import BitSet._
-
-abstract class BitSet {
-
-  protected def nwords: Int
-  protected def word(idx: Int): Long
-  protected def updateWord(idx: Int, w: Long): BitSet
-
-  def + (elem: Int): BitSet = {
-    require(elem >= 0)
-    if (contains(elem)) this
-    else {
-      val idx = elem >> LogWL
-      updateWord(idx, word(idx) | (1L << elem))
-    }
-  }
-
-  def - (elem: Int): BitSet = {
-    require(elem >= 0)
-    if (contains(elem)) {
-      val idx = elem >> LogWL
-      updateWord(idx, word(idx) & ~(1L << elem))
-    } else this
-  }
-
-  def | (other: BitSet): BitSet = {
-    val len = this.nwords max other.nwords
-    val words = new Array[Long](len)
-    for (idx <- 0 until len)
-      words(idx) = this.word(idx) | other.word(idx)
-    fromArray(words)
-  }
-
-  def & (other: BitSet): BitSet = {
-    val len = this.nwords min other.nwords
-    val words = new Array[Long](len)
-    for (idx <- 0 until len)
-      words(idx) = this.word(idx) & other.word(idx)
-    fromArray(words)
-  }
-
-  def &~ (other: BitSet): BitSet = {
-    val len = this.nwords
-    val words = new Array[Long](len)
-    for (idx <- 0 until len)
-      words(idx) = this.word(idx) & ~other.word(idx)
-    fromArray(words)
-  }
-
-  def ^ (other: BitSet): BitSet = {
-    val len = this.nwords max other.nwords
-    val words = new Array[Long](len)
-    for (idx <- 0 until len)
-      words(idx) = this.word(idx) ^ other.word(idx)
-    fromArray(words)
-  }
-
-  def contains(elem: Int): Boolean =
-    0 <= elem && (word(elem >> LogWL) & (1L << elem)) != 0L
-
-  def subSet(other: BitSet): Boolean =
-    (0 until nwords) forall (idx => (this.word(idx) & ~ other.word(idx)) == 0L)
-
-  override def equals(other: Any) = other match {
-    case that: BitSet =>
-      (0 until (this.nwords max that.nwords)) forall (idx => this.word(idx) == that.word(idx))
-    case _ =>
-      false
-  }
-
-  override def hashCode: Int = {
-    import scala.util.MurmurHash3._
-    var h = hashSeed
-    var i = 0; while(i < nwords) {
-      val w = word(i)
-      h = mix(h, (w >>> 32).toInt)
-      h = mix(h, w.toInt)
-      i += 1
-    }
-    finalizeHash(h, nwords)
-  }
-
-  def addString(sb: StringBuilder, start: String, sep: String, end: String) {
-    sb append start
-    var pre = ""
-    for (i <- 0 until nwords * WordLength)
-      if (contains(i)) {
-        sb append pre append i
-        pre = sep
-      }
-    sb append end
-  }
-
-  def mkString(start: String, sep: String, end: String) = {
-    val sb = new StringBuilder
-    addString(sb, start, sep, end)
-    sb.toString
-  }
-
-  override def toString = mkString("BitSet(", ", ", ")")
-}
-
-object BitSet {
-
-  private final val WordLength = 64
-  private final val LogWL = 6
-  private val hashSeed = "BitSet".hashCode
-
-  val empty: BitSet = new BitSet1(0L)
-
-  def apply(elems: Int*) = (empty /: elems) (_ + _)
-
-  def fromArray(elems: Array[Long]) = {
-    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 new BitSetN(elems)
-  }
-
-  private def updateArray(elems: Array[Long], idx: Int, w: Long): BitSet = {
-    var len = elems.length
-    while (len > 0 && (elems(len - 1) == 0L || w == 0L && idx == len - 1)) len -= 1
-    var newlen = len
-    if (idx >= newlen && w != 0L) newlen = idx + 1
-    val newelems = new Array[Long](newlen)
-    Array.copy(elems, 0, newelems, 0, len)
-    if (idx < newlen) newelems(idx) = w
-    else assert(w == 0L)
-    fromArray(newelems)
-  }
-
-  class BitSet1(val elems: Long) extends BitSet {
-    protected def nwords = 1
-    protected def word(idx: Int) = if (idx == 0) elems else 0L
-    protected def updateWord(idx: Int, w: Long): BitSet =
-      if (idx == 0) new BitSet1(w)
-      else if (idx == 1) new BitSet2(elems, w)
-      else updateArray(Array(elems), idx, w)
-  }
-
-  class BitSet2(val elems0: Long, elems1: Long) extends BitSet {
-    protected def nwords = 2
-    protected def word(idx: Int) = if (idx == 0) elems0 else if (idx == 1) elems1 else 0L
-    protected def updateWord(idx: Int, w: Long): BitSet =
-      if (idx == 0) new BitSet2(w, elems1)
-      else if (idx == 1) new BitSet2(elems0, w)
-      else updateArray(Array(elems0, elems1), idx, w)
-  }
-
-  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 = updateArray(elems, idx, w)
-  }
-}
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)
 }
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
 }
 
 //############################################################################