101 lines
3.0 KiB
C#
101 lines
3.0 KiB
C#
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();
|
|
}
|
|
}
|
|
}
|
|
}
|