01: /* Soot - a J*va Optimization Framework
02: * Copyright (C) 2001 Felix Kwok
03: *
04: * This library is free software; you can redistribute it and/or
05: * modify it under the terms of the GNU Lesser General Public
06: * License as published by the Free Software Foundation; either
07: * version 2.1 of the License, or (at your option) any later version.
08: *
09: * This library is distributed in the hope that it will be useful,
10: * but WITHOUT ANY WARRANTY; without even the implied warranty of
11: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12: * Lesser General Public License for more details.
13: *
14: * You should have received a copy of the GNU Lesser General Public
15: * License along with this library; if not, write to the
16: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17: * Boston, MA 02111-1307, USA.
18: */
19:
20: /*
21: * Modified by the Sable Research Group and others 1997-1999.
22: * See the 'credits' file distributed with Soot for the complete list of
23: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24: */
25:
26: package soot.util;
27:
28: import java.util.*;
29:
30: /** A fast enumerator for sparse bit sets. When the enumerator is
31: * created, it takes a snapshot of the underlying BitVector, and iterates
32: * through the set bits. Note that this class almost implements the
33: * Iterator interface, but it doesn't because the return type of next
34: * is int rather than Object. */
35: public class BitSetIterator {
36:
37: long[] bits; // Bits inherited from the underlying BitVector
38: int index; // The 64-bit block currently being examined
39: long save = 0; // A copy of the 64-bit block (for fast access)
40:
41: /* Computes log_2(x) modulo 67. This uses the fact that 2 is a
42: * primitive root modulo 67 */
43: final static int[] lookup = { -1, 0, 1, 39, 2, 15, 40, 23, 3, 12,
44: 16, 59, 41, 19, 24, 54, 4, -1, 13, 10, 17, 62, 60, 28, 42,
45: 30, 20, 51, 25, 44, 55, 47, 5, 32, -1, 38, 14, 22, 11, 58,
46: 18, 53, -1, 9, 61, 27, 29, 50, 43, 46, 31, 37, 21, 57, 52,
47: 8, 26, 49, 45, 36, 56, 7, 48, 35, 6, 34, 33 };
48:
49: /** Creates a new BitSetIterator */
50: BitSetIterator(long[] bits) {
51: //this.bits = new long[bits.length];
52: //System.arraycopy(bits,0,this.bits,0,bits.length);
53: this .bits = bits;
54: index = 0;
55:
56: /* Zip through empty blocks */
57: while (index < bits.length && bits[index] == 0L)
58: index++;
59: if (index < bits.length)
60: save = bits[index];
61: }
62:
63: /** Returns true if there are more set bits in the BitVector; false otherwise. */
64: public boolean hasNext() {
65: return index < bits.length;
66: }
67:
68: /** Returns the index of the next set bit. Note that the return type is int,
69: * and not Object. */
70: public int next() {
71: if (index >= bits.length)
72: throw new NoSuchElementException();
73:
74: long k = (save & (save - 1)); // Clears the last non-zero bit. save is guaranteed non-zero.
75: long diff = save ^ k; // Finds out which bit it is. diff has exactly one bit set.
76: save = k;
77:
78: // Computes the position of the set bit.
79: int result = (diff < 0) ? 64 * index + 63 : 64 * index
80: + lookup[(int) (diff % 67)];
81:
82: if (save == 0) {
83: index++;
84: while (index < bits.length && bits[index] == 0L)
85: index++;
86: if (index < bits.length)
87: save = bits[index];
88: }
89: return result;
90: }
91: }
|