an input range
an input range with the cached values of range
1 import std.algorithm.comparison : equal; 2 import std.range, std.stdio; 3 import std.typecons : tuple; 4 5 ulong counter = 0; 6 double fun(int x) 7 { 8 ++counter; 9 // http://en.wikipedia.org/wiki/Quartic_function 10 return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5; 11 } 12 // Without cache, with array (greedy) 13 auto result1 = iota(-4, 5).map!(a =>tuple(a, fun(a)))() 14 .filter!(a => a[1] < 0)() 15 .map!(a => a[0])() 16 .array(); 17 18 // the values of x that have a negative y are: 19 assert(equal(result1, [-3, -2, 2])); 20 21 // Check how many times fun was evaluated. 22 // As many times as the number of items in both source and result. 23 assert(counter == iota(-4, 5).length + result1.length); 24 25 counter = 0; 26 // Without array, with cache (lazy) 27 auto result2 = iota(-4, 5).map!(a =>tuple(a, fun(a)))() 28 .cache() 29 .filter!(a => a[1] < 0)() 30 .map!(a => a[0])(); 31 32 // the values of x that have a negative y are: 33 assert(equal(result2, [-3, -2, 2])); 34 35 // Check how many times fun was evaluated. 36 // Only as many times as the number of items in source. 37 assert(counter == iota(-4, 5).length);
Tip: cache is eager when evaluating elements. If calling front on the underlying _range has a side effect, it will be observable before calling front on the actual cached _range.
Furthermore, care should be taken composing cache with std._range.take. By placing take before cache, then cache will be "aware" of when the _range ends, and correctly stop caching elements when needed. If calling front has no side effect though, placing take after cache may yield a faster _range.
Either way, the resulting ranges will be equivalent, but maybe not at the same cost or side effects.
1 import std.algorithm.comparison : equal; 2 import std.range; 3 int i = 0; 4 5 auto r = iota(0, 4).tee!((a){i = a;}, No.pipeOnPop); 6 auto r1 = r.take(3).cache(); 7 auto r2 = r.cache().take(3); 8 9 assert(equal(r1, [0, 1, 2])); 10 assert(i == 2); //The last "seen" element was 2. The data in cache has been cleared. 11 12 assert(equal(r2, [0, 1, 2])); 13 assert(i == 3); //cache has accessed 3. It is still stored internally by cache.
cache eagerly evaluates front of range on each construction or call to popFront, to store the result in a cache. The result is then directly returned when front is called, rather than re-evaluated.
This can be a useful function to place in a chain, after functions that have expensive evaluation, as a lazy alternative to std.array.array. In particular, it can be placed after a call to map, or before a call to filter.
cache may provide bidirectional range iteration if needed, but since this comes at an increased cost, it must be explicitly requested via the call to cacheBidirectional. Furthermore, a bidirectional cache will evaluate the "center" element twice, when there is only one element left in the range.
cache does not provide random access primitives, as cache would be unable to cache the random accesses. If Range provides slicing primitives, then cache will provide the same slicing primitives, but hasSlicing!Cache will not yield true (as the std._range.primitives.hasSlicing trait also checks for random access).