Bug 58: Breakdancing Links
- This is a data structure for backtrack programming. It uses Knuth's doubly linked list "dancing links".
- It maintains a sequence of integers. NewResidue(n) returns a sequence consisting of integers 1, 2, ..., n.
- Prev(0) returns the last integer in the sequence. Next(0) returns the first integer. Both return 0 if none.
- Prev(x) returns the integer that precedes x in the sequence and Next(x) returns the integer that follows x.
- If x is the first integer in the sequence, Prev(x) returns 0. If x is the last integer, Next(x) returns 0.
- If 1 <= x <= n is not in the sequence: Contains(x) returns false; Remove(x) returns false, no other effect.
- If x is in the sequence: Contains(x) returns true; Remove(x) removes x, preserving order, and returns true.
- Undo reverts the effect of the most recent call to Remove that returned true and has not yet been reverted.
- There is a stack of removed integers. Remove(x) removes x from the sequence and pushes x onto the stack.
- If the stack is not empty, Undo pops x off the stack, inserts x into the sequence, and returns true.
- If the stack is empty, Undo returns false with no other effect.
Fix The Tiny Bug In This Go Code: