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
148
149
150
151
152
153
154
155
156
157
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $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
* @author Martin Odersky
* @version 2.0 01/01/2007
*/
abstract class BitSet extends Set[Int] {
import compat.Platform.arraycopy
/** number of bits in this bitset */
def size: Int
/**
* @param i ...
* @return <code>true</code> if bit <code>i</code> is set.
*/
def contains(i: Int): Boolean = {
(i < capacity) && {
val j = offset(i)
(0 <= j) && (j < arr.length) &&
((arr(j) & 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)
if (arr.length > 0)
arraycopy(this.arr, 0, newarr, 0, length)
newarr
}*/
/** Checks if two bitsets are structurally identical.
* Uses accelerated (32 x faster) check if the other set is a BitSet
*
* @param other ...
* @return <code>true</code>, iff both bitsets contain the same
* elements.
*/
override def equals(other: Any): Boolean = other match {
case that: BitSet =>
(size == that.size) && {
var len = memsize(Math.min(this.capacity, that.capacity))
var i = 0
while (i < len && arr(i) == that.arr(i)) i = i + 1
i == len
}
case _ =>
super.equals(other)
}
override def hashCode(): Int = {
val len = memsize(this.capacity)
var h = 0
var i = 0
while (i < len) { h = h * 41 + arr(i); i = i + 1 }
h
}
/** 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 other another set.
* @return <code>true</code>, iff the other set is a superset of
* this set.
*/
override def subsetOf(other: Set[Int]): Boolean = other match {
case that: BitSet =>
val thisLen = memsize(this.capacity)
val thatLen = memsize(that.capacity)
val minLen = Math.min(thisLen, thatLen)
var i = 0
while (i < minLen && that.arr(i) == (that.arr(i) | arr(i))) i = i + 1
while (i < thisLen && arr(i) == 0) i = i + 1
i == thisLen
case _ =>
super.subsetOf(other)
}
/**
* @param n the number of bits to be stored.
* @return the number of <code>Int</code> cells needed to store
* <code>n</code> bits.
*/
protected final def memsize(n: Int): Int = offset(n + 31)
/**
* @param n ...
* @return the number of bits represented by <code>n</code> words.
*/
protected final def nbits(n: Int): Int = n << 5
/**
* @param n ...
* @return the position in the array where the bit resides.
*/
protected final def offset(n: Int): Int = n >>> 5
/**
* @param n ...
* @return a mask with 1 at the position of the bit.
*/
protected final def mask(n: Int): Int = 1 << (n & 0x1F)
/**
* @return a copy of the array underlying this bitset
*/
def underlying : Array[Int] = {
val length = memsize(capacity)
val newarr = new Array[Int](length)
if (arr.length > 0)
arraycopy(this.arr, 0, newarr, 0, length)
newarr
}
protected override def stringPrefix = "Set"
}
|
