104 lines
2.4 KiB
Text
104 lines
2.4 KiB
Text
use Collection;
|
|
|
|
class LZW {
|
|
function : Main(args : String[]) ~ Nil {
|
|
compressed := Compress("TOBEORNOTTOBEORTOBEORNOT");
|
|
Show(compressed);
|
|
decompressed := Decompress(compressed);
|
|
decompressed->PrintLine();
|
|
}
|
|
|
|
function : native : Compress(uncompressed : String) ~ IntVector {
|
|
# Build the dictionary.
|
|
dictSize := 256;
|
|
dictionary := StringMap->New();
|
|
for (i := 0; i < 256; i+=1;) {
|
|
key := "";
|
|
key->Append(i->As(Char));
|
|
dictionary->Insert(key, IntHolder->New(i));
|
|
};
|
|
|
|
w := "";
|
|
result := IntVector->New();
|
|
|
|
each (i : uncompressed) {
|
|
c := uncompressed->Get(i);
|
|
wc := String->New(w);
|
|
wc->Append(c);
|
|
if (dictionary->Has(wc)) {
|
|
w := wc;
|
|
}
|
|
else {
|
|
value := dictionary->Find(w)->As(IntHolder);
|
|
result->AddBack(value->Get());
|
|
# Add wc to the dictionary.
|
|
dictionary->Insert(wc, IntHolder->New(dictSize));
|
|
dictSize+=1;
|
|
w := "";
|
|
w->Append(c);
|
|
};
|
|
};
|
|
|
|
# Output the code for w.
|
|
if (w->Size() > 0) {
|
|
value := dictionary->Find(w)->As(IntHolder);
|
|
result->AddBack(value->Get());
|
|
};
|
|
|
|
return result;
|
|
}
|
|
|
|
function : Decompress(compressed : IntVector) ~ String {
|
|
# Build the dictionary.
|
|
dictSize := 256;
|
|
dictionary := IntMap->New();
|
|
for (i := 0; i < 256; i+=1;) {
|
|
value := "";
|
|
value->Append(i->As(Char));
|
|
dictionary->Insert(i, value);
|
|
};
|
|
|
|
w := "";
|
|
found := compressed->Remove(0);
|
|
w->Append(found->As(Char));
|
|
|
|
result := String->New(w);
|
|
each (i : compressed) {
|
|
k := compressed->Get(i);
|
|
|
|
entry : String;
|
|
if (dictionary->Has(k)) {
|
|
entry := dictionary->Find(k);
|
|
}
|
|
else if (k = dictSize) {
|
|
entry := String->New(w);
|
|
entry->Append(w->Get(0));
|
|
}
|
|
else {
|
|
return "";
|
|
};
|
|
result->Append(entry);
|
|
|
|
# Add w+entry[0] to the dictionary.
|
|
value := String->New(w);
|
|
value->Append(entry->Get(0));
|
|
dictionary->Insert(dictSize, value);
|
|
dictSize+=1;
|
|
|
|
w := entry;
|
|
};
|
|
|
|
return result;
|
|
}
|
|
|
|
function : Show(results : IntVector) ~ Nil {
|
|
"["->Print();
|
|
each(i : results) {
|
|
results->Get(i)->Print();
|
|
if(i + 1 < results->Size()) {
|
|
", "->Print();
|
|
};
|
|
};
|
|
"]"->PrintLine();
|
|
}
|
|
}
|