Merge branch 'features/r2_11_2/JAL-3821_reinstate_patch' into develop
[jalview.git] / unused / 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 }