blob: 66b279cf376caab310177c575f2c4e6a018792c5 (
plain) (
blame)
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
package scala.collection.generic
import BitSetTemplate._
import generic._
/** common base class for mutable and immutable bit sets
*/
trait BitSetTemplate[+This <: BitSetTemplate[This] with Set[Int]] extends SetTemplate[Int, This] { self =>
def empty: This
/** The number of words (each with 64 bits) making up the set */
protected def nwords: Int
/** The words at index `idx', or 0L if outside the range of the set
* @pre idx >= 0
*/
protected def word(idx: Int): Long
/** Create a new set of this kind from an array of longs
*/
protected def fromArray(elems: Array[Long]): This
/** The number of elements in the bitset.
*/
override def size: Int = {
var s = 0
var i = nwords
while (i > 0) {
i -= 1
s += popCount(word(i))
}
s
}
def iterator = new Iterator[Int] {
private var current = 0
private val end = nwords * WordLength
def hasNext: Boolean = {
while (current < end && !self.contains(current)) current += 1
current < end
}
def next(): Int =
if (hasNext) { val r = current; current += 1; r }
else Iterator.empty.next
}
override def foreach[B](f: Int => B) {
for (i <- 0 until nwords) {
val w = word(i)
for (j <- i * WordLength until (i + 1) * WordLength) {
if ((w & (1L << j)) != 0) f(j)
}
}
}
/** A new bitset which is the logical or of this set and the given argument set.
*/
def | (other: BitSet): This = {
val len = this.nwords max other.nwords
val words = new Array[Long](len)
for (idx <- 0 until len)
words(idx) = this.word(idx) | other.word(idx)
fromArray(words)
}
/** A new bitset which is the logical and of this set and the given argument set.
*/
def & (other: BitSet): This = {
val len = this.nwords min other.nwords
val words = new Array[Long](len)
for (idx <- 0 until len)
words(idx) = this.word(idx) & other.word(idx)
fromArray(words)
}
/** A new bitset which is the logical and-not of this set and the given argument set.
*/
def &~ (other: BitSet): This = {
val len = this.nwords
val words = new Array[Long](len)
for (idx <- 0 until len)
words(idx) = this.word(idx) & ~other.word(idx)
fromArray(words)
}
/** A new bitset which is the logical exclusive or of this set and the given argument set.
*/
def ^ (other: BitSet): This = {
val len = this.nwords max other.nwords
val words = new Array[Long](len)
for (idx <- 0 until len)
words(idx) = this.word(idx) ^ other.word(idx)
fromArray(words)
}
/** Does the set contain the given element?
*/
def contains(elem: Int): Boolean =
0 <= elem && (word(elem >> LogWL) & (1L << elem)) != 0
/** Is the set a subset of the given bitset
*/
def subSet(other: BitSet): Boolean =
(0 until nwords) forall (idx => (this.word(idx) & ~ other.word(idx)) == 0L)
/** Add bitset elements as numbers to string buffer
*/
override def addString(sb: StringBuilder, start: String, sep: String, end: String) = {
sb append start
var pre = ""
for (i <- 0 until nwords * WordLength)
if (contains(i)) {
sb append pre append i
pre = sep
}
sb append end
}
}
object BitSetTemplate {
private[collection] val LogWL = 6
private val WordLength = 64
private[collection] def updateArray(elems: Array[Long], idx: Int, w: Long): Array[Long] = {
var len = elems.length
while (len > 0 && (elems(len - 1) == 0L || w == 0L && idx == len - 1)) len -= 1
var newlen = len
if (idx >= newlen && w != 0L) newlen = idx + 1
val newelems = new Array[Long](newlen)
Array.copy(elems, 0, newelems, 0, len)
if (idx < newlen) newelems(idx) = w
else assert(w == 0L)
newelems
}
private val pc1: Array[Int] = {
def countBits(x: Int): Int = if (x == 0) 0 else x % 2 + countBits(x >>> 1)
Array.tabulate(256)(countBits _)
}
private def popCount(w: Long): Int = {
def pc2(w: Int) = if (w == 0) 0 else pc1(w & 0xff) + pc1(w >>> 8)
def pc4(w: Int) = if (w == 0) 0 else pc2(w & 0xffff) + pc2(w >>> 16)
if (w == 0) 0 else pc4(w.toInt) + pc4((w >>> 32).toInt)
}
}
|
