$ include "seed7_05.s7i";

const func string: burrowsWheelerTransform (in string: stri) is func
  result
    var string: encoded is "";
  local
    var integer: length is 0;
    var integer: index is 0;
    var array string: rotations is 0 times "";
  begin
    length := succ(length(stri));
    rotations := length times "";
    for index range 1 to length do
      rotations[index] := stri[index ..] & "\256;" & stri[.. pred(index)];
    end for;
    rotations := sort(rotations);
    for index range 1 to length do
      encoded &:= rotations[index][length];
    end for;
  end func;

const func string: inverseBurrowsWheelerTransform (in string: stri) is func
  result
    var string: decoded is "";
  local
    var integer: length is 0;
    var integer: count is 0;
    var integer: index is 0;
    var array string: rotations is 0 times "";
  begin
    length := length(stri);
    rotations := length times "";
    for count range 1 to length do
      for index range 1 to length do
        rotations[index] := str(stri[index]) & rotations[index];
      end for;
      rotations := sort(rotations);
    end for;
    decoded := rotations[1];
    index := pos(decoded, "\256;");
    decoded := decoded[succ(index) ..] & decoded[.. pred(index)];
  end func;

const proc: test(in string: stri) is func
  local
    var string: encoded is "";
    var string: decoded is "";
  begin
    writeln;
    writeln("     " <& stri);
    encoded := burrowsWheelerTransform(stri);
    writeln("---> " <& literal(encoded));
    decoded := inverseBurrowsWheelerTransform(encoded);
    writeln("---> " <& decoded);
  end func;

const proc: main is func
  begin
    test("banana");
    test("appellee");
    test("dogwood");
    test("TO BE OR NOT TO BE OR WANT TO BE OR NOT?");
    test("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES");
  end func;