libjava/java/util/BitSet.java

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