001    /* BitSet.java -- A vector of bits.
002       Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005  Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    package java.util;
039    
040    import gnu.java.lang.CPStringBuilder;
041    
042    import java.io.Serializable;
043    
044    /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3
045     * hashCode algorithm taken from JDK 1.2 docs.
046     */
047    
048    /**
049     * This class can be thought of in two ways.  You can see it as a
050     * vector of bits or as a set of non-negative integers.  The name
051     * <code>BitSet</code> is a bit misleading.
052     *
053     * It is implemented by a bit vector, but its equally possible to see
054     * it as set of non-negative integer; each integer in the set is
055     * represented by a set bit at the corresponding index.  The size of
056     * this structure is determined by the highest integer in the set.
057     *
058     * You can union, intersect and build (symmetric) remainders, by
059     * invoking the logical operations and, or, andNot, resp. xor.
060     *
061     * This implementation is NOT synchronized against concurrent access from
062     * multiple threads. Specifically, if one thread is reading from a bitset
063     * while another thread is simultaneously modifying it, the results are
064     * undefined.
065     *
066     * @author Jochen Hoenicke
067     * @author Tom Tromey (tromey@cygnus.com)
068     * @author Eric Blake (ebb9@email.byu.edu)
069     * @status updated to 1.4
070     */
071    public class BitSet implements Cloneable, Serializable
072    {
073      /**
074       * Compatible with JDK 1.0.
075       */
076      private static final long serialVersionUID = 7997698588986878753L;
077    
078      /**
079       * A common mask.
080       */
081      private static final int LONG_MASK = 0x3f;
082    
083      /**
084       * The actual bits.
085       * @serial the i'th bit is in bits[i/64] at position i%64 (where position
086       *         0 is the least significant).
087       */
088      private long[] bits;
089    
090      /**
091       * Create a new empty bit set. All bits are initially false.
092       */
093      public BitSet()
094      {
095        this(64);
096      }
097    
098      /**
099       * Create a new empty bit set, with a given size.  This
100       * constructor reserves enough space to represent the integers
101       * from <code>0</code> to <code>nbits-1</code>.
102       *
103       * @param nbits the initial size of the bit set
104       * @throws NegativeArraySizeException if nbits &lt; 0
105       */
106      public BitSet(int nbits)
107      {
108        if (nbits < 0)
109          throw new NegativeArraySizeException();
110    
111        int length = nbits >>> 6;
112        if ((nbits & LONG_MASK) != 0)
113          ++length;
114        bits = new long[length];
115      }
116    
117      /**
118       * Performs the logical AND operation on this bit set and the
119       * given <code>set</code>.  This means it builds the intersection
120       * of the two sets.  The result is stored into this bit set.
121       *
122       * @param bs the second bit set
123       * @throws NullPointerException if bs is null
124       */
125      public void and(BitSet bs)
126      {
127        int max = Math.min(bits.length, bs.bits.length);
128        int i;
129        for (i = 0; i < max; ++i)
130          bits[i] &= bs.bits[i];
131        while (i < bits.length)
132          bits[i++] = 0;
133      }
134    
135      /**
136       * Performs the logical AND operation on this bit set and the
137       * complement of the given <code>bs</code>.  This means it
138       * selects every element in the first set, that isn't in the
139       * second set.  The result is stored into this bit set and is
140       * effectively the set difference of the two.
141       *
142       * @param bs the second bit set
143       * @throws NullPointerException if bs is null
144       * @since 1.2
145       */
146      public void andNot(BitSet bs)
147      {
148        int i = Math.min(bits.length, bs.bits.length);
149        while (--i >= 0)
150          bits[i] &= ~bs.bits[i];
151      }
152    
153      /**
154       * Returns the number of bits set to true.
155       *
156       * @return the number of true bits
157       * @since 1.4
158       */
159      public int cardinality()
160      {
161        int card = 0;
162        for (int i = bits.length - 1; i >= 0; i--)
163          {
164            long a = bits[i];
165            // Take care of common cases.
166            if (a == 0)
167              continue;
168            if (a == -1)
169              {
170                card += 64;
171                continue;
172              }
173    
174            // Successively collapse alternating bit groups into a sum.
175            a = ((a >> 1) & 0x5555555555555555L) + (a & 0x5555555555555555L);
176            a = ((a >> 2) & 0x3333333333333333L) + (a & 0x3333333333333333L);
177            int b = (int) ((a >>> 32) + a);
178            b = ((b >> 4) & 0x0f0f0f0f) + (b & 0x0f0f0f0f);
179            b = ((b >> 8) & 0x00ff00ff) + (b & 0x00ff00ff);
180            card += ((b >> 16) & 0x0000ffff) + (b & 0x0000ffff);
181          }
182        return card;
183      }
184    
185      /**
186       * Sets all bits in the set to false.
187       *
188       * @since 1.4
189       */
190      public void clear()
191      {
192        Arrays.fill(bits, 0);
193      }
194    
195      /**
196       * Removes the integer <code>pos</code> from this set. That is
197       * the corresponding bit is cleared.  If the index is not in the set,
198       * this method does nothing.
199       *
200       * @param pos a non-negative integer
201       * @throws IndexOutOfBoundsException if pos &lt; 0
202       */
203      public void clear(int pos)
204      {
205        int offset = pos >> 6;
206        ensure(offset);
207        // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
208        // so we'll just let that be our exception.
209        bits[offset] &= ~(1L << pos);
210      }
211    
212      /**
213       * Sets the bits between from (inclusive) and to (exclusive) to false.
214       *
215       * @param from the start range (inclusive)
216       * @param to the end range (exclusive)
217       * @throws IndexOutOfBoundsException if from &lt; 0 || to &lt; 0 ||
218       *         from &gt; to
219       * @since 1.4
220       */
221      public void clear(int from, int to)
222      {
223        if (from < 0 || from > to)
224          throw new IndexOutOfBoundsException();
225        if (from == to)
226          return;
227        int lo_offset = from >>> 6;
228        int hi_offset = to >>> 6;
229        ensure(hi_offset);
230        if (lo_offset == hi_offset)
231          {
232            bits[hi_offset] &= ((1L << from) - 1) | (-1L << to);
233            return;
234          }
235    
236        bits[lo_offset] &= (1L << from) - 1;
237        bits[hi_offset] &= -1L << to;
238        for (int i = lo_offset + 1; i < hi_offset; i++)
239          bits[i] = 0;
240      }
241    
242      /**
243       * Create a clone of this bit set, that is an instance of the same
244       * class and contains the same elements.  But it doesn't change when
245       * this bit set changes.
246       *
247       * @return the clone of this object.
248       */
249      public Object clone()
250      {
251        try
252          {
253            BitSet bs = (BitSet) super.clone();
254            bs.bits = (long[]) bits.clone();
255            return bs;
256          }
257        catch (CloneNotSupportedException e)
258          {
259            // Impossible to get here.
260            return null;
261          }
262      }
263    
264      /**
265       * Returns true if the <code>obj</code> is a bit set that contains
266       * exactly the same elements as this bit set, otherwise false.
267       *
268       * @param obj the object to compare to
269       * @return true if obj equals this bit set
270       */
271      public boolean equals(Object obj)
272      {
273        if (!(obj instanceof BitSet))
274          return false;
275        BitSet bs = (BitSet) obj;
276        int max = Math.min(bits.length, bs.bits.length);
277        int i;
278        for (i = 0; i < max; ++i)
279          if (bits[i] != bs.bits[i])
280            return false;
281        // If one is larger, check to make sure all extra bits are 0.
282        for (int j = i; j < bits.length; ++j)
283          if (bits[j] != 0)
284            return false;
285        for (int j = i; j < bs.bits.length; ++j)
286          if (bs.bits[j] != 0)
287            return false;
288        return true;
289      }
290    
291      /**
292       * Sets the bit at the index to the opposite value.
293       *
294       * @param index the index of the bit
295       * @throws IndexOutOfBoundsException if index is negative
296       * @since 1.4
297       */
298      public void flip(int index)
299      {
300        int offset = index >> 6;
301        ensure(offset);
302        // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
303        // so we'll just let that be our exception.
304        bits[offset] ^= 1L << index;
305      }
306    
307      /**
308       * Sets a range of bits to the opposite value.
309       *
310       * @param from the low index (inclusive)
311       * @param to the high index (exclusive)
312       * @throws IndexOutOfBoundsException if from &gt; to || from &lt; 0 ||
313       *         to &lt; 0
314       * @since 1.4
315       */
316      public void flip(int from, int to)
317      {
318        if (from < 0 || from > to)
319          throw new IndexOutOfBoundsException();
320        if (from == to)
321          return;
322        int lo_offset = from >>> 6;
323        int hi_offset = to >>> 6;
324        ensure(hi_offset);
325        if (lo_offset == hi_offset)
326          {
327            bits[hi_offset] ^= (-1L << from) & ((1L << to) - 1);
328            return;
329          }
330    
331        bits[lo_offset] ^= -1L << from;
332        bits[hi_offset] ^= (1L << to) - 1;
333        for (int i = lo_offset + 1; i < hi_offset; i++)
334          bits[i] ^= -1;
335      }
336    
337      /**
338       * Returns true if the integer <code>bitIndex</code> is in this bit
339       * set, otherwise false.
340       *
341       * @param pos a non-negative integer
342       * @return the value of the bit at the specified position
343       * @throws IndexOutOfBoundsException if the pos is negative
344       */
345      public boolean get(int pos)
346      {
347        int offset = pos >> 6;
348        if (offset >= bits.length)
349          return false;
350        // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
351        // so we'll just let that be our exception.
352        return (bits[offset] & (1L << pos)) != 0;
353      }
354    
355      /**
356       * Returns a new <code>BitSet</code> composed of a range of bits from
357       * this one.
358       *
359       * @param from the low index (inclusive)
360       * @param to the high index (exclusive)
361       * @throws IndexOutOfBoundsException if from &gt; to || from &lt; 0 ||
362       *         to &lt; 0
363       * @since 1.4
364       */
365      public BitSet get(int from, int to)
366      {
367        if (from < 0 || from > to)
368          throw new IndexOutOfBoundsException();
369        BitSet bs = new BitSet(to - from);
370        int lo_offset = from >>> 6;
371        if (lo_offset >= bits.length || to == from)
372          return bs;
373    
374        int lo_bit = from & LONG_MASK;
375        int hi_offset = to >>> 6;
376        if (lo_bit == 0)
377          {
378            int len = Math.min(hi_offset - lo_offset + 1, bits.length - lo_offset);
379            System.arraycopy(bits, lo_offset, bs.bits, 0, len);
380            if (hi_offset < bits.length)
381              bs.bits[hi_offset - lo_offset] &= (1L << to) - 1;
382            return bs;
383          }
384    
385        int len = Math.min(hi_offset, bits.length - 1);
386        int reverse = 64 - lo_bit;
387        int i;
388        for (i = 0; lo_offset < len; lo_offset++, i++)
389          bs.bits[i] = ((bits[lo_offset] >>> lo_bit)
390                        | (bits[lo_offset + 1] << reverse));
391        if ((to & LONG_MASK) > lo_bit)
392          bs.bits[i++] = bits[lo_offset] >>> lo_bit;
393        if (hi_offset < bits.length)
394          bs.bits[i - 1] &= (1L << (to - from)) - 1;
395        return bs;
396      }
397    
398      /**
399       * Returns a hash code value for this bit set.  The hash code of
400       * two bit sets containing the same integers is identical.  The algorithm
401       * used to compute it is as follows:
402       *
403       * Suppose the bits in the BitSet were to be stored in an array of
404       * long integers called <code>bits</code>, in such a manner that
405       * bit <code>k</code> is set in the BitSet (for non-negative values
406       * of <code>k</code>) if and only if
407       *
408       * <code>((k/64) &lt; bits.length)
409       * && ((bits[k/64] & (1L &lt;&lt; (bit % 64))) != 0)
410       * </code>
411       *
412       * Then the following definition of the hashCode method
413       * would be a correct implementation of the actual algorithm:
414       *
415       *
416    <pre>public int hashCode()
417    {
418      long h = 1234;
419      for (int i = bits.length-1; i &gt;= 0; i--)
420      {
421        h ^= bits[i] * (i + 1);
422      }
423    
424      return (int)((h >> 32) ^ h);
425    }</pre>
426       *
427       * Note that the hash code values changes, if the set is changed.
428       *
429       * @return the hash code value for this bit set.
430       */
431      public int hashCode()
432      {
433        long h = 1234;
434        for (int i = bits.length; i > 0; )
435          h ^= i * bits[--i];
436        return (int) ((h >> 32) ^ h);
437      }
438    
439      /**
440       * Returns true if the specified BitSet and this one share at least one
441       * common true bit.
442       *
443       * @param set the set to check for intersection
444       * @return true if the sets intersect
445       * @throws NullPointerException if set is null
446       * @since 1.4
447       */
448      public boolean intersects(BitSet set)
449      {
450        int i = Math.min(bits.length, set.bits.length);
451        while (--i >= 0)
452          if ((bits[i] & set.bits[i]) != 0)
453            return true;
454        return false;
455      }
456    
457      /**
458       * Returns true if this set contains no true bits.
459       *
460       * @return true if all bits are false
461       * @since 1.4
462       */
463      public boolean isEmpty()
464      {
465        for (int i = bits.length - 1; i >= 0; i--)
466          if (bits[i] != 0)
467            return false;
468        return true;
469      }
470    
471      /**
472       * Returns the logical number of bits actually used by this bit
473       * set.  It returns the index of the highest set bit plus one.
474       * Note that this method doesn't return the number of set bits.
475       *
476       * @return the index of the highest set bit plus one.
477       */
478      public int length()
479      {
480        // Set i to highest index that contains a non-zero value.
481        int i;
482        for (i = bits.length - 1; i >= 0 && bits[i] == 0; --i)
483          ;
484    
485        // if i < 0 all bits are cleared.
486        if (i < 0)
487          return 0;
488    
489        // Now determine the exact length.
490        long b = bits[i];
491        int len = (i + 1) * 64;
492        // b >= 0 checks if the highest bit is zero.
493        while (b >= 0)
494          {
495            --len;
496            b <<= 1;
497          }
498    
499        return len;
500      }
501    
502      /**
503       * Returns the index of the next false bit, from the specified bit
504       * (inclusive).
505       *
506       * @param from the start location
507       * @return the first false bit
508       * @throws IndexOutOfBoundsException if from is negative
509       * @since 1.4
510       */
511      public int nextClearBit(int from)
512      {
513        int offset = from >> 6;
514        long mask = 1L << from;
515        while (offset < bits.length)
516          {
517            // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
518            // so we'll just let that be our exception.
519            long h = bits[offset];
520            do
521              {
522                if ((h & mask) == 0)
523                  return from;
524                mask <<= 1;
525                from++;
526              }
527            while (mask != 0);
528            mask = 1;
529            offset++;
530          }
531        return from;
532      }
533    
534      /**
535       * Returns the index of the next true bit, from the specified bit
536       * (inclusive). If there is none, -1 is returned. You can iterate over
537       * all true bits with this loop:<br>
538       *
539    <pre>for (int i = bs.nextSetBit(0); i &gt;= 0; i = bs.nextSetBit(i + 1))
540    {
541      // operate on i here
542    }</pre>
543       *
544       * @param from the start location
545       * @return the first true bit, or -1
546       * @throws IndexOutOfBoundsException if from is negative
547       * @since 1.4
548       */
549      public int nextSetBit(int from)
550      {
551        int offset = from >> 6;
552        long mask = 1L << from;
553        while (offset < bits.length)
554          {
555            // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
556            // so we'll just let that be our exception.
557            long h = bits[offset];
558            do
559              {
560                if ((h & mask) != 0)
561                  return from;
562                mask <<= 1;
563                from++;
564              }
565            while (mask != 0);
566            mask = 1;
567            offset++;
568          }
569        return -1;
570      }
571    
572      /**
573       * Performs the logical OR operation on this bit set and the
574       * given <code>set</code>.  This means it builds the union
575       * of the two sets.  The result is stored into this bit set, which
576       * grows as necessary.
577       *
578       * @param bs the second bit set
579       * @throws NullPointerException if bs is null
580       */
581      public void or(BitSet bs)
582      {
583        ensure(bs.bits.length - 1);
584        for (int i = bs.bits.length - 1; i >= 0; i--)
585          bits[i] |= bs.bits[i];
586      }
587    
588      /**
589       * Add the integer <code>bitIndex</code> to this set.  That is
590       * the corresponding bit is set to true.  If the index was already in
591       * the set, this method does nothing.  The size of this structure
592       * is automatically increased as necessary.
593       *
594       * @param pos a non-negative integer.
595       * @throws IndexOutOfBoundsException if pos is negative
596       */
597      public void set(int pos)
598      {
599        int offset = pos >> 6;
600        ensure(offset);
601        // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
602        // so we'll just let that be our exception.
603        bits[offset] |= 1L << pos;
604      }
605    
606      /**
607       * Sets the bit at the given index to the specified value. The size of
608       * this structure is automatically increased as necessary.
609       *
610       * @param index the position to set
611       * @param value the value to set it to
612       * @throws IndexOutOfBoundsException if index is negative
613       * @since 1.4
614       */
615      public void set(int index, boolean value)
616      {
617        if (value)
618          set(index);
619        else
620          clear(index);
621      }
622    
623      /**
624       * Sets the bits between from (inclusive) and to (exclusive) to true.
625       *
626       * @param from the start range (inclusive)
627       * @param to the end range (exclusive)
628       * @throws IndexOutOfBoundsException if from &lt; 0 || from &gt; to ||
629       *         to &lt; 0
630       * @since 1.4
631       */
632      public void set(int from, int to)
633      {
634        if (from < 0 || from > to)
635          throw new IndexOutOfBoundsException();
636        if (from == to)
637          return;
638        int lo_offset = from >>> 6;
639        int hi_offset = to >>> 6;
640        ensure(hi_offset);
641        if (lo_offset == hi_offset)
642          {
643            bits[hi_offset] |= (-1L << from) & ((1L << to) - 1);
644            return;
645          }
646    
647        bits[lo_offset] |= -1L << from;
648        bits[hi_offset] |= (1L << to) - 1;
649        for (int i = lo_offset + 1; i < hi_offset; i++)
650          bits[i] = -1;
651      }
652    
653      /**
654       * Sets the bits between from (inclusive) and to (exclusive) to the
655       * specified value.
656       *
657       * @param from the start range (inclusive)
658       * @param to the end range (exclusive)
659       * @param value the value to set it to
660       * @throws IndexOutOfBoundsException if from &lt; 0 || from &gt; to ||
661       *         to &lt; 0
662       * @since 1.4
663       */
664      public void set(int from, int to, boolean value)
665      {
666        if (value)
667          set(from, to);
668        else
669          clear(from, to);
670      }
671    
672      /**
673       * Returns the number of bits actually used by this bit set.  Note
674       * that this method doesn't return the number of set bits, and that
675       * future requests for larger bits will make this automatically grow.
676       *
677       * @return the number of bits currently used.
678       */
679      public int size()
680      {
681        return bits.length * 64;
682      }
683    
684      /**
685       * Returns the string representation of this bit set.  This
686       * consists of a comma separated list of the integers in this set
687       * surrounded by curly braces.  There is a space after each comma.
688       * A sample string is thus "{1, 3, 53}".
689       * @return the string representation.
690       */
691      public String toString()
692      {
693        CPStringBuilder r = new CPStringBuilder("{");
694        boolean first = true;
695        for (int i = 0; i < bits.length; ++i)
696          {
697            long bit = 1;
698            long word = bits[i];
699            if (word == 0)
700              continue;
701            for (int j = 0; j < 64; ++j)
702              {
703                if ((word & bit) != 0)
704                  {
705                    if (! first)
706                      r.append(", ");
707                    r.append(64 * i + j);
708                    first = false;
709                  }
710                bit <<= 1;
711              }
712          }
713        return r.append("}").toString();
714      }
715    
716      /**
717       * Performs the logical XOR operation on this bit set and the
718       * given <code>set</code>.  This means it builds the symmetric
719       * remainder of the two sets (the elements that are in one set,
720       * but not in the other).  The result is stored into this bit set,
721       * which grows as necessary.
722       *
723       * @param bs the second bit set
724       * @throws NullPointerException if bs is null
725       */
726      public void xor(BitSet bs)
727      {
728        ensure(bs.bits.length - 1);
729        for (int i = bs.bits.length - 1; i >= 0; i--)
730          bits[i] ^= bs.bits[i];
731      }
732    
733      /**
734       * Make sure the vector is big enough.
735       *
736       * @param lastElt the size needed for the bits array
737       */
738      private void ensure(int lastElt)
739      {
740        if (lastElt >= bits.length)
741          {
742            long[] nd = new long[lastElt + 1];
743            System.arraycopy(bits, 0, nd, 0, bits.length);
744            bits = nd;
745          }
746      }
747    
748      // This is used by EnumSet for efficiency.
749      final boolean containsAll(BitSet other)
750      {
751        for (int i = other.bits.length - 1; i >= 0; i--)
752          {
753            if ((bits[i] & other.bits[i]) != other.bits[i])
754              return false;
755          }
756        return true;
757      }
758    }