bitset.java

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

package open_cmpp.util;

import java.io.IOException;

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 unitsInUse-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 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
	 */
	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;