10
|
1 |
/*
|
|
2 |
* Copyright 1999-2005 Sun Microsystems, Inc. All Rights Reserved.
|
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
|
4 |
*
|
|
5 |
* This code is free software; you can redistribute it and/or modify it
|
|
6 |
* under the terms of the GNU General Public License version 2 only, as
|
|
7 |
* published by the Free Software Foundation. Sun designates this
|
|
8 |
* particular file as subject to the "Classpath" exception as provided
|
|
9 |
* by Sun in the LICENSE file that accompanied this code.
|
|
10 |
*
|
|
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT
|
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that
|
|
15 |
* accompanied this code).
|
|
16 |
*
|
|
17 |
* You should have received a copy of the GNU General Public License version
|
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation,
|
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
|
20 |
*
|
|
21 |
* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
|
22 |
* CA 95054 USA or visit www.sun.com if you need additional information or
|
|
23 |
* have any questions.
|
|
24 |
*/
|
|
25 |
|
|
26 |
package com.sun.tools.javac.util;
|
|
27 |
|
|
28 |
/** A class for extensible, mutable bit sets.
|
|
29 |
*
|
|
30 |
* <p><b>This is NOT part of any API supported by Sun Microsystems. If
|
|
31 |
* you write code that depends on this, you do so at your own risk.
|
|
32 |
* This code and its internal interfaces are subject to change or
|
|
33 |
* deletion without notice.</b>
|
|
34 |
*/
|
|
35 |
public class Bits {
|
|
36 |
|
|
37 |
|
|
38 |
private final static int wordlen = 32;
|
|
39 |
private final static int wordshift = 5;
|
|
40 |
private final static int wordmask = wordlen - 1;
|
|
41 |
|
|
42 |
private int[] bits;
|
|
43 |
|
|
44 |
/** Construct an initially empty set.
|
|
45 |
*/
|
|
46 |
public Bits() {
|
|
47 |
this(new int[1]);
|
|
48 |
}
|
|
49 |
|
|
50 |
/** Construct a set consisting initially of given bit vector.
|
|
51 |
*/
|
|
52 |
public Bits(int[] bits) {
|
|
53 |
this.bits = bits;
|
|
54 |
}
|
|
55 |
|
|
56 |
/** Construct a set consisting initially of given range.
|
|
57 |
*/
|
|
58 |
public Bits(int start, int limit) {
|
|
59 |
this();
|
|
60 |
inclRange(start, limit);
|
|
61 |
}
|
|
62 |
|
|
63 |
private void sizeTo(int len) {
|
|
64 |
if (bits.length < len) {
|
|
65 |
int[] newbits = new int[len];
|
|
66 |
System.arraycopy(bits, 0, newbits, 0, bits.length);
|
|
67 |
bits = newbits;
|
|
68 |
}
|
|
69 |
}
|
|
70 |
|
|
71 |
/** This set = {}.
|
|
72 |
*/
|
|
73 |
public void clear() {
|
|
74 |
for (int i = 0; i < bits.length; i++) bits[i] = 0;
|
|
75 |
}
|
|
76 |
|
|
77 |
/** Return a copy of this set.
|
|
78 |
*/
|
|
79 |
public Bits dup() {
|
|
80 |
int[] newbits = new int[bits.length];
|
|
81 |
System.arraycopy(bits, 0, newbits, 0, bits.length);
|
|
82 |
return new Bits(newbits);
|
|
83 |
}
|
|
84 |
|
|
85 |
/** Include x in this set.
|
|
86 |
*/
|
|
87 |
public void incl(int x) {
|
|
88 |
assert x >= 0;
|
|
89 |
sizeTo((x >>> wordshift) + 1);
|
|
90 |
bits[x >>> wordshift] = bits[x >>> wordshift] |
|
|
91 |
(1 << (x & wordmask));
|
|
92 |
}
|
|
93 |
|
|
94 |
|
|
95 |
/** Include [start..limit) in this set.
|
|
96 |
*/
|
|
97 |
public void inclRange(int start, int limit) {
|
|
98 |
sizeTo((limit >>> wordshift) + 1);
|
|
99 |
for (int x = start; x < limit; x++)
|
|
100 |
bits[x >>> wordshift] = bits[x >>> wordshift] |
|
|
101 |
(1 << (x & wordmask));
|
|
102 |
}
|
|
103 |
|
|
104 |
/** Exclude x from this set.
|
|
105 |
*/
|
|
106 |
public void excl(int x) {
|
|
107 |
assert x >= 0;
|
|
108 |
sizeTo((x >>> wordshift) + 1);
|
|
109 |
bits[x >>> wordshift] = bits[x >>> wordshift] &
|
|
110 |
~(1 << (x & wordmask));
|
|
111 |
}
|
|
112 |
|
|
113 |
/** Is x an element of this set?
|
|
114 |
*/
|
|
115 |
public boolean isMember(int x) {
|
|
116 |
return
|
|
117 |
0 <= x && x < (bits.length << wordshift) &&
|
|
118 |
(bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
|
|
119 |
}
|
|
120 |
|
|
121 |
/** this set = this set & xs.
|
|
122 |
*/
|
|
123 |
public Bits andSet(Bits xs) {
|
|
124 |
sizeTo(xs.bits.length);
|
|
125 |
for (int i = 0; i < xs.bits.length; i++)
|
|
126 |
bits[i] = bits[i] & xs.bits[i];
|
|
127 |
return this;
|
|
128 |
}
|
|
129 |
|
|
130 |
/** this set = this set | xs.
|
|
131 |
*/
|
|
132 |
public Bits orSet(Bits xs) {
|
|
133 |
sizeTo(xs.bits.length);
|
|
134 |
for (int i = 0; i < xs.bits.length; i++)
|
|
135 |
bits[i] = bits[i] | xs.bits[i];
|
|
136 |
return this;
|
|
137 |
}
|
|
138 |
|
|
139 |
/** this set = this set \ xs.
|
|
140 |
*/
|
|
141 |
public Bits diffSet(Bits xs) {
|
|
142 |
for (int i = 0; i < bits.length; i++) {
|
|
143 |
if (i < xs.bits.length) {
|
|
144 |
bits[i] = bits[i] & ~xs.bits[i];
|
|
145 |
}
|
|
146 |
}
|
|
147 |
return this;
|
|
148 |
}
|
|
149 |
|
|
150 |
/** this set = this set ^ xs.
|
|
151 |
*/
|
|
152 |
public Bits xorSet(Bits xs) {
|
|
153 |
sizeTo(xs.bits.length);
|
|
154 |
for (int i = 0; i < xs.bits.length; i++)
|
|
155 |
bits[i] = bits[i] ^ xs.bits[i];
|
|
156 |
return this;
|
|
157 |
}
|
|
158 |
|
|
159 |
/** Count trailing zero bits in an int. Algorithm from "Hacker's
|
|
160 |
* Delight" by Henry S. Warren Jr. (figure 5-13)
|
|
161 |
*/
|
|
162 |
private static int trailingZeroBits(int x) {
|
|
163 |
assert wordlen == 32;
|
|
164 |
if (x == 0) return 32;
|
|
165 |
int n = 1;
|
|
166 |
if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
|
|
167 |
if ((x & 0x00ff) == 0) { n += 8; x >>>= 8; }
|
|
168 |
if ((x & 0x000f) == 0) { n += 4; x >>>= 4; }
|
|
169 |
if ((x & 0x0003) == 0) { n += 2; x >>>= 2; }
|
|
170 |
return n - (x&1);
|
|
171 |
}
|
|
172 |
|
|
173 |
/** Return the index of the least bit position >= x that is set.
|
|
174 |
* If none are set, returns -1. This provides a nice way to iterate
|
|
175 |
* over the members of a bit set:
|
|
176 |
* <pre>
|
|
177 |
* for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
|
|
178 |
* </pre>
|
|
179 |
*/
|
|
180 |
public int nextBit(int x) {
|
|
181 |
int windex = x >>> wordshift;
|
|
182 |
if (windex >= bits.length) return -1;
|
|
183 |
int word = bits[windex] & ~((1 << (x & wordmask))-1);
|
|
184 |
while (true) {
|
|
185 |
if (word != 0)
|
|
186 |
return (windex << wordshift) + trailingZeroBits(word);
|
|
187 |
windex++;
|
|
188 |
if (windex >= bits.length) return -1;
|
|
189 |
word = bits[windex];
|
|
190 |
}
|
|
191 |
}
|
|
192 |
|
|
193 |
/** a string representation of this set.
|
|
194 |
*/
|
|
195 |
public String toString() {
|
|
196 |
char[] digits = new char[bits.length * wordlen];
|
|
197 |
for (int i = 0; i < bits.length * wordlen; i++)
|
|
198 |
digits[i] = isMember(i) ? '1' : '0';
|
|
199 |
return new String(digits);
|
|
200 |
}
|
|
201 |
|
|
202 |
/** Test Bits.nextBit(int). */
|
|
203 |
public static void main(String[] args) {
|
|
204 |
java.util.Random r = new java.util.Random();
|
|
205 |
Bits bits = new Bits();
|
|
206 |
int dupCount = 0;
|
|
207 |
for (int i=0; i<125; i++) {
|
|
208 |
int k;
|
|
209 |
do {
|
|
210 |
k = r.nextInt(250);
|
|
211 |
} while (bits.isMember(k));
|
|
212 |
System.out.println("adding " + k);
|
|
213 |
bits.incl(k);
|
|
214 |
}
|
|
215 |
int count = 0;
|
|
216 |
for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i+1)) {
|
|
217 |
System.out.println("found " + i);
|
|
218 |
count ++;
|
|
219 |
}
|
|
220 |
if (count != 125) throw new Error();
|
|
221 |
}
|
|
222 |
}
|