Home » openjdk-7 » java » util » [javadoc | source]

    1   /*
    2    * Copyright (c) 1995, 2007, Oracle and/or its affiliates. All rights reserved.
    3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    4    *
    5    * This code is free software; you can redistribute it and/or modify it
    6    * under the terms of the GNU General Public License version 2 only, as
    7    * published by the Free Software Foundation.  Oracle designates this
    8    * particular file as subject to the "Classpath" exception as provided
    9    * by Oracle in the LICENSE file that accompanied this code.
   10    *
   11    * This code is distributed in the hope that it will be useful, but WITHOUT
   12    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   13    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   14    * version 2 for more details (a copy is included in the LICENSE file that
   15    * accompanied this code).
   16    *
   17    * You should have received a copy of the GNU General Public License version
   18    * 2 along with this work; if not, write to the Free Software Foundation,
   19    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   20    *
   21    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   22    * or visit www.oracle.com if you need additional information or have any
   23    * questions.
   24    */
   25   
   26   package java.util;
   27   
   28   import java.io;
   29   import java.nio.ByteBuffer;
   30   import java.nio.ByteOrder;
   31   import java.nio.LongBuffer;
   32   
   33   /**
   34    * This class implements a vector of bits that grows as needed. Each
   35    * component of the bit set has a {@code boolean} value. The
   36    * bits of a {@code BitSet} are indexed by nonnegative integers.
   37    * Individual indexed bits can be examined, set, or cleared. One
   38    * {@code BitSet} may be used to modify the contents of another
   39    * {@code BitSet} through logical AND, logical inclusive OR, and
   40    * logical exclusive OR operations.
   41    *
   42    * <p>By default, all bits in the set initially have the value
   43    * {@code false}.
   44    *
   45    * <p>Every bit set has a current size, which is the number of bits
   46    * of space currently in use by the bit set. Note that the size is
   47    * related to the implementation of a bit set, so it may change with
   48    * implementation. The length of a bit set relates to logical length
   49    * of a bit set and is defined independently of implementation.
   50    *
   51    * <p>Unless otherwise noted, passing a null parameter to any of the
   52    * methods in a {@code BitSet} will result in a
   53    * {@code NullPointerException}.
   54    *
   55    * <p>A {@code BitSet} is not safe for multithreaded use without
   56    * external synchronization.
   57    *
   58    * @author  Arthur van Hoff
   59    * @author  Michael McCloskey
   60    * @author  Martin Buchholz
   61    * @since   JDK1.0
   62    */
   63   public class BitSet implements Cloneable, java.io.Serializable {
   64       /*
   65        * BitSets are packed into arrays of "words."  Currently a word is
   66        * a long, which consists of 64 bits, requiring 6 address bits.
   67        * The choice of word size is determined purely by performance concerns.
   68        */
   69       private final static int ADDRESS_BITS_PER_WORD = 6;
   70       private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
   71       private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
   72   
   73       /* Used to shift left or right for a partial word mask */
   74       private static final long WORD_MASK = 0xffffffffffffffffL;
   75   
   76       /**
   77        * @serialField bits long[]
   78        *
   79        * The bits in this BitSet.  The ith bit is stored in bits[i/64] at
   80        * bit position i % 64 (where bit position 0 refers to the least
   81        * significant bit and 63 refers to the most significant bit).
   82        */
   83       private static final ObjectStreamField[] serialPersistentFields = {
   84           new ObjectStreamField("bits", long[].class),
   85       };
   86   
   87       /**
   88        * The internal field corresponding to the serialField "bits".
   89        */
   90       private long[] words;
   91   
   92       /**
   93        * The number of words in the logical size of this BitSet.
   94        */
   95       private transient int wordsInUse = 0;
   96   
   97       /**
   98        * Whether the size of "words" is user-specified.  If so, we assume
   99        * the user knows what he's doing and try harder to preserve it.
  100        */
  101       private transient boolean sizeIsSticky = false;
  102   
  103       /* use serialVersionUID from JDK 1.0.2 for interoperability */
  104       private static final long serialVersionUID = 7997698588986878753L;
  105   
  106       /**
  107        * Given a bit index, return word index containing it.
  108        */
  109       private static int wordIndex(int bitIndex) {
  110           return bitIndex >> ADDRESS_BITS_PER_WORD;
  111       }
  112   
  113       /**
  114        * Every public method must preserve these invariants.
  115        */
  116       private void checkInvariants() {
  117           assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
  118           assert(wordsInUse >= 0 && wordsInUse <= words.length);
  119           assert(wordsInUse == words.length || words[wordsInUse] == 0);
  120       }
  121   
  122       /**
  123        * Sets the field wordsInUse to the logical size in words of the bit set.
  124        * WARNING:This method assumes that the number of words actually in use is
  125        * less than or equal to the current value of wordsInUse!
  126        */
  127       private void recalculateWordsInUse() {
  128           // Traverse the bitset until a used word is found
  129           int i;
  130           for (i = wordsInUse-1; i >= 0; i--)
  131               if (words[i] != 0)
  132                   break;
  133   
  134           wordsInUse = i+1; // The new logical size
  135       }
  136   
  137       /**
  138        * Creates a new bit set. All bits are initially {@code false}.
  139        */
  140       public BitSet() {
  141           initWords(BITS_PER_WORD);
  142           sizeIsSticky = false;
  143       }
  144   
  145       /**
  146        * Creates a bit set whose initial size is large enough to explicitly
  147        * represent bits with indices in the range {@code 0} through
  148        * {@code nbits-1}. All bits are initially {@code false}.
  149        *
  150        * @param  nbits the initial size of the bit set
  151        * @throws NegativeArraySizeException if the specified initial size
  152        *         is negative
  153        */
  154       public BitSet(int nbits) {
  155           // nbits can't be negative; size 0 is OK
  156           if (nbits < 0)
  157               throw new NegativeArraySizeException("nbits < 0: " + nbits);
  158   
  159           initWords(nbits);
  160           sizeIsSticky = true;
  161       }
  162   
  163       private void initWords(int nbits) {
  164           words = new long[wordIndex(nbits-1) + 1];
  165       }
  166   
  167       /**
  168        * Creates a bit set using words as the internal representation.
  169        * The last word (if there is one) must be non-zero.
  170        */
  171       private BitSet(long[] words) {
  172           this.words = words;
  173           this.wordsInUse = words.length;
  174           checkInvariants();
  175       }
  176   
  177       /**
  178        * Returns a new bit set containing all the bits in the given long array.
  179        *
  180        * <p>More precisely,
  181        * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
  182        * <br>for all {@code n < 64 * longs.length}.
  183        *
  184        * <p>This method is equivalent to
  185        * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
  186        *
  187        * @param longs a long array containing a little-endian representation
  188        *        of a sequence of bits to be used as the initial bits of the
  189        *        new bit set
  190        * @since 1.7
  191        */
  192       public static BitSet valueOf(long[] longs) {
  193           int n;
  194           for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
  195               ;
  196           return new BitSet(Arrays.copyOf(longs, n));
  197       }
  198   
  199       /**
  200        * Returns a new bit set containing all the bits in the given long
  201        * buffer between its position and limit.
  202        *
  203        * <p>More precisely,
  204        * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
  205        * <br>for all {@code n < 64 * lb.remaining()}.
  206        *
  207        * <p>The long buffer is not modified by this method, and no
  208        * reference to the buffer is retained by the bit set.
  209        *
  210        * @param lb a long buffer containing a little-endian representation
  211        *        of a sequence of bits between its position and limit, to be
  212        *        used as the initial bits of the new bit set
  213        * @since 1.7
  214        */
  215       public static BitSet valueOf(LongBuffer lb) {
  216           lb = lb.slice();
  217           int n;
  218           for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
  219               ;
  220           long[] words = new long[n];
  221           lb.get(words);
  222           return new BitSet(words);
  223       }
  224   
  225       /**
  226        * Returns a new bit set containing all the bits in the given byte array.
  227        *
  228        * <p>More precisely,
  229        * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
  230        * <br>for all {@code n <  8 * bytes.length}.
  231        *
  232        * <p>This method is equivalent to
  233        * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
  234        *
  235        * @param bytes a byte array containing a little-endian
  236        *        representation of a sequence of bits to be used as the
  237        *        initial bits of the new bit set
  238        * @since 1.7
  239        */
  240       public static BitSet valueOf(byte[] bytes) {
  241           return BitSet.valueOf(ByteBuffer.wrap(bytes));
  242       }
  243   
  244       /**
  245        * Returns a new bit set containing all the bits in the given byte
  246        * buffer between its position and limit.
  247        *
  248        * <p>More precisely,
  249        * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
  250        * <br>for all {@code n < 8 * bb.remaining()}.
  251        *
  252        * <p>The byte buffer is not modified by this method, and no
  253        * reference to the buffer is retained by the bit set.
  254        *
  255        * @param bb a byte buffer containing a little-endian representation
  256        *        of a sequence of bits between its position and limit, to be
  257        *        used as the initial bits of the new bit set
  258        * @since 1.7
  259        */
  260       public static BitSet valueOf(ByteBuffer bb) {
  261           bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
  262           int n;
  263           for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
  264               ;
  265           long[] words = new long[(n + 7) / 8];
  266           bb.limit(n);
  267           int i = 0;
  268           while (bb.remaining() >= 8)
  269               words[i++] = bb.getLong();
  270           for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
  271               words[i] |= (bb.get() & 0xffL) << (8 * j);
  272           return new BitSet(words);
  273       }
  274   
  275       /**
  276        * Returns a new byte array containing all the bits in this bit set.
  277        *
  278        * <p>More precisely, if
  279        * <br>{@code byte[] bytes = s.toByteArray();}
  280        * <br>then {@code bytes.length == (s.length()+7)/8} and
  281        * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
  282        * <br>for all {@code n < 8 * bytes.length}.
  283        *
  284        * @return a byte array containing a little-endian representation
  285        *         of all the bits in this bit set
  286        * @since 1.7
  287       */
  288       public byte[] toByteArray() {
  289           int n = wordsInUse;
  290           if (n == 0)
  291               return new byte[0];
  292           int len = 8 * (n-1);
  293           for (long x = words[n - 1]; x != 0; x >>>= 8)
  294               len++;
  295           byte[] bytes = new byte[len];
  296           ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
  297           for (int i = 0; i < n - 1; i++)
  298               bb.putLong(words[i]);
  299           for (long x = words[n - 1]; x != 0; x >>>= 8)
  300               bb.put((byte) (x & 0xff));
  301           return bytes;
  302       }
  303   
  304       /**
  305        * Returns a new long array containing all the bits in this bit set.
  306        *
  307        * <p>More precisely, if
  308        * <br>{@code long[] longs = s.toLongArray();}
  309        * <br>then {@code longs.length == (s.length()+63)/64} and
  310        * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
  311        * <br>for all {@code n < 64 * longs.length}.
  312        *
  313        * @return a long array containing a little-endian representation
  314        *         of all the bits in this bit set
  315        * @since 1.7
  316       */
  317       public long[] toLongArray() {
  318           return Arrays.copyOf(words, wordsInUse);
  319       }
  320   
  321       /**
  322        * Ensures that the BitSet can hold enough words.
  323        * @param wordsRequired the minimum acceptable number of words.
  324        */
  325       private void ensureCapacity(int wordsRequired) {
  326           if (words.length < wordsRequired) {
  327               // Allocate larger of doubled size or required size
  328               int request = Math.max(2 * words.length, wordsRequired);
  329               words = Arrays.copyOf(words, request);
  330               sizeIsSticky = false;
  331           }
  332       }
  333   
  334       /**
  335        * Ensures that the BitSet can accommodate a given wordIndex,
  336        * temporarily violating the invariants.  The caller must
  337        * restore the invariants before returning to the user,
  338        * possibly using recalculateWordsInUse().
  339        * @param wordIndex the index to be accommodated.
  340        */
  341       private void expandTo(int wordIndex) {
  342           int wordsRequired = wordIndex+1;
  343           if (wordsInUse < wordsRequired) {
  344               ensureCapacity(wordsRequired);
  345               wordsInUse = wordsRequired;
  346           }
  347       }
  348   
  349       /**
  350        * Checks that fromIndex ... toIndex is a valid range of bit indices.
  351        */
  352       private static void checkRange(int fromIndex, int toIndex) {
  353           if (fromIndex < 0)
  354               throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
  355           if (toIndex < 0)
  356               throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
  357           if (fromIndex > toIndex)
  358               throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
  359                                                   " > toIndex: " + toIndex);
  360       }
  361   
  362       /**
  363        * Sets the bit at the specified index to the complement of its
  364        * current value.
  365        *
  366        * @param  bitIndex the index of the bit to flip
  367        * @throws IndexOutOfBoundsException if the specified index is negative
  368        * @since  1.4
  369        */
  370       public void flip(int bitIndex) {
  371           if (bitIndex < 0)
  372               throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
  373   
  374           int wordIndex = wordIndex(bitIndex);
  375           expandTo(wordIndex);
  376   
  377           words[wordIndex] ^= (1L << bitIndex);
  378   
  379           recalculateWordsInUse();
  380           checkInvariants();
  381       }
  382   
  383       /**
  384        * Sets each bit from the specified {@code fromIndex} (inclusive) to the
  385        * specified {@code toIndex} (exclusive) to the complement of its current
  386        * value.
  387        *
  388        * @param  fromIndex index of the first bit to flip
  389        * @param  toIndex index after the last bit to flip
  390        * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
  391        *         or {@code toIndex} is negative, or {@code fromIndex} is
  392        *         larger than {@code toIndex}
  393        * @since  1.4
  394        */
  395       public void flip(int fromIndex, int toIndex) {
  396           checkRange(fromIndex, toIndex);
  397   
  398           if (fromIndex == toIndex)
  399               return;
  400   
  401           int startWordIndex = wordIndex(fromIndex);
  402           int endWordIndex   = wordIndex(toIndex - 1);
  403           expandTo(endWordIndex);
  404   
  405           long firstWordMask = WORD_MASK << fromIndex;
  406           long lastWordMask  = WORD_MASK >>> -toIndex;
  407           if (startWordIndex == endWordIndex) {
  408               // Case 1: One word
  409               words[startWordIndex] ^= (firstWordMask & lastWordMask);
  410           } else {
  411               // Case 2: Multiple words
  412               // Handle first word
  413               words[startWordIndex] ^= firstWordMask;
  414   
  415               // Handle intermediate words, if any
  416               for (int i = startWordIndex+1; i < endWordIndex; i++)
  417                   words[i] ^= WORD_MASK;
  418   
  419               // Handle last word
  420               words[endWordIndex] ^= lastWordMask;
  421           }
  422   
  423           recalculateWordsInUse();
  424           checkInvariants();
  425       }
  426   
  427       /**
  428        * Sets the bit at the specified index to {@code true}.
  429        *
  430        * @param  bitIndex a bit index
  431        * @throws IndexOutOfBoundsException if the specified index is negative
  432        * @since  JDK1.0
  433        */
  434       public void set(int bitIndex) {
  435           if (bitIndex < 0)
  436               throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
  437   
  438           int wordIndex = wordIndex(bitIndex);
  439           expandTo(wordIndex);
  440   
  441           words[wordIndex] |= (1L << bitIndex); // Restores invariants
  442   
  443           checkInvariants();
  444       }
  445   
  446       /**
  447        * Sets the bit at the specified index to the specified value.
  448        *
  449        * @param  bitIndex a bit index
  450        * @param  value a boolean value to set
  451        * @throws IndexOutOfBoundsException if the specified index is negative
  452        * @since  1.4
  453        */
  454       public void set(int bitIndex, boolean value) {
  455           if (value)
  456               set(bitIndex);
  457           else
  458               clear(bitIndex);
  459       }
  460   
  461       /**
  462        * Sets the bits from the specified {@code fromIndex} (inclusive) to the
  463        * specified {@code toIndex} (exclusive) to {@code true}.
  464        *
  465        * @param  fromIndex index of the first bit to be set
  466        * @param  toIndex index after the last bit to be set
  467        * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
  468        *         or {@code toIndex} is negative, or {@code fromIndex} is
  469        *         larger than {@code toIndex}
  470        * @since  1.4
  471        */
  472       public void set(int fromIndex, int toIndex) {
  473           checkRange(fromIndex, toIndex);
  474   
  475           if (fromIndex == toIndex)
  476               return;
  477   
  478           // Increase capacity if necessary
  479           int startWordIndex = wordIndex(fromIndex);
  480           int endWordIndex   = wordIndex(toIndex - 1);
  481           expandTo(endWordIndex);
  482   
  483           long firstWordMask = WORD_MASK << fromIndex;
  484           long lastWordMask  = WORD_MASK >>> -toIndex;
  485           if (startWordIndex == endWordIndex) {
  486               // Case 1: One word
  487               words[startWordIndex] |= (firstWordMask & lastWordMask);
  488           } else {
  489               // Case 2: Multiple words
  490               // Handle first word
  491               words[startWordIndex] |= firstWordMask;
  492   
  493               // Handle intermediate words, if any
  494               for (int i = startWordIndex+1; i < endWordIndex; i++)
  495                   words[i] = WORD_MASK;
  496   
  497               // Handle last word (restores invariants)
  498               words[endWordIndex] |= lastWordMask;
  499           }
  500   
  501           checkInvariants();
  502       }
  503   
  504       /**
  505        * Sets the bits from the specified {@code fromIndex} (inclusive) to the
  506        * specified {@code toIndex} (exclusive) to the specified value.
  507        *
  508        * @param  fromIndex index of the first bit to be set
  509        * @param  toIndex index after the last bit to be set
  510        * @param  value value to set the selected bits to
  511        * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
  512        *         or {@code toIndex} is negative, or {@code fromIndex} is
  513        *         larger than {@code toIndex}
  514        * @since  1.4
  515        */
  516       public void set(int fromIndex, int toIndex, boolean value) {
  517           if (value)
  518               set(fromIndex, toIndex);
  519           else
  520               clear(fromIndex, toIndex);
  521       }
  522   
  523       /**
  524        * Sets the bit specified by the index to {@code false}.
  525        *
  526        * @param  bitIndex the index of the bit to be cleared
  527        * @throws IndexOutOfBoundsException if the specified index is negative
  528        * @since  JDK1.0
  529        */
  530       public void clear(int bitIndex) {
  531           if (bitIndex < 0)
  532               throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
  533   
  534           int wordIndex = wordIndex(bitIndex);
  535           if (wordIndex >= wordsInUse)
  536               return;
  537   
  538           words[wordIndex] &= ~(1L << bitIndex);
  539   
  540           recalculateWordsInUse();
  541           checkInvariants();
  542       }
  543   
  544       /**
  545        * Sets the bits from the specified {@code fromIndex} (inclusive) to the
  546        * specified {@code toIndex} (exclusive) to {@code false}.
  547        *
  548        * @param  fromIndex index of the first bit to be cleared
  549        * @param  toIndex index after the last bit to be cleared
  550        * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
  551        *         or {@code toIndex} is negative, or {@code fromIndex} is
  552        *         larger than {@code toIndex}
  553        * @since  1.4
  554        */
  555       public void clear(int fromIndex, int toIndex) {
  556           checkRange(fromIndex, toIndex);
  557   
  558           if (fromIndex == toIndex)
  559               return;
  560   
  561           int startWordIndex = wordIndex(fromIndex);
  562           if (startWordIndex >= wordsInUse)
  563               return;
  564   
  565           int endWordIndex = wordIndex(toIndex - 1);
  566           if (endWordIndex >= wordsInUse) {
  567               toIndex = length();
  568               endWordIndex = wordsInUse - 1;
  569           }
  570   
  571           long firstWordMask = WORD_MASK << fromIndex;
  572           long lastWordMask  = WORD_MASK >>> -toIndex;
  573           if (startWordIndex == endWordIndex) {
  574               // Case 1: One word
  575               words[startWordIndex] &= ~(firstWordMask & lastWordMask);
  576           } else {
  577               // Case 2: Multiple words
  578               // Handle first word
  579               words[startWordIndex] &= ~firstWordMask;
  580   
  581               // Handle intermediate words, if any
  582               for (int i = startWordIndex+1; i < endWordIndex; i++)
  583                   words[i] = 0;
  584   
  585               // Handle last word
  586               words[endWordIndex] &= ~lastWordMask;
  587           }
  588   
  589           recalculateWordsInUse();
  590           checkInvariants();
  591       }
  592   
  593       /**
  594        * Sets all of the bits in this BitSet to {@code false}.
  595        *
  596        * @since 1.4
  597        */
  598       public void clear() {
  599           while (wordsInUse > 0)
  600               words[--wordsInUse] = 0;
  601       }
  602   
  603       /**
  604        * Returns the value of the bit with the specified index. The value
  605        * is {@code true} if the bit with the index {@code bitIndex}
  606        * is currently set in this {@code BitSet}; otherwise, the result
  607        * is {@code false}.
  608        *
  609        * @param  bitIndex   the bit index
  610        * @return the value of the bit with the specified index
  611        * @throws IndexOutOfBoundsException if the specified index is negative
  612        */
  613       public boolean get(int bitIndex) {
  614           if (bitIndex < 0)
  615               throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
  616   
  617           checkInvariants();
  618   
  619           int wordIndex = wordIndex(bitIndex);
  620           return (wordIndex < wordsInUse)
  621               && ((words[wordIndex] & (1L << bitIndex)) != 0);
  622       }
  623   
  624       /**
  625        * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
  626        * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
  627        *
  628        * @param  fromIndex index of the first bit to include
  629        * @param  toIndex index after the last bit to include
  630        * @return a new {@code BitSet} from a range of this {@code BitSet}
  631        * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
  632        *         or {@code toIndex} is negative, or {@code fromIndex} is
  633        *         larger than {@code toIndex}
  634        * @since  1.4
  635        */
  636       public BitSet get(int fromIndex, int toIndex) {
  637           checkRange(fromIndex, toIndex);
  638   
  639           checkInvariants();
  640   
  641           int len = length();
  642   
  643           // If no set bits in range return empty bitset
  644           if (len <= fromIndex || fromIndex == toIndex)
  645               return new BitSet(0);
  646   
  647           // An optimization
  648           if (toIndex > len)
  649               toIndex = len;
  650   
  651           BitSet result = new BitSet(toIndex - fromIndex);
  652           int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
  653           int sourceIndex = wordIndex(fromIndex);
  654           boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
  655   
  656           // Process all words but the last word
  657           for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
  658               result.words[i] = wordAligned ? words[sourceIndex] :
  659                   (words[sourceIndex] >>> fromIndex) |
  660                   (words[sourceIndex+1] << -fromIndex);
  661   
  662           // Process the last word
  663           long lastWordMask = WORD_MASK >>> -toIndex;
  664           result.words[targetWords - 1] =
  665               ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
  666               ? /* straddles source words */
  667               ((words[sourceIndex] >>> fromIndex) |
  668                (words[sourceIndex+1] & lastWordMask) << -fromIndex)
  669               :
  670               ((words[sourceIndex] & lastWordMask) >>> fromIndex);
  671   
  672           // Set wordsInUse correctly
  673           result.wordsInUse = targetWords;
  674           result.recalculateWordsInUse();
  675           result.checkInvariants();
  676   
  677           return result;
  678       }
  679   
  680       /**
  681        * Returns the index of the first bit that is set to {@code true}
  682        * that occurs on or after the specified starting index. If no such
  683        * bit exists then {@code -1} is returned.
  684        *
  685        * <p>To iterate over the {@code true} bits in a {@code BitSet},
  686        * use the following loop:
  687        *
  688        *  <pre> {@code
  689        * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
  690        *     // operate on index i here
  691        * }}</pre>
  692        *
  693        * @param  fromIndex the index to start checking from (inclusive)
  694        * @return the index of the next set bit, or {@code -1} if there
  695        *         is no such bit
  696        * @throws IndexOutOfBoundsException if the specified index is negative
  697        * @since  1.4
  698        */
  699       public int nextSetBit(int fromIndex) {
  700           if (fromIndex < 0)
  701               throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
  702   
  703           checkInvariants();
  704   
  705           int u = wordIndex(fromIndex);
  706           if (u >= wordsInUse)
  707               return -1;
  708   
  709           long word = words[u] & (WORD_MASK << fromIndex);
  710   
  711           while (true) {
  712               if (word != 0)
  713                   return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
  714               if (++u == wordsInUse)
  715                   return -1;
  716               word = words[u];
  717           }
  718       }
  719   
  720       /**
  721        * Returns the index of the first bit that is set to {@code false}
  722        * that occurs on or after the specified starting index.
  723        *
  724        * @param  fromIndex the index to start checking from (inclusive)
  725        * @return the index of the next clear bit
  726        * @throws IndexOutOfBoundsException if the specified index is negative
  727        * @since  1.4
  728        */
  729       public int nextClearBit(int fromIndex) {
  730           // Neither spec nor implementation handle bitsets of maximal length.
  731           // See 4816253.
  732           if (fromIndex < 0)
  733               throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
  734   
  735           checkInvariants();
  736   
  737           int u = wordIndex(fromIndex);
  738           if (u >= wordsInUse)
  739               return fromIndex;
  740   
  741           long word = ~words[u] & (WORD_MASK << fromIndex);
  742   
  743           while (true) {
  744               if (word != 0)
  745                   return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
  746               if (++u == wordsInUse)
  747                   return wordsInUse * BITS_PER_WORD;
  748               word = ~words[u];
  749           }
  750       }
  751   
  752       /**
  753        * Returns the index of the nearest bit that is set to {@code true}
  754        * that occurs on or before the specified starting index.
  755        * If no such bit exists, or if {@code -1} is given as the
  756        * starting index, then {@code -1} is returned.
  757        *
  758        * <p>To iterate over the {@code true} bits in a {@code BitSet},
  759        * use the following loop:
  760        *
  761        *  <pre> {@code
  762        * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
  763        *     // operate on index i here
  764        * }}</pre>
  765        *
  766        * @param  fromIndex the index to start checking from (inclusive)
  767        * @return the index of the previous set bit, or {@code -1} if there
  768        *         is no such bit
  769        * @throws IndexOutOfBoundsException if the specified index is less
  770        *         than {@code -1}
  771        * @since  1.7
  772        */
  773       public int previousSetBit(int fromIndex) {
  774           if (fromIndex < 0) {
  775               if (fromIndex == -1)
  776                   return -1;
  777               throw new IndexOutOfBoundsException(
  778                   "fromIndex < -1: " + fromIndex);
  779           }
  780   
  781           checkInvariants();
  782   
  783           int u = wordIndex(fromIndex);
  784           if (u >= wordsInUse)
  785               return length() - 1;
  786   
  787           long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
  788   
  789           while (true) {
  790               if (word != 0)
  791                   return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
  792               if (u-- == 0)
  793                   return -1;
  794               word = words[u];
  795           }
  796       }
  797   
  798       /**
  799        * Returns the index of the nearest bit that is set to {@code false}
  800        * that occurs on or before the specified starting index.
  801        * If no such bit exists, or if {@code -1} is given as the
  802        * starting index, then {@code -1} is returned.
  803        *
  804        * @param  fromIndex the index to start checking from (inclusive)
  805        * @return the index of the previous clear bit, or {@code -1} if there
  806        *         is no such bit
  807        * @throws IndexOutOfBoundsException if the specified index is less
  808        *         than {@code -1}
  809        * @since  1.7
  810        */
  811       public int previousClearBit(int fromIndex) {
  812           if (fromIndex < 0) {
  813               if (fromIndex == -1)
  814                   return -1;
  815               throw new IndexOutOfBoundsException(
  816                   "fromIndex < -1: " + fromIndex);
  817           }
  818   
  819           checkInvariants();
  820   
  821           int u = wordIndex(fromIndex);
  822           if (u >= wordsInUse)
  823               return fromIndex;
  824   
  825           long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
  826   
  827           while (true) {
  828               if (word != 0)
  829                   return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
  830               if (u-- == 0)
  831                   return -1;
  832               word = ~words[u];
  833           }
  834       }
  835   
  836       /**
  837        * Returns the "logical size" of this {@code BitSet}: the index of
  838        * the highest set bit in the {@code BitSet} plus one. Returns zero
  839        * if the {@code BitSet} contains no set bits.
  840        *
  841        * @return the logical size of this {@code BitSet}
  842        * @since  1.2
  843        */
  844       public int length() {
  845           if (wordsInUse == 0)
  846               return 0;
  847   
  848           return BITS_PER_WORD * (wordsInUse - 1) +
  849               (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
  850       }
  851   
  852       /**
  853        * Returns true if this {@code BitSet} contains no bits that are set
  854        * to {@code true}.
  855        *
  856        * @return boolean indicating whether this {@code BitSet} is empty
  857        * @since  1.4
  858        */
  859       public boolean isEmpty() {
  860           return wordsInUse == 0;
  861       }
  862   
  863       /**
  864        * Returns true if the specified {@code BitSet} has any bits set to
  865        * {@code true} that are also set to {@code true} in this {@code BitSet}.
  866        *
  867        * @param  set {@code BitSet} to intersect with
  868        * @return boolean indicating whether this {@code BitSet} intersects
  869        *         the specified {@code BitSet}
  870        * @since  1.4
  871        */
  872       public boolean intersects(BitSet set) {
  873           for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
  874               if ((words[i] & set.words[i]) != 0)
  875                   return true;
  876           return false;
  877       }
  878   
  879       /**
  880        * Returns the number of bits set to {@code true} in this {@code BitSet}.
  881        *
  882        * @return the number of bits set to {@code true} in this {@code BitSet}
  883        * @since  1.4
  884        */
  885       public int cardinality() {
  886           int sum = 0;
  887           for (int i = 0; i < wordsInUse; i++)
  888               sum += Long.bitCount(words[i]);
  889           return sum;
  890       }
  891   
  892       /**
  893        * Performs a logical <b>AND</b> of this target bit set with the
  894        * argument bit set. This bit set is modified so that each bit in it
  895        * has the value {@code true} if and only if it both initially
  896        * had the value {@code true} and the corresponding bit in the
  897        * bit set argument also had the value {@code true}.
  898        *
  899        * @param set a bit set
  900        */
  901       public void and(BitSet set) {
  902           if (this == set)
  903               return;
  904   
  905           while (wordsInUse > set.wordsInUse)
  906               words[--wordsInUse] = 0;
  907   
  908           // Perform logical AND on words in common
  909           for (int i = 0; i < wordsInUse; i++)
  910               words[i] &= set.words[i];
  911   
  912           recalculateWordsInUse();
  913           checkInvariants();
  914       }
  915   
  916       /**
  917        * Performs a logical <b>OR</b> of this bit set with the bit set
  918        * argument. This bit set is modified so that a bit in it has the
  919        * value {@code true} if and only if it either already had the
  920        * value {@code true} or the corresponding bit in the bit set
  921        * argument has the value {@code true}.
  922        *
  923        * @param set a bit set
  924        */
  925       public void or(BitSet set) {
  926           if (this == set)
  927               return;
  928   
  929           int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
  930   
  931           if (wordsInUse < set.wordsInUse) {
  932               ensureCapacity(set.wordsInUse);
  933               wordsInUse = set.wordsInUse;
  934           }
  935   
  936           // Perform logical OR on words in common
  937           for (int i = 0; i < wordsInCommon; i++)
  938               words[i] |= set.words[i];
  939   
  940           // Copy any remaining words
  941           if (wordsInCommon < set.wordsInUse)
  942               System.arraycopy(set.words, wordsInCommon,
  943                                words, wordsInCommon,
  944                                wordsInUse - wordsInCommon);
  945   
  946           // recalculateWordsInUse() is unnecessary
  947           checkInvariants();
  948       }
  949   
  950       /**
  951        * Performs a logical <b>XOR</b> of this bit set with the bit set
  952        * argument. This bit set is modified so that a bit in it has the
  953        * value {@code true} if and only if one of the following
  954        * statements holds:
  955        * <ul>
  956        * <li>The bit initially has the value {@code true}, and the
  957        *     corresponding bit in the argument has the value {@code false}.
  958        * <li>The bit initially has the value {@code false}, and the
  959        *     corresponding bit in the argument has the value {@code true}.
  960        * </ul>
  961        *
  962        * @param  set a bit set
  963        */
  964       public void xor(BitSet set) {
  965           int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
  966   
  967           if (wordsInUse < set.wordsInUse) {
  968               ensureCapacity(set.wordsInUse);
  969               wordsInUse = set.wordsInUse;
  970           }
  971   
  972           // Perform logical XOR on words in common
  973           for (int i = 0; i < wordsInCommon; i++)
  974               words[i] ^= set.words[i];
  975   
  976           // Copy any remaining words
  977           if (wordsInCommon < set.wordsInUse)
  978               System.arraycopy(set.words, wordsInCommon,
  979                                words, wordsInCommon,
  980                                set.wordsInUse - wordsInCommon);
  981   
  982           recalculateWordsInUse();
  983           checkInvariants();
  984       }
  985   
  986       /**
  987        * Clears all of the bits in this {@code BitSet} whose corresponding
  988        * bit is set in the specified {@code BitSet}.
  989        *
  990        * @param  set the {@code BitSet} with which to mask this
  991        *         {@code BitSet}
  992        * @since  1.2
  993        */
  994       public void andNot(BitSet set) {
  995           // Perform logical (a & !b) on words in common
  996           for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
  997               words[i] &= ~set.words[i];
  998   
  999           recalculateWordsInUse();
 1000           checkInvariants();
 1001       }
 1002   
 1003       /**
 1004        * Returns the hash code value for this bit set. The hash code depends
 1005        * only on which bits are set within this {@code BitSet}.
 1006        *
 1007        * <p>The hash code is defined to be the result of the following
 1008        * calculation:
 1009        *  <pre> {@code
 1010        * public int hashCode() {
 1011        *     long h = 1234;
 1012        *     long[] words = toLongArray();
 1013        *     for (int i = words.length; --i >= 0; )
 1014        *         h ^= words[i] * (i + 1);
 1015        *     return (int)((h >> 32) ^ h);
 1016        * }}</pre>
 1017        * Note that the hash code changes if the set of bits is altered.
 1018        *
 1019        * @return the hash code value for this bit set
 1020        */
 1021       public int hashCode() {
 1022           long h = 1234;
 1023           for (int i = wordsInUse; --i >= 0; )
 1024               h ^= words[i] * (i + 1);
 1025   
 1026           return (int)((h >> 32) ^ h);
 1027       }
 1028   
 1029       /**
 1030        * Returns the number of bits of space actually in use by this
 1031        * {@code BitSet} to represent bit values.
 1032        * The maximum element in the set is the size - 1st element.
 1033        *
 1034        * @return the number of bits currently in this bit set
 1035        */
 1036       public int size() {
 1037           return words.length * BITS_PER_WORD;
 1038       }
 1039   
 1040       /**
 1041        * Compares this object against the specified object.
 1042        * The result is {@code true} if and only if the argument is
 1043        * not {@code null} and is a {@code Bitset} object that has
 1044        * exactly the same set of bits set to {@code true} as this bit
 1045        * set. That is, for every nonnegative {@code int} index {@code k},
 1046        * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
 1047        * must be true. The current sizes of the two bit sets are not compared.
 1048        *
 1049        * @param  obj the object to compare with
 1050        * @return {@code true} if the objects are the same;
 1051        *         {@code false} otherwise
 1052        * @see    #size()
 1053        */
 1054       public boolean equals(Object obj) {
 1055           if (!(obj instanceof BitSet))
 1056               return false;
 1057           if (this == obj)
 1058               return true;
 1059   
 1060           BitSet set = (BitSet) obj;
 1061   
 1062           checkInvariants();
 1063           set.checkInvariants();
 1064   
 1065           if (wordsInUse != set.wordsInUse)
 1066               return false;
 1067   
 1068           // Check words in use by both BitSets
 1069           for (int i = 0; i < wordsInUse; i++)
 1070               if (words[i] != set.words[i])
 1071                   return false;
 1072   
 1073           return true;
 1074       }
 1075   
 1076       /**
 1077        * Cloning this {@code BitSet} produces a new {@code BitSet}
 1078        * that is equal to it.
 1079        * The clone of the bit set is another bit set that has exactly the
 1080        * same bits set to {@code true} as this bit set.
 1081        *
 1082        * @return a clone of this bit set
 1083        * @see    #size()
 1084        */
 1085       public Object clone() {
 1086           if (! sizeIsSticky)
 1087               trimToSize();
 1088   
 1089           try {
 1090               BitSet result = (BitSet) super.clone();
 1091               result.words = words.clone();
 1092               result.checkInvariants();
 1093               return result;
 1094           } catch (CloneNotSupportedException e) {
 1095               throw new InternalError();
 1096           }
 1097       }
 1098   
 1099       /**
 1100        * Attempts to reduce internal storage used for the bits in this bit set.
 1101        * Calling this method may, but is not required to, affect the value
 1102        * returned by a subsequent call to the {@link #size()} method.
 1103        */
 1104       private void trimToSize() {
 1105           if (wordsInUse != words.length) {
 1106               words = Arrays.copyOf(words, wordsInUse);
 1107               checkInvariants();
 1108           }
 1109       }
 1110   
 1111       /**
 1112        * Save the state of the {@code BitSet} instance to a stream (i.e.,
 1113        * serialize it).
 1114        */
 1115       private void writeObject(ObjectOutputStream s)
 1116           throws IOException {
 1117   
 1118           checkInvariants();
 1119   
 1120           if (! sizeIsSticky)
 1121               trimToSize();
 1122   
 1123           ObjectOutputStream.PutField fields = s.putFields();
 1124           fields.put("bits", words);
 1125           s.writeFields();
 1126       }
 1127   
 1128       /**
 1129        * Reconstitute the {@code BitSet} instance from a stream (i.e.,
 1130        * deserialize it).
 1131        */
 1132       private void readObject(ObjectInputStream s)
 1133           throws IOException, ClassNotFoundException {
 1134   
 1135           ObjectInputStream.GetField fields = s.readFields();
 1136           words = (long[]) fields.get("bits", null);
 1137   
 1138           // Assume maximum length then find real length
 1139           // because recalculateWordsInUse assumes maintenance
 1140           // or reduction in logical size
 1141           wordsInUse = words.length;
 1142           recalculateWordsInUse();
 1143           sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
 1144           checkInvariants();
 1145       }
 1146   
 1147       /**
 1148        * Returns a string representation of this bit set. For every index
 1149        * for which this {@code BitSet} contains a bit in the set
 1150        * state, the decimal representation of that index is included in
 1151        * the result. Such indices are listed in order from lowest to
 1152        * highest, separated by ",&nbsp;" (a comma and a space) and
 1153        * surrounded by braces, resulting in the usual mathematical
 1154        * notation for a set of integers.
 1155        *
 1156        * <p>Example:
 1157        * <pre>
 1158        * BitSet drPepper = new BitSet();</pre>
 1159        * Now {@code drPepper.toString()} returns "{@code {}}".<p>
 1160        * <pre>
 1161        * drPepper.set(2);</pre>
 1162        * Now {@code drPepper.toString()} returns "{@code {2}}".<p>
 1163        * <pre>
 1164        * drPepper.set(4);
 1165        * drPepper.set(10);</pre>
 1166        * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
 1167        *
 1168        * @return a string representation of this bit set
 1169        */
 1170       public String toString() {
 1171           checkInvariants();
 1172   
 1173           int numBits = (wordsInUse > 128) ?
 1174               cardinality() : wordsInUse * BITS_PER_WORD;
 1175           StringBuilder b = new StringBuilder(6*numBits + 2);
 1176           b.append('{');
 1177   
 1178           int i = nextSetBit(0);
 1179           if (i != -1) {
 1180               b.append(i);
 1181               for (i = nextSetBit(i+1); i >= 0; i = nextSetBit(i+1)) {
 1182                   int endOfRun = nextClearBit(i);
 1183                   do { b.append(", ").append(i); }
 1184                   while (++i < endOfRun);
 1185               }
 1186           }
 1187   
 1188           b.append('}');
 1189           return b.toString();
 1190       }
 1191   }

Home » openjdk-7 » java » util » [javadoc | source]