6
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I planned to do some data compression, so this class was a good place to start. \$\endgroup\$ – coderodde Nov 13 '16 at 14:48
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Karol Nov 13 '16 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.