Burrows–Wheeler transform: Difference between revisions
Content added Content deleted
(Added Wren) |
|||
Line 1,755: | Line 1,755: | ||
--> ERROR: Input can't contain STX or ETX |
--> ERROR: Input can't contain STX or ETX |
||
--></pre> |
--></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}}== |
=={{header|zkl}}== |