diff options
author | mihaylov <mihaylov@epfl.ch> | 2006-01-25 23:27:15 +0000 |
---|---|---|
committer | mihaylov <mihaylov@epfl.ch> | 2006-01-25 23:27:15 +0000 |
commit | 09ff70349db0dce12ad010cf375e4b8673dd31e3 (patch) | |
tree | 97503ea9edef66f4e129f2d8bd0bdbae51adeab6 | |
parent | ab90a0a69c57af80fcbafde4c388d209a2104d7f (diff) | |
download | scala-09ff70349db0dce12ad010cf375e4b8673dd31e3.tar.gz scala-09ff70349db0dce12ad010cf375e4b8673dd31e3.tar.bz2 scala-09ff70349db0dce12ad010cf375e4b8673dd31e3.zip |
- improved efficiency
- fixed a bug in the handling of size
-rw-r--r-- | src/library/scala/collection/mutable/BitSet.scala | 33 |
1 files changed, 20 insertions, 13 deletions
diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala index 4662993059..295340a1bf 100644 --- a/src/library/scala/collection/mutable/BitSet.scala +++ b/src/library/scala/collection/mutable/BitSet.scala @@ -29,13 +29,15 @@ class BitSet(initSize: Int) extends collection.BitSet with mutable.Set[Int] { /** ensure that this bitset can store at least <pre>n</pre> bits */ def ensureCapacity(n: Int): Unit = if (capacity < n) { - val newn = memsize(n); - var newsize = (arr.length + 1) * 2; // works even in the case arr.length == 0 - while(newn > newsize) - newsize = newsize * 2; - val newarr = new Array[Int](newsize); - arraycopy(arr, 0, newarr, 0, arr.length); - arr = newarr; + if (nbits(arr.length) < n) { + val newn = memsize(n); + var newsize = if (arr.length == 0) newn else arr.length * 2; + while (newn > newsize) + newsize = newsize * 2; + val newarr = new Array[Int](newsize); + arraycopy(arr, 0, newarr, 0, arr.length); + arr = newarr; + } capacity = n; } @@ -45,18 +47,23 @@ class BitSet(initSize: Int) extends collection.BitSet with mutable.Set[Int] { */ def +=(i: Int): Unit = { ensureCapacity(i+1); - if (!contains(i)) { - arr(offset(i)) = arr(offset(i)) | mask(i); - size = i + 1; + val oldInt = arr(offset(i)); + val newInt = oldInt | mask(i); + if (oldInt != newInt) { + arr(offset(i)) = newInt; + size = size + 1; } } /** Clears <code>i<sup>th</sup></code> bit */ - def -=(i: Int): Unit = - if (i < capacity && contains(i)) { - arr(offset(i)) = arr(offset(i)) & ~mask(i); + def -=(i: Int): Unit = { + val oldInt = arr(offset(i)); + val newInt = oldInt & ~mask(i); + if (oldInt != newInt) { + arr(offset(i)) = newInt; size = size - 1; } + } def clear: Unit = { java.util.Arrays.fill(arr, 0); |