001/* BitSet.java -- A vector of bits.
002   Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005  Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038package java.util;
039
040import gnu.java.lang.CPStringBuilder;
041
042import 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 */
071public 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}