Bit string builder for Java

Question

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.

Answer 1

It looks like you want to optimize something but you did not define what are your performance requirements. Your tests do not justify your implementation.

Why the state of builder is stored in array of longs? In toString method you rewrite everything to StringBuilder and build the String. This approach increases complexity of the whole class without known benefits.

I recommend to use StringBuilder or Bitset instead of array of longs. Write an adapter that implements your expected interface and delegates calls to the StringBuilder.

Use array of longs when StringBuilder or Bitset are not enough for you, but tell us why it is not enough. Write tests that prove this.

• coderodde: I planned to do some data compression, so this class was a good place to start.
• Karol: Maybe it is a good place to start from but it is not so obvious. It depends on who should take benefits from this data compression. Now you are compressing the state of builder. Do you plan to retain many builders or some that are big ones? Do you want to transfer them over the network? If not, the complexity of the code is still not justified.