Burrows–Wheeler transform: Difference between revisions
Added Wren
(Added Wren) |
|||
Line 1,755:
--> ERROR: Input can't contain STX or ETX
--></pre>
=={{header|Wren}}==
{{trans|Go}}
There's currently no 'sort' routine in the standard library so we have to write our own.
<lang ecmascript>// Compares two strings lexicographically by codepoint.
var cmp = Fn.new { |s1, s2|
if (s1 == s2) return 0
var cp1 = s1.codePoints
var cp2 = s2.codePoints
var len = (cp1.count < cp2.count) ? cp1.count : cp2.count
for (i in 0...len) {
if (cp1[i] < cp2[i]) return -1
if (cp1[i] > cp2[i]) return 1
}
return (cp1.count < cp2.count) ? -1 : 1
}
// Sorts a list of strings in place using quicksort algorithm.
var strSort // as recursive need to declare variable first
strSort = Fn.new { |a, s, e|
if (e <= s) return
var p = a[s]
var l = s
var r = e
while (l <= r) {
while (cmp.call(a[l], p) < 0) l = l + 1
while (cmp.call(a[r], p) > 0) r = r - 1
if (l <= r) {
var t = a[l]
a[l] = a[r]
a[r] = t
l = l + 1
r = r - 1
}
}
strSort.call(a, s, r)
strSort.call(a, l, e)
}
var stx = "\x02"
var etx = "\x03"
var bwt = Fn.new { |s|
if (s.indexOf(stx) >= 0 || s.indexOf(etx) >= 0) return null
s = stx + s + etx
var len = s.count
var table = [""] * len
table[0] = s
for (i in 1...len) table[i] = s[i..-1] + s[0...i]
strSort.call(table, 0, len - 1)
var lastChars = [""] * len
for (i in 0...len) lastChars[i] = table[i][len-1]
return lastChars.join()
}
var ibwt = Fn.new { |r|
var len = r.count
var table = [""] * len
for (i in 0...len) {
for (j in 0...len) table[j] = r[j] + table[j]
strSort.call(table, 0, len - 1)
}
for (row in table) {
if (row.endsWith(etx)) return row[1...len-1]
}
return ""
}
var makePrintable = Fn.new { |s|
// substitute ^ for STX and | for ETX to print results
s = s.replace(stx, "^")
return s.replace(etx, "|")
}
var tests = [
"banana",
"appellee",
"dogwood",
"TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
"\x02ABC\x03"
]
for (test in tests) {
System.print(makePrintable.call(test))
System.write(" --> ")
var t = bwt.call(test)
if (t == null) {
System.print("ERROR: String can't contain STX or ETX")
t = ""
} else {
System.print(makePrintable.call(t))
}
var r = ibwt.call(t)
System.print(" --> %(r)\n")
}</lang>
{{out}}
<pre>
banana
--> |annb^aa
--> banana
appellee
--> |e^elplepa
--> appellee
dogwood
--> |do^oodwg
--> dogwood
TO BE OR NOT TO BE OR WANT TO BE OR NOT?
--> |?OOORREEETTRTW BBB ATTT NNOOONOO^
--> TO BE OR NOT TO BE OR WANT TO BE OR NOT?
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
--> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
--> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
^ABC|
--> ERROR: String can't contain STX or ETX
-->
</pre>
=={{header|zkl}}==
| |||