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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2005, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
** $Id$
\* */
package scala.collection.immutable;
/** The class <code>BitSet</code>provides an immutable bitset view on an
* int array. Instances can conveniently be created from instances of
* <code>mutable.ResizableBitSet</code>. Bit indices are between 0..(size-1) inclusive
*
* @param <code>n</code> represents the number of relevant bits
* @param ba: array of ints of length <code>n</code>>>>5
* @param copy: if yes, then <code>ba</code> is copied and updates will
* not affect this bitset
*
* @author Burak Emir
* @version 1.0
*/
[serializable]
class BitSet(n:Int, ba: Array[Int], copy: Boolean) extends collection.BitSet with Ordered[BitSet] {
/** lexicographic ordering */
def compareTo [b >: BitSet <% Ordered[b]](other: b): int = other match {
case that:BitSet =>
val it1 = this.toSet(true).elements;
val it2 = that.toSet(true).elements;
var res = 0;
while((0==res) && it1.hasNext) {
while((0==res) && it2.hasNext) {
if(!it1.hasNext)
res = -1
else {
val i1 = it1.next;
val i2 = it2.next;
if(i1<i2)
res = -1
else if(i1>i2)
res = 1
}
}
if(it1.hasNext)
res = 1
}
if(it2.hasNext)
res = -1;
res
case _ => -(other.compareTo(this))
}
final def size = n;
protected val array: Array[Int] =
if (copy) {
val arr = new Array[Int](ba.length);
java.lang.System.arraycopy(ba, 0, arr, 0, ba.length);
arr
}
else
ba;
/**
* Checks if two bitsets are structurally identical.
*
* @return true, iff both bitsets contain the same sequence of elements.
*/
override def equals(that: Any): Boolean =
that.isInstanceOf[BitSet] &&
{ val other = that.asInstanceOf[BitSet];
(size == other.size) && ( size == 0 || {
var len = memsize( size );
var i = 0;
var res=true;
while(( i< len ) && res ) { // 32 x faster equality check
res = array(i) == other.array(i);
i = i + 1;
}
res
})
} || super.equals(that);
def this(rbs: mutable.BitSet) = {
this(rbs.size, rbs.toArray, false);
}
/** returns true if bit i is set
*
* @param i
*/
def apply(i: Int):Boolean = {
val j = (i >>> 5);
val mask = (1 << (i & 0x1F));
(array(j) & mask) != 0;
}
def makeMutable = {
val rbs = new mutable.BitSet(size) ;
val it = this.toSet(true).elements;
while(it.hasNext) {
rbs.set(it.next)
}
rbs
}
def toArray: Array[Int] = {
val arr = new Array[Int](array.length);
java.lang.System.arraycopy(arr, 0, array, 0, array.length);
arr
}
}
|
