libjava/java/util/BitSet.java

   1 /* BitSet.java -- A vector of bits.
   2    Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005  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 and is
 137    * effectively the set difference of the two.
 138    *
 139    * @param set the second bit set
 140    * @throws NullPointerException if set 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>bitIndex</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 bitIndex a non-negative integer
 198    * @throws IndexOutOfBoundsException if bitIndex &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 index
 340    * @throws IndexOutOfBoundsException if the index 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)
 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 = ~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 }