srcjar/javajs/util/BS.java

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