From 1b3a379e7b0518279ceae3a47135df35b4fe3439 Mon Sep 17 00:00:00 2001
From: Eugene Vigdorchik <eugene.vigdorchik@gmail.com>
Date: Thu, 21 Mar 2013 12:14:52 +0400
Subject: SI-7102 Specialize isEmpty for bitsets

Currently bitsets use default isEmpty implementation inherited from
Set, which tests for "size == 0".

Calculating the size of a word in a bitmap requires summing through
all bits set, whereas testing for emptyness needs only one comparison
with zero.

This commit overrides the default implementation with the specialized
one looking for a non-zero word in this bitmap.
---
 src/library/scala/collection/BitSetLike.scala |  2 ++
 test/files/run/bitsets.scala                  | 13 +++++++++++++
 2 files changed, 15 insertions(+)

diff --git a/src/library/scala/collection/BitSetLike.scala b/src/library/scala/collection/BitSetLike.scala
index 72a6713ffd..034ed2b24a 100644
--- a/src/library/scala/collection/BitSetLike.scala
+++ b/src/library/scala/collection/BitSetLike.scala
@@ -69,6 +69,8 @@ trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSe
     s
   }
 
+  override def isEmpty: Boolean = 0 until nwords forall (i => word(i) == 0)
+
   implicit def ordering: Ordering[Int] = Ordering.Int
 
   def rangeImpl(from: Option[Int], until: Option[Int]): This = {
diff --git a/test/files/run/bitsets.scala b/test/files/run/bitsets.scala
index 0ea43fcb95..d55f9e4e83 100644
--- a/test/files/run/bitsets.scala
+++ b/test/files/run/bitsets.scala
@@ -37,6 +37,19 @@ object TestMutable {
   Console.println("mi1 = " + ms1.toImmutable)
   Console.println("mi2 = " + ms2.toImmutable)
   Console.println
+
+  val N = 257
+  val gen = 3
+  val bs = BitSet((1 until N): _*)
+  (1 until N).foldLeft(gen) {
+    case (acc, i) =>
+      assert(bs.size == N-i, s"Bad size for $bs, expected ${N-i} actual ${bs.size}")
+      assert(!bs.isEmpty, s"Unexpected isEmpty for $bs")
+      bs -= acc
+      acc*gen % N
+  }
+  assert(bs.size == 0, s"Expected size == 0 for $bs")
+  assert(bs.isEmpty, s"Expected isEmpty for $bs")
 }
 
 object TestMutable2 {
-- 
cgit v1.2.3