src/javajs/util/BS.java

   1 /*
   2  * Copyright 1995-2007 Sun Microsystems, Inc.  All Rights Reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Sun designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Sun in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  22  * CA 95054 USA or visit www.sun.com if you need additional information or
  23  * have any questions.
  24  */
  25
  26 package javajs.util;
  27
  28 import javajs.api.JSONEncodable;
  29
  30
  31
  32 /**
  33  *
  34  * a fast 32-bit BitSet optimized for Java2Script -- about 25 times faster than
  35  * java.util.BitSet
  36  *
  37  * @author Bob Hanson hansonr@stolaf.edu
  38  *
  39  *         Additions by Bob Hanson to allow for JavaScript mix of int/long Note
  40  *         that Firefox (Sept 2012) does not really treat "Int32Array" as such,
  41  *         because any element can be pushed into being a 64-bit number, which
  42  *         really isn't because the last 8 bits are not usable.
  43  *
  44  *         This class implements a vector of bits that grows as needed. Each
  45  *         component of the bit set has a {@code boolean} value. The bits of a
  46  *         {@code BitSet} are indexed by nonnegative integers. Individual
  47  *         indexed bits can be examined, set, or cleared. One {@code BitSet} may
  48  *         be used to modify the contents of another {@code BitSet} through
  49  *         logical AND, logical inclusive OR, and logical exclusive OR
  50  *         operations.
  51  *
  52  *         <p>
  53  *         By default, all bits in the set initially have the value {@code
  54  *         false}.
  55  *
  56  *         <p>
  57  *         Every bit set has a current size, which is the number of bits of
  58  *         space currently in use by the bit set. Note that the size is related
  59  *         to the implementation of a bit set, so it may change with
  60  *         implementation. The length of a bit set relates to logical length of
  61  *         a bit set and is defined independently of implementation.
  62  *
  63  *         <p>
  64  *         Unless otherwise noted, passing a null parameter to any of the
  65  *         methods in a {@code BitSet} will result in a {@code
  66  *         NullPointerException}.
  67  *
  68  *         <p>
  69  *         A {@code BitSet} is not safe for multithreaded use without external
  70  *         synchronization.
  71  *
  72  * @author Arthur van Hoff
  73  * @author Michael McCloskey
  74  * @author Martin Buchholz
  75  * @since JDK1.0
  76  */
  77 public class BS implements Cloneable, JSONEncodable {
  78   /*
  79    * BitSets are packed into arrays of "words."
  80    *
  81    * An int, which consists of 32 bits, requiring 5 address bits, is used for
  82    * the JavaScript port.
  83    */
  84   private final static int ADDRESS_BITS_PER_WORD = 5;
  85   private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
  86
  87   /* Used to shift left or right for a partial word mask */
  88   private static final int WORD_MASK = 0xffffffff;
  89
  90
  91   /**
  92    * The internal field corresponding to the serialField "bits".
  93    */
  94   private int[] words;
  95
  96   /**
  97    * The number of words in the logical size of this BitSet.
  98    */
  99   private transient int wordsInUse = 0;
 100
 101   /**
 102    * Whether the size of "words" is user-specified. If so, we assume the user
 103    * knows what he's doing and try harder to preserve it.
 104    */
 105   private transient boolean sizeIsSticky = false;
 106
 107   /* use serialVersionUID from JDK 1.0.2 for interoperability */
 108   //private static final long serialVersionUID = 7997698588986878753L;
 109
 110   /**
 111    * Given a bit index, return word index containing it.
 112    * @param bitIndex
 113    * @return b
 114    */
 115   private static int wordIndex(int bitIndex) {
 116     return bitIndex >> ADDRESS_BITS_PER_WORD;
 117   }
 118
 119   /**
 120    * Sets the field wordsInUse to the logical size in words of the bit set.
 121    * WARNING:This method assumes that the number of words actually in use is
 122    * less than or equal to the current value of wordsInUse!
 123    */
 124   private void recalculateWordsInUse() {
 125     // Traverse the bitset until a used word is found
 126     int i;
 127     for (i = wordsInUse - 1; i >= 0; i--)
 128       if (words[i] != 0)
 129         break;
 130
 131     wordsInUse = i + 1; // The new logical size
 132   }
 133
 134   /**
 135    * Creates a new bit set. All bits are initially {@code false}.
 136    */
 137   public BS() {
 138     initWords(BITS_PER_WORD);
 139     sizeIsSticky = false;
 140   }
 141
 142   /**
 143    * Creates a bit set whose initial size is large enough to explicitly
 144    * represent bits with indices in the range {@code 0} through {@code nbits-1}.
 145    * All bits are initially {@code false}.
 146    *
 147    * @param nbits
 148    *          the initial size of the bit set
 149    * @return bs
 150    * @throws NegativeArraySizeException
 151    *           if the specified initial size is negative
 152    */
 153   public static BS newN(int nbits) {
 154     BS bs = new BS();
 155     bs.init(nbits);
 156     return bs;
 157   }
 158
 159   private void init(int nbits) {
 160     // nbits can't be negative; size 0 is OK
 161     if (nbits < 0)
 162       throw new NegativeArraySizeException("nbits < 0: " + nbits);
 163     initWords(nbits);
 164     sizeIsSticky = true;
 165   }
 166
 167   private void initWords(int nbits) {
 168     words = new int[wordIndex(nbits - 1) + 1];
 169   }
 170
 171   /**
 172    * Ensures that the BitSet can hold enough words.
 173    *
 174    * @param wordsRequired
 175    *          the minimum acceptable number of words.
 176    */
 177   private void ensureCapacity(int wordsRequired) {
 178     if (words.length < wordsRequired) {
 179       // Allocate larger of doubled size or required size
 180       int request = Math.max(2 * words.length, wordsRequired);
 181       setLength(request);
 182       sizeIsSticky = false;
 183     }
 184   }
 185
 186   /**
 187    * Ensures that the BitSet can accommodate a given wordIndex, temporarily
 188    * violating the invariants. The caller must restore the invariants before
 189    * returning to the user, possibly using recalculateWordsInUse().
 190    *
 191    * @param wordIndex
 192    *          the index to be accommodated.
 193    */
 194   private void expandTo(int wordIndex) {
 195     int wordsRequired = wordIndex + 1;
 196     if (wordsInUse < wordsRequired) {
 197       ensureCapacity(wordsRequired);
 198       wordsInUse = wordsRequired;
 199     }
 200   }
 201
 202
 203   /**
 204    * Sets the bit at the specified index to {@code true}.
 205    *
 206    * @param bitIndex
 207    *          a bit index
 208    * @throws IndexOutOfBoundsException
 209    *           if the specified index is negative
 210    * @since JDK1.0
 211    */
 212   public void set(int bitIndex) {
 213     if (bitIndex < 0)
 214       throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
 215
 216     int wordIndex = wordIndex(bitIndex);
 217     expandTo(wordIndex);
 218
 219     words[wordIndex] |= (1 << bitIndex); // Restores invariants
 220
 221   }
 222
 223   /**
 224    * Sets the bit at the specified index to the specified value.
 225    *
 226    * @param bitIndex
 227    *          a bit index
 228    * @param value
 229    *          a boolean value to set
 230    * @throws IndexOutOfBoundsException
 231    *           if the specified index is negative
 232    * @since 1.4
 233    */
 234   public void setBitTo(int bitIndex, boolean value) {
 235     if (value)
 236       set(bitIndex);
 237     else
 238       clear(bitIndex);
 239   }
 240
 241   /**
 242    * Sets the bits from the specified {@code fromIndex} (inclusive) to the
 243    * specified {@code toIndex} (exclusive) to {@code true}.
 244    *
 245    * @param fromIndex
 246    *          index of the first bit to be set
 247    * @param toIndex
 248    *          index after the last bit to be set
 249    * @throws IndexOutOfBoundsException
 250    *           if {@code fromIndex} is negative, or {@code toIndex} is negative,
 251    *           or {@code fromIndex} is larger than {@code toIndex}
 252    * @since 1.4
 253    */
 254   public void setBits(int fromIndex, int toIndex) {
 255
 256     if (fromIndex == toIndex)
 257       return;
 258
 259     // Increase capacity if necessary
 260     int startWordIndex = wordIndex(fromIndex);
 261     int endWordIndex = wordIndex(toIndex - 1);
 262     expandTo(endWordIndex);
 263
 264     int firstWordMask = WORD_MASK << fromIndex;
 265     int lastWordMask = WORD_MASK >>> -toIndex;
 266     if (startWordIndex == endWordIndex) {
 267       // Case 1: One word
 268       words[startWordIndex] |= (firstWordMask & lastWordMask);
 269     } else {
 270       // Case 2: Multiple words
 271       // Handle first word
 272       words[startWordIndex] |= firstWordMask;
 273
 274       // Handle intermediate words, if any
 275       for (int i = startWordIndex + 1; i < endWordIndex; i++)
 276         words[i] = WORD_MASK;
 277
 278       // Handle last word (restores invariants)
 279       words[endWordIndex] |= lastWordMask;
 280     }
 281   }
 282
 283   /**
 284    * Sets the bit specified by the index to {@code false}.
 285    *
 286    * @param bitIndex
 287    *          the index of the bit to be cleared
 288    * @throws IndexOutOfBoundsException
 289    *           if the specified index is negative
 290    * @since JDK1.0
 291    */
 292   public void clear(int bitIndex) {
 293     if (bitIndex < 0)
 294       throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
 295
 296     int wordIndex = wordIndex(bitIndex);
 297     if (wordIndex >= wordsInUse)
 298       return;
 299
 300     words[wordIndex] &= ~(1 << bitIndex);
 301
 302     recalculateWordsInUse();
 303   }
 304
 305   /**
 306    * Sets the bits from the specified {@code fromIndex} (inclusive) to the
 307    * specified {@code toIndex} (exclusive) to {@code false}.
 308    *
 309    * @param fromIndex
 310    *          index of the first bit to be cleared
 311    * @param toIndex
 312    *          index after the last bit to be cleared
 313    * @throws IndexOutOfBoundsException
 314    *           if {@code fromIndex} is negative, or {@code toIndex} is negative,
 315    *           or {@code fromIndex} is larger than {@code toIndex}
 316    * @since 1.4
 317    */
 318   public void clearBits(int fromIndex, int toIndex) {
 319     if (fromIndex == toIndex)
 320       return;
 321
 322     int startWordIndex = wordIndex(fromIndex);
 323     if (startWordIndex >= wordsInUse)
 324       return;
 325
 326     int endWordIndex = wordIndex(toIndex - 1);
 327     if (endWordIndex >= wordsInUse) {
 328       toIndex = length();
 329       endWordIndex = wordsInUse - 1;
 330     }
 331
 332     int firstWordMask = WORD_MASK << fromIndex;
 333     int lastWordMask = WORD_MASK >>> -toIndex;
 334     if (startWordIndex == endWordIndex) {
 335       // Case 1: One word
 336       words[startWordIndex] &= ~(firstWordMask & lastWordMask);
 337     } else {
 338       // Case 2: Multiple words
 339       // Handle first word
 340       words[startWordIndex] &= ~firstWordMask;
 341
 342       // Handle intermediate words, if any
 343       for (int i = startWordIndex + 1; i < endWordIndex; i++)
 344         words[i] = 0;
 345
 346       // Handle last word
 347       words[endWordIndex] &= ~lastWordMask;
 348     }
 349
 350     recalculateWordsInUse();
 351   }
 352
 353   /**
 354    * Sets all of the bits in this BitSet to {@code false}.
 355    *
 356    * @since 1.4
 357    */
 358   public void clearAll() {
 359     while (wordsInUse > 0)
 360       words[--wordsInUse] = 0;
 361   }
 362
 363   /**
 364    * Returns the value of the bit with the specified index. The value is {@code
 365    * true} if the bit with the index {@code bitIndex} is currently set in this
 366    * {@code BitSet}; otherwise, the result is {@code false}.
 367    *
 368    * @param bitIndex
 369    *          the bit index
 370    * @return the value of the bit with the specified index
 371    * @throws IndexOutOfBoundsException
 372    *           if the specified index is negative
 373    */
 374   public boolean get(int bitIndex) {
 375     if (bitIndex < 0)
 376       throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
 377
 378     int wordIndex = wordIndex(bitIndex);
 379     return (wordIndex < wordsInUse)
 380         && ((words[wordIndex] & (1 << bitIndex)) != 0);
 381   }
 382
 383   /**
 384    * Returns the index of the first bit that is set to {@code true} that occurs
 385    * on or after the specified starting index. If no such bit exists then
 386    * {@code -1} is returned.
 387    *
 388    * <p>
 389    * To iterate over the {@code true} bits in a {@code BitSet}, use the
 390    * following loop:
 391    *
 392    * <pre>
 393    * @code
 394    * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
 395    *     // operate on index i here
 396    * }}
 397    * </pre>
 398    *
 399    * @param fromIndex
 400    *          the index to start checking from (inclusive)
 401    * @return the index of the next set bit, or {@code -1} if there is no such
 402    *         bit
 403    * @throws IndexOutOfBoundsException
 404    *           if the specified index is negative
 405    * @since 1.4
 406    */
 407   public int nextSetBit(int fromIndex) {
 408     if (fromIndex < 0)
 409       throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
 410
 411     int u = wordIndex(fromIndex);
 412     if (u >= wordsInUse)
 413       return -1;
 414
 415     int word = words[u] & (WORD_MASK << fromIndex);
 416
 417     while (true) {
 418       if (word != 0)
 419         return (u * BITS_PER_WORD) + Integer.numberOfTrailingZeros(word);
 420       if (++u == wordsInUse)
 421         return -1;
 422       word = words[u];
 423     }
 424   }
 425
 426   /**
 427    * Returns the index of the first bit that is set to {@code false} that occurs
 428    * on or after the specified starting index.
 429    *
 430    * @param fromIndex
 431    *          the index to start checking from (inclusive)
 432    * @return the index of the next clear bit
 433    * @throws IndexOutOfBoundsException
 434    *           if the specified index is negative
 435    * @since 1.4
 436    */
 437   public int nextClearBit(int fromIndex) {
 438     // Neither spec nor implementation handle bitsets of maximal length.
 439     // See 4816253.
 440     if (fromIndex < 0)
 441       throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
 442
 443     int u = wordIndex(fromIndex);
 444     if (u >= wordsInUse)
 445       return fromIndex;
 446
 447     int word = ~words[u] & (WORD_MASK << fromIndex);
 448
 449     while (true) {
 450       if (word != 0)
 451         return (u * BITS_PER_WORD) + Integer.numberOfTrailingZeros(word);
 452       if (++u == wordsInUse)
 453         return wordsInUse * BITS_PER_WORD;
 454       word = ~words[u];
 455     }
 456   }
 457
 458   /**
 459    * Returns the "logical size" of this {@code BitSet}: the index of the highest
 460    * set bit in the {@code BitSet} plus one. Returns zero if the {@code BitSet}
 461    * contains no set bits.
 462    *
 463    * @return the logical size of this {@code BitSet}
 464    * @since 1.2
 465    */
 466   public int length() {
 467     if (wordsInUse == 0)
 468       return 0;
 469
 470     return BITS_PER_WORD * (wordsInUse - 1)
 471         + (BITS_PER_WORD - Integer.numberOfLeadingZeros(words[wordsInUse - 1]));
 472   }
 473
 474   /**
 475    * Returns true if this {@code BitSet} contains no bits that are set to
 476    * {@code true}.
 477    *
 478    * @return boolean indicating whether this {@code BitSet} is empty
 479    * @since 1.4
 480    */
 481   public boolean isEmpty() {
 482     return wordsInUse == 0;
 483   }
 484
 485   /**
 486    * Returns true if the specified {@code BitSet} has any bits set to {@code
 487    * true} that are also set to {@code true} in this {@code BitSet}.
 488    *
 489    * @param set
 490    *          {@code BitSet} to intersect with
 491    * @return boolean indicating whether this {@code BitSet} intersects the
 492    *         specified {@code BitSet}
 493    * @since 1.4
 494    */
 495   public boolean intersects(BS set) {
 496     for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
 497       if ((words[i] & set.words[i]) != 0)
 498         return true;
 499     return false;
 500   }
 501
 502   /**
 503    * Returns the number of bits set to {@code true} in this {@code BitSet}.
 504    *
 505    * @return the number of bits set to {@code true} in this {@code BitSet}
 506    * @since 1.4
 507    */
 508   public int cardinality() {
 509     int sum = 0;
 510     for (int i = 0; i < wordsInUse; i++)
 511       sum += Integer.bitCount(words[i]);
 512     return sum;
 513   }
 514
 515   /**
 516    * Performs a logical <b>AND</b> of this target bit set with the argument bit
 517    * set. This bit set is modified so that each bit in it has the value {@code
 518    * true} if and only if it both initially had the value {@code true} and the
 519    * corresponding bit in the bit set argument also had the value {@code true}.
 520    *
 521    * @param set
 522    *          a bit set
 523    */
 524   public void and(BS set) {
 525     if (this == set)
 526       return;
 527
 528     while (wordsInUse > set.wordsInUse)
 529       words[--wordsInUse] = 0;
 530
 531     // Perform logical AND on words in common
 532     for (int i = 0; i < wordsInUse; i++)
 533       words[i] &= set.words[i];
 534
 535     recalculateWordsInUse();
 536   }
 537
 538   /**
 539    * Performs a logical <b>OR</b> of this bit set with the bit set argument.
 540    * This bit set is modified so that a bit in it has the value {@code true} if
 541    * and only if it either already had the value {@code true} or the
 542    * corresponding bit in the bit set argument has the value {@code true}.
 543    *
 544    * @param set
 545    *          a bit set
 546    */
 547   public void or(BS set) {
 548     if (this == set)
 549       return;
 550
 551     int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
 552
 553     if (wordsInUse < set.wordsInUse) {
 554       ensureCapacity(set.wordsInUse);
 555       wordsInUse = set.wordsInUse;
 556     }
 557
 558     // Perform logical OR on words in common
 559     for (int i = 0; i < wordsInCommon; i++)
 560       words[i] |= set.words[i];
 561
 562     // Copy any remaining words
 563     if (wordsInCommon < set.wordsInUse)
 564       System.arraycopy(set.words, wordsInCommon, words, wordsInCommon,
 565           wordsInUse - wordsInCommon);
 566
 567   }
 568
 569   /**
 570    * Performs a logical <b>XOR</b> of this bit set with the bit set argument.
 571    * This bit set is modified so that a bit in it has the value {@code true} if
 572    * and only if one of the following statements holds:
 573    * <ul>
 574    * <li>The bit initially has the value {@code true}, and the corresponding bit
 575    * in the argument has the value {@code false}.
 576    * <li>The bit initially has the value {@code false}, and the corresponding
 577    * bit in the argument has the value {@code true}.
 578    * </ul>
 579    *
 580    * @param set
 581    *          a bit set
 582    */
 583   public void xor(BS set) {
 584     int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
 585
 586     if (wordsInUse < set.wordsInUse) {
 587       ensureCapacity(set.wordsInUse);
 588       wordsInUse = set.wordsInUse;
 589     }
 590
 591     // Perform logical XOR on words in common
 592     for (int i = 0; i < wordsInCommon; i++)
 593       words[i] ^= set.words[i];
 594
 595     // Copy any remaining words
 596     if (wordsInCommon < set.wordsInUse)
 597       System.arraycopy(set.words, wordsInCommon, words, wordsInCommon,
 598           set.wordsInUse - wordsInCommon);
 599
 600     recalculateWordsInUse();
 601   }
 602
 603   /**
 604    * Clears all of the bits in this {@code BitSet} whose corresponding bit is
 605    * set in the specified {@code BitSet}.
 606    *
 607    * @param set
 608    *          the {@code BitSet} with which to mask this {@code BitSet}
 609    * @since 1.2
 610    */
 611   public void andNot(BS set) {
 612     // Perform logical (a & !b) on words in common
 613     for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
 614       words[i] &= ~set.words[i];
 615
 616     recalculateWordsInUse();
 617   }
 618
 619   /**
 620    * Returns a hash code value for this bit set. The hash code depends only on
 621    * which bits have been set within this <code>BitSet</code>. The algorithm
 622    * used to compute it may be described as follows.
 623    * <p>
 624    * Suppose the bits in the <code>BitSet</code> were to be stored in an array
 625    * of <code>long</code> integers called, say, <code>words</code>, in such a
 626    * manner that bit <code>k</code> is set in the <code>BitSet</code> (for
 627    * nonnegative values of <code>k</code>) if and only if the expression
 628    *
 629    * <pre>
 630    * ((k &gt;&gt; 6) &lt; words.length) &amp;&amp; ((words[k &gt;&gt; 6] &amp; (1 &lt;&lt; (bit &amp; 0x3F))) != 0)
 631    * </pre>
 632    *
 633    * is true. Then the following definition of the <code>hashCode</code> method
 634    * would be a correct implementation of the actual algorithm:
 635    *
 636    * <pre>
 637    * public int hashCode() {
 638    *  long h = 1234;
 639    *  for (int i = words.length; --i &gt;= 0;) {
 640    *    h &circ;= words[i] * (i + 1);
 641    *  }
 642    *  return (int) ((h &gt;&gt; 32) &circ; h);
 643    * }
 644    * </pre>
 645    *
 646    * Note that the hash code values change if the set of bits is altered.
 647    * <p>
 648    * Overrides the <code>hashCode</code> method of <code>Object</code>.
 649    *
 650    * @return a hash code value for this bit set.
 651    */
 652   @Override
 653   public int hashCode() {
 654     long h = 1234;
 655     for (int i = wordsInUse; --i >= 0;)
 656       h ^= words[i] * (i + 1);
 657
 658     return (int) ((h >> 32) ^ h);
 659   }
 660
 661   /**
 662    * Returns the number of bits of space actually in use by this {@code BitSet}
 663    * to represent bit values. The maximum element in the set is the size - 1st
 664    * element.
 665    *
 666    * @return the number of bits currently in this bit set
 667    */
 668   public int size() {
 669     return words.length * BITS_PER_WORD;
 670   }
 671
 672   /**
 673    * Compares this object against the specified object. The result is {@code
 674    * true} if and only if the argument is not {@code null} and is a {@code
 675    * Bitset} object that has exactly the same set of bits set to {@code true} as
 676    * this bit set. That is, for every nonnegative {@code int} index {@code k},
 677    *
 678    * <pre>
 679    * ((BitSet) obj).get(k) == this.get(k)
 680    * </pre>
 681    *
 682    * must be true. The current sizes of the two bit sets are not compared.
 683    *
 684    * @param obj
 685    *          the object to compare with
 686    * @return {@code true} if the objects are the same; {@code false} otherwise
 687    * @see #size()
 688    */
 689   @Override
 690   public boolean equals(Object obj) {
 691     if (!(obj instanceof BS))
 692       return false;
 693     if (this == obj)
 694       return true;
 695
 696     BS set = (BS) obj;
 697
 698     if (wordsInUse != set.wordsInUse)
 699       return false;
 700
 701     // Check words in use by both BitSets
 702     for (int i = 0; i < wordsInUse; i++)
 703       if (words[i] != set.words[i])
 704         return false;
 705
 706     return true;
 707   }
 708
 709   /**
 710    * Cloning this {@code BitSet} produces a new {@code BitSet} that is equal to
 711    * it. The clone of the bit set is another bit set that has exactly the same
 712    * bits set to {@code true} as this bit set.
 713    *
 714    * @return a clone of this bit set
 715    * @see #size()
 716    */
 717   @Override
 718   public Object clone() {
 719     if (!sizeIsSticky && wordsInUse != words.length)
 720       setLength(wordsInUse);
 721     return copy(this);
 722   }
 723
 724   /**
 725    * Attempts to reduce internal storage used for the bits in this bit set.
 726    * Calling this method may, but is not required to, affect the value returned
 727    * by a subsequent call to the {@link #size()} method.
 728    * @param n
 729    */
 730   private void setLength(int n) {
 731     int[] a = new int[n];
 732     System.arraycopy(words, 0, a, 0, Math.min(wordsInUse, n));
 733     words = a;
 734   }
 735
 736   /**
 737    * Returns a string representation of this bit set. For every index for which
 738    * this {@code BitSet} contains a bit in the set state, the decimal
 739    * representation of that index is included in the result. Such indices are
 740    * listed in order from lowest to highest, separated by ",&nbsp;" (a comma and
 741    * a space) and surrounded by braces, resulting in the usual mathematical
 742    * notation for a set of integers.
 743    *
 744    * <p>
 745    * Example:
 746    *
 747    * <pre>
 748    * BitSet drPepper = new BitSet();
 749    * </pre>
 750    *
 751    * Now {@code drPepper.toString()} returns "{}".
 752    * <p>
 753    *
 754    * <pre>
 755    * drPepper.set(2);
 756    * </pre>
 757    *
 758    * Now {@code drPepper.toString()} returns "{2}".
 759    * <p>
 760    *
 761    * <pre>
 762    * drPepper.set(4);
 763    * drPepper.set(10);
 764    * </pre>
 765    *
 766    * Now {@code drPepper.toString()} returns "{2, 4, 10}".
 767    *
 768    * @return a string representation of this bit set
 769    */
 770   @Override
 771   public String toString() {
 772     return escape(this, '{', '}');
 773   }
 774
 775   private final static int[] emptyBitmap = new int[0];
 776
 777   /**
 778    * fast copy
 779    *
 780    * @param bitsetToCopy
 781    * @return bs
 782    */
 783   public static BS copy(BS bitsetToCopy) {
 784     BS bs;
 785     /**
 786      * Clazz.clone will copy wordsInUse and sizeIsSticky,
 787      * but just a pointer to the words array.
 788      *
 789      * @j2sNative
 790      *
 791      *            bs = Clazz.clone(bitsetToCopy);
 792      *
 793      */
 794     {
 795       bs = new BS();
 796     }
 797     int wordCount = bitsetToCopy.wordsInUse;
 798     if (wordCount == 0) {
 799       bs.words = emptyBitmap;
 800     } else {
 801       bs.words = new int[bs.wordsInUse = wordCount];
 802       System.arraycopy(bitsetToCopy.words, 0, bs.words, 0, wordCount);
 803     }
 804     return bs;
 805   }
 806
 807   /**
 808    *
 809    * @param max
 810    * @return n bits below max
 811    */
 812   public int cardinalityN(int max) {
 813     int n = cardinality();
 814     for (int i = length(); --i >= max;)
 815       if (get(i))
 816         n--;
 817     return n;
 818   }
 819
 820   @Override
 821   public String toJSON() {
 822
 823     int numBits = (wordsInUse > 128) ? cardinality() : wordsInUse
 824         * BITS_PER_WORD;
 825     SB b = SB.newN(6 * numBits + 2);
 826     b.appendC('[');
 827
 828     int i = nextSetBit(0);
 829     if (i != -1) {
 830       b.appendI(i);
 831       for (i = nextSetBit(i + 1); i >= 0; i = nextSetBit(i + 1)) {
 832         int endOfRun = nextClearBit(i);
 833         do {
 834           b.append(", ").appendI(i);
 835         } while (++i < endOfRun);
 836       }
 837     }
 838
 839     b.appendC(']');
 840     return b.toString();
 841   }
 842
 843   public static String escape(BS bs, char chOpen, char chClose) {
 844     if (bs == null)
 845       return chOpen + "{}" + chClose;
 846     SB s = new SB();
 847     s.append(chOpen + "{");
 848     int imax = bs.length();
 849     int iLast = -1;
 850     int iFirst = -2;
 851     int i = -1;
 852     while (++i <= imax) {
 853       boolean isSet = bs.get(i);
 854       if (i == imax || iLast >= 0 && !isSet) {
 855         if (iLast >= 0 && iFirst != iLast)
 856           s.append((iFirst == iLast - 1 ? " " : ":") + iLast);
 857         if (i == imax)
 858           break;
 859         iLast = -1;
 860       }
 861       if (bs.get(i)) {
 862         if (iLast < 0) {
 863           s.append((iFirst == -2 ? "" : " ") + i);
 864           iFirst = i;
 865         }
 866         iLast = i;
 867       }
 868     }
 869     s.append("}").appendC(chClose);
 870     return s.toString();
 871   }
 872
 873   public static BS unescape(String str) {
 874     char ch;
 875     int len;
 876     if (str == null || (len = (str = str.trim()).length()) < 4
 877         || str.equalsIgnoreCase("({null})")
 878         || (ch = str.charAt(0)) != '(' && ch != '['
 879         || str.charAt(len - 1) != (ch == '(' ? ')' : ']')
 880         || str.charAt(1) != '{' || str.indexOf('}') != len - 2)
 881       return null;
 882     len -= 2;
 883     for (int i = len; --i >= 2;)
 884       if (!PT.isDigit(ch = str.charAt(i)) && ch != ' ' && ch != '\t'
 885           && ch != ':')
 886         return null;
 887     int lastN = len;
 888     while (PT.isDigit(str.charAt(--lastN))) {
 889       // loop
 890     }
 891     if (++lastN == len)
 892       lastN = 0;
 893     else
 894       try {
 895         lastN = Integer.parseInt(str.substring(lastN, len));
 896       } catch (NumberFormatException e) {
 897         return null;
 898       }
 899     BS bs = BS.newN(lastN);
 900     lastN = -1;
 901     int iPrev = -1;
 902     int iThis = -2;
 903     for (int i = 2; i <= len; i++) {
 904       switch (ch = str.charAt(i)) {
 905       case '\t':
 906       case ' ':
 907       case '}':
 908         if (iThis < 0)
 909           break;
 910         if (iThis < lastN)
 911           return null;
 912         lastN = iThis;
 913         if (iPrev < 0)
 914           iPrev = iThis;
 915         bs.setBits(iPrev, iThis + 1);
 916         iPrev = -1;
 917         iThis = -2;
 918         break;
 919       case ':':
 920         iPrev = lastN = iThis;
 921         iThis = -2;
 922         break;
 923       default:
 924         if (PT.isDigit(ch)) {
 925           if (iThis < 0)
 926             iThis = 0;
 927           iThis = (iThis * 10) + (ch - 48);
 928         }
 929       }
 930     }
 931     return (iPrev >= 0 ? null : bs);
 932   }
 933
 934 }