diff options
author | mihaylov <mihaylov@epfl.ch> | 2006-01-25 23:17:57 +0000 |
---|---|---|
committer | mihaylov <mihaylov@epfl.ch> | 2006-01-25 23:17:57 +0000 |
commit | ab90a0a69c57af80fcbafde4c388d209a2104d7f (patch) | |
tree | 1b1f193cd6f55543bee7be201350525d2fa730f4 | |
parent | 5953fca1fe8c7260b99cea8a86bdf8439b48ffc2 (diff) | |
download | scala-ab90a0a69c57af80fcbafde4c388d209a2104d7f.tar.gz scala-ab90a0a69c57af80fcbafde4c388d209a2104d7f.tar.bz2 scala-ab90a0a69c57af80fcbafde4c388d209a2104d7f.zip |
Added a fast subsetOf implementation
-rw-r--r-- | src/library/scala/collection/BitSet.scala | 38 |
1 files changed, 35 insertions, 3 deletions
diff --git a/src/library/scala/collection/BitSet.scala b/src/library/scala/collection/BitSet.scala index b65c7deb7e..f9180ac49e 100644 --- a/src/library/scala/collection/BitSet.scala +++ b/src/library/scala/collection/BitSet.scala @@ -59,6 +59,7 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] { /** * Checks if two bitsets are structurally identical. + * Uses accelerated (32 x faster) check if the other set is a BitSet * * @return true, iff both bitsets contain the same elements. */ @@ -69,7 +70,7 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] { var len = memsize(min(this.capacity, other.capacity)); var i = 0; var res = true; - while((i < len) && res) { // 32 x faster equality check + while((i < len) && res) { res = arr(i) == other.arr(i); i = i + 1; } @@ -78,8 +79,39 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] { } || super.equals(that) ); - /** returns number of Int cells needed to store n bits */ - protected final def memsize(n:Int) = offset(n + 31); + /** + * Checks if this set is a subset of set <code>that</code>. + * Uses accelerated (32 x faster) check if the other set is a BitSet + * + * @param that another set. + * @return true, iff the other set is a superset of this set. + */ + override def subsetOf(that: Set[Int]): Boolean = + (that.isInstanceOf[BitSet] && { + val other = that.asInstanceOf[BitSet]; + val len = memsize(min(this.capacity, other.capacity)); + var i = 0; + var res = true; + while((i < len) && res) { + res = other.arr(i) == (other.arr(i) | arr(i)); + i = i + 1; + } + res && (this.capacity <= other.capacity || { + // if this set is bigger check that the rest is empty + while (i < memsize(this.capacity) && res) { + res == arr(i) == 0; + i = i + 1 + } + res + }) + }) || super.subsetOf(that); + + + /** @return the number of Int cells needed to store <code>n</code> bits */ + protected final def memsize(n: Int): Int = offset(n + 31); + + /** @return the number of bits represented by <code>n</code> words */ + protected final def nbits(n: Int): Int = n << 5; /** @return the position in the array where the bit resides */ protected final def offset(n: Int): Int = n >>> 5; |