bitset.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 700 行 · 第 1/2 页

		int lo_offset = from >>> 6;
		if (lo_offset >= bits.length)
			return bs;

		int lo_bit = from & LONG_MASK;
		int hi_offset = to >>> 6;
		if (lo_bit == 0) {
			int len =
				Math.min(hi_offset - lo_offset + 1, bits.length - lo_offset);
			System.arraycopy(bits, lo_offset, bs.bits, 0, len);
			if (hi_offset < bits.length)
				bs.bits[hi_offset - lo_offset] &= (1L << to) - 1;
			return bs;
		}

		int len = Math.min(hi_offset, bits.length - 1);
		int reverse = ~lo_bit;
		int i;
		for (i = 0; lo_offset < len; lo_offset++, i++)
			bs.bits[i] =
				((bits[lo_offset] >>> lo_bit)
					| (bits[lo_offset + 1] << reverse));
		if ((to & LONG_MASK) > lo_bit)
			bs.bits[i++] = bits[lo_offset] >>> lo_bit;
		if (hi_offset < bits.length)
			bs.bits[i - 1] &= (1L << (to - from)) - 1;
		return bs;
	}

	/**
	 * Returns a hash code value for this bit set.  The hash code of
	 * two bit sets containing the same integers is identical.  The algorithm
	 * used to compute it is as follows:
	 *
	 * Suppose the bits in the BitSet were to be stored in an array of
	 * long integers called <code>bits</code>, in such a manner that
	 * bit <code>k</code> is set in the BitSet (for non-negative values
	 * of <code>k</code>) if and only if
	 *
	 * <code>((k/64) &lt; bits.length)
	 * && ((bits[k/64] & (1L &lt;&lt; (bit % 64))) != 0)
	 * </code>
	 *
	 * Then the following definition of the hashCode method
	 * would be a correct implementation of the actual algorithm:
	 *
	 * 
	<pre>public int hashCode()
	{
	long h = 1234;
	for (int i = bits.length-1; i &gt;= 0; i--)
	{
		h ^= bits[i] * (i + 1);
	}
	
	return (int)((h >> 32) ^ h);
	}</pre>
	 *
	 * Note that the hash code values changes, if the set is changed.
	 *
	 * @return the hash code value for this bit set.
	 */
	public int hashCode() {
		long h = 1234;
		for (int i = bits.length; i > 0;)
			h ^= i * bits[--i];
		return (int) ((h >> 32) ^ h);
	}

	/**
	 * Returns true if the specified BitSet and this one share at least one
	 * common true bit.
	 *
	 * @param set the set to check for intersection
	 * @return true if the sets intersect
	 * @throws NullPointerException if set is null
	 * @since 1.4
	 */
	public boolean intersects(BitSet set) {
		int i = Math.min(bits.length, set.bits.length);
		while (--i >= 0)
			if ((bits[i] & set.bits[i]) != 0)
				return true;
		return false;
	}

	/**
	 * Returns true if this set contains no true bits.
	 *
	 * @return true if all bits are false
	 * @since 1.4
	 */
	public boolean isEmpty() {
		for (int i = bits.length - 1; i >= 0; i--)
			if (bits[i] != 0)
				return false;
		return true;
	}

	/**
	 * Returns the logical number of bits actually used by this bit
	 * set.  It returns the index of the highest set bit plus one.
	 * Note that this method doesn't return the number of set bits.
	 *
	 * @return the index of the highest set bit plus one.
	 */
	public int length() {
		// Set i to highest index that contains a non-zero value.
		int i;
		for (i = bits.length - 1; i >= 0 && bits[i] == 0; --i);

		// if i < 0 all bits are cleared.
		if (i < 0)
			return 0;

		// Now determine the exact length.
		long b = bits[i];
		int len = (i + 1) * 64;
		// b >= 0 checks if the highest bit is zero.
		while (b >= 0) {
			--len;
			b <<= 1;
		}

		return len;
	}

	/**
	 * Returns the index of the next false bit, from the specified bit
	 * (inclusive).
	 *
	 * @param from the start location
	 * @return the first false bit
	 * @throws IndexOutOfBoundsException if from is negative
	 * @since 1.4
	 */
	public int nextClearBit(int from) {
		int offset = from >> 6;
		long mask = 1L << from;
		while (offset < bits.length) {
			// ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
			// so we'll just let that be our exception.
			long h = bits[offset];
			do {
				if ((h & mask) == 0)
					return from;
				mask <<= 1;
				from++;
			} while (mask != 0);
			mask = 1;
			offset++;
		}
		return from;
	}

	/**
	 * Returns the index of the next true bit, from the specified bit
	 * (inclusive). If there is none, -1 is returned. You can iterate over
	 * all true bits with this loop:<br>
	 * 
	<pre>for (int i = bs.nextSetBit(0); i &gt;= 0; i = bs.nextSetBit(i + 1))
	{
	// operate on i here
	}</pre>
	 *
	 * @param from the start location
	 * @return the first true bit, or -1
	 * @throws IndexOutOfBoundsException if from is negative
	 * @since 1.4
	 */
	public int nextSetBit(int from) {
		int offset = from >> 6;
		long mask = 1L << from;
		while (offset < bits.length) {
			// ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
			// so we'll just let that be our exception.
			long h = bits[offset];
			do {
				if ((h & mask) != 0)
					return from;
				mask <<= 1;
				from++;
			} while (mask != 0);
			mask = 1;
			offset++;
		}
		return -1;
	}

	/**
	 * Performs the logical OR operation on this bit set and the
	 * given <code>set</code>.  This means it builds the union
	 * of the two sets.  The result is stored into this bit set, which
	 * grows as necessary.
	 *
	 * @param bs the second bit set
	 * @throws NullPointerException if bs is null
	 */
	public void or(BitSet bs) {
		ensure(bs.bits.length - 1);
		for (int i = bs.bits.length - 1; i >= 0; i--)
			bits[i] |= bs.bits[i];
	}

	/**
	 * Add the integer <code>bitIndex</code> to this set.  That is
	 * the corresponding bit is set to true.  If the index was already in
	 * the set, this method does nothing.  The size of this structure
	 * is automatically increased as necessary.
	 *
	 * @param pos a non-negative integer.
	 * @throws IndexOutOfBoundsException if pos is negative
	 */
	public void set(int pos) {
		int offset = pos >> 6;
		ensure(offset);
		// ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
		// so we'll just let that be our exception.
		bits[offset] |= 1L << pos;
	}

	/**
	 * Sets the bit at the given index to the specified value. The size of
	 * this structure is automatically increased as necessary.
	 *
	 * @param index the position to set
	 * @param value the value to set it to
	 * @throws IndexOutOfBoundsException if index is negative
	 * @since 1.4
	 */
	public void set(int index, boolean value) {
		if (value)
			set(index);
		else
			clear(index);
	}

	/**
	 * Sets the bits between from (inclusive) and to (exclusive) to true.
	 *
	 * @param from the start range (inclusive)
	 * @param to the end range (exclusive)
	 * @throws IndexOutOfBoundsException if from &lt; 0 || from &gt; to
	 * @since 1.4
	 */
	public void set(int from, int to) {
		if (from < 0 || from > to)
			throw new IndexOutOfBoundsException();
		if (from == to)
			return;
		int lo_offset = from >>> 6;
		int hi_offset = to >>> 6;
		ensure(hi_offset);
		if (lo_offset == hi_offset) {
			bits[hi_offset] |= (-1L << from) & ((1L << to) - 1);
			return;
		}

		bits[lo_offset] |= -1L << from;
		bits[hi_offset] |= (1L << to) - 1;
		for (int i = lo_offset + 1; i < hi_offset; i++)
			bits[i] = -1;
	}

	/**
	 * Sets the bits between from (inclusive) and to (exclusive) to the
	 * specified value.
	 *
	 * @param from the start range (inclusive)
	 * @param to the end range (exclusive)
	 * @param value the value to set it to
	 * @throws IndexOutOfBoundsException if from &lt; 0 || from &gt; to
	 * @since 1.4
	 */
	public void set(int from, int to, boolean value) {
		if (value)
			set(from, to);
		else
			clear(from, to);
	}

	/**
	 * Returns the number of bits actually used by this bit set.  Note
	 * that this method doesn't return the number of set bits, and that
	 * future requests for larger bits will make this automatically grow.
	 *
	 * @return the number of bits currently used.
	 */
	public int size() {
		return bits.length * 64;
	}

	/**
	 * Returns the string representation of this bit set.  This
	 * consists of a comma separated list of the integers in this set
	 * surrounded by curly braces.  There is a space after each comma.
	 * A sample string is thus "{1, 3, 53}".
	 * @return the string representation.
	 */
	public String toString() {
		StringBuffer r = new StringBuffer("{");
		boolean first = true;
		for (int i = 0; i < bits.length; ++i) {
			long bit = 1;
			long word = bits[i];
			if (word == 0)
				continue;
			for (int j = 0; j < 64; ++j) {
				if ((word & bit) != 0) {
					if (!first)
						r.append(", ");
					r.append(64 * i + j);
					first = false;
				}
				bit <<= 1;
			}
		}
		return r.append("}").toString();
	}

	/**
	 * Performs the logical XOR operation on this bit set and the
	 * given <code>set</code>.  This means it builds the symmetric
	 * remainder of the two sets (the elements that are in one set,
	 * but not in the other).  The result is stored into this bit set,
	 * which grows as necessary.
	 *
	 * @param bs the second bit set
	 * @throws NullPointerException if bs is null
	 */
	public void xor(BitSet bs) {
		ensure(bs.bits.length - 1);
		for (int i = bs.bits.length - 1; i >= 0; i--)
			bits[i] ^= bs.bits[i];
	}

	/**
	 * Make sure the vector is big enough.
	 *
	 * @param lastElt the size needed for the bits array
	 */
	private final void ensure(int lastElt) {
		if (lastElt >= bits.length) {
			long[] nd = new long[lastElt + 1];
			System.arraycopy(bits, 0, nd, 0, bits.length);
			bits = nd;
		}
	}
}