#!/bin/sh -eu
# Burrows-Wheeler transform
# <https://en.wikipedia.org/wiki/Burrows-Wheeler_transform>
TXT=$( tr '\n' '\032'; printf '\177' )
IFS='
'

make_all_rotations() {
 INPUT=${1}
 OUTPUT=${INPUT}
 for J in $(seq "${#INPUT}"); do
  PREFIX="${OUTPUT%?}"
  SUFFIX="${OUTPUT#"${PREFIX}"}"
  OUTPUT="${SUFFIX}${PREFIX}"
  printf '%s\n' "${OUTPUT}"
  PERCENTAGE=$(( ( ${J} * 100 ) / ${#INPUT} ))
  >&2 printf '\r%s%% (%s/%s)' "${PERCENTAGE}" "${J}" "${#INPUT}"
 done
 >&2 printf '\n'
}

make_all_rotations "${TXT}" \
 |LC_ALL=C sort \
 |cut -c ${#TXT} \
 |tr -d '\n' \
 |tr '\032' '\n'