src/javajs/util/BS.java

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