# Rosalind: BA9I — Construct the Burrows-Wheeler Transform of a String
# https://rosalind.info/problems/ba9i/
#
# Given: A string Text.
# Return: BWT(Text).

let text = "GCGTGCCTGGTCA$"

# The BWT is the last column of the sorted rotations — but sorting rotations is
# the same as sorting suffixes when the string ends in a sentinel, so the suffix
# array gives it directly: the character just before each sorted suffix.
let n = len(text)
let sa = suffix_array(text)
let bwt = sa |> map(|i| substr(text, (i + n - 1) % n, 1)) |> join("")

println("Result:   " + bwt)
println("Expected: ACTGGCT$TGCGGC")

fn test_ba9i_burrows_wheeler_transform() {
    assert bwt == "ACTGGCT$TGCGGC", "BA9I: got " + bwt
    # A permutation of the input, which is what makes it invertible.
    assert len(bwt) == n, "BA9I: wrong length"
    assert sort(chars(bwt)) == sort(chars(text)), "BA9I: not a permutation of the input"
}