A tiny Java library for generating Gray codes

Question

This library is for generating Gray codes. A Gray code over \$n\$ bits is a list of \$2^n\$ different \$n\$-bit strings subject to the following constraint: two adjacent bit string differ in only one position. For example, the Gray code over four bits is

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

Without further ado, let's proceed to code.

GrayCode.java

package net.coderodde.graycode;

import java.util.BitSet;

/**
 * This class holds the Gray code.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 4, 2018)
 */
public final class GrayCode {

    private final BitSet[] code;
    private final int bits;

    GrayCode(BitSet[] code, int bits) {
        this.code = code;
        this.bits = bits;
    }

    public boolean isValid() {
        if (getNumberOfBits() == 0) {
            return code.length == 0;
        }

        int rowLength = getNumberOfBits();
        BitSet previousRow = getRow(0);

        for (int row = 1; row < getNumberOfRows(); row++) {
            BitSet currentRow = getRow(row);

            if (getDifferenceCounts(previousRow, currentRow) != 1) {
                return false;
            }

            previousRow = currentRow;
        }

        return true;
    }

    public int getNumberOfBits() {
        return bits;
    }

    public int getNumberOfRows() {
        return this.code.length;
    }

    public BitSet getRow(int index) {
        BitSet bitSet = new BitSet(getNumberOfBits());

        for (int i = 0; i < bits; ++i) {
            bitSet.set(i, code[index].get(i));
        }

        return bitSet;
    }

    public boolean readBit(int row, int column) {
        return code[row].get(column);
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        String rowSeparator = "";

        for (int row = 0; row < code.length; ++row) {
            stringBuilder.append(rowSeparator);
            rowSeparator = "\n";
            rowToBitString(stringBuilder, code[row]);
        }

        return stringBuilder.toString();
    }

    private void rowToBitString(StringBuilder stringBuilder, BitSet bitSet) {
        for (int i = 0; i != bits; ++i) {
            stringBuilder.append(bitSet.get(i) ? '1' : '0');
        }
    }

    private int getDifferenceCounts(BitSet row1, BitSet row2) {
        int differenceCount = 0;

        for (int i = 0; i < bits; ++i) {
            if (row1.get(i) != row2.get(i)) {
                differenceCount++;

                if (differenceCount == 2) {
                    return differenceCount;
                }
            }
        }

        return differenceCount;
    }
}

GrayCodeGenerator.java

package net.coderodde.graycode;

import java.util.BitSet;

/**
 * This class provides a method for generating Gray code over particular number
 * of bits.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 4, 2018)
 */
public class GrayCodeGenerator {

    public static GrayCode generate(int bits) {
        checkBits(bits);

        if (bits == 0) {
            return new GrayCode(new BitSet[0], 0);
        }

        BitSet[] bitSetArray = new BitSet[getNumberOfBitStrings(bits)];

        for (int i = 0; i != bitSetArray.length; ++i) {
            bitSetArray[i] = new BitSet(bits);
        }

        bitSetArray[1].set(bits - 1);

        for (int bitIndex = bits - 1, columnHeight = 2, width = 1;
                bitIndex > 0;
                bitIndex--, columnHeight <<= 1, ++width) {
            // Mirror down:
            for (int row1 = columnHeight,
                     row2 = columnHeight - 1;
                    row1 < (columnHeight << 1); 
                    row1++,
                    row2--) {
                for (int w = bits - 1; w > bitIndex - 1; w--) {
                    bitSetArray[row1].set(w, bitSetArray[row2].get(w));
                }
            }

            // Fill the prefix bits:
            for (int row = columnHeight; row < (columnHeight << 1); ++row) {
                bitSetArray[row].set(bitIndex - 1);
            }
        }

        return new GrayCode(bitSetArray, bits);
    }

    /**
     * Returns the number of rows in the Gray code over {@code bits} bits.
     * 
     * @param bits the number of bits.
     * @return the number of rows in the resulting Gray code.
     */
    private static int getNumberOfBitStrings(int bits) {
        return 1 << bits;
    }

    /**
     * Checks that the number of bits is not negative.
     * 
     * @param bits the number of bits to check.
     */
    private static void checkBits(int bits) {
        if (bits < 0) {
            throw new IllegalArgumentException(
                    "Negative number of bits requested: " + bits);
        }
    }
}

GrayCodeDemo.java

package net.coderodde.graycode;

