/* * @(#)BitSet.java	1.55 03/01/23 * * Copyright 2003 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */package java.util;import java.io.*;/** * This class implements a vector of bits that grows as needed. Each  * component of the bit set has a <code>boolean</code> value. The  * bits of a <code>BitSet</code> are indexed by nonnegative integers.  * Individual indexed bits can be examined, set, or cleared. One  * <code>BitSet</code> may be used to modify the contents of another  * <code>BitSet</code> through logical AND, logical inclusive OR, and  * logical exclusive OR operations. * <p> * By default, all bits in the set initially have the value  * <code>false</code>.  * <p> * Every bit set has a current size, which is the number of bits  * of space currently in use by the bit set. Note that the size is * related to the implementation of a bit set, so it may change with * implementation. The length of a bit set relates to logical length * of a bit set and is defined independently of implementation. * <p> * Unless otherwise noted, passing a null parameter to any of the * methods in a <code>BitSet</code> will result in a * <code>NullPointerException</code>. * * A <code>BitSet</code> is not safe for multithreaded use without * external synchronization. * * @author  Arthur van Hoff * @author  Michael McCloskey * @version 1.55, 01/23/03 * @since   JDK1.0 */public class BitSet implements Cloneable, java.io.Serializable {    /*     * BitSets are packed into arrays of "units."  Currently a unit is a long,     * which consists of 64 bits, requiring 6 address bits.  The choice of unit     * is determined purely by performance concerns.     */    private final static int ADDRESS_BITS_PER_UNIT = 6;    private final static int BITS_PER_UNIT = 1 << ADDRESS_BITS_PER_UNIT;    private final static int BIT_INDEX_MASK = BITS_PER_UNIT - 1;    /* Used to shift left or right for a partial word mask */    private static final long WORD_MASK = 0xffffffffffffffffL;    /**     * The bits in this BitSet.  The ith bit is stored in bits[i/64] at     * bit position i % 64 (where bit position 0 refers to the least     * significant bit and 63 refers to the most significant bit).     * INVARIANT: The words in bits[] above unitInUse-1 are zero.     *     * @serial     */    private long bits[];  // this should be called unit[]    /**     * The number of units in the logical size of this BitSet.     * INVARIANT: unitsInUse is nonnegative.     * INVARIANT: bits[unitsInUse-1] is nonzero unless unitsInUse is zero.     */    private transient int unitsInUse = 0;    /* use serialVersionUID from JDK 1.0.2 for interoperability */    private static final long serialVersionUID = 7997698588986878753L;    /**     * Given a bit index return unit index containing it.     */    private static int unitIndex(int bitIndex) {        return bitIndex >> ADDRESS_BITS_PER_UNIT;    }    /**     * Given a bit index, return a unit that masks that bit in its unit.     */    private static long bit(int bitIndex) {        return 1L << (bitIndex & BIT_INDEX_MASK);    }    /**     * Set the field unitsInUse with the logical size in units of the bit     * set.  WARNING:This function assumes that the number of units actually     * in use is less than or equal to the current value of unitsInUse!     */    private void recalculateUnitsInUse() {        // Traverse the bitset until a used unit is found        int i;        for (i = unitsInUse-1; i >= 0; i--)	    if(bits[i] != 0)		break;        unitsInUse = i+1; // The new logical size    }    /**     * Creates a new bit set. All bits are initially <code>false</code>.     */    public BitSet() {	this(BITS_PER_UNIT);    }    /**     * Creates a bit set whose initial size is large enough to explicitly     * represent bits with indices in the range <code>0</code> through     * <code>nbits-1</code>. All bits are initially <code>false</code>.      *     * @param     nbits   the initial size of the bit set.     * @exception NegativeArraySizeException if the specified initial size     *               is negative.     */    public BitSet(int nbits) {	// nbits can't be negative; size 0 is OK	if (nbits < 0)	    throw new NegativeArraySizeException("nbits < 0: " + nbits);	bits = new long[(unitIndex(nbits-1) + 1)];    }    /**     * Ensures that the BitSet can hold enough units.     * @param	unitsRequired the minimum acceptable number of units.     */    private void ensureCapacity(int unitsRequired) {	if (bits.length < unitsRequired) {	    // Allocate larger of doubled size or required size	    int request = Math.max(2 * bits.length, unitsRequired);	    long newBits[] = new long[request];	    System.arraycopy(bits, 0, newBits, 0, unitsInUse);	    bits = newBits;	}    }    /**     * Sets the bit at the specified index to to the complement of its     * current value.     *      * @param   bitIndex the index of the bit to flip.     * @exception IndexOutOfBoundsException if the specified index is negative.     * @since   1.4     */    public void flip(int bitIndex) {	if (bitIndex < 0)	    throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);        	int unitIndex = unitIndex(bitIndex);        int unitsRequired = unitIndex+1;        if (unitsInUse < unitsRequired) {            ensureCapacity(unitsRequired);            bits[unitIndex] ^= bit(bitIndex);            unitsInUse = unitsRequired;        } else {            bits[unitIndex] ^= bit(bitIndex);            if (bits[unitsInUse-1] == 0)                recalculateUnitsInUse();        }    }    /**     * Sets each bit from the specified fromIndex(inclusive) to the     * specified toIndex(exclusive) to the complement of its current     * value.     *      * @param     fromIndex   index of the first bit to flip.     * @param     toIndex index after the last bit to flip.     * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,     *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is     *            larger than <tt>toIndex</tt>.     * @since   1.4     */    public void flip(int fromIndex, int toIndex) {	if (fromIndex < 0)	    throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);        if (toIndex < 0)	    throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);        if (fromIndex > toIndex)	    throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +                                                " > toIndex: " + toIndex);                // Increase capacity if necessary        int endUnitIndex = unitIndex(toIndex);        int unitsRequired = endUnitIndex + 1;        if (unitsInUse < unitsRequired) {            ensureCapacity(unitsRequired);            unitsInUse = unitsRequired;        }        int startUnitIndex = unitIndex(fromIndex);        long bitMask = 0;        if (startUnitIndex == endUnitIndex) {            // Case 1: One word            bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -                      (1L << (fromIndex & BIT_INDEX_MASK));            bits[startUnitIndex] ^= bitMask;            if (bits[unitsInUse-1] == 0)                recalculateUnitsInUse();            return;        }                // Case 2: Multiple words        // Handle first word        bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);        bits[startUnitIndex] ^= bitMask;        // Handle intermediate words, if any        if (endUnitIndex - startUnitIndex > 1) {            for(int i=startUnitIndex+1; i<endUnitIndex; i++)                bits[i] ^= WORD_MASK;        }        // Handle last word        bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);        bits[endUnitIndex] ^= bitMask;        // Check to see if we reduced size        if (bits[unitsInUse-1] == 0)            recalculateUnitsInUse();    }    /**     * Returns a long that has all bits that are less significant     * than the specified index set to 1. All other bits are 0.     */    private static long bitsRightOf(int x) {        return (x==0 ? 0 : WORD_MASK >>> (64-x));    }    /**     * Returns a long that has all the bits that are more significant     * than or equal to the specified index set to 1. All other bits are 0.     */    private static long bitsLeftOf(int x) {        return WORD_MASK << x;    }    /**     * Sets the bit at the specified index to <code>true</code>.     *     * @param     bitIndex   a bit index.     * @exception IndexOutOfBoundsException if the specified index is negative.     * @since     JDK1.0     */    public void set(int bitIndex) {	if (bitIndex < 0)	    throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);        int unitIndex = unitIndex(bitIndex);        int unitsRequired = unitIndex + 1;        if (unitsInUse < unitsRequired) {            ensureCapacity(unitsRequired);            bits[unitIndex] |= bit(bitIndex);            unitsInUse = unitsRequired;        } else {            bits[unitIndex] |= bit(bitIndex);        }                }    /**     * Sets the bit at the specified index to the specified value.     *     * @param     bitIndex   a bit index.     * @param     value a boolean value to set.     * @exception IndexOutOfBoundsException if the specified index is negative.     * @since     1.4     */    public void set(int bitIndex, boolean value) {        if (value)            set(bitIndex);        else            clear(bitIndex);    }    /**     * Sets the bits from the specified fromIndex(inclusive) to the     * specified toIndex(exclusive) to <code>true</code>.     *     * @param     fromIndex   index of the first bit to be set.     * @param     toIndex index after the last bit to be set.     * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,     *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is     *            larger than <tt>toIndex</tt>.     * @since     1.4     */    public void set(int fromIndex, int toIndex) {	if (fromIndex < 0)	    throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);        if (toIndex < 0)	    throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);        if (fromIndex > toIndex)	    throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +                                                " > toIndex: " + toIndex);        // Increase capacity if necessary        int endUnitIndex = unitIndex(toIndex);        int unitsRequired = endUnitIndex + 1;        if (unitsInUse < unitsRequired) {            ensureCapacity(unitsRequired);            unitsInUse = unitsRequired;        }        int startUnitIndex = unitIndex(fromIndex);        long bitMask = 0;        if (startUnitIndex == endUnitIndex) {            // Case 1: One word            bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -                      (1L << (fromIndex & BIT_INDEX_MASK));            bits[startUnitIndex] |= bitMask;            return;        }                // Case 2: Multiple words        // Handle first word        bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);        bits[startUnitIndex] |= bitMask;        // Handle intermediate words, if any        if (endUnitIndex - startUnitIndex > 1) {            for(int i=startUnitIndex+1; i<endUnitIndex; i++)                bits[i] |= WORD_MASK;        }        // Handle last word        bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);        bits[endUnitIndex] |= bitMask;    }    /**     * Sets the bits from the specified fromIndex(inclusive) to the     * specified toIndex(exclusive) to the specified value.     *     * @param     fromIndex   index of the first bit to be set.     * @param     toIndex index after the last bit to be set     * @param     value value to set the selected bits to     * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,     *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is     *            larger than <tt>toIndex</tt>.     * @since     1.4