BitVector


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 2003 Ondrej Lhotak
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  package soot.util;
21  
22  /** This is the Soot internal implementation of java.util.BitSet with
23   * Felix and Jerome's clever efficient iterator. It was re-implemented
24   * from scratch by Ondrej Lhotak to avoid licence issues. It was named
25   * BitVector rather than BitSet to avoid a name clash with the one in
26   * the standard Java library.
27   *
28   * @author Ondrej Lhotak
29   */
30  public class BitVector
31  { 
32      public BitVector() {
33          this(64);
34      }
35      public BitVector( int numBits ) {
36          int lastIndex = indexOf( numBits-1 );
37          bits = new long[lastIndex+1];
38      }
39      private long[] bits;
40      private int indexOf( int bit ) {
41          return bit >> 6;
42      }
43      private long mask( int bit ) {
44          return 1L << ( bit & 63 );
45      }
46      public void and(BitVector other) {
47          if( this == other ) return;
48          long[] otherBits = other.bits;
49          int numToAnd = otherBits.length;
50          if( bits.length < numToAnd ) numToAnd = bits.length;
51          int i;
52          for( i = 0; i < numToAnd; i++ ) {
53              bits[i] = bits[i] & otherBits[i];
54          }
55          for( ; i < bits.length; i++ ) {
56              bits[i] = 0L;
57          }
58      }
59      public void andNot(BitVector other) {
60          long[] otherBits = other.bits;
61          int numToAnd = otherBits.length;
62          if( bits.length < numToAnd ) numToAnd = bits.length;
63          for( int i = 0; i < numToAnd; i++ ) {
64              bits[i] = bits[i] & ~otherBits[i];
65          }
66      }
67      public void clear( int bit ) {
68          if( indexOf(bit) < bits.length )
69              bits[indexOf(bit)] &= ~mask(bit);
70      }
71      public Object   clone() {
72          BitVector ret = new BitVector( length() );
73          System.arraycopy( bits, 0, ret.bits, 0, ret.bits.length );
74          return ret;
75      }
76      public boolean equals( Object   o ) {
77          if( !( o instanceof BitVector ) ) return false;
78          BitVector other = (BitVector) o;
79          int min = bits.length;
80          long[] longer = other.bits;
81          if( other.bits.length < min ) {
82              min = other.bits.length;
83              longer = bits;
84          }
85          int i;
86          for( i = 0; i < min; i++ ) {
87              if( bits[i] != other.bits[i] ) return false;
88          }
89          for( ; i < longer.length; i++ ) {
90              if( longer[i] != 0L ) return false;
91          }
92          return true;
93      }
94      public boolean get( int bit ) {
95          if( indexOf(bit) >= bits.length ) return false;
96          return ( bits[indexOf(bit)] & mask(bit) ) != 0L;
97      }
98      public int hashCode() {
99          long ret = 0;
100         for( int i = 0; i < bits.length; i++ ) {
101             ret ^= bits[i];
102         }
103         return (int) ( (ret >> 32) ^ ret );
104     }
105     public int length() {
106         int i;
107         for( i = bits.length-1; i >= 0; i-- ) {
108             if( bits[i] != 0L ) break;
109         }
110         if( i < 0 ) return 0;
111         long j = bits[i];
112         i++;
113         i <<= 6;
114         for( long k = 1L << 63; (k&j) == 0L; k >>=1, i-- );
115         return i;
116     }
117     public void copyFrom( BitVector other ) {
118         if( this == other ) return;
119         long[] otherBits = other.bits;
120         int j;
121         for( j = otherBits.length-1; j >= 0; j-- ) {
122             if( otherBits[j] != 0L ) break;
123         }
124         expand( j<<6 );
125         int i = j+1;
126         for( ; j >= 0; j-- ) {
127             bits[j] = otherBits[j];
128         }
129         for( ; i < bits.length; i++ ) {
130             bits[i] = 0L;
131         }
132     }
133     public void or( BitVector other ) {
134         if( this == other ) return;
135         long[] otherBits = other.bits;
136         int j;
137         for( j = otherBits.length-1; j >= 0; j-- ) {
138             if( otherBits[j] != 0L ) break;
139         }
140         expand( j<<6 );
141         for( ; j >= 0; j-- ) {
142             bits[j] |= otherBits[j];
143         }
144     }
145     private void expand( int bit ) {
146         int n = indexOf( bit )+1;
147         if( n <= bits.length ) return;
148         if( bits.length*2 > n ) n = bits.length*2;
149         long[] newBits = new long[n];
150         System.arraycopy( bits, 0, newBits, 0, bits.length );
151         bits = newBits;
152     }
153     public void xor( BitVector other ) {
154         if( this == other ) return;
155         long[] otherBits = other.bits;
156         int j;
157         for( j = otherBits.length-1; j >= 0; j-- ) {
158             if( otherBits[j] != 0L ) break;
159         }
160         expand( j<<6 );
161         for( ; j >= 0; j-- ) {
162             bits[j] ^= otherBits[j];
163         }
164     }
165     public boolean set( int bit ) {
166         expand(bit);
167         boolean ret = !get(bit);
168         bits[indexOf(bit)] |= mask(bit);
169         return ret;
170     }
171     public int size() {
172         return bits.length << 6;
173     }
174     public String   toString() {
175         StringBuffer   ret = new StringBuffer  ();
176         ret.append('{');
177         boolean start = true;
178         BitSetIterator it = new BitSetIterator( bits );
179         while( it.hasNext() ) {
180             int bit = it.next();
181             if( !start ) ret.append( ", " );
182             start = false;
183             ret.append(bit);
184         }
185         ret.append('}');
186         return ret.toString();
187     }
188     /*
189     public boolean orAndAndNotCheck(BitVector orset, BitVector andset, BitVector andnotset) {
190         BitVector orAndAnd = (BitVector) orset.clone();
191         if( andset != null ) orAndAnd.and( andset );
192         if( andnotset != null ) orAndAnd.andNot( andnotset );
193         orAndAnd.or( this );
194         boolean ret = !orAndAnd.equals(this);
195         orAndAndNotOld( orset, andset, andnotset );
196         if( !this.equals( orAndAnd ) ) {
197             throw new RuntimeException( "orset is "+orset+"\nandset is "+andset+"\nandnotset is "+andnotset+"\nthis is "+this+"\ncorrect is "+orAndAnd );
198         }
199         return ret;
200     }
201     */
202     /**
203      * Computes this = this OR ((orset AND andset ) AND (NOT andnotset))
204      * Returns true iff this is modified.
205      * @param set a bit set.
206      */
207     public boolean orAndAndNot(BitVector orset, BitVector andset, BitVector andnotset) {
208         boolean ret = false;
209         long[] a = null, b = null, c = null, d = null, e = null;
210         int al, bl, cl, dl, el;
211         a = this.bits;
212         al = a.length;
213         if( orset == null ) {
214             bl = 0;
215         } else {
216             b = orset.bits;
217             bl = b.length;
218         }
219         if( andset == null ) {
220             cl = 0;
221         } else {
222             c = andset.bits;
223             cl = c.length;
224         }
225         if( andnotset == null ) {
226             dl = 0;
227         } else {
228             d = andnotset.bits;
229             dl = d.length;
230         }
231 
232         if( al < bl ) {
233             e = new long[bl];
234             System.arraycopy( a, 0, e, 0, al );
235             this.bits = e;
236         } else {
237             e = a;
238         }
239         el = e.length;
240 
241         // INV: el >= bl
242 
243         int i = 0;
244         long l;
245 
246         if( c == null ) {
247             if( dl <= bl ) {
248                 while( i < dl ) {
249                     l = b[i] & ~d[i];
250                     if( (l & ~e[i]) != 0 ) ret = true;
251                     e[i] |= l;
252                     i++;
253                 }
254                 while( i < bl ) {
255                     l = b[i];
256                     if( (l & ~e[i]) != 0 ) ret = true;
257                     e[i] |= l;
258                     i++;
259                 }
260             } else {
261                 while( i < bl ) {
262                     l = b[i] & ~d[i];
263                     if( (l & ~e[i]) != 0 ) ret = true;
264                     e[i] |= l;
265                     i++;
266                 }
267             }
268         } else if( bl <= cl && bl <= dl ) {
269             // bl is the shortest
270             while( i < bl ) {
271                 l = b[i] & c[i] & ~d[i];
272                 if( (l & ~e[i]) != 0 ) ret = true;
273                 e[i] |= l;
274                 i++;
275             }
276         } else if( cl <= bl && cl <= dl ) {
277             // cl is the shortest
278             while( i < cl ) {
279                 l = b[i] & c[i] & ~d[i];
280                 if( (l & ~e[i]) != 0 ) ret = true;
281                 e[i] |= l;
282                 i++;
283             }
284         } else {
285             // dl is the shortest
286             while( i < dl ) {
287                 l = b[i] & c[i] & ~d[i];
288                 if( (l & ~e[i]) != 0 ) ret = true;
289                 e[i] |= l;
290                 i++;
291             }
292             int shorter = cl;
293             if( bl < shorter ) shorter = bl;
294             while( i < shorter ) {
295                 l = b[i] & c[i];
296                 if( (l & ~e[i]) != 0 ) ret = true;
297                 e[i] |= l;
298                 i++;
299             }
300         }
301 
302         return ret;
303     }
304         public static BitVector and( BitVector set1, BitVector set2 ) {
305         int min = set1.size();
306         {
307             int max = set2.size();
308             if( min > max ) {
309                 min = max;
310             }
311             // max is not necessarily correct at this point, so let it go
312             // out of scope
313         }
314 
315         BitVector ret = new BitVector( min );
316         long[] retbits = ret.bits;
317         long[] bits1 = set1.bits;
318         long[] bits2 = set2.bits;
319         min <<= 6;
320         for( int i = 0; i < min; i++ ) {
321             retbits[i] = bits1[i] & bits2[i];
322         }
323         return ret;
324     }
325 
326     public static BitVector or( BitVector set1, BitVector set2 ) {
327         int min = set1.size();
328         int max = set2.size();
329         if( min > max ) {
330             min = max;
331             max = set1.size();
332         }
333 
334         BitVector ret = new BitVector( max );
335         long[] retbits = ret.bits;
336         long[] bits1 = set1.bits;
337         long[] bits2 = set2.bits;
338         min <<= 6;
339         max <<= 6;
340         for( int i = 0; i < min; i++ ) {
341             retbits[i] = bits1[i] | bits2[i];
342         }
343         if( bits1.length == min ) {
344             System.arraycopy( bits2, min, retbits, min, max-min );
345         } else {
346             System.arraycopy( bits1, min, retbits, min, max-min );
347         }
348         return ret;
349     }
350     public BitSetIterator iterator() {
351         return new BitSetIterator(bits);
352     }
353 }
354 
355 
356
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags