61 lines
1.5 KiB
Kotlin
61 lines
1.5 KiB
Kotlin
// Version 1.2.60
|
|
|
|
const val STX = "\u0002"
|
|
const val ETX = "\u0003"
|
|
|
|
fun bwt(s: String): String {
|
|
if (s.contains(STX) || s.contains(ETX)) {
|
|
throw RuntimeException("String can't contain STX or ETX")
|
|
}
|
|
val ss = STX + s + ETX
|
|
val table = Array<String>(ss.length) { ss.substring(it) + ss.substring(0, it) }
|
|
table.sort()
|
|
return String(table.map { it[it.lastIndex] }.toCharArray())
|
|
}
|
|
|
|
fun ibwt(r: String): String {
|
|
val len = r.length
|
|
val table = Array<String>(len) { "" }
|
|
repeat(len) {
|
|
for (i in 0 until len) {
|
|
table[i] = r[i].toString() + table[i]
|
|
}
|
|
table.sort()
|
|
}
|
|
for (row in table) {
|
|
if (row.endsWith(ETX)) {
|
|
return row.substring(1, len - 1)
|
|
}
|
|
}
|
|
return ""
|
|
}
|
|
|
|
fun makePrintable(s: String): String {
|
|
// substitute ^ for STX and | for ETX to print results
|
|
return s.replace(STX, "^").replace(ETX, "|")
|
|
}
|
|
|
|
fun main(args: Array<String>) {
|
|
val tests = listOf(
|
|
"banana",
|
|
"appellee",
|
|
"dogwood",
|
|
"TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
|
|
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
|
|
"\u0002ABC\u0003"
|
|
)
|
|
for (test in tests) {
|
|
println(makePrintable(test))
|
|
print(" --> ")
|
|
var t = ""
|
|
try {
|
|
t = bwt(test)
|
|
println(makePrintable(t))
|
|
}
|
|
catch (ex: RuntimeException) {
|
|
println("ERROR: " + ex.message)
|
|
}
|
|
val r = ibwt(t)
|
|
println(" --> $r\n")
|
|
}
|
|
}
|