001: /*
002: * Copyright 1999-2005 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package com.sun.tools.javac.util;
027:
028: /** A class for extensible, mutable bit sets.
029: *
030: * <p><b>This is NOT part of any API supported by Sun Microsystems. If
031: * you write code that depends on this, you do so at your own risk.
032: * This code and its internal interfaces are subject to change or
033: * deletion without notice.</b>
034: */
035: @Version("@(#)Bits.java 1.26 07/05/05")
036: public class Bits {
037:
038: private final static int wordlen = 32;
039: private final static int wordshift = 5;
040: private final static int wordmask = wordlen - 1;
041:
042: private int[] bits;
043:
044: /** Construct an initially empty set.
045: */
046: public Bits() {
047: this (new int[1]);
048: }
049:
050: /** Construct a set consisting initially of given bit vector.
051: */
052: public Bits(int[] bits) {
053: this .bits = bits;
054: }
055:
056: /** Construct a set consisting initially of given range.
057: */
058: public Bits(int start, int limit) {
059: this ();
060: inclRange(start, limit);
061: }
062:
063: private void sizeTo(int len) {
064: if (bits.length < len) {
065: int[] newbits = new int[len];
066: System.arraycopy(bits, 0, newbits, 0, bits.length);
067: bits = newbits;
068: }
069: }
070:
071: /** This set = {}.
072: */
073: public void clear() {
074: for (int i = 0; i < bits.length; i++)
075: bits[i] = 0;
076: }
077:
078: /** Return a copy of this set.
079: */
080: public Bits dup() {
081: int[] newbits = new int[bits.length];
082: System.arraycopy(bits, 0, newbits, 0, bits.length);
083: return new Bits(newbits);
084: }
085:
086: /** Include x in this set.
087: */
088: public void incl(int x) {
089: assert x >= 0;
090: sizeTo((x >>> wordshift) + 1);
091: bits[x >>> wordshift] = bits[x >>> wordshift]
092: | (1 << (x & wordmask));
093: }
094:
095: /** Include [start..limit) in this set.
096: */
097: public void inclRange(int start, int limit) {
098: sizeTo((limit >>> wordshift) + 1);
099: 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 0 <= x && x < (bits.length << wordshift)
117: && (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
118: }
119:
120: /** this set = this set & xs.
121: */
122: public Bits andSet(Bits xs) {
123: sizeTo(xs.bits.length);
124: for (int i = 0; i < xs.bits.length; i++)
125: bits[i] = bits[i] & xs.bits[i];
126: return this ;
127: }
128:
129: /** this set = this set | xs.
130: */
131: public Bits orSet(Bits xs) {
132: sizeTo(xs.bits.length);
133: for (int i = 0; i < xs.bits.length; i++)
134: bits[i] = bits[i] | xs.bits[i];
135: return this ;
136: }
137:
138: /** this set = this set \ xs.
139: */
140: public Bits diffSet(Bits xs) {
141: for (int i = 0; i < bits.length; i++) {
142: if (i < xs.bits.length) {
143: bits[i] = bits[i] & ~xs.bits[i];
144: }
145: }
146: return this ;
147: }
148:
149: /** this set = this set ^ xs.
150: */
151: public Bits xorSet(Bits xs) {
152: sizeTo(xs.bits.length);
153: for (int i = 0; i < xs.bits.length; i++)
154: bits[i] = bits[i] ^ xs.bits[i];
155: return this ;
156: }
157:
158: /** Count trailing zero bits in an int. Algorithm from "Hacker's
159: * Delight" by Henry S. Warren Jr. (figure 5-13)
160: */
161: private static int trailingZeroBits(int x) {
162: assert wordlen == 32;
163: if (x == 0)
164: return 32;
165: int n = 1;
166: if ((x & 0xffff) == 0) {
167: n += 16;
168: x >>>= 16;
169: }
170: if ((x & 0x00ff) == 0) {
171: n += 8;
172: x >>>= 8;
173: }
174: if ((x & 0x000f) == 0) {
175: n += 4;
176: x >>>= 4;
177: }
178: if ((x & 0x0003) == 0) {
179: n += 2;
180: x >>>= 2;
181: }
182: return n - (x & 1);
183: }
184:
185: /** Return the index of the least bit position >= x that is set.
186: * If none are set, returns -1. This provides a nice way to iterate
187: * over the members of a bit set:
188: * <pre>
189: * for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
190: * </pre>
191: */
192: public int nextBit(int x) {
193: int windex = x >>> wordshift;
194: if (windex >= bits.length)
195: return -1;
196: int word = bits[windex] & ~((1 << (x & wordmask)) - 1);
197: while (true) {
198: if (word != 0)
199: return (windex << wordshift) + trailingZeroBits(word);
200: windex++;
201: if (windex >= bits.length)
202: return -1;
203: word = bits[windex];
204: }
205: }
206:
207: /** a string representation of this set.
208: */
209: public String toString() {
210: char[] digits = new char[bits.length * wordlen];
211: for (int i = 0; i < bits.length * wordlen; i++)
212: digits[i] = isMember(i) ? '1' : '0';
213: return new String(digits);
214: }
215:
216: /** Test Bits.nextBit(int). */
217: public static void main(String[] args) {
218: java.util.Random r = new java.util.Random();
219: Bits bits = new Bits();
220: int dupCount = 0;
221: for (int i = 0; i < 125; i++) {
222: int k;
223: do {
224: k = r.nextInt(250);
225: } while (bits.isMember(k));
226: System.out.println("adding " + k);
227: bits.incl(k);
228: }
229: int count = 0;
230: for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i + 1)) {
231: System.out.println("found " + i);
232: count++;
233: }
234: if (count != 125)
235: throw new Error();
236: }
237: }
|