public final class BitVector {
private int sizeInBits;
- private int bytePosition;
private byte[] array;
// For efficiency, start out with some room to work.
- private static final int DEFAULT_SIZE_IN_BITS = 32 * 8;
+ private static final int DEFAULT_SIZE_IN_BYTES = 32;
public BitVector() {
- sizeInBits = DEFAULT_SIZE_IN_BITS;
- bytePosition = 0;
- array = new byte[DEFAULT_SIZE_IN_BITS / 8];
+ sizeInBits = 0;
+ array = new byte[DEFAULT_SIZE_IN_BYTES];
}
// Return the bit value at "index".
- public int at(final int index) {
- Debug.DCHECK_LE(0, index);
- Debug.DCHECK_LT(index, sizeInBits);
- final int value = array[index / 8];
- return (value >> (7 - (index % 8))) & 1;
+ public int at(int index) {
+ if (index < 0 || index >= sizeInBits) {
+ throw new IllegalArgumentException("Bad index: " + index);
+ }
+ int value = array[index >> 3] & 0xff;
+ return (value >> (7 - (index & 0x7))) & 1;
}
// Return the number of bits in the bit vector.
}
// Return the number of bytes in the bit vector.
- public int num_bytes() {
- return sizeInBits / 8;
+ public int sizeInBytes() {
+ return (sizeInBits + 7) >> 3;
}
// Append one bit to the bit vector.
- public void AppendBit(final int bit) {
- Debug.DCHECK(bit == 0 || bit == 1);
- final int num_bits_in_last_byte = sizeInBits % 8;
+ public void appendBit(int bit) {
+ if (!(bit == 0 || bit == 1)) {
+ throw new IllegalArgumentException("Bad bit");
+ }
+ int numBitsInLastByte = sizeInBits & 0x7;
// We'll expand array if we don't have bits in the last byte.
- if (num_bits_in_last_byte == 0) {
+ if (numBitsInLastByte == 0) {
appendByte(0);
+ sizeInBits -= 8;
}
// Modify the last byte.
- array[array.length - 1] |= (bit << (7 - num_bits_in_last_byte));
+ array[sizeInBits >> 3] |= (bit << (7 - numBitsInLastByte));
++sizeInBits;
}
- // Append "num_bits" bits in "value" to the bit vector.
- // REQUIRES: 0<= num_bits <= 32.
+ // Append "numBits" bits in "value" to the bit vector.
+ // REQUIRES: 0<= numBits <= 32.
//
// Examples:
- // - AppendBits(0x00, 1) adds 0.
- // - AppendBits(0x00, 4) adds 0000.
- // - AppendBits(0xff, 8) adds 11111111.
- public void AppendBits(final int value, final int num_bits) {
- Debug.DCHECK(num_bits >= 0 && num_bits <= 32);
- int num_bits_left = num_bits;
- while (num_bits_left > 0) {
+ // - appendBits(0x00, 1) adds 0.
+ // - appendBits(0x00, 4) adds 0000.
+ // - appendBits(0xff, 8) adds 11111111.
+ public void appendBits(int value, int numBits) {
+ if (numBits < 0 || numBits > 32) {
+ throw new IllegalArgumentException("Num bits must be between 0 and 32");
+ }
+ int numBitsLeft = numBits;
+ while (numBitsLeft > 0) {
// Optimization for byte-oriented appending.
- if (sizeInBits % 8 == 0 && num_bits_left >= 8) {
- final int newByte = (value >> (num_bits_left - 8)) & 0xff;
+ if ((sizeInBits & 0x7) == 0 && numBitsLeft >= 8) {
+ int newByte = (value >> (numBitsLeft - 8)) & 0xff;
appendByte(newByte);
- sizeInBits += 8;
- num_bits_left -= 8;
+ numBitsLeft -= 8;
} else {
- final int bit = (value >> (num_bits_left - 1)) & 1;
- AppendBit(bit);
- --num_bits_left;
+ int bit = (value >> (numBitsLeft - 1)) & 1;
+ appendBit(bit);
+ --numBitsLeft;
}
}
}
// Append "bits".
- public void AppendBitVector(final BitVector bits) {
+ public void appendBitVector(BitVector bits) {
int size = bits.size();
for (int i = 0; i < size; ++i) {
- AppendBit(bits.at(i));
+ appendBit(bits.at(i));
}
}
// Modify the bit vector by XOR'ing with "other"
- public void XOR(final BitVector other) {
- Debug.DCHECK_EQ(sizeInBits, other.size());
- for (int i = 0; i < array.length; ++i) {
+ public void xor(BitVector other) {
+ if (sizeInBits != other.size()) {
+ throw new IllegalArgumentException("BitVector sizes don't match");
+ }
+ int sizeInBytes = (sizeInBits + 7) >> 3;
+ for (int i = 0; i < sizeInBytes; ++i) {
// The last byte could be incomplete (i.e. not have 8 bits in
// it) but there is no problem since 0 XOR 0 == 0.
array[i] ^= other.array[i];
StringBuffer result = new StringBuffer(sizeInBits);
for (int i = 0; i < sizeInBits; ++i) {
if (at(i) == 0) {
- result.append("0");
+ result.append('0');
} else if (at(i) == 1) {
- result.append("1");
+ result.append('1');
} else {
- Debug.DCHECK(false);
+ throw new IllegalArgumentException("Byte isn't 0 or 1");
}
}
return result.toString();
}
+ // Callers should not assume that array.length is the exact number of bytes needed to hold
+ // sizeInBits - it will typically be larger for efficiency.
+ public byte[] getArray() {
+ return array;
+ }
+
// Add a new byte to the end, possibly reallocating and doubling the size of the array if we've
// run out of room.
private void appendByte(int value) {
- if (bytePosition >= array.length) {
- byte[] newArray = new byte[array.length * 2];
+ if ((sizeInBits >> 3) == array.length) {
+ byte[] newArray = new byte[(array.length << 1)];
System.arraycopy(array, 0, newArray, 0, array.length);
array = newArray;
}
- array[bytePosition] = (byte) value;
- bytePosition++;
+ array[sizeInBits >> 3] = (byte) value;
+ sizeInBits += 8;
}
}