2 * Copyright 1995-2007 Sun Microsystems, Inc. All Rights Reserved.
\r
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
\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
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
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
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
26 package javajs.util;
\r
28 import javajs.api.JSONEncodable;
\r
34 * a fast 32-bit BitSet optimized for Java2Script -- about 25 times faster than
\r
37 * @author Bob Hanson hansonr@stolaf.edu
\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
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
53 * By default, all bits in the set initially have the value {@code
\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
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
69 * A {@code BitSet} is not safe for multithreaded use without external
\r
72 * @author Arthur van Hoff
\r
73 * @author Michael McCloskey
\r
74 * @author Martin Buchholz
\r
77 public class BS implements Cloneable, JSONEncodable {
\r
79 * BitSets are packed into arrays of "words."
\r
81 * An int, which consists of 32 bits, requiring 5 address bits, is used for
\r
82 * the JavaScript port.
\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
87 /* Used to shift left or right for a partial word mask */
\r
88 private static final int WORD_MASK = 0xffffffff;
\r
92 * The internal field corresponding to the serialField "bits".
\r
94 private int[] words;
\r
97 * The number of words in the logical size of this BitSet.
\r
99 private transient int wordsInUse = 0;
\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
105 private transient boolean sizeIsSticky = false;
\r
107 /* use serialVersionUID from JDK 1.0.2 for interoperability */
\r
108 //private static final long serialVersionUID = 7997698588986878753L;
\r
111 * Given a bit index, return word index containing it.
\r
115 private static int wordIndex(int bitIndex) {
\r
116 return bitIndex >> ADDRESS_BITS_PER_WORD;
\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
124 private void recalculateWordsInUse() {
\r
125 // Traverse the bitset until a used word is found
\r
127 for (i = wordsInUse - 1; i >= 0; i--)
\r
131 wordsInUse = i + 1; // The new logical size
\r
135 * Creates a new bit set. All bits are initially {@code false}.
\r
138 initWords(BITS_PER_WORD);
\r
139 sizeIsSticky = false;
\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
148 * the initial size of the bit set
\r
150 * @throws NegativeArraySizeException
\r
151 * if the specified initial size is negative
\r
153 public static BS newN(int nbits) {
\r
159 private void init(int nbits) {
\r
160 // nbits can't be negative; size 0 is OK
\r
162 throw new NegativeArraySizeException("nbits < 0: " + nbits);
\r
164 sizeIsSticky = true;
\r
167 private void initWords(int nbits) {
\r
168 words = new int[wordIndex(nbits - 1) + 1];
\r
172 * Ensures that the BitSet can hold enough words.
\r
174 * @param wordsRequired
\r
175 * the minimum acceptable number of words.
\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
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
192 * the index to be accommodated.
\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
204 * Sets the bit at the specified index to {@code true}.
\r
208 * @throws IndexOutOfBoundsException
\r
209 * if the specified index is negative
\r
212 public void set(int bitIndex) {
\r
214 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
\r
216 int wordIndex = wordIndex(bitIndex);
\r
217 expandTo(wordIndex);
\r
219 words[wordIndex] |= (1 << bitIndex); // Restores invariants
\r
224 * Sets the bit at the specified index to the specified value.
\r
229 * a boolean value to set
\r
230 * @throws IndexOutOfBoundsException
\r
231 * if the specified index is negative
\r
234 public void setBitTo(int bitIndex, boolean value) {
\r
242 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
\r
243 * specified {@code toIndex} (exclusive) to {@code true}.
\r
246 * index of the first bit to be set
\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
254 public void setBits(int fromIndex, int toIndex) {
\r
256 if (fromIndex == toIndex)
\r
259 // Increase capacity if necessary
\r
260 int startWordIndex = wordIndex(fromIndex);
\r
261 int endWordIndex = wordIndex(toIndex - 1);
\r
262 expandTo(endWordIndex);
\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
270 // Case 2: Multiple words
\r
271 // Handle first word
\r
272 words[startWordIndex] |= firstWordMask;
\r
274 // Handle intermediate words, if any
\r
275 for (int i = startWordIndex + 1; i < endWordIndex; i++)
\r
276 words[i] = WORD_MASK;
\r
278 // Handle last word (restores invariants)
\r
279 words[endWordIndex] |= lastWordMask;
\r
284 * Sets the bit specified by the index to {@code false}.
\r
287 * the index of the bit to be cleared
\r
288 * @throws IndexOutOfBoundsException
\r
289 * if the specified index is negative
\r
292 public void clear(int bitIndex) {
\r
294 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
\r
296 int wordIndex = wordIndex(bitIndex);
\r
297 if (wordIndex >= wordsInUse)
\r
300 words[wordIndex] &= ~(1 << bitIndex);
\r
302 recalculateWordsInUse();
\r
306 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
\r
307 * specified {@code toIndex} (exclusive) to {@code false}.
\r
310 * index of the first bit to be cleared
\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
318 public void clearBits(int fromIndex, int toIndex) {
\r
319 if (fromIndex == toIndex)
\r
322 int startWordIndex = wordIndex(fromIndex);
\r
323 if (startWordIndex >= wordsInUse)
\r
326 int endWordIndex = wordIndex(toIndex - 1);
\r
327 if (endWordIndex >= wordsInUse) {
\r
328 toIndex = length();
\r
329 endWordIndex = wordsInUse - 1;
\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
338 // Case 2: Multiple words
\r
339 // Handle first word
\r
340 words[startWordIndex] &= ~firstWordMask;
\r
342 // Handle intermediate words, if any
\r
343 for (int i = startWordIndex + 1; i < endWordIndex; i++)
\r
346 // Handle last word
\r
347 words[endWordIndex] &= ~lastWordMask;
\r
350 recalculateWordsInUse();
\r
354 * Sets all of the bits in this BitSet to {@code false}.
\r
358 public void clearAll() {
\r
359 while (wordsInUse > 0)
\r
360 words[--wordsInUse] = 0;
\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
370 * @return the value of the bit with the specified index
\r
371 * @throws IndexOutOfBoundsException
\r
372 * if the specified index is negative
\r
374 public boolean get(int bitIndex) {
\r
376 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
\r
378 int wordIndex = wordIndex(bitIndex);
\r
379 return (wordIndex < wordsInUse)
\r
380 && ((words[wordIndex] & (1 << bitIndex)) != 0);
\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
389 * To iterate over the {@code true} bits in a {@code BitSet}, use the
\r
394 * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
\r
395 * // operate on index i here
\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
403 * @throws IndexOutOfBoundsException
\r
404 * if the specified index is negative
\r
407 public int nextSetBit(int fromIndex) {
\r
409 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
\r
411 int u = wordIndex(fromIndex);
\r
412 if (u >= wordsInUse)
\r
415 int word = words[u] & (WORD_MASK << fromIndex);
\r
419 return (u * BITS_PER_WORD) + Integer.numberOfTrailingZeros(word);
\r
420 if (++u == wordsInUse)
\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
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
437 public int nextClearBit(int fromIndex) {
\r
438 // Neither spec nor implementation handle bitsets of maximal length.
\r
441 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
\r
443 int u = wordIndex(fromIndex);
\r
444 if (u >= wordsInUse)
\r
447 int word = ~words[u] & (WORD_MASK << fromIndex);
\r
451 return (u * BITS_PER_WORD) + Integer.numberOfTrailingZeros(word);
\r
452 if (++u == wordsInUse)
\r
453 return wordsInUse * BITS_PER_WORD;
\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
463 * @return the logical size of this {@code BitSet}
\r
466 public int length() {
\r
467 if (wordsInUse == 0)
\r
470 return BITS_PER_WORD * (wordsInUse - 1)
\r
471 + (BITS_PER_WORD - Integer.numberOfLeadingZeros(words[wordsInUse - 1]));
\r
475 * Returns true if this {@code BitSet} contains no bits that are set to
\r
478 * @return boolean indicating whether this {@code BitSet} is empty
\r
481 public boolean isEmpty() {
\r
482 return wordsInUse == 0;
\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
490 * {@code BitSet} to intersect with
\r
491 * @return boolean indicating whether this {@code BitSet} intersects the
\r
492 * specified {@code BitSet}
\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
503 * Returns the number of bits set to {@code true} in this {@code BitSet}.
\r
505 * @return the number of bits set to {@code true} in this {@code BitSet}
\r
508 public int cardinality() {
\r
510 for (int i = 0; i < wordsInUse; i++)
\r
511 sum += Integer.bitCount(words[i]);
\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
524 public void and(BS set) {
\r
528 while (wordsInUse > set.wordsInUse)
\r
529 words[--wordsInUse] = 0;
\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
535 recalculateWordsInUse();
\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
547 public void or(BS set) {
\r
551 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
\r
553 if (wordsInUse < set.wordsInUse) {
\r
554 ensureCapacity(set.wordsInUse);
\r
555 wordsInUse = set.wordsInUse;
\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
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
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
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
583 public void xor(BS set) {
\r
584 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
\r
586 if (wordsInUse < set.wordsInUse) {
\r
587 ensureCapacity(set.wordsInUse);
\r
588 wordsInUse = set.wordsInUse;
\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
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
600 recalculateWordsInUse();
\r
604 * Clears all of the bits in this {@code BitSet} whose corresponding bit is
\r
605 * set in the specified {@code BitSet}.
\r
608 * the {@code BitSet} with which to mask this {@code BitSet}
\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
616 recalculateWordsInUse();
\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
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
630 * ((k >> 6) < words.length) && ((words[k >> 6] & (1 << (bit & 0x3F))) != 0)
\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
637 * public int hashCode() {
\r
639 * for (int i = words.length; --i >= 0;) {
\r
640 * h ˆ= words[i] * (i + 1);
\r
642 * return (int) ((h >> 32) ˆ h);
\r
646 * Note that the hash code values change if the set of bits is altered.
\r
648 * Overrides the <code>hashCode</code> method of <code>Object</code>.
\r
650 * @return a hash code value for this bit set.
\r
653 public int hashCode() {
\r
655 for (int i = wordsInUse; --i >= 0;)
\r
656 h ^= words[i] * (i + 1);
\r
658 return (int) ((h >> 32) ^ h);
\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
666 * @return the number of bits currently in this bit set
\r
668 public int size() {
\r
669 return words.length * BITS_PER_WORD;
\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
679 * ((BitSet) obj).get(k) == this.get(k)
\r
682 * must be true. The current sizes of the two bit sets are not compared.
\r
685 * the object to compare with
\r
686 * @return {@code true} if the objects are the same; {@code false} otherwise
\r
690 public boolean equals(Object obj) {
\r
691 if (!(obj instanceof BS))
\r
698 if (wordsInUse != set.wordsInUse)
\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
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
714 * @return a clone of this bit set
\r
718 public Object clone() {
\r
719 if (!sizeIsSticky && wordsInUse != words.length)
\r
720 setLength(wordsInUse);
\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
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
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 ", " (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
748 * BitSet drPepper = new BitSet();
\r
751 * Now {@code drPepper.toString()} returns "{}".
\r
758 * Now {@code drPepper.toString()} returns "{2}".
\r
763 * drPepper.set(10);
\r
766 * Now {@code drPepper.toString()} returns "{2, 4, 10}".
\r
768 * @return a string representation of this bit set
\r
771 public String toString() {
\r
772 return escape(this, '{', '}');
\r
775 private final static int[] emptyBitmap = new int[0];
\r
780 * @param bitsetToCopy
\r
783 public static BS copy(BS bitsetToCopy) {
\r
786 * Clazz.clone will copy wordsInUse and sizeIsSticky,
\r
787 * but just a pointer to the words array.
\r
791 * bs = Clazz.clone(bitsetToCopy);
\r
797 int wordCount = bitsetToCopy.wordsInUse;
\r
798 if (wordCount == 0) {
\r
799 bs.words = emptyBitmap;
\r
801 bs.words = new int[bs.wordsInUse = wordCount];
\r
802 System.arraycopy(bitsetToCopy.words, 0, bs.words, 0, wordCount);
\r
810 * @return n bits below max
\r
812 public int cardinalityN(int max) {
\r
813 int n = cardinality();
\r
814 for (int i = length(); --i >= max;)
\r
821 public String toJSON() {
\r
823 int numBits = (wordsInUse > 128) ? cardinality() : wordsInUse
\r
825 SB b = SB.newN(6 * numBits + 2);
\r
828 int i = nextSetBit(0);
\r
831 for (i = nextSetBit(i + 1); i >= 0; i = nextSetBit(i + 1)) {
\r
832 int endOfRun = nextClearBit(i);
\r
834 b.append(", ").appendI(i);
\r
835 } while (++i < endOfRun);
\r
840 return b.toString();
\r
843 public static String escape(BS bs, char chOpen, char chClose) {
\r
845 return chOpen + "{}" + chClose;
\r
847 s.append(chOpen + "{");
\r
848 int imax = bs.length();
\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
863 s.append((iFirst == -2 ? "" : " ") + i);
\r
869 s.append("}").appendC(chClose);
\r
870 return s.toString();
\r
873 public static BS unescape(String str) {
\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
883 for (int i = len; --i >= 2;)
\r
884 if (!PT.isDigit(ch = str.charAt(i)) && ch != ' ' && ch != '\t'
\r
888 while (PT.isDigit(str.charAt(--lastN))) {
\r
891 if (++lastN == len)
\r
895 lastN = Integer.parseInt(str.substring(lastN, len));
\r
896 } catch (NumberFormatException e) {
\r
899 BS bs = BS.newN(lastN);
\r
903 for (int i = 2; i <= len; i++) {
\r
904 switch (ch = str.charAt(i)) {
\r
915 bs.setBits(iPrev, iThis + 1);
\r
920 iPrev = lastN = iThis;
\r
924 if (PT.isDigit(ch)) {
\r
927 iThis = (iThis * 10) + (ch - 48);
\r
931 return (iPrev >= 0 ? null : bs);
\r