KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > util > BitSetIterator


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