Burrows–Wheeler transform: Difference between revisions

=={{header|C#|C sharp}}==

{{trans|D}}

<lang csharp>using System;

using System.Collections.Generic;

using System.Linq;

namespace BurrowsWheeler {

class Program {

const char STX = (char)0x02;

const char ETX = (char)0x03;

private static void Rotate(ref char[] a) {

char t = a.Last();

for (int i = a.Length - 1; i > 0; --i) {

a[i] = a[i - 1];

}

a[0] = t;

}

// For some reason, strings do not compare how whould be expected

private static int Compare(string s1, string s2) {

for (int i = 0; i < s1.Length && i < s2.Length; ++i) {

if (s1[i] < s2[i]) {

return -1;

}

if (s2[i] < s1[i]) {

return 1;

}

}

if (s1.Length < s2.Length) {

return -1;

}

if (s2.Length < s1.Length) {

return 1;

}

return 0;

}

static string Bwt(string s) {

if (s.Any(a => a == STX || a == ETX)) {

throw new ArgumentException("Input can't contain STX or ETX");

}

char[] ss = (STX + s + ETX).ToCharArray();

List<string> table = new List<string>();

for (int i = 0; i < ss.Length; ++i) {

table.Add(new string(ss));

Rotate(ref ss);

}

table.Sort(Compare);

return new string(table.Select(a => a.Last()).ToArray());

}

static string Ibwt(string r) {

int len = r.Length;

List<string> table = new List<string>(new string[len]);

for (int i = 0; i < len; ++i) {

for (int j = 0; j < len; ++j) {

table[j] = r[j] + table[j];

}

table.Sort(Compare);

}

foreach (string row in table) {

if (row.Last() == ETX) {

return row.Substring(1, len - 2);

}

}

return "";

}

static string MakePrintable(string s) {

return s.Replace(STX, '^').Replace(ETX, '|');

}

static void Main() {

string[] tests = new string[] {

"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"

};

foreach (string test in tests) {

Console.WriteLine(MakePrintable(test));

Console.Write(" --> ");

string t = "";

try {

t = Bwt(test);

Console.WriteLine(MakePrintable(t));

} catch (Exception e) {

Console.WriteLine("ERROR: {0}", e.Message);

}

string r = Ibwt(t);

Console.WriteLine(" --> {0}", r);

Console.WriteLine();

}

}

}

}</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: Input can't contain STX or ETX

--></pre>