bitset.java

java源代码 请看看啊 提点宝贵的意见

     */
    public void set(int fromIndex, int toIndex, boolean value) {
	if (value)
            set(fromIndex, toIndex);
        else
            clear(fromIndex, toIndex);
    }

    /**
     * Sets the bit specified by the index to <code>false</code>.
     *
     * @param     bitIndex   the index of the bit to be cleared.
     * @exception IndexOutOfBoundsException if the specified index is negative.
     * @since     JDK1.0
     */
    public void clear(int bitIndex) {
	if (bitIndex < 0)
	    throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

	int unitIndex = unitIndex(bitIndex);
	if (unitIndex >= unitsInUse)
	    return;

	bits[unitIndex] &= ~bit(bitIndex);
        if (bits[unitsInUse-1] == 0)
            recalculateUnitsInUse();
    }

    /**
     * Sets the bits from the specified fromIndex(inclusive) to the
     * specified toIndex(exclusive) to <code>false</code>.
     *
     * @param     fromIndex   index of the first bit to be cleared.
     * @param     toIndex index after the last bit to be cleared. 
     * @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 clear(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);

        int startUnitIndex = unitIndex(fromIndex);
	if (startUnitIndex >= unitsInUse)
	    return;
        int endUnitIndex = unitIndex(toIndex);

        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++) {
                if (i < unitsInUse)
                    bits[i] = 0;
            }
        }

        // Handle last word
        if (endUnitIndex < unitsInUse) {
            bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
            bits[endUnitIndex] &= ~bitMask;
        }

        if (bits[unitsInUse-1] == 0)
            recalculateUnitsInUse();
    }

    /**
     * Sets all of the bits in this BitSet to <code>false</code>.
     *
     * @since   1.4
     */
    public void clear() {
        while (unitsInUse > 0)
            bits[--unitsInUse] = 0;
    }

    /**
     * Returns the value of the bit with the specified index. The value 
     * is <code>true</code> if the bit with the index <code>bitIndex</code> 
     * is currently set in this <code>BitSet</code>; otherwise, the result 
     * is <code>false</code>.
     *
     * @param     bitIndex   the bit index.
     * @return    the value of the bit with the specified index.
     * @exception IndexOutOfBoundsException if the specified index is negative.
     */
    public boolean get(int bitIndex) {
	if (bitIndex < 0)
	    throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

	boolean result = false;
	int unitIndex = unitIndex(bitIndex);
	if (unitIndex < unitsInUse)
	    result = ((bits[unitIndex] & bit(bitIndex)) != 0);

	return result;
    }

    /**
     * Returns a new <tt>BitSet</tt> composed of bits from this <tt>BitSet</tt>
     * from <tt>fromIndex</tt>(inclusive) to <tt>toIndex</tt>(exclusive).
     *
     * @param     fromIndex   index of the first bit to include.
     * @param     toIndex     index after the last bit to include.
     * @return    a new <tt>BitSet</tt> from a range of this <tt>BitSet</tt>.
     * @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 BitSet get(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);

        // If no set bits in range return empty bitset
        if (length() <= fromIndex || fromIndex == toIndex)
            return new BitSet(0);

        // An optimization
        if (length() < toIndex)
            toIndex = length();

        BitSet result = new BitSet(toIndex - fromIndex);
        int startBitIndex = fromIndex & BIT_INDEX_MASK;
        int endBitIndex = toIndex & BIT_INDEX_MASK;
        int targetWords = (toIndex - fromIndex + 63)/64;
        int sourceWords = unitIndex(toIndex) - unitIndex(fromIndex) + 1;
        int inverseIndex = 64 - startBitIndex;
        int targetIndex = 0;
        int sourceIndex = unitIndex(fromIndex);

        // Process all words but the last word
        while (targetIndex < targetWords - 1)
            result.bits[targetIndex++] =
               (bits[sourceIndex++] >>> startBitIndex) |
               ((inverseIndex==64) ? 0 : bits[sourceIndex] << inverseIndex);

        // Process the last word
        result.bits[targetIndex] = (sourceWords == targetWords ?
           (bits[sourceIndex] & bitsRightOf(endBitIndex)) >>> startBitIndex :
           (bits[sourceIndex++] >>> startBitIndex) | ((inverseIndex==64) ? 0 :
           (getBits(sourceIndex) & bitsRightOf(endBitIndex)) << inverseIndex));

        // Set unitsInUse correctly
        result.unitsInUse = targetWords;
        result.recalculateUnitsInUse();
	return result;
    }

    /**
     * Returns the unit of this bitset at index j as if this bitset had an
     * infinite amount of storage.
     */
    private long getBits(int j) {
        return (j < unitsInUse) ? bits[j] : 0;
    }

    /**
     * Returns the index of the first bit that is set to <code>true</code>
     * that occurs on or after the specified starting index. If no such
     * bit exists then -1 is returned.
     *
     * To iterate over the <code>true</code> bits in a <code>BitSet</code>,
     * use the following loop:
     *
     * for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) {
     *     // operate on index i here
     * }
     * 
     * @param   fromIndex the index to start checking from (inclusive).
     * @return  the index of the next set bit.
     * @throws  IndexOutOfBoundsException if the specified index is negative.
     * @since   1.4
     */
    public int nextSetBit(int fromIndex) {
	if (fromIndex < 0)
	    throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
        int u = unitIndex(fromIndex);
        if (u >= unitsInUse)
            return -1;
        int testIndex = (fromIndex & BIT_INDEX_MASK);
        long unit = bits[u] >> testIndex;

        if (unit == 0)
            testIndex = 0;

        while((unit==0) && (u < unitsInUse-1))
            unit = bits[++u];

        if (unit == 0)
            return -1;

        testIndex  += trailingZeroCnt(unit);
        return ((u * BITS_PER_UNIT) + testIndex);
    }

    private static int trailingZeroCnt(long val) {
        // Loop unrolled for performance
        int byteVal = (int)val & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal];

        byteVal = (int)(val >>> 8) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 8;

        byteVal = (int)(val >>> 16) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 16;

        byteVal = (int)(val >>> 24) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 24;

        byteVal = (int)(val >>> 32) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 32;

        byteVal = (int)(val >>> 40) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 40;

        byteVal = (int)(val >>> 48) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 48;

        byteVal = (int)(val >>> 56) & 0xff;
        return trailingZeroTable[byteVal] + 56;
    }

    /*
     * trailingZeroTable[i] is the number of trailing zero bits in the binary
     * representaion of i.
     */
    private final static byte trailingZeroTable[] = {
      -25, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};

    /**
     * Returns the index of the first bit that is set to <code>false</code>
     * that occurs on or after the specified starting index.
     * 
     * @param   fromIndex the index to start checking from (inclusive).
     * @return  the index of the next clear bit.
     * @throws  IndexOutOfBoundsException if the specified index is negative.
     * @since   1.4
     */
    public int nextClearBit(int fromIndex) {
	if (fromIndex < 0)
	    throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

        int u = unitIndex(fromIndex);
        if (u >= unitsInUse)
            return fromIndex;
        int testIndex = (fromIndex & BIT_INDEX_MASK);
        long unit = bits[u] >> testIndex;

        if (unit == (WORD_MASK >> testIndex))
            testIndex = 0;

        while((unit==WORD_MASK) && (u < unitsInUse-1))
            unit = bits[++u];

        if (unit == WORD_MASK)
            return length();
        
        if (unit == 0)
            return u * BITS_PER_UNIT + testIndex;

        testIndex += trailingZeroCnt(~unit);
        return ((u * BITS_PER_UNIT) + testIndex);
    }

    /**
     * Returns the "logical size" of this <code>BitSet</code>: the index of
     * the highest set bit in the <code>BitSet</code> plus one. Returns zero
     * if the <code>BitSet</code> contains no set bits.
     *
     * @return  the logical size of this <code>BitSet</code>.
     * @since   1.2
     */
    public int length() {
        if (unitsInUse == 0)
            return 0;

	long highestUnit = bits[unitsInUse - 1];
	int highPart = (int)(highestUnit >>> 32);
        return 64 * (unitsInUse - 1) +
               (highPart == 0 ? bitLen((int)highestUnit)
                              : 32 + bitLen((int)highPart));
    }

    /**
     * bitLen(val) is the number of bits in val.
     */
    private static int bitLen(int w) {
        // Binary search - decision tree (5 tests, rarely 6)
        return
         (w < 1<<15 ?
          (w < 1<<7 ?
           (w < 1<<3 ?
            (w < 1<<1 ? (w < 1<<0 ? (w<0 ? 32 : 0) : 1) : (w < 1<<2 ? 2 : 3)) :
            (w < 1<<5 ? (w < 1<<4 ? 4 : 5) : (w < 1<<6 ? 6 : 7))) :
           (w < 1<<11 ?
            (w < 1<<9 ? (w < 1<<8 ? 8 : 9) : (w < 1<<10 ? 10 : 11)) :
            (w < 1<<13 ? (w < 1<<12 ? 12 : 13) : (w < 1<<14 ? 14 : 15)))) :
          (w < 1<<23 ?
           (w < 1<<19 ?
            (w < 1<<17 ? (w < 1<<16 ? 16 : 17) : (w < 1<<18 ? 18 : 19)) :