bitset.java

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

	 * 
	 * @param set
	 *            <code>BitSet</code> to intersect with
	 * @return boolean indicating whether this <code>BitSet</code> intersects
	 *         the specified <code>BitSet</code>.
	 * @since 1.4
	 */
	public boolean intersects(BitSet set) {
		for (int i = Math.min(unitsInUse, set.unitsInUse) - 1; i >= 0; i--)
			if ((bits[i] & set.bits[i]) != 0)
				return true;
		return false;
	}

	/**
	 * Returns the number of bits set to <tt>true</tt> in this
	 * <code>BitSet</code>.
	 * 
	 * @return the number of bits set to <tt>true</tt> in this
	 *         <code>BitSet</code>.
	 * @since 1.4
	 */
	public int cardinality() {
		int sum = 0;
		for (int i = 0; i < unitsInUse; i++)
			sum += bitCount(bits[i]);
		return sum;
	}

	/**
	 * Returns the number of bits set in val. For a derivation of this
	 * algorithm, see "Algorithms and data structures with applications to
	 * graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs, Prentice
	 * Hall, 1993.
	 */
	private static int bitCount(long val) {
		val -= (val & 0xaaaaaaaaaaaaaaaaL) >>> 1;
		val = (val & 0x3333333333333333L) + ((val >>> 2) & 0x3333333333333333L);
		val = (val + (val >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
		val += val >>> 8;
		val += val >>> 16;
		return ((int) (val) + (int) (val >>> 32)) & 0xff;
	}

	/**
	 * Performs a logical <b>AND</b> of this target bit set with the argument
	 * bit set. This bit set is modified so that each bit in it has the value
	 * <code>true</code> if and only if it both initially had the value
	 * <code>true</code> and the corresponding bit in the bit set argument
	 * also had the value <code>true</code>.
	 * 
	 * @param set
	 *            a bit set.
	 */
	public void and(BitSet set) {
		if (this == set)
			return;

		// Perform logical AND on bits in common
		int oldUnitsInUse = unitsInUse;
		unitsInUse = Math.min(unitsInUse, set.unitsInUse);
		int i;
		for (i = 0; i < unitsInUse; i++)
			bits[i] &= set.bits[i];

		// Clear out units no longer used
		for (; i < oldUnitsInUse; i++)
			bits[i] = 0;

		// Recalculate units in use if necessary
		if (unitsInUse > 0 && bits[unitsInUse - 1] == 0)
			recalculateUnitsInUse();
	}

	/**
	 * Performs a logical <b>OR</b> of this bit set with the bit set argument.
	 * This bit set is modified so that a bit in it has the value
	 * <code>true</code> if and only if it either already had the value
	 * <code>true</code> or the corresponding bit in the bit set argument has
	 * the value <code>true</code>.
	 * 
	 * @param set
	 *            a bit set.
	 */
	public void or(BitSet set) {
		if (this == set)
			return;

		ensureCapacity(set.unitsInUse);

		// Perform logical OR on bits in common
		int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);
		int i;
		for (i = 0; i < unitsInCommon; i++)
			bits[i] |= set.bits[i];

		// Copy any remaining bits
		for (; i < set.unitsInUse; i++)
			bits[i] = set.bits[i];

		if (unitsInUse < set.unitsInUse)
			unitsInUse = set.unitsInUse;
	}

	/**
	 * Performs a logical <b>XOR</b> of this bit set with the bit set argument.
	 * This bit set is modified so that a bit in it has the value
	 * <code>true</code> if and only if one of the following statements holds:
	 * <ul>
	 * <li>The bit initially has the value <code>true</code>, and the
	 * corresponding bit in the argument has the value <code>false</code>.
	 * <li>The bit initially has the value <code>false</code>, and the
	 * corresponding bit in the argument has the value <code>true</code>.
	 * </ul>
	 * 
	 * @param set
	 *            a bit set.
	 */
	public void xor(BitSet set) {
		int unitsInCommon;

		if (unitsInUse >= set.unitsInUse) {
			unitsInCommon = set.unitsInUse;
		} else {
			unitsInCommon = unitsInUse;
			int newUnitsInUse = set.unitsInUse;
			ensureCapacity(newUnitsInUse);
			unitsInUse = newUnitsInUse;
		}

		// Perform logical XOR on bits in common
		int i;
		for (i = 0; i < unitsInCommon; i++)
			bits[i] ^= set.bits[i];

		// Copy any remaining bits
		for (; i < set.unitsInUse; i++)
			bits[i] = set.bits[i];

		recalculateUnitsInUse();
	}

	/**
	 * Clears all of the bits in this <code>BitSet</code> whose corresponding
	 * bit is set in the specified <code>BitSet</code>.
	 * 
	 * @param set
	 *            the <code>BitSet</code> with which to mask this
	 *            <code>BitSet</code>.
	 * @since JDK1.2
	 */
	public void andNot(BitSet set) {
		int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);

		// Perform logical (a & !b) on bits in common
		for (int i = 0; i < unitsInCommon; i++) {
			bits[i] &= ~set.bits[i];
		}

		recalculateUnitsInUse();
	}

	/**
	 * Returns a hash code value for this bit set. The has code depends only on
	 * which bits have been set within this <code>BitSet</code>. The
	 * algorithm used to compute it may be described as follows.
	 * <p>
	 * Suppose the bits in the <code>BitSet</code> were to be stored in an
	 * array of <code>long</code> integers called, say, <code>bits</code>,
	 * in such a manner that bit <code>k</code> is set in the
	 * <code>BitSet</code> (for nonnegative values of <code>k</code>) if
	 * and only if the expression
	 * 
	 * <pre>
	 * ((k &gt;&gt; 6) &lt; bits.length) &amp;&amp; ((bits[k &gt;&gt; 6] &amp; (1L &lt;&lt; (bit &amp; 0x3F))) != 0)
	 * </pre>
	 * 
	 * is true. Then the following definition of the <code>hashCode</code>
	 * method would be a correct implementation of the actual algorithm:
	 * 
	 * <pre>
	 * public int hashCode() {
	 * 	long h = 1234;
	 * 	for (int i = bits.length; --i &gt;= 0;) {
	 * 		h &circ;= bits[i] * (i + 1);
	 * 	}
	 * 	return (int) ((h &gt;&gt; 32) &circ; h);
	 * }
	 * </pre>
	 * 
	 * Note that the hash code values change if the set of bits is altered.
	 * <p>
	 * Overrides the <code>hashCode</code> method of <code>Object</code>.
	 * 
	 * @return a hash code value for this bit set.
	 */
	public int hashCode() {
		long h = 1234;
		for (int i = bits.length; --i >= 0;)
			h ^= bits[i] * (i + 1);

		return (int) ((h >> 32) ^ h);
	}

	/**
	 * Returns the number of bits of space actually in use by this
	 * <code>BitSet</code> to represent bit values. The maximum element in the
	 * set is the size - 1st element.
	 * 
	 * @return the number of bits currently in this bit set.
	 */
	public int size() {
		return bits.length << ADDRESS_BITS_PER_UNIT;
	}

	/**
	 * Compares this object against the specified object. The result is
	 * <code>true</code> if and only if the argument is not <code>null</code>
	 * and is a <code>Bitset</code> object that has exactly the same set of
	 * bits set to <code>true</code> as this bit set. That is, for every
	 * nonnegative <code>int</code> index <code>k</code>,
	 * 
	 * <pre>
	 * ((BitSet) obj).get(k) == this.get(k)
	 * </pre>
	 * 
	 * must be true. The current sizes of the two bit sets are not compared.
	 * <p>
	 * Overrides the <code>equals</code> method of <code>Object</code>.
	 * 
	 * @param obj
	 *            the object to compare with.
	 * @return <code>true</code> if the objects are the same;
	 *         <code>false</code> otherwise.
	 * @see java.util.BitSet#size()
	 */
	public boolean equals(Object obj) {
		if (!(obj instanceof BitSet))
			return false;
		if (this == obj)
			return true;

		BitSet set = (BitSet) obj;
		int minUnitsInUse = Math.min(unitsInUse, set.unitsInUse);

		// Check units in use by both BitSets
		for (int i = 0; i < minUnitsInUse; i++)
			if (bits[i] != set.bits[i])
				return false;

		// Check any units in use by only one BitSet (must be 0 in other)
		if (unitsInUse > minUnitsInUse) {
			for (int i = minUnitsInUse; i < unitsInUse; i++)
				if (bits[i] != 0)
					return false;
		} else {
			for (int i = minUnitsInUse; i < set.unitsInUse; i++)
				if (set.bits[i] != 0)
					return false;
		}

		return true;
	}

	/**
	 * Cloning this <code>BitSet</code> produces a new <code>BitSet</code>
	 * that is equal to it. The clone of the bit set is another bit set that has
	 * exactly the same bits set to <code>true</code> as this bit set and the
	 * same current size.
	 * <p>
	 * Overrides the <code>clone</code> method of <code>Object</code>.
	 * 
	 * @return a clone of this bit set.
	 * @see java.util.BitSet#size()
	 */
	public Object clone() {
		BitSet result = null;
		try {
			result = (BitSet) super.clone();
		} catch (CloneNotSupportedException e) {
			throw new InternalError();
		}
		result.bits = new long[bits.length];
		System.arraycopy(bits, 0, result.bits, 0, unitsInUse);
		return result;
	}

	/**
	 * This override of readObject makes sure unitsInUse is set properly when
	 * deserializing a bitset
	 * 
	 */
	private void readObject(java.io.ObjectInputStream in) throws IOException,
			ClassNotFoundException {

		in.defaultReadObject();
		// Assume maximum length then find real length
		// because recalculateUnitsInUse assumes maintenance
		// or reduction in logical size
		unitsInUse = bits.length;
		recalculateUnitsInUse();
	}

	/**
	 * Returns a string representation of this bit set. For every index for
	 * which this <code>BitSet</code> contains a bit in the set state, the
	 * decimal representation of that index is included in the result. Such
	 * indices are listed in order from lowest to highest, separated by
	 * ",&nbsp;" (a comma and a space) and surrounded by braces, resulting in
	 * the usual mathematical notation for a set of integers.
	 * <p>
	 * Overrides the <code>toString</code> method of <code>Object</code>.
	 * <p>
	 * Example:
	 * 
	 * <pre>
	 * BitSet drPepper = new BitSet();
	 * </pre>
	 * 
	 * Now <code>drPepper.toString()</code> returns "<code>{}</code>".
	 * <p>
	 * 
	 * <pre>
	 * drPepper.set(2);
	 * </pre>
	 * 
	 * Now <code>drPepper.toString()</code> returns "<code>{2}</code>".
	 * <p>
	 * 
	 * <pre>
	 * drPepper.set(4);
	 * drPepper.set(10);
	 * </pre>
	 * 
	 * Now <code>drPepper.toString()</code> returns "<code>{2, 4, 10}</code>".
	 * 
	 * @return a string representation of this bit set.
	 */
	public String toString() {
		int numBits = unitsInUse << ADDRESS_BITS_PER_UNIT;
		StringBuffer buffer = new StringBuffer(8 * numBits + 2);
		String separator = "";
		buffer.append('{');

		for (int i = 0; i < numBits; i++) {
			if (get(i)) {
				buffer.append(separator);
				separator = ", ";
				buffer.append(i);
			}
		}

		buffer.append('}');
		return buffer.toString();
	}
}