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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2010, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection
package mutable
import generic._
import BitSetLike.{LogWL, updateArray}
/** A class for mutable bitsets.
* $bitsetinfo
*
* @author Martin Odersky
* @version 2.8
* @since 1
*/
@serializable @SerialVersionUID(8483111450368547763L)
class BitSet(protected var elems: Array[Long]) extends Set[Int]
with scala.collection.BitSet
with BitSetLike[BitSet]
with SetLike[Int, BitSet] {
override def empty = BitSet.empty
def this(initSize: Int) = this(new Array[Long]((initSize + 63) >> 6 max 1))
def this() = this(0)
protected def nwords = elems.length
protected def word(idx: Int): Long =
if (idx < nwords) elems(idx) else 0L
private def updateWord(idx: Int, w: Long) {
if (idx >= nwords) {
var newlen = nwords
while (idx >= newlen) newlen = newlen * 2
val elems1 = new Array[Long](newlen)
Array.copy(elems, 0, elems1, 0, nwords)
elems = elems1
}
elems(idx) = w
}
protected def fromArray(words: Array[Long]): BitSet = new BitSet(words)
override def add(elem: Int): Boolean = {
require(elem >= 0)
if (contains(elem)) false
else {
val idx = elem >> LogWL
updateWord(idx, word(idx) | (1L << elem))
true
}
}
override def remove(elem: Int): Boolean = {
require(elem >= 0)
if (contains(elem)) {
val idx = elem >> LogWL
updateWord(idx, word(idx) & ~(1L << elem))
true
} else false
}
def += (elem: Int): this.type = { add(elem); this }
def -= (elem: Int): this.type = { remove(elem); this }
override def clear() {
elems = new Array[Long](elems.length)
}
/** Wraps this bitset as an immutable bitset backed by the array of bits
* of this bitset.
* @note Subsequent changes in this bitset will be reflected in the returned immutable bitset.
*/
def toImmutable = immutable.BitSet.fromArray(elems)
override def clone(): BitSet = {
val elems1 = new Array[Long](elems.length)
Array.copy(elems, 0, elems1, 0, elems.length)
new BitSet(elems1)
}
}
object BitSet extends BitSetFactory[BitSet] {
def empty: BitSet = new BitSet
/** $canBuildFromInfo */
implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom
}
|