Generation of De Bruijn sequence using BitVector

BitVectorDeBruijn.java

// generates a binary De Bruijn sequence over words of length n
private BitVector generateDeBruijn(int n) {
	// Check arguments
	if (n < 0) throw new IllegalArgumentException("n is negative");
	if (n > 31) throw new IllegalArgumentException("n exceeds 31");
	// There are 2^n words in the entire sequence
	int length = 1 << n;
	// Create a set that records which words we have already seen
	Set<Integer> memory = new BitVector(length).asSet();
	// Store the sequence with an extra n bits
	// makes things easier for enumerating the values 
	BitVector sequence = new BitVector(length + n);
	// Seed the sequence with the initial value (n 1s)
	sequence.setRange(0, n, true);
	// Populate the sequence
	for (int i = 0; i < length; i++) {
		// Extract the current word from the sequence
		int word = (int) sequence.getBits(i, n);
		// Record that we've seen it
		memory.add(word);
		// Shift the word left, populating the rightmost bit with zero
		// if we've seen the word before, use a one instead
		sequence.setBit(i + n, memory.contains(word >> 1));
	}
	return sequence;
}