Regarding ranges

[bearophile]

The type system knows the length of a fixed size array at 
compile-time, but to call a function that accepts ranges you have 
to slice it. So you are throwing away some compile-time 
information. This is rather bad, because such information is 
useful for the compiler to produce more optimized code 
(especially when the array is small) or to detect some out of 
array bound errors at compile time instead of at run time. Who 
knows what Alexander Stepanov thinks about this :-)

The usual work around to avoid this problem in D is to add 
overloads that accept fixed sized arrays as inputs.

Regarding ranges, as Andrei says the main restriction of a range 
is that it can always shrink, never grow.

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 useless 
heap-allocations managing a Slice that is able to grow (In some 
of my benchmarks compress2 is about twice faster than compress1). 
Do you know if it's 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