bitset.java

华为模拟网关源码 华为模拟网关源码 华为模拟网关源码

		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
	 * representation 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))
						: (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21)
								: (w < 1 << 22 ? 22 : 23)))
						: (w < 1 << 27 ? (w < 1 << 25 ? (w < 1 << 24 ? 24 : 25)
								: (w < 1 << 26 ? 26 : 27))
								: (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29)
										: (w < 1 << 30 ? 30 : 31)))));
	}

	/**
	 * Returns true if this <code>BitSet</code> contains no bits that are set
	 * to <code>true</code>.
	 * 
	 * @return boolean indicating whether this <code>BitSet</code> is empty.
	 * @since 1.4
	 */
	public boolean isEmpty() {
		return (unitsInUse == 0);
	}

	/**
	 * Returns true if the specified <code>BitSet</code> has any bits set to
	 * <code>true</code> that are also set to <code>true</code> in this
	 * <code>BitSet</code>.