Skip to content

Instantly share code, notes, and snippets.

@johandahlberg
Last active December 12, 2015 04:49
Show Gist options
  • Save johandahlberg/4717504 to your computer and use it in GitHub Desktop.
Save johandahlberg/4717504 to your computer and use it in GitHub Desktop.
Naive functional implementation of Burrows-Wheels transform in scala
import scala.math.Ordering
object SimpleBW extends App {
def bwt(s: String): String = {
def tranformString(string: String): List[String] = { transformString(string, string.length) }
def transformString(string: String, splitIndex: Int): List[String] = {
if (splitIndex == 0) {
// Recursion base case
Nil
} else {
val (firstString, secondString) = string.splitAt(splitIndex)
val newString = secondString + firstString
newString :: transformString(string, splitIndex - 1)
}
}
val list: List[String] = tranformString(s);
val sortedList = list.sortWith((x, y) => { x <= y })
val lastColumn = sortedList.map(row => row.last).mkString
lastColumn
}
def inverseBwt(s: String): String = {
def createTable(s: String): String = {
val length = s.length
println(length)
createTableFromString(s, length, new Array[String](length))
}
def createTableFromString(column: String, l: Int, table: Array[String]): String = {
if(l == 0){
val indexOfRowToGet = table(s.length-1).indexOf("|")
val row = table.map(s => s(indexOfRowToGet)).mkString
table.foreach(println)
row
//table.filterNot(s => s.charAt(s.length-1).toString.equals("|")).mkString//table.filterNot(s: String => s.last.toString.equals("|")).mkString
}
else{
table(l-1) = column
// Sort table by rows
table.map(s => s.toCharArray()).
createTableFromString(column, l -1, table)
}
}
createTable(s)
}
// list.sorted(scala.Math.Ordering.)
// list.sort((a: String, b: String) => compareStringWithStartAndEndCharacter(a.first, b.first))
val string = "^BANANA|"
println("bwt: " + bwt(string))
println("bwt: " + inverseBwt(bwt(string)))
//
// val bwt: String = list.map(s => s.last).mkString;
// println("bwt is: " + bwt);
//
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment