BUGFIX-66

Bug 12: Bungled Burrows-Wheeler Transform

The BWT reorders a sequence of bytes to simplify compression. The inverse transform is efficient.
This code sorts a slice of integers. Each integer is an offset into the (length n) input slice a.
These n integers are sorted lexicographically according to the byte sequences they represent.
Integer i represents the (length n) byte sequence a[i], a[i+1], ..., a[n-1], a[0], ..., a[i-2], a[i-1].
For each integer i in this sorted order, the code outputs byte a[i-1].
The effect is that the input bytes are reordered according to the contexts in which they occur.

Fix The Tiny Bug In This Go Code:

func bwt(a []byte) ([]byte, int) { var ( n = len(a) x = make([]int, n) ) for i := range x { x[i] = i } less := func(i1, i2 int) bool { if i1 < i2 { len1 := n - i2 cmp1 := bytes.Compare(a[i1:i1+len1], a[i2:]) if cmp1 != 0 { return cmp1 < 0 } len2 := i2 - i1 cmp2 := bytes.Compare(a[i1+len1:], a[:len2]) if cmp2 != 0 { return cmp2 < 0 } cmp3 := bytes.Compare(a[:i1], a[len2:i2]) return cmp3 < 0 } len1 := n - i1 cmp1 := bytes.Compare(a[i1:], a[i2:i2+len1]) if cmp1 != 0 { return cmp1 < 0 } len2 := i1 - i2 cmp2 := bytes.Compare(a[:len2], a[i2+len1:]) if cmp2 != 0 { return cmp2 < 0 } cmp3 := bytes.Compare(a[len2:i1], a[:i2]) return cmp3 < 0 } sort.Slice(x, less) var ( last = make([]byte, n) root int ) for i, x := range x { if x == 0 { x = n root = i } last[i] = a[x-1] } return last, root }

To receive a hint, submit unfixed code.