Source for java.util.BitSet

   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., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 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: 
  40: import gnu.java.lang.CPStringBuilder;
  41: 
  42: import java.io.Serializable;
  43: 
  44: /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3
  45:  * hashCode algorithm taken from JDK 1.2 docs.
  46:  */
  47: 
  48: /**
  49:  * This class can be thought of in two ways.  You can see it as a
  50:  * vector of bits or as a set of non-negative integers.  The name
  51:  * <code>BitSet</code> is a bit misleading.
  52:  *
  53:  * It is implemented by a bit vector, but its equally possible to see
  54:  * it as set of non-negative integer; each integer in the set is
  55:  * represented by a set bit at the corresponding index.  The size of
  56:  * this structure is determined by the highest integer in the set.
  57:  *
  58:  * You can union, intersect and build (symmetric) remainders, by
  59:  * invoking the logical operations and, or, andNot, resp. xor.
  60:  *
  61:  * This implementation is NOT synchronized against concurrent access from
  62:  * multiple threads. Specifically, if one thread is reading from a bitset
  63:  * while another thread is simultaneously modifying it, the results are
  64:  * undefined.
  65:  *
  66:  * @author Jochen Hoenicke
  67:  * @author Tom Tromey (tromey@cygnus.com)
  68:  * @author Eric Blake (ebb9@email.byu.edu)
  69:  * @status updated to 1.4
  70:  */
  71: public class BitSet implements Cloneable, Serializable
  72: {
  73:   /**
  74:    * Compatible with JDK 1.0.
  75:    */
  76:   private static final long serialVersionUID = 7997698588986878753L;
  77: 
  78:   /**
  79:    * A common mask.
  80:    */
  81:   private static final int LONG_MASK = 0x3f;
  82: 
  83:   /**
  84:    * The actual bits.
  85:    * @serial the i'th bit is in bits[i/64] at position i%64 (where position
  86:    *         0 is the least significant).
  87:    */
  88:   private long[] bits;
  89: 
  90:   /**
  91:    * Create a new empty bit set. All bits are initially false.
  92:    */
  93:   public BitSet()
  94:   {
  95:     this(64);
  96:   }
  97: 
  98:   /**
  99:    * 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: }