BUGFIX-66

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:

type node struct { undo int prev int next int } type Residue struct { nodes []node } func NewResidue(n int) *Residue { nodes := make([]node, 1+n) nodes[0].undo = -1 if n > 0 { nodes[0].prev = n nodes[0].next = 1 for x := 1; x < n; x++ { nodes[x].prev = x - 1 nodes[x].next = x + 1 } nodes[n].prev = n - 1 } return &Residue{ nodes: nodes, } } func (r *Residue) Prev(x int) int { if r.nodes[x].undo != 0 { x = 0 } return r.nodes[x].prev } func (r *Residue) Next(x int) int { if r.nodes[x].undo != 0 { x = 0 } return r.nodes[x].next } func (r *Residue) Contains(x int) bool { return r.nodes[x].undo == 0 } func (r *Residue) Remove(x int) bool { if r.nodes[x].undo != 0 { return false } r.nodes[x].undo = r.nodes[0].undo r.nodes[0].undo = 0 var ( i1 = r.nodes[x].prev i2 = r.nodes[x].next ) r.nodes[i1].next = i2 r.nodes[i2].prev = i1 return true } func (r *Residue) Undo() bool { x := r.nodes[0].undo if x == -1 { return false } r.nodes[0].undo = r.nodes[x].undo r.nodes[x].undo = 0 var ( i1 = r.nodes[x].prev i2 = r.nodes[x].next ) r.nodes[i1].next = x r.nodes[i2].prev = x return true }

To receive a hint, submit unfixed code.