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