Rosetta Code

Burrows–Wheeler transform: Difference between revisions

Page Discussion

Burrows–Wheeler transform (view source)

Revision as of 09:17, 29 May 2020

997 bytes removed ,  3 years ago
→‎{{header|Wren}}: Now uses Wren-sort module.
(Added Wren)
(→‎{{header|Wren}}: Now uses Wren-sort module.)
Line 1,758:
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-sort}}
There's currently no 'sort' routine in the standard library so we have to write our own.
<lang ecmascript>import "// Compares two strings lexicographicallysort" byfor codepoint.Sort
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
Line 1,804 ⟶ 1,771:
table[0] = s
for (i in 1...len) table[i] = s[i..-1] + s[0...i]
strSortSort.callquick(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
Line 1,815 ⟶ 1,782:
for (i in 0...len) {
for (j in 0...len) table[j] = r[j] + table[j]
strSortSort.callquick(table, 0, len - 1)
}
for (row in table) {
Line 1,822 ⟶ 1,789:
return ""
}
 
var makePrintable = Fn.new { |s|
// substitute ^ for STX and | for ETX to print results
Line 1,828 ⟶ 1,795:
return s.replace(etx, "|")
}
 
var tests = [
"banana",
Line 1,877 ⟶ 1,844:
-->
</pre>
 
 
=={{header|zkl}}==
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/283590"