diff options
author | buraq <buraq@epfl.ch> | 2004-07-13 12:33:47 +0000 |
---|---|---|
committer | buraq <buraq@epfl.ch> | 2004-07-13 12:33:47 +0000 |
commit | c2505b8e5ed99b02fa60f6220d095d2a8feb3137 (patch) | |
tree | d2f5df1a9045624f6edcc54f44c729f35398b526 | |
parent | 74946c736c35d9852b2414bf05323c7eabb97dd7 (diff) | |
download | scala-c2505b8e5ed99b02fa60f6220d095d2a8feb3137.tar.gz scala-c2505b8e5ed99b02fa60f6220d095d2a8feb3137.tar.bz2 scala-c2505b8e5ed99b02fa60f6220d095d2a8feb3137.zip |
useful for small sets of ints
-rw-r--r-- | sources/scala/collection/mutable/ResizableBitSet.scala | 84 |
1 files changed, 84 insertions, 0 deletions
diff --git a/sources/scala/collection/mutable/ResizableBitSet.scala b/sources/scala/collection/mutable/ResizableBitSet.scala new file mode 100644 index 0000000000..dee4de2505 --- /dev/null +++ b/sources/scala/collection/mutable/ResizableBitSet.scala @@ -0,0 +1,84 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala.collection.mutable ; + +/** resizable bit sets, to represent small sets of integers + * @author Burak Emir + * @param initSize: initial size in nbits + */ +class ResizableBitSet(initSize: Int) with Iterable[Boolean] { + + /** default constructor, initial size of 16 bits */ + def this() = this( 16 ); + + class ByteArray with ResizableArray[Byte] { + override protected val initialSize: Int = initSize >>> 3; + override protected var array: Array[Byte] = new Array[Byte](initialSize); + + /** size of this bitset in nbits */ + def ensureBits(nbits: Int): Unit = ensureSize(nbits >>> 3); + + final def and(j: Int, mask:Int): Unit = { + array.update( j, (array(j) & mask).asInstanceOf[Byte] ); + } + final def or(j: Int, mask:Int): Unit = { + array.update( j, (array(j) | mask).asInstanceOf[Byte] ); + } + def get(j:Int, mask:Int):Boolean = { + (array(j) & mask) != 0; + } + } + + protected val internal = new ByteArray(); + + /** size of this bitset in nbytes */ + protected var size: Int = 0; + + /** size of this bitset in nbits */ + def ensureSize(nbits: Int): Unit = { + internal.ensureBits( nbits ); + size = nbits; + } + + /** Returns the length of this resizable bitset in nbytes */ + def length: Int = size; + + /** Returns a new iterator over all elements of this resizable array. */ + def elements: Iterator[Boolean] = new Iterator[Boolean] { + var i = 0; + def hasNext: Boolean = i < length; + def next: Boolean = { + val j = i >>> 3; + val mask = (1 << (i & 0x07)); + i = i + 1; + internal.get(j,mask) + } + } + + final def set(i: Int, b: Boolean): Unit = if( b ) set(i) else clear(i); + + final def set(i: Int): Unit = { + val j = (i >>> 3); + val mask = (1 << (i & 0x07)); + internal.or(j, mask); + } + + def clear(i: Int): Unit = { + val j = (i >>> 3); + val mask = (1 << (i & 0x07)); + internal.and(j, ~mask); + } + + def get(i: Int):Boolean = { + val j = (i >>> 3); + val mask = (1 << (i & 0x07)); + internal.get(j, mask); + } +} |