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
117
118
119
120
121
122
123
124
125
126
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2006, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection
/** <p>
* The class <code>BitSet</code> provides the interface for a space-efficient
* implementation of dense integer sets represented as bits in array of
* integers. Bit indices are between <code>0..(capacity-1)</code> inclusive.
* </p>
*
* @author Burak Emir, Stephane Micheloud, Nikolay Mihaylov
* @version 1.1
*/
abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] {
import compat.Platform.arraycopy
import compat.Math.min
/** number of bits in this bitset */
def size: Int
/** @return true if bit i is set */
def contains(i: Int): Boolean =
(i < capacity) && ((arr(offset(i)) & mask(i)) != 0)
def capacity: Int
protected def arr: Array[Int]
/** returns an iterator over the truth values of all bits */
final def elements: Iterator[Int] = new Iterator[Int] {
var i = 0
def findNext: Unit = {
while (!BitSet.this.contains(i) && (i < capacity))
i = i + 1
}
findNext
def hasNext: Boolean = i < capacity
def next: Int = { val j = i; i = i + 1; findNext; j }
}
/**
* @return a copy of the array underlying this bitset
*/
def toArray: Array[Int] = {
val length = memsize(capacity)
val newarr = new Array[Int](length)
arraycopy(newarr, 0, this.arr, 0, length)
newarr
}
/**
* 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.
*/
override def equals(that: Any): Boolean = (
that.isInstanceOf[BitSet] &&
{ val other = that.asInstanceOf[BitSet];
(size == other.size) && ( size == 0 || {
var len = memsize(min(this.capacity, other.capacity))
var i = 0
var res = true
while ((i < len) && res) {
res = arr(i) == other.arr(i)
i = i + 1
}
res
})
} || super.equals(that)
);
/**
* 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
/** @return a mask with 1 at the position of the bit */
protected final def mask(n: Int): Int = 1 << (n & 0x1F)
}
|
