I have this Java class for building bit strings. The set of methods it provides resembles that of java.lang.StringBuilder.
See what I have:
BitStringBuilder.java:
package net.coderodde.util;
import java.util.BitSet;
/**
* This class implements a simple bit string builder.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (May 25, 2016)
*/
public class BitStringBuilder {
/**
* The minimum number of bits to commit in the constructor.
*/
private static final int MINIMUM_BIT_COMMIT = 64;
private static final int BITS_PER_WORD = 64;
/**
* The actual bit storage.
*/
private long[] bits;
/**
* The size of bits this builder holds.
*/
private int size;
/**
* Constructs a new empty bit string builder.
*/
public BitStringBuilder() {
this(MINIMUM_BIT_COMMIT);
}
/**
* Constructs a new empty bit string builder capable holding
* {@code bitCommit} bits immediately after construction.
*
* @param bitCommit the number of bits to reserve.
*/
public BitStringBuilder(int bitCommit) {
bitCommit = Math.max(bitCommit, MINIMUM_BIT_COMMIT);
final int longs = bitCommit / BITS_PER_WORD +
(bitCommit % BITS_PER_WORD != 0 ? 1 : 0);
this.bits = new long[longs];
}
public int size() {
return this.size;
}
public boolean isEmpty() {
return this.size == 0;
}
/**
* Appends the bit string described by {@code bitset} to the end of this
* builder.
*
* @param bitset the {@link java.util.BitSet} holding the bits.
* @param numBits the number of bits to consider in {@code bitset}.
*/
public void append(final BitSet bitset, final int numBits) {
if (numBits <= 0) {
return;
}
final int startIndex = this.size;
expandBitArray(this.size += numBits);
for (int i = 0, j = startIndex; i < numBits; ++i, ++j) {
writeBit(j, bitset.get(i));
}
}
/**
* Deletes all the bits whose index is at least {@code fromIndex} and at
* most {@code toIndex - 1}.
*
* @param fromIndex the starting inclusive index of the range to remove.
* @param toIndex the ending exclusive index of the range to remove.
*/
public void delete(final int fromIndex, final int toIndex) {
if (fromIndex > toIndex) {
throw new IllegalArgumentException(
"'fromIndex' (" + fromIndex + ") is larger than 'toIndex' (" +
toIndex + ")!");
}
if (fromIndex < 0) {
throw new IndexOutOfBoundsException(
"'fromIndex' (" + fromIndex + ") is negative!");
}
if (toIndex > this.size) {
throw new IndexOutOfBoundsException(
"'toIndex' (" + toIndex + ") is too large. Should be at most " +
this.size + ".");
}
final int length = toIndex - fromIndex;
for (int bitIndex = toIndex; bitIndex < this.size; ++bitIndex) {
writeBit(bitIndex - length, readBit(bitIndex));
}
this.size -= length;
}
/**
* Inserts the {@code numBits} bits from {@code bitset} starting at index
* {@code startIndex}, shifting the tail elements to the right in order to
* make space for new bits.
*
* @param bitset the {@link java.util.BitSet} holding the bits to
* insert.
* @param startIndex the index at which to perform the insertion.
* @param numBits the number of bits to take from {@code bitset}.
*/
public void insert(final BitSet bitset,
final int startIndex,
final int numBits) {
if (startIndex < 0) {
throw new IndexOutOfBoundsException(
"'startIndex' (" + startIndex + ") is negative!");
}
if (startIndex > this.size) {
throw new IndexOutOfBoundsException(
"'startIndex' (" + startIndex + ") is too large! Must be at most " +
this.size + ".");
}
if (numBits <= 0) {
return;
}
final int oldSize = this.size;
expandBitArray(this.size += numBits);
// Shift the bit content to the right.
for (int i = oldSize - 1; i >= startIndex; --i) {
writeBit(i + numBits, readBit(i));
}
// Insert the bits from the bit set.
for (int i = 0, j = startIndex; i < numBits; ++i, ++j) {
writeBit(j, bitset.get(i));
}
}
/**
* Sets {@code numBits} bits from {@code bitset} to this builder. This
* method may extend the size of this builder from the tail.
*
* @param bitset the {@link java.util.BitSet} holding the bits.
* @param startIndex the index at which to set the bits.
* @param numBits the number of bits to set.
*/
public void set(final BitSet bitset,
final int startIndex,
final int numBits) {
final int lastIndex = startIndex + numBits;
expandBitArray(lastIndex);
this.size = Math.max(this.size, lastIndex);
for (int i = startIndex, j = 0; j < numBits; ++j, ++i) {
writeBit(i, bitset.get(j));
}
}
/**
* Clears this builder.
*/
public void clear() {
this.size = 0;
}
/**
* Returns the textual representation of the contents of this builder.
*
* @return the textual representation of the contents of this bit string
* builder.
*/
@Override
public String toString() {
final StringBuilder sb = new StringBuilder(this.size);
for (int i = this.size - 1; i >= 0; --i) {
sb.append(readBit(i) ? '1' : '0');
}
return sb.toString();
}
public boolean readBit(final int index) {
checkAccessIndex(index);
return readBit(index / BITS_PER_WORD, index % BITS_PER_WORD);
}
public void writeBit(final int index, final boolean value) {
checkAccessIndex(index);
writeBit(index / BITS_PER_WORD, index % BITS_PER_WORD, value);
}
public BitSet toBitSet() {
final BitSet bs = new BitSet(size);
for (int i = 0; i < this.size; ++i) {
bs.set(i, readBit(i));
}
return bs;
}
private void checkAccessIndex(final int index) {
if (this.size == 0) {
throw new IllegalStateException("The bit string builder is empty.");
}
if (index < 0) {
throw new IndexOutOfBoundsException(
"The index is negative: " + index + ".");
}
if (index >= this.size) {
throw new IndexOutOfBoundsException(
"The index is too large (" + index + "). Must be at most " +
(this.size - 1) + "!");
}
}
private boolean readBit(final int wordIndex,
final int bitIndex) {
final long mask = 1L << bitIndex;
return (this.bits[wordIndex] & mask) != 0;
}
private void writeBit(final int wordIndex,
final int bitIndex,
final boolean value) {
if (value == true) {
final long mask = 1L << bitIndex;
bits[wordIndex] |= mask;
} else {
final long mask = ~(1L << bitIndex);
bits[wordIndex] &= mask;
}
}
private void expandBitArray(final int requestedCapacity) {
final int currentCapacity = this.bits.length * BITS_PER_WORD;
if (requestedCapacity <= currentCapacity) {
return;
}
final long[] newBitArray = new long[Math.max(2 * currentCapacity,
requestedCapacity)];
System.arraycopy(bits, 0, newBitArray, 0, bits.length);
bits = newBitArray;
}
}
BitStringBuilderTest.java:
package net.coderodde.util;
import java.util.BitSet;
import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;
public class BitStringBuilderTest {
private BitStringBuilder builder;
@Before
public void beforeEachTest() {
builder = new BitStringBuilder();
}
@Test
public void testSize() {
assertEquals(0, builder.size());
builder.append(create(101L, 3), 3);
assertEquals(3, builder.size());
builder.append(create(11L, 2), 2);
assertEquals(5, builder.size());
builder.append(create(31L, 65), 65);
assertEquals(70, builder.size());
builder.delete(10, 15);
assertEquals(65, builder.size());
builder.insert(create(1101L, 4), 10, 4);
assertEquals(69, builder.size());
builder.set(create(1001L, 5), 20, 5);
assertEquals(69, builder.size());
builder.set(create(100011L, 6), 66, 6);
assertEquals(72, builder.size());
}
@Test
public void testAppend() {
builder.append(create(0b111001L, 6), 6);
assertTrue(builder.readBit(0));
assertFalse(builder.readBit(1));
assertFalse(builder.readBit(2));
assertTrue(builder.readBit(3));
assertTrue(builder.readBit(4));
assertTrue(builder.readBit(5));
builder.append(create(0b1101L, 4), 4);
assertTrue(builder.readBit(6));
assertFalse(builder.readBit(7));
assertTrue(builder.readBit(8));
assertTrue(builder.readBit(9));
}
@Test
public void testDelete() {
builder.append(create(0b10011100010, 11), 11);
builder.delete(2, 6);
// Here 'builder' should be 1001110
assertFalse(builder.readBit(0));
assertTrue(builder.readBit(1));
assertTrue(builder.readBit(2));
assertTrue(builder.readBit(3));
assertFalse(builder.readBit(4));
assertFalse(builder.readBit(5));
assertTrue(builder.readBit(6));
}
@Test
public void testInsert() {
builder.insert(create(0b1011L, 4), 0, 4);
assertTrue(builder.readBit(0));
assertTrue(builder.readBit(1));
assertFalse(builder.readBit(2));
assertTrue(builder.readBit(3));
builder.insert(create(0b00L, 2), 2, 2);
// Here 'builder' should be 100011
assertEquals("100011", builder.toString());
}
@Test
public void testSet() {
builder.append(create(0b10_0110_0010L, 10), 10);
builder.set(create(0b110, 3), 2, 3);
assertEquals("1001111010", builder.toString());
builder.set(create(0b100L, 3), 8, 3);
assertEquals("10001111010", builder.toString());
}
@Test
public void testToString() {
builder.append(create(0b1011011100L, 10), 10);
assertEquals("1011011100", builder.toString());
}
@Test
public void testReadBit() {
builder.append(create(0b10110L, 5), 5);
assertFalse(builder.readBit(0));
assertTrue(builder.readBit(1));
assertTrue(builder.readBit(2));
assertFalse(builder.readBit(3));
assertTrue(builder.readBit(4));
}
@Test
public void testWriteBit() {
builder.append(create(0b10110L, 5), 5);
builder.writeBit(2, false);
builder.writeBit(0, true);
assertTrue(builder.readBit(0));
assertTrue(builder.readBit(1));
assertFalse(builder.readBit(2));
assertFalse(builder.readBit(3));
assertTrue(builder.readBit(4));
}
@Test
public void testToBitSet() {
assertTrue(builder.isEmpty());
builder.append(create(0b011100L, 6), 6);
final BitSet bs = builder.toBitSet();
assertFalse(builder.isEmpty());
assertFalse(bs.get(0));
assertFalse(bs.get(1));
assertTrue(bs.get(2));
assertTrue(bs.get(3));
assertTrue(bs.get(4));
assertFalse(bs.get(5));
}
@Test(expected = IllegalArgumentException.class)
public void testDeleteThrowsOnInversedIndices() {
builder.append(create(0b101L, 3), 3);
builder.delete(1, 0);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testDeleteThrowsOnNegativeFromIndex() {
builder.append(create(0b101L, 3), 3);
builder.delete(-1, 0);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testDeleteThrowsOnTooLargeToIndex() {
builder.append(create(0b101L, 3), 3);
builder.delete(1, 4);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testInsertThrowsOnNegativeStartIndex() {
builder.insert(create(0b111L, 3), -1, 3);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testInsertThrowsOnTooLargeIndex() {
builder.append(create(0b001100L, 6), 6);
builder.insert(create(0b11L, 2), 7, 2);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testReadBitThrowsOnNegativeIndex() {
builder.append(create(0b10L, 2), 2);
builder.readBit(-1);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testReadBitThrowsOnTooLargeIndex() {
builder.append(create(0b10L, 2), 2);
builder.readBit(3);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testWriteBitThrowsOnNegativeIndex() {
builder.append(create(0b10L, 2), 2);
builder.writeBit(-1, false);
}
@Test(expected = IndexOutOfBoundsException.class)
public void testWriteBitThrowsOnTooLargeIndex() {
builder.append(create(0b10L, 2), 2);
builder.writeBit(3, false);
}
private BitSet create(final long bits, final int length) {
BitSet bitset = new BitSet();
for (int i = 0; i < length; ++i) {
bitset.set(i, (bits & (1L << i)) != 0);
}
return bitset;
}
}
Critique request
I would like to hear comments regarding API design, naming/coding conventions and testing, yet feel free to tell me anything that comes to mind.
