/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package java.util;
import java.io.Serializable;
import org.apache.harmony.luni.util.Msg;
/**
* The {@code BitSet} class implements a bit field. Each element in a
* {@code BitSet} can be on(1) or off(0). A {@code BitSet} is created with a
* given size and grows if this size is exceeded. Growth is always rounded to a
* 64 bit boundary.
*
* @since Android 1.0
*/
public class BitSet implements Serializable, Cloneable {
private static final long serialVersionUID = 7997698588986878753L;
// Size in bits of the data type being used in the bits array
private static final int ELM_SIZE = 64;
private long[] bits;
/**
* Create a new {@code BitSet} with size equal to 64 bits.
*
* @see #clear(int)
* @see #set(int)
* @see #clear()
* @see #clear(int, int)
* @see #set(int, boolean)
* @see #set(int, int)
* @see #set(int, int, boolean)
* @since Android 1.0
*/
public BitSet() {
this(64);
}
/**
* Create a new {@code BitSet} with size equal to nbits. If nbits is not a
* multiple of 64, then create a {@code BitSet} with size nbits rounded to
* the next closest multiple of 64.
*
* @param nbits
* the size of the bit set.
* @throws NegativeArraySizeException
* if {@code nbits} is negative.
* @see #clear(int)
* @see #set(int)
* @see #clear()
* @see #clear(int, int)
* @see #set(int, boolean)
* @see #set(int, int)
* @see #set(int, int, boolean)
* @since Android 1.0
*/
public BitSet(int nbits) {
if (nbits >= 0) {
bits = new long[(nbits / ELM_SIZE) + (nbits % ELM_SIZE > 0 ? 1 : 0)];
} else {
throw new NegativeArraySizeException();
}
}
/**
* Private constructor called from get(int, int) method
*
* @param bits
* the size of the bit set
*/
private BitSet(long[] bits) {
this.bits = bits;
}
/**
* Creates a copy of this {@code BitSet}.
*
* @return a copy of this {@code BitSet}.
* @since Android 1.0
*/
@Override
public Object clone() {
try {
BitSet clone = (BitSet) super.clone();
clone.bits = bits.clone();
return clone;
} catch (CloneNotSupportedException e) {
return null;
}
}
/**
* Compares the argument to this {@code BitSet} and returns whether they are
* equal. The object must be an instance of {@code BitSet} with the same
* bits set.
*
* @param obj
* the {@code BitSet} object to compare.
* @return a {@code boolean} indicating whether or not this {@code BitSet} and
* {@code obj} are equal.
* @see #hashCode
* @since Android 1.0
*/
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj instanceof BitSet) {
long[] bsBits = ((BitSet) obj).bits;
int length1 = bits.length, length2 = bsBits.length;
// If one of the BitSets is larger than the other, check to see if
// any of
// its extra bits are set. If so return false.
if (length1 <= length2) {
for (int i = 0; i < length1; i++) {
if (bits[i] != bsBits[i]) {
return false;
}
}
for (int i = length1; i < length2; i++) {
if (bsBits[i] != 0) {
return false;
}
}
} else {
for (int i = 0; i < length2; i++) {
if (bits[i] != bsBits[i]) {
return false;
}
}
for (int i = length2; i < length1; i++) {
if (bits[i] != 0) {
return false;
}
}
}
return true;
}
return false;
}
/**
* Increase the size of the internal array to accommodate {@code pos} bits.
* The new array max index will be a multiple of 64.
*
* @param pos
* the index the new array needs to be able to access.
* @since Android 1.0
*/
private void growBits(int pos) {
pos++; // Inc to get correct bit count
long[] tempBits = new long[(pos / ELM_SIZE)
+ (pos % ELM_SIZE > 0 ? 1 : 0)];
System.arraycopy(bits, 0, tempBits, 0, bits.length);
bits = tempBits;
}
/**
* Computes the hash code for this {@code BitSet}. If two {@code BitSet}s are equal
* the have to return the same result for {@code hashCode()}.
*
* @return the {@code int} representing the hash code for this bit
* set.
* @see #equals
* @see java.util.Hashtable
* @since Android 1.0
*/
@Override
public int hashCode() {
long x = 1234;
// for (int i = 0, length = bits.length; i < length; i+=2)
// x ^= (bits[i] + ((long)bits[i+1] << 32)) * (i/2 + 1);
for (int i = 0, length = bits.length; i < length; i++) {
x ^= bits[i] * (i + 1);
}
return (int) ((x >> 32) ^ x);
}
/**
* Retrieves the bit at index {@code pos}. Grows the {@code BitSet} if
* {@code pos > size}.
*
* @param pos
* the index of the bit to be retrieved.
* @return {@code true} if the bit at {@code pos} is set,
* {@code false} otherwise.
* @throws IndexOutOfBoundsException
* if {@code pos} is negative.
* @see #clear(int)
* @see #set(int)
* @see #clear()
* @see #clear(int, int)
* @see #set(int, boolean)
* @see #set(int, int)
* @see #set(int, int, boolean)
* @since Android 1.0
*/
public boolean get(int pos) {
if (pos >= 0) {
if (pos < bits.length * ELM_SIZE) {
return (bits[pos / ELM_SIZE] & (1L << (pos % ELM_SIZE))) != 0;
}
return false;
}
// Negative index specified
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
/**
* Retrieves the bits starting from {@code pos1} to {@code pos2} and returns
* back a new bitset made of these bits. Grows the {@code BitSet} if
* {@code pos2 > size}.
*
* @param pos1
* beginning position.
* @param pos2
* ending position.
* @return new bitset of the range specified.
* @throws IndexOutOfBoundsException
* if {@code pos1} or {@code pos2} is negative, or if
* {@code pos2} is smaller than {@code pos1}.
* @see #get(int)
* @since Android 1.0
*/
public BitSet get(int pos1, int pos2) {
if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) {
int last = (bits.length * ELM_SIZE);
if (pos1 >= last || pos1 == pos2) {
return new BitSet(0);
}
if (pos2 > last) {
pos2 = last;
}
int idx1 = pos1 / ELM_SIZE;
int idx2 = (pos2 - 1) / ELM_SIZE;
long factor1 = (~0L) << (pos1 % ELM_SIZE);
long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
if (idx1 == idx2) {
long result = (bits[idx1] & (factor1 & factor2)) >>> (pos1 % ELM_SIZE);
return new BitSet(new long[] { result });
}
long[] newbits = new long[idx2 - idx1 + 1];
// first fill in the first and last indexes in the new bitset
newbits[0] = bits[idx1] & factor1;
newbits[newbits.length - 1] = bits[idx2] & factor2;
// fill in the in between elements of the new bitset
for (int i = 1; i < idx2 - idx1; i++) {
newbits[i] = bits[idx1 + i];
}
// shift all the elements in the new bitset to the right by pos1
// % ELM_SIZE
int numBitsToShift = pos1 % ELM_SIZE;
if (numBitsToShift != 0) {
for (int i = 0; i < newbits.length; i++) {
// shift the current element to the right regardless of
// sign
newbits[i] = newbits[i] >>> (numBitsToShift);
// apply the last x bits of newbits[i+1] to the current
// element
if (i != newbits.length - 1) {
newbits[i] |= newbits[i + 1] << (ELM_SIZE - (numBitsToShift));
}
}
}
return new BitSet(newbits);
}
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
/**
* Sets the bit at index {@code pos} to 1. Grows the {@code BitSet} if
* {@code pos > size}.
*
* @param pos
* the index of the bit to set.
* @throws IndexOutOfBoundsException
* if {@code pos} is negative.
* @see #clear(int)
* @see #clear()
* @see #clear(int, int)
* @since Android 1.0
*/
public void set(int pos) {
if (pos >= 0) {
if (pos >= bits.length * ELM_SIZE) {
growBits(pos);
}
bits[pos / ELM_SIZE] |= 1L << (pos % ELM_SIZE);
} else {
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
}
/**
* Sets the bit at index {@code pos} to {@code val}. Grows the
* {@code BitSet} if {@code pos > size}.
*
* @param pos
* the index of the bit to set.
* @param val
* value to set the bit.
* @throws IndexOutOfBoundsException
* if {@code pos} is negative.
* @see #set(int)
* @since Android 1.0
*/
public void set(int pos, boolean val) {
if (val) {
set(pos);
} else {
clear(pos);
}
}
/**
* Sets the bits starting from {@code pos1} to {@code pos2}. Grows the
* {@code BitSet} if {@code pos2 > size}.
*
* @param pos1
* beginning position.
* @param pos2
* ending position.
* @throws IndexOutOfBoundsException
* if {@code pos1} or {@code pos2} is negative, or if
* {@code pos2} is smaller than {@code pos1}.
* @see #set(int)
* @since Android 1.0
*/
public void set(int pos1, int pos2) {
if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) {
if (pos1 == pos2) {
return;
}
if (pos2 >= bits.length * ELM_SIZE) {
growBits(pos2);
}
int idx1 = pos1 / ELM_SIZE;
int idx2 = (pos2 - 1) / ELM_SIZE;
long factor1 = (~0L) << (pos1 % ELM_SIZE);
long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
if (idx1 == idx2) {
bits[idx1] |= (factor1 & factor2);
} else {
bits[idx1] |= factor1;
bits[idx2] |= factor2;
for (int i = idx1 + 1; i < idx2; i++) {
bits[i] |= (~0L);
}
}
} else {
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
}
/**
* Sets the bits starting from {@code pos1} to {@code pos2} to the given
* {@code val}. Grows the {@code BitSet} if {@code pos2 > size}.
*
* @param pos1
* beginning position.
* @param pos2
* ending position.
* @param val
* value to set these bits.
* @throws IndexOutOfBoundsException
* if {@code pos1} or {@code pos2} is negative, or if
* {@code pos2} is smaller than {@code pos1}.
* @see #set(int,int)
* @since Android 1.0
*/
public void set(int pos1, int pos2, boolean val) {
if (val) {
set(pos1, pos2);
} else {
clear(pos1, pos2);
}
}
/**
* Clears all the bits in this {@code BitSet}.
*
* @see #clear(int)
* @see #clear(int, int)
* @since Android 1.0
*/
public void clear() {
for (int i = 0; i < bits.length; i++) {
bits[i] = 0L;
}
}
/**
* Clears the bit at index {@code pos}. Grows the {@code BitSet} if
* {@code pos > size}.
*
* @param pos
* the index of the bit to clear.
* @throws IndexOutOfBoundsException
* if {@code pos} is negative.
* @see #clear(int, int)
* @since Android 1.0
*/
public void clear(int pos) {
if (pos >= 0) {
if (pos < bits.length * ELM_SIZE) {
bits[pos / ELM_SIZE] &= ~(1L << (pos % ELM_SIZE));
}
} else {
// Negative index specified
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
}
/**
* Clears the bits starting from {@code pos1} to {@code pos2}. Grows the
* {@code BitSet} if {@code pos2 > size}.
*
* @param pos1
* beginning position.
* @param pos2
* ending position.
* @throws IndexOutOfBoundsException
* if {@code pos1} or {@code pos2} is negative, or if
* {@code pos2} is smaller than {@code pos1}.
* @see #clear(int)
* @since Android 1.0
*/
public void clear(int pos1, int pos2) {
if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) {
int last = (bits.length * ELM_SIZE);
if (pos1 >= last || pos1 == pos2) {
return;
}
if (pos2 > last) {
pos2 = last;
}
int idx1 = pos1 / ELM_SIZE;
int idx2 = (pos2 - 1) / ELM_SIZE;
long factor1 = (~0L) << (pos1 % ELM_SIZE);
long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
if (idx1 == idx2) {
bits[idx1] &= ~(factor1 & factor2);
} else {
bits[idx1] &= ~factor1;
bits[idx2] &= ~factor2;
for (int i = idx1 + 1; i < idx2; i++) {
bits[i] = 0L;
}
}
} else {
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
}
/**
* Flips the bit at index {@code pos}. Grows the {@code BitSet} if
* {@code pos > size}.
*
* @param pos
* the index of the bit to flip.
* @throws IndexOutOfBoundsException
* if {@code pos} is negative.
* @see #flip(int, int)
* @since Android 1.0
*/
public void flip(int pos) {
if (pos >= 0) {
if (pos >= bits.length * ELM_SIZE) {
growBits(pos);
}
bits[pos / ELM_SIZE] ^= 1L << (pos % ELM_SIZE);
} else {
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
}
/**
* Flips the bits starting from {@code pos1} to {@code pos2}. Grows the
* {@code BitSet} if {@code pos2 > size}.
*
* @param pos1
* beginning position.
* @param pos2
* ending position.
* @throws IndexOutOfBoundsException
* if {@code pos1} or {@code pos2} is negative, or if
* {@code pos2} is smaller than {@code pos1}.
* @see #flip(int)
* @since Android 1.0
*/
public void flip(int pos1, int pos2) {
if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) {
if (pos1 == pos2) {
return;
}
if (pos2 >= bits.length * ELM_SIZE) {
growBits(pos2);
}
int idx1 = pos1 / ELM_SIZE;
int idx2 = (pos2 - 1) / ELM_SIZE;
long factor1 = (~0L) << (pos1 % ELM_SIZE);
long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
if (idx1 == idx2) {
bits[idx1] ^= (factor1 & factor2);
} else {
bits[idx1] ^= factor1;
bits[idx2] ^= factor2;
for (int i = idx1 + 1; i < idx2; i++) {
bits[i] ^= (~0L);
}
}
} else {
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
}
/**
* Checks if these two {@code BitSet}s have at least one bit set to true in the same
* position.
*
* @param bs
* {@code BitSet} used to calculate the intersection.
* @return {@code true} if bs intersects with this {@code BitSet},
* {@code false} otherwise.
* @since Android 1.0
*/
public boolean intersects(BitSet bs) {
long[] bsBits = bs.bits;
int length1 = bits.length, length2 = bsBits.length;
if (length1 <= length2) {
for (int i = 0; i < length1; i++) {
if ((bits[i] & bsBits[i]) != 0L) {
return true;
}
}
} else {
for (int i = 0; i < length2; i++) {
if ((bits[i] & bsBits[i]) != 0L) {
return true;
}
}
}
return false;
}
/**
* Performs the logical AND of this {@code BitSet} with another
* {@code BitSet}. The values of this {@code BitSet} are changed accordingly.
*
* @param bs
* {@code BitSet} to AND with.
* @see #or
* @see #xor
* @since Android 1.0
*/
public void and(BitSet bs) {
long[] bsBits = bs.bits;
int length1 = bits.length, length2 = bsBits.length;
if (length1 <= length2) {
for (int i = 0; i < length1; i++) {
bits[i] &= bsBits[i];
}
} else {
for (int i = 0; i < length2; i++) {
bits[i] &= bsBits[i];
}
for (int i = length2; i < length1; i++) {
bits[i] = 0;
}
}
}
/**
* Clears all bits in the receiver which are also set in the parameter
* {@code BitSet}. The values of this {@code BitSet} are changed accordingly.
*
* @param bs
* {@code BitSet} to ANDNOT with.
* @since Android 1.0
*/
public void andNot(BitSet bs) {
long[] bsBits = bs.bits;
int range = bits.length < bsBits.length ? bits.length : bsBits.length;
for (int i = 0; i < range; i++) {
bits[i] &= ~bsBits[i];
}
}
/**
* Performs the logical OR of this {@code BitSet} with another {@code BitSet}.
* The values of this {@code BitSet} are changed accordingly.
*
* @param bs
* {@code BitSet} to OR with.
* @see #xor
* @see #and
* @since Android 1.0
*/
public void or(BitSet bs) {
int nbits = bs.length();
int length = nbits / ELM_SIZE + (nbits % ELM_SIZE > 0 ? 1 : 0);
if (length > bits.length) {
growBits(nbits - 1);
}
long[] bsBits = bs.bits;
for (int i = 0; i < length; i++) {
bits[i] |= bsBits[i];
}
}
/**
* Performs the logical XOR of this {@code BitSet} with another {@code BitSet}.
* The values of this {@code BitSet} are changed accordingly.
*
* @param bs
* {@code BitSet} to XOR with.
* @see #or
* @see #and
* @since Android 1.0
*/
public void xor(BitSet bs) {
int nbits = bs.length();
int length = nbits / ELM_SIZE + (nbits % ELM_SIZE > 0 ? 1 : 0);
if (length > bits.length) {
growBits(nbits - 1);
}
long[] bsBits = bs.bits;
for (int i = 0; i < length; i++) {
bits[i] ^= bsBits[i];
}
}
/**
* Returns the number of bits this {@code BitSet} has.
*
* @return the number of bits contained in this {@code BitSet}.
* @see #length
* @since Android 1.0
*/
public int size() {
return bits.length * ELM_SIZE;
}
/**
* Returns the number of bits up to and including the highest bit set.
*
* @return the length of the {@code BitSet}.
* @since Android 1.0
*/
public int length() {
int idx = bits.length - 1;
while (idx >= 0 && bits[idx] == 0) {
--idx;
}
if (idx == -1) {
return 0;
}
int i = ELM_SIZE - 1;
long val = bits[idx];
while ((val & (1L << i)) == 0 && i > 0) {
i--;
}
return idx * ELM_SIZE + i + 1;
}
/**
* Returns a string containing a concise, human-readable description of the
* receiver.
*
* @return a comma delimited list of the indices of all bits that are set.
* @since Android 1.0
*/
@Override
public String toString() {
StringBuffer sb = new StringBuffer(bits.length / 2);
int bitCount = 0;
sb.append('{');
boolean comma = false;
for (int i = 0; i < bits.length; i++) {
if (bits[i] == 0) {
bitCount += ELM_SIZE;
continue;
}
for (int j = 0; j < ELM_SIZE; j++) {
if (((bits[i] & (1L << j)) != 0)) {
if (comma) {
sb.append(", "); //$NON-NLS-1$
}
sb.append(bitCount);
comma = true;
}
bitCount++;
}
}
sb.append('}');
return sb.toString();
}
/**
* Returns the position of the first bit that is {@code true} on or after {@code pos}.
*
* @param pos
* the starting position (inclusive).
* @return -1 if there is no bits that are set to {@code true} on or after {@code pos}.
* @since Android 1.0
*/
public int nextSetBit(int pos) {
if (pos >= 0) {
if (pos >= bits.length * ELM_SIZE) {
return -1;
}
int idx = pos / ELM_SIZE;
// first check in the same bit set element
if (bits[idx] != 0L) {
for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++) {
if (((bits[idx] & (1L << j)) != 0)) {
return idx * ELM_SIZE + j;
}
}
}
idx++;
while (idx < bits.length && bits[idx] == 0L) {
idx++;
}
if (idx == bits.length) {
return -1;
}
// we know for sure there is a bit set to true in this element
// since the bitset value is not 0L
for (int j = 0; j < ELM_SIZE; j++) {
if (((bits[idx] & (1L << j)) != 0)) {
return idx * ELM_SIZE + j;
}
}
return -1;
}
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
/**
* Returns the position of the first bit that is {@code false} on or after {@code pos}.
*
* @param pos
* the starting position (inclusive).
* @return the position of the next bit set to {@code false}, even if it is further
* than this {@code BitSet}'s size.
* @since Android 1.0
*/
public int nextClearBit(int pos) {
if (pos >= 0) {
int bssize = bits.length * ELM_SIZE;
if (pos >= bssize) {
return pos;
}
int idx = pos / ELM_SIZE;
// first check in the same bit set element
if (bits[idx] != (~0L)) {
for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++) {
if (((bits[idx] & (1L << j)) == 0)) {
return idx * ELM_SIZE + j;
}
}
}
idx++;
while (idx < bits.length && bits[idx] == (~0L)) {
idx++;
}
if (idx == bits.length) {
return bssize;
}
// we know for sure there is a bit set to true in this element
// since the bitset value is not 0L
for (int j = 0; j < ELM_SIZE; j++) {
if (((bits[idx] & (1L << j)) == 0)) {
return idx * ELM_SIZE + j;
}
}
return bssize;
}
throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
}
/**
* Returns true if all the bits in this {@code BitSet} are set to false.
*
* @return {@code true} if the {@code BitSet} is empty,
* {@code false} otherwise.
* @since Android 1.0
*/
public boolean isEmpty() {
for (int idx = 0; idx < bits.length; idx++) {
if (bits[idx] != 0L) {
return false;
}
}
return true;
}
/**
* Returns the number of bits that are {@code true} in this {@code BitSet}.
*
* @return the number of {@code true} bits in the set.
* @since Android 1.0
*/
public int cardinality() {
int count = 0;
for (int idx = 0; idx < bits.length; idx++) {
long temp = bits[idx];
if (temp != 0L) {
for (int i = 0; i < ELM_SIZE; i++) {
if ((temp & (1L << i)) != 0L) {
count++;
}
}
}
}
return count;
}
}
|
