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.