1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
** $Id$
\* */
package scala.collection.mutable ;
/** mutable, resizable bit sets, to represent dense sets of small integers
* Bit indices are between 0..(size-1) inclusive
* @author Burak Emir
* @param initSize: initial size in nbits
*/
[serializable]
class BitSet(initSize: Int) extends scala.collection.BitSet {
import scala.runtime.compat.Platform.arraycopy;
/** default constructor, initial size of 512 bits */
def this() = this( 512 ); // ResizableArray.initialSize << 5
[serializable]
class ByteArray extends AnyRef with ResizableArray[Int] {
final def ensureBits(nbits: Int): Unit = {
val l = array.length;
super[ResizableArray].ensureSize(memsize( nbits ));
}
final def or(j: Int, mask:Int): Unit = {
array.update( j, array(j) | mask );
}
final def and(j: Int, mask:Int): Unit = {
array.update( j, array(j) & mask );
}
def get(j:Int, mask:Int):Boolean = {
(array(j) & mask) != 0;
}
def freeze: Array[Int] = {
val arr = new Array[Int]( array.length );
arraycopy(array, 0, arr, 0, arr.length);
arr
}
}
/** size of this bitset in nbytes */
var size: Int = initSize;
protected val internal = new ByteArray();
internal.ensureBits( size );
/** ensure that this bitset can store at least nbits bits */
def ensureSize(n: Int): Unit = {
internal.ensureBits( n );
if( size < n ) size = n;
}
/** calls set or clear for i-th bit */
final def set(i: Int, b: Boolean): Unit = if( b ) set(i) else clear(i);
/** sets i-th bit to true. Grows to size i+1 if needed. */
final def set(i: Int): Unit = {
ensureSize(i+1);
val j = (i >>> 5);
val mask = (1 << (i & 0x1F));
internal.or(j, mask);
}
/** clears i-th bit. Grows to size i+1 if needed. */
def clear(i: Int): Unit = {
ensureSize(i+1);
val j = (i >>> 5);
val mask = (1 << (i & 0x1F));
internal.and(j, ~mask);
}
/** gets i-th bit. Grows to size i+1 if needed. */
def apply(i: Int):Boolean = {
val j = (i >>> 5);
val mask = (1 << (i & 0x1F));
internal.get(j, mask);
}
def toArray: Array[Int] = internal.freeze;
def makeImmutable = new scala.collection.immutable.BitSet(this);
}
|
