50 lines
1.5 KiB
D
50 lines
1.5 KiB
D
import std.stdio, std.string, std.ascii, std.algorithm;
|
|
|
|
ptrdiff_t[] mtfEncoder(in string data) pure nothrow @safe
|
|
in {
|
|
assert(data.countchars("a-z") == data.length);
|
|
} out(result) {
|
|
assert(result.length == data.length);
|
|
assert(result.all!(e => e >= 0 && e < lowercase.length));
|
|
} body {
|
|
ubyte[lowercase.length] order = lowercase.representation;
|
|
auto encoded = new typeof(return)(data.length);
|
|
|
|
size_t i = 0;
|
|
foreach (immutable b; data) {
|
|
immutable j = encoded[i++] = order[].countUntil(b);
|
|
bringToFront(order[0 .. j], order[j .. j + 1]);
|
|
}
|
|
|
|
return encoded;
|
|
}
|
|
|
|
string mtfDecoder(in ptrdiff_t[] encoded) pure nothrow @safe
|
|
in {
|
|
assert(encoded.all!(e => e >= 0 && e < lowercase.length));
|
|
} out(result) {
|
|
assert(result.length == encoded.length);
|
|
assert(result.countchars("a-z") == result.length);
|
|
} body {
|
|
ubyte[lowercase.length] order = lowercase.representation;
|
|
auto decoded = new char[encoded.length];
|
|
|
|
size_t i = 0;
|
|
foreach (immutable code; encoded) {
|
|
decoded[i++] = order[code];
|
|
bringToFront(order[0 .. code], order[code .. code + 1]);
|
|
}
|
|
|
|
return decoded;
|
|
}
|
|
|
|
void main() {
|
|
foreach (immutable word; ["broood", "bananaaa", "hiphophiphop"]) {
|
|
immutable encoded = word.mtfEncoder;
|
|
immutable decoded = encoded.mtfDecoder;
|
|
writefln("'%s' encodes to %s, which decodes back to '%s'",
|
|
word, encoded, decoded);
|
|
assert(word == decoded);
|
|
}
|
|
}
|