BurrowsWheelerTransform.scala

/**
 * Implemented from the algorithm taught in
 * Burrows-Wheeler Transform (Ep 4, Compressor Head) Google
 * https://www.youtube.com/watch?v=4WRANhDiSHM
 */ 

object BurrowsWheelerTransform {
  def transform(s: String): (String, Int) = {
    val shifted: Iterator[String] = (s + s).tail.sliding(s.length)
    val sorted: Array[String] = shifted.toArray.sortWith(_<_)
    val index: Int = sorted.indexOf(s)
    val encoded: String = sorted.map(_.last).mkString("")
    (encoded, index)
  }
  import scala.math.Ordering.Implicits._
  def invert(s: String, i: Int): String = {
    val emptyCharList: List[Char] = Nil
    val table: Array[List[Char]] = Array.fill(s.length)(emptyCharList)
    var j, k = 0
    while(j < s.length) {
      k = 0
      while(k < table.length) {
        table(k) = s(k) :: table(k)
        k += 1
      }
      scala.util.Sorting.quickSort(table)
      j += 1
    }
    table(i).mkString("")
  }
}

object ScalaJSExample extends js.JSApp{
  def main(): Unit = {
    println(
      p(
        "Implemented from the algorithm taught in ",
        a(href:="http://www.scala-js.org/", "Burrows-Wheeler Transform (Ep 4, Compressor Head) Google"),
        "."
      )
    )

    val original = "There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable. There is another theory which states that this has already happened."
    //val original = "Banana"
    println("Original:")
    println(s"$original")
    println("...")
    println("Transforming...")
    val (transformed, index) = BurrowsWheelerTransform.transform(original)
    println(s"$transformed")
    println(s"index = $index")
    println("...")
    println("Inverting...")
    val inverted = BurrowsWheelerTransform.invert(transformed, index)
    println(s"$inverted")
  }
}