74 lines
2.2 KiB
Groovy
74 lines
2.2 KiB
Groovy
class BWT {
|
|
private static final String STX = "\u0002"
|
|
private static final String ETX = "\u0003"
|
|
|
|
private static String bwt(String s) {
|
|
if (s.contains(STX) || s.contains(ETX)) {
|
|
throw new IllegalArgumentException("String cannot contain STX or ETX")
|
|
}
|
|
|
|
String ss = STX + s + ETX
|
|
List<String> table = new ArrayList<>()
|
|
for (int i = 0; i < ss.length(); i++) {
|
|
String before = ss.substring(i)
|
|
String after = ss.substring(0, i)
|
|
table.add(before + after)
|
|
}
|
|
Collections.sort(table)
|
|
|
|
StringBuilder sb = new StringBuilder()
|
|
for (String str : table) {
|
|
sb.append(str[str.length() - 1])
|
|
}
|
|
return sb.toString()
|
|
}
|
|
|
|
private static String ibwt(String r) {
|
|
int len = r.length()
|
|
List<String> table = new ArrayList<>()
|
|
for (int i = 0; i < len; ++i) {
|
|
table.add("")
|
|
}
|
|
for (int j = 0; j < len; ++j) {
|
|
for (int i = 0; i < len; ++i) {
|
|
table[i] = r[i] + table[i]
|
|
}
|
|
Collections.sort(table)
|
|
}
|
|
for (String row : table) {
|
|
if (row.endsWith(ETX)) {
|
|
return row.substring(1, len - 1)
|
|
}
|
|
}
|
|
return ""
|
|
}
|
|
|
|
private static String makePrintable(String s) {
|
|
// substitute ^ for STX and | for ETX to print results
|
|
return s.replace(STX, "^").replace(ETX, "|")
|
|
}
|
|
|
|
static void main(String[] args) {
|
|
List<String> tests = new ArrayList<>()
|
|
tests.add("banana")
|
|
tests.add("appellee")
|
|
tests.add("dogwood")
|
|
tests.add("TO BE OR NOT TO BE OR WANT TO BE OR NOT?")
|
|
tests.add("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES")
|
|
tests.add("\u0002ABC\u0003")
|
|
|
|
for (String test : tests) {
|
|
println(makePrintable(test))
|
|
print(" --> ")
|
|
String t = ""
|
|
try {
|
|
t = bwt(test)
|
|
println(makePrintable(t))
|
|
} catch (IllegalArgumentException e) {
|
|
println("ERROR: " + e.getMessage())
|
|
}
|
|
String r = ibwt(t)
|
|
printf(" --> %s\n\n", r)
|
|
}
|
|
}
|
|
}
|