[Rosettacode] Growable slices

bearophile via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Thu May 15 02:00:11 PDT 2014


This task asks for an basic implementation of the the 
Lempel-Ziv-Welch (LZW) compression/decompression algorithm. I am 
keeping two D versions, the first one is minimal, and the second 
is a little more optimized:
http://rosettacode.org/wiki/LZW_compression#More_Refined_Version

There are of course ways to implement a really efficient ZLW 
compressor in D, and such implementation could be added as third 
D entry if it manages to be not too much long, but for the first 
two versions keeping the code very short is more important.

Despite the compressor in the second D entry is still not 
efficient at all, I have tried to make it not terrible regarding 
its efficiency, so I have defined a new kind of slice that can be 
extended, unlike the D slices, to avoid the string appends 
visible in the first D entry:


struct Slice {
     size_t start, end;
     @property opSlice() const pure nothrow @safe @nogc {
         return original[start .. end];
     }
     alias opSlice this;
}

Slice w;
Tcomp[] result;
foreach (immutable i; 0 .. original.length) {
     auto wc = Slice(w.start, w.end + 1); // Extend slice.
     if (wc in dict) {
         w = wc;
     } else {
         result ~= dict[w];
         assert(dict.length < Tcomp.max); // Overflow guard.
         dict[wc] = cast(Tcomp)dict.length;
         w = Slice(i, i + 1);
     }
}


Is this showing a limit (problem) of D slices, or is this design 
better written in other ways?

Bye,
bearophile


More information about the Digitalmars-d-learn mailing list