/**
 * This class implements a sample Gray code demonstration.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 4, 2018)
 */
public final class GrayCodeDemo {

    public static void main(String[] args) {
        GrayCode grayCode = GrayCodeGenerator.generate(4);
        System.out.println(grayCode);
        System.out.println("Valid Gray code: " + grayCode.isValid());
    }
}

GrayCodeTest.java

package net.coderodde.graycode;

import java.util.BitSet;
import org.junit.Test;
import static org.junit.Assert.*;

public class GrayCodeTest {

    @Test
    public void test() {
        GrayCode grayCode = GrayCodeGenerator.generate(2);
        assertEquals(4, grayCode.getNumberOfRows());
        assertEquals(2, grayCode.getNumberOfBits());
        System.out.println(grayCode);
        assertTrue(grayCode.isValid());

        // Check first column:
        assertFalse(grayCode.readBit(0, 0));
        assertFalse(grayCode.readBit(1, 0));
        assertTrue(grayCode.readBit(2, 0));
        assertTrue(grayCode.readBit(3, 0));

        // Check second column:
        assertFalse(grayCode.readBit(0, 1));
        assertTrue(grayCode.readBit(1, 1));
        assertTrue(grayCode.readBit(2, 1));
        assertFalse(grayCode.readBit(3, 1));

        BitSet row1 = grayCode.getRow(1);
        assertFalse(row1.get(0));
        assertTrue(row1.get(1));
    }

    @Test
    public void bruteForceTest() {
        for (int bits = 0; bits < 12; bits++) {
            assertTrue(GrayCodeGenerator.generate(bits).isValid());
        }
    }
}

Critique request

Please tell me anything that comes to mind. I am most interested in comments regarding the API design.

Answer 1

What is a bit missing, is the logic / proof / explanation. And it is generative, creating a sequence.

Hence one could look at an immediate mapping function:

static int grayCode(int n) {
    assert n >= 0;
    if (n == 0) {
       return 0;
    }
    int high = Integer.highestOneBit(n);
    int lows = n & ~high; // Or n - high
    return high | grayCode(high - 1 - lows); // Reverse order backwards
}

• Proof can be done by induction because of the recursion.
• The recursion can be resolved a bit. (Also generative with a non-tail recursion.)
• An explanation is simple too:

Having a valid sequence of 0 .. 2^k - 1, the following 2^k numbers can be retrieved by reversing the list and adding a bit 1 in front: every step also flips one single bit.

I did not want to spoil this nice usage of BitSet, but Gray Codes seem useful, like de-Bruijn sequences.

Answer 2

Personally, I would have put the generator code (and helper functions) within the GrayCode class, not within its own class. A key point here is that there is not initialiser for the GrayCodeGenerator class. You can then use this to see if the gray code has been set - useful for avoiding programming errors where the future code declares a GrayCode but does not generate with it. You could also use this for a new constructor where only a number of bits is passed, and the GrayCode class then automatically generates the BitSet. Yes, you could also do this with the current code, but having the generator inside the GrayCode class will make it neater.

Answer 3

As interface design is pivotal in type design, I'm happy to start there -
let me refer to java.util.BitSet. In no uncertain terms, the documentation summarises in just two sentences what BitSet is about: element access and
bulk boolean operations (see java.math.BigInteger for something irritatingly similar)
(leaving out summaries (cardinality() and intersects​(BitSet other)) and paraphernalia).

I like that it is possible to have non-reflected binary codes - assuming a
GrayCode(int nBits, long ... codes): new GrayCode(3, 0, 1, 3, 7, 6, 4).
I second AJD in preferring a constructor with a single int parameter as an alternative to a separate generator class for reflected binary Gray codes.
With that change, the whole API collapses to public boolean GrayCode.isValid() - which in itself is weird:
Objects should be constructed in a valid state and never get invalid if that can be helped.
(Another hint about the API is the lack of documentation - compare to BitSet.)

Then, there is implementation:

• getRow() could just return (BitSet) code[index].clone();

• int getDifferenceCount(BitSet row1, BitSet row2) {
      BitSet bits = (BitSet) row1.clone();
      bits.xor(row2);
      return bits.cardinality();
  }
  

isValid() needs to initialise BitSet previousRow = getRow(getNumberOfRows()-1); and start from 0 to check every transition - but even that is just one necessary condition where a second comes to mind: no code may repeat. (I don't know better that to sort with a "throwing comparator".)