Ranges usages

[bearophile]

(This is a partial repost from D.learn.)

Some time ago after Andrei Alexandrescu talk "Iterators must Go" 
someone asked about implementing the Dutch national flag sort 
algorithm with D ranges. This is a version of mine (but 
unfortunately currently I can't try it on the Dlist of Phobos), 
it looks short but for me it wasn't immediate to write:


void dutchNationalFlagSort(Range, T)(Range secondLast,
                                      in T lowVal, in T highVal)
pure nothrow if (isBidirectionalRange!Range &&
                  hasSwappableElements!Range &&
                  is(ElementType!Range == T)) {
     for (auto first = secondLast; !secondLast.empty; )
         if (secondLast.front == lowVal) {
             swap(first.front, secondLast.front);
             first.popFront();
             secondLast.popFront();
         } else if (secondLast.front == highVal) {
             swap(secondLast.front, secondLast.back);
             secondLast.popBack();
         } else
             secondLast.popFront();
}


In the following program there are two versions of the compress 
function, that implement the same bare-bones version of the LZW 
(http://en.wikipedia.org/wiki/Lempel-Ziv-Welch ) compression 
algorithm.

compress1 is the simpler version, while compress2 avoids some 
heap allocations using a Slice that is able to grow (in some of 
my benchmarks compress2 is about twice faster than compress1).

Is it possible to write similar code nicely & efficiently with 
ranges?


import std.stdio, std.array;

alias T = ubyte;
alias Ta = immutable(T)[];

int[] compress1(immutable T[] original) {
     int[Ta] dictionary;
     foreach (i; 0 .. 256)
         dictionary[cast(Ta)[i]] = i;

     Ta w;
     int[] result;
     foreach (ch; original) {
         auto wc = w ~ ch;
         if (wc in dictionary) {
             w = wc;
         } else {
             result ~= dictionary[w];
             dictionary[wc] = dictionary.length - 1;
             w = [ch];
         }
     }

     return w.empty ? result : (result ~ dictionary[w]);
}

int[] compress2(immutable T[] original) {
     int[Ta] dictionary;
     foreach (i; 0 .. 256)
         dictionary[cast(Ta)[i]] = i;

     struct Slice {
         size_t start, end;
         @property opSlice() {
             return original[start .. end];
         }
         alias this = opSlice;
     }

     Slice w;
     int[] result;
     foreach (i; 0 .. original.length) {
         auto wc = Slice(w.start, w.end + 1);
         if (wc in dictionary) {
             w = wc;
         } else {
             result ~= dictionary[w];
             dictionary[wc] = dictionary.length - 1;
             w = Slice(i, i + 1);
         }
     }

     return w.empty ? result : (result ~ dictionary[w]);
}

void main() {
     auto txt = cast(Ta)"TOBEORNOTTOBEORTOBEORNOT";
     writeln(compress1(txt));
     writeln(compress2(txt));
}


Thank you,
bye,
bearophile