[Rosettacode] Growable slices

[monarch_dodra via Digitalmars-d-learn]

On Thursday, 15 May 2014 at 09:00:13 UTC, bearophile wrote:
> 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

I don't think it shows a limit of "slices" in and out of itself, 
but rather the whole "range" concept, that conveniently 
encapsulates a start/end iteration scheme.

The problem though is that, unlike iterators, these can only 
shrink, and never grow. Furthermore, it is usally hard to "split" 
a range into two parts, given a center iterator (especially for 
bidirectional-only ranges: EG: linked list).

I think ranges/slices still provide more functionality and are 
worth it, but they do sacrifice *some* power: Growth and 
splitting.

To be honest, what you are doing is essentially working with 
iterator pairs, disguised as indexes inside a "Slice" struct. Not 
that there's anything wrong with that, but that's my impression 
when looking at the code.

Related:
http://forum.dlang.org/thread/bhssgxfcscfbionhqcmn@forum.dlang.org#post-umxlhsfqmfjwydemfdeb:40forum.dlang.org
http://forum.dlang.org/thread/gpsiwnslxtsyfolymesc@forum.dlang.org#post-mailman.2149.1353648522.5162.digitalmars-d:40puremagic.com