dranges.algorithm
This module contains functions akin to map and filter , found in std.
algorithm
.
You'll find there generalizations of these functions to act on a variadic numbers
of ranges in parallel (tmap , tfilter ) or to map nary functions on a range (nmap , nfilter ).
There are also many function inspired by the sequence/list/map libraries of other (functional) programming
languages (namely, Haskell, Clojure, Scala, Python) : a range comprehension,
zipping ranges, reduceR , fold /foldR , scan /scanR , and so on.
As far as possible, all higherorder ranges presented in this module
and in dranges.range are 'tight wrappers': they are bidirectional if their input range is bidirectional,
define opIndex , opIndexAssign , length if it's possible, etc. That way, a good input range (for example, a randomaccess range)
will see its properties propagated through a chain of calls.
License:
Boost License 1.0.
Authors:
Philippe Sigaud
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 ElementType!(R)
sum
(R)(R range);
ElementType!(R)
product
(R)(R range);
ElementType!(R)
maxOf
(R)(R range);
ElementType!(R)
minOf
(R)(R range);
 Small oneliners to use reduce. Sum and product work on empty ranges (they return 0 and 1, respectively),
but not minOf and maxOf.
Example:
auto r1 = [1,2,3,4,5];
auto r2 = [1.0,2.7818281828, 3.1415926];
assert(sum(r1) == 1+2+3+4+5);
assert(product(r1) == 1*2*3*4*5);
assert(minOf(r2) == 1.0);
assert(maxOf(r2) == 3.1415926);
 size_t[ElementType!(R)]
frequency
(R)(R range);
 Returns an associative array containing the number of times each element
is present in the range. It's a greedy algorithm: it does not work
on infinite ranges.
Example:
auto r = "Mississippi";
auto f = frequency(r);
assert(f['i'] == 4);
assert(f['s'] == 4);
assert(f['M'] == 1);
 NMapType!(fun,R)
nmap
(alias fun, R)(R range);
 Maps a nary function on a range, taking nelements segment at a time. You can use
standard functions or 'string' functions. For string functions, it will automatically determine their arity.
Examples:
auto r1 = [0,1,2,3,4,5,6];
auto nm1 = nmap!"a*b"(r1); // Will map "a*b" on (0,1), (1,2), (2,3), (3,4), (4,5), (5,6)
assert(equal(nm1, [0,2,6,12,20,30][]));
// Will map "a*b*c"/"a+b+c" alternatively on (0,1,2), (1,2,3), (2,3,4), (3,4,5), (4,5,6)
auto nm2 = nmap!"a%2 == 0 ? a*b*c : a+b+c"(r1);
assert(equal(nm2, [0,6,24,12,120][]));
auto nm3 = nmap!"a"(r1); // Will map "a" on (0), (1), (2), ...
assert(equal(nm3, [0,1,2,3,4,5,6][])); // Completly equivalent to map!"a"(r1)
int[] e;
auto nm4 = nmap!"a%2 == 0 ? a*b*c : a+b+c"(e); // e is empty > cannot map a ternary function on it
assert(nm4.empty);
 TMapType!(fun,R)
tmap
(alias fun, R...)(R ranges);
TMapType!(fun,R)
tmap
(alias fun, R)(R r);
 Maps a nargs function on either n ranges in parallel or on an ntuple producing range.
Examples:
// With functions mapped on n ranges in parallel:
auto r1 = [1,2,3,4,5,6];
string s = "abcdefghijk";
auto tm1 = tmap!"replicate(a,b)"(r1,s); // [a], [b,b], [c,c,c], [d,d,d,d], ...
assert(equal(flatten(tm1), "abbcccddddeeeeeffffff")); // Note the use of flatten
auto tm2 = tmap!"a%2 == 0 ? b : '_'"(r1,s); // alternate between a char from s and '_'
assert(equal(tm2, "_b_d_f"));
auto tm3 = tmap!"a%2==0 ? b : c"(r1,s,flatten(tm1)); // ternary function mapped on three ranges in parallel
assert(equal(tm3, "abbdcf"));
string e = "";
assert(tmap!"a"(r1, s, e).empty); // e is empty > tmap also
Examples:
// With functions mapped on a tupleproducing range:
auto tf = tfilter!"a%2"(r1, s); // keeps the odd elements from r1, produces 2tuples (1,'a'),(3,'c'),(5,'e')
string foo(int a, char b) { return to!string(array(replicate(a,b)));}
auto tm4 = tmap!foo(tf); // maps a standard binary function on a 2tuple range
assert(equal(tm4, ["a","ccc","eeeee"][]));
auto r2 = [1,2,3][];
// combinations(r2,r2) is equivalent to [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)][]
auto combs = tmap!"a*b"(combinations(r2,r2));
assert(equal(combs, [1,2,3,2,4,6,3,6,9][]));
 NFilterType!(fun,step,R)
nfilter
(alias fun, size_t step = 1, R)(R range);

nfilter
takes a nargs predicate and a range and outputs the nuplets that verify the predicate.
As with other nargs functions on ranges (dropWhile, takeWhile, nmap, ...) it accepts
'string' functions and adapts its behavior accordingly.
It also takes an optional step argument, defaulting to 1 (see the examples).
To use it easily with other ranges,
nfilter
produces tuples, not arrays.
That also means that if you use a unary predicate it will produce the same
values than std.algorithm.filter but wrapped in a tuple. (tuple(1), ...)
TODO:
Fuse the arrayreturning version and the tuplereturning version and control the behavior with a policy. Do that also
with the sibling functions: dropWhile, takeWhile, nmap.
Example:
auto r1 = [0,1,2,3,3,5,4,3,2,1,0];
int foo(int a, int b, int c) { return a<=b && b<=c;} // increase on three elements
auto nf1 = nfilter!(foo)(r1);
assert(equal(nf1, [tuple(0,1,2), tuple(1,2,3), tuple(2,3,3), tuple(3,3,5)][]));
auto nf2 = nfilter!"a<=b && b<=c"(r1); // The same with a string function.
// Automatically deduces that the predicate is a 3args function.
assert(equal(nf2, [tuple(0,1,2), tuple(1,2,3), tuple(2,3,3), tuple(3,3,5)][]));
auto nf3 = nfilter!("a == b1  a == b+1", 2)(r1); // step of 2, will test (0,1) (2,3), (3,5), (4,3), (2,1)
assert(equal(nf3, [tuple(0,1), tuple(2,3), tuple(4,3), tuple(2,1)][]));
auto nf4 = nfilter!"a>100"(r1); // this predicate is always false
assert(nf4.empty); // the filtered range is empty.
 TFilterType!(fun,R)
tfilter
(alias fun, R...)(R ranges);
TFilterType!(fun,R)
tfilter
(alias fun, R)(R range);

tfilter
stands for tuplefilter: it either filters a variadic list of ranges in lockstep,
with a nargs predicate spanning all ranges or filters a tuplereturning range with a function.
In all cases, it returns the ntuples that satisfy the predicate.
It can take standard functions or 'string' functions.
The first arg will be filled with the front from the first field or range element, the second arg with the second field or range and so on.
That's a,b,c,d... for a string function.
Examples:
// Filtering n ranges in parallel
auto r1 = [ 0, 1, 2, 3, 4, 5];
auto r2 = [ 3.0, 4.0, 5.0, 6.0];
string[] r3 = ["a", "b", "cc"];
// standard function
bool pred(int a, double b, string c) { return (a<b) && (c.length>1);}
auto tf1 = tfilter!(pred)(r1,r2,r3);
assert(equal(tf1, [tuple(2, 5.0, "cc")][])); // tf1 is just (2, 5.0, "cc)
// string function
auto tf2 = tfilter!"a<b && c.length>1"(r1,r2,r3); // knows arity must be 3. Will instantiate the (int,double,string) version
assert(equal(tf2, [tuple(2, 5.0, "cc")][])); // tf2 is equal to tf1
auto tf3 = tfilter!"a*a>b"(r1, r2);
assert(equal(tf3, [tuple(3, 6.0)][])); // Only one tuple satisfies a*a>b before reaching the end of r2
// templated predicate
bool pred2(T,U)(T t, U u) { return t*t>u;}
auto tf4 = tfilter!(pred2!(int, double))(r1, r2); // it doesn't automatically instantiate the correct function from a template.
assert(equal(tf4, [tuple(3,6.0)][])); // because tfilter has no way to know which types the template is waiting for.
Example:
// Filtering a tuplereturning range with a function:
// combinations(r1,r3) is equivalent to [(0,"a"),(0,"b"),(0,"cc"),(1,"a), ..., (5,"a),(5,"b),(5,"cc")][]
auto tf5 = tfilter!"a%2 && b.length>1"(combinations(r1,r3));
assert(equal(tf5, [tuple(1,"cc"),tuple(3,"cc"),tuple(5,"cc")][]));
 template
reduceR
(fun...)
 The complementary function to reduce: it reduces a (bidirectional) range from the right
reduce!fun(seed, range) applies successively the binary function fun
to the left elements of range (beginning with seed)
and produces fun(fun(... fun(fun(seed, range.front), range[1])...)).
By comparison,
reduceR
!fun(seed, range) applies successively fun to the right elements of range (also beginning
with seed or range.back, if seed is not given) and produces: fun(fun(... fun(range[$2], fun(range.back, seed)) ...)).
If fun is not a commutative operation (that is, if fun(a,b) != fun(b,a) in general), then
reduceR
will
produce different results from reduce. See for example the lines with reduce!"a/b" and
reduceR
!"a/b".
Like reduce, it accepts many functions at the same time. In that case, the result is a tuple of the different values.
Note:
It's completly based on std.algorithm.reduce's code.
Example:
auto a = [ 3, 4 ];
auto r = reduce!("a + b")(0, a);
assert(r == 7);
auto rR = reduceR!("a + b")(0, a); // a+b is commutative > same result than reduce
assert(rR == 7);
r = reduce!"a+b"(a);
assert(r == 7);
rR = reduceR!"a+b"(a); // Without seed value
assert(rR == 7);
auto a2 = [1.0,2.0,3.0,4.0];
auto r2 = reduce!"a / b"(a2);
assert(r2 == (((1.0)/2.0)/3.0)/4.0 );
auto rR2 = reduceR!"a / b"(a2);
assert(rR2 == 1.0/(2.0/(3.0/(4.0))) ); // a/b is not a commutative operation
a = [ 1, 2, 3, 4, 5 ];
// Stringize with commas
// the function has been 'symmetrized' compared to reduce's unittest
string rep = reduce!("to!string(a) ~ `, ` ~ to!(string)(b)")("", a);
assert(rep[2 .. $] == "1, 2, 3, 4, 5");
string repR = reduceR!("to!string(a) ~ `, ` ~ to!string(b)")("", a);
assert(repR[0 .. $2] == "1, 2, 3, 4, 5");
// Continued fraction
double continuedFraction(double a, double b) { return a + 1.0/b;}
auto piFrac = [3, 7, 15, 1, 292]; // pi continued fraction,
// 3.141592 is approx. 3 + 1/(7 + 1/(15 + 1/(1 + 1/(292 + 1/...))))
auto pi2 = reduceR!continuedFraction(piFrac); // calculates the continued fraction: needs reduceR as reduce wouldn't make it
assert(approxEqual(pi2, PI)); // check
 struct
Iterate
(alias fun,S);
Iterate!(fun,S)
iterate
(alias fun, S)(S seed);
 Given a function fun and a seed value, iterate repeatedly applies fun
and produces the infinite range seed, fun(seed), fun(fun(seed)), fun(fun(fun(seed))), ...
opIndex is defined, but may take some time (if you ask for a high index).
Example:
// Generating the natural numbers
auto natural = iterate!"a+1"(0); // 0,1,2,3,4,5, (as ints)
assert(equal(take(5, natural), [0,1,2,3,4][]));
// Generating powers of two
auto powersOf(size_t n)() { return iterate!(to!string(n) ~ "*a")(1L); // 1, n, n*n, n*n*n, n*n*n*n (as longs)
assert(equal(take(5, powersOf!2), [1,2,4,8,16][]));
assert(powersOf!2[10] == 1024); // opIndex is defined
// Converging on a value
// (x+n/x)/2 applied repeatedly converges towards sqrt(n)
auto sqrtOf(size_t n)() {
return iterate!Format("(a + %s/a)/2", n)(1.0);
}
auto sqrt2 = sqrtOf!2; // Converges towards sqrt(2), 1.414
popFrontN(sqrt2, 4); // letting it converge
assert(approxEqual(sqrt2.front, sqrt(2.0), 0.0000001)); // 5 iterations, already quite good
// Conway's 'Look and Say' sequence
// http://en.wikipedia.org/wiki/Look_and_say_sequence
int[] LookAndSay(int[] r) {
int[] e;
return reduce!"a ~ b.field[1] ~ b.field[0]"(e, std.algorithm.group(r));
}
auto conwaySequence = iterate!LookAndSay([1][]);
assert(equal(take(6, conwaySequence), [[1][], /+ One 1 +/
[1,1][], /+ Two 1s +/
[2,1][], /+ One 2, one 1+/
[1,2,1,1][], /+ One 1, one 2, two 1s+/
[1,1,1,2,2,1][],/+ Three 1s, two 2s, one 1+/
[3,1,2,2,1,1][]
][]));
 struct
Scan
(alias fun,S,R) if (isForwardRange!(R));
Scan!(fun,S,R)
scan
(alias fun, S, R)(S seed, R range);
Scan!(fun,ElementType!(R),R)
scan
(alias fun, R)(R range);
 A range that produces the successive result of reduce!fun(seed, range).
[seed, fun(seed, range.front), fun(fun(seed, range.front), range[1]), ...]
It's useful to get moving calculations, like moving sums, products, minima, etc.
Taken from Haskell.
Note:
only the onefunction version is implemented. scan!(max, min, foo)(r) is not possible right now,
though not difficult to code...
Example:
// moving sum
auto r1 = [1,2,3,4];
auto s = scan!"a+b"(0,r1);
assert(equal(s, [0,1,3,6,10][])); // 0, 0+1, 0+1+2, 0+1+2+3, 0+1+2+3+4
s = scan!"a+b"(r1);
assert(equal(s, [1,3,6,10][])); // 1, 1+2, 1+2+3, 1+2+3+4
// factorials
auto fac = scan!"a*b"(1L, numbers(1)); // numbers(1) is 1,2,3,4,5,6,...
assert(equal(take(fac,6), [1,1,2,6,24,120][])); // 1, 1*1, 1*1*2, 1*1*2*3, 1*1*2*3*4, 1*1*2*3*4*5
//Moving minima
auto r2 = [1,2, 1, 4, 0, 3, 4];
auto r = scan!min(0,r2);
assert(equal(r, [0,0,0,1,4,4,4,4][]));
r = scan!min(r2);
assert(equal(r, [1,1,1,4,4,4,4][]));
 struct
Scan2
(alias fun,S,R) if (isForwardRange!(R));
Scan2!(fun,S,R)
scan2
(alias fun, S, R)(S seed, R range);
Scan2!(fun,ElementType!(R),R)
scan2
(alias fun, R)(R range);
 A variation on scan: this range returns the same values than scan, but paired
with the rest of the range.
Example:
auto arr = [1,2,3,4];
// running sum
assert(equal(scan!"a+b"(0,arr), [0,1,3,6,10]));
// sum with rest of range
assert(equal(scan2!"a+b"(0,arr), [tuple(0, [1,2,3,4][]),
tuple(1, [2,3,4][]),
tuple(3, [3,4][]),
tuple(6, [4][]),
tuple(10,(int[]).init)]));
 struct
ScanR
(alias fun,S,R) if (isBidirectionalRange!(R));
ScanR!(fun,S,R)
scanR
(alias fun, S, R)(S seed, R range);
ScanR!(fun,ElementType!(R),R)
scanR
(alias fun, R)(R range);
 The cousin of scan. A range that produces the successive result of reduceR!fun(seed, range):
[seed, fun(range.back, seed), fun(range[1], fun(range.back, seed)), ...]
Taken from Haskell.
See Also:
scan, reduce, reduceR
Example:
auto r1 = [1,2,3,4];
auto s = scanR!"a+b"(0,r1); // moving sum
assert(equal(s, [0,4,7,9,10][])); // 0, 4+0, 3+4+0, 2+3+4+0, 1+2+3+4+0
s = scanR!"a+b"(r1);
assert(equal(s, [4,7,9,10][]));
auto r2 = [1,2, 1, 4, 0, 3, 4];
auto r = scanR!min(0,r2); // moving minimum
assert(equal(r, [0,0,0,0,4,4,4,4][]));
r = scanR!min(r2);
assert(equal(r, [4,3,0,4,4,4,4][]));
int[] e;
assert(scanR!"a+b"(e).empty);
 struct
TScan
(alias fun,S,R...) if (allSatisfy!(isForwardRange,R));
TScan!(fun,S,R)
tscan0
(alias fun, S, R...)(S seed, R ranges);
TScan!(fun,ElementType!(Knit!(R)),R)
tscan
(alias fun, R...)(R ranges);
 To Be Documented.
The nrangesinparallel version of scan.
 struct
TScanR
(alias fun,S,R...) if (allSatisfy!(isBidirectionalRange,R));
TScanR!(fun,S,R)
tscanR0
(alias fun, S, R...)(S seed, R ranges);
TScanR!(fun,ElementType!(Knit!(R)),R)
tscanR
(alias fun, R...)(R ranges);
 To Be Documented.
The rightfold cousin of tscan.
 Concat!(Map!(unaryFun!(fun),R))
flatMap
(alias fun, R)(R range);

flatMap
is the concatenation of the results of a map on a range.
If the mapped function produces another range,
flatMap
concatenates all these ranges
into a unique range. If the function returns only a value,
flatMap
is not different from map.
Example:
string text = "this is just a test.\nI mean, I have no idea\nif this will work.";
auto lines = splitlines(text);
assert(equal(lines, ["this is just a test.", "I mean, I have no idea", "if this will work."][]));
auto words = map!split(lines); // With map: you obtain a range of ranges
assert(equal(words, [["this", "is", "just", "a", "test."],
["I", "mean,", "I", "have", "no", "idea"],
["if", "this", "will", "work."]][]));
auto words2 = flatMap!split(lines); // With flatMap, it gives a range
assert(equal(words2, ["this", "is", "just", "a", "test.",
"I", "mean,", "I", "have", "no", "idea",
"if", "this", "will", "work."][]));
auto r1 = [1,2,3,4];
auto f = flatMap!"replicate(a,a)"(r1); // stretching a range
assert(equal(f, [1,2,2,3,3,3,4,4,4,4][]));
auto f2 = flatMap!("take(a, iota(0,int.max))")(r1); // growing ramps of numbers
assert(equal(f2, [0,0,1,0,1,2,0,1,2,3][]));
 struct
Unfold
(alias fun,T...);
Unfold!(fun,T)
unfold
(alias fun, T...)(T initialParameters);
 Equivalent to the unfold of functional programming, the 'inverse' (dual?) of reduce. Given a seed and a generative
function, it creates an entire range. The function must have a special signature: it takes T... for arguments
and returns a Tuple!(Result, T...). The first part is the value for the range, the second part is used
as argument for the next step.
Compared to reduce which takes two arguments and returns one value, unfold uses a function
that takes n arguments and returns n+1 values. Thus, the expansion and the generation of a range.
Compare also to iterate, for which the value produced and the current state (next args) are the same.
Note that this version of unfold produces an infinite range.
Example:
Tuple!(R,R,R) fibonacci(R)(R a, R b) { return tuple(a, b, a+b);} // value produced: a. Next state: (b,a+b)
auto fibs = unfold!fibonacci!int(0,1);
assert(equal(take(10, fibs), [0,1,1,2,3,5,8,13,21,34][])); // lazily computes the Fibonacci numbers.
assert(isInfinite!(typeof(fibs))); // It's an infinite range.
// And now with BigInts!
auto fibs2 = unfold!(fibonacci!BigInt)(BigInt(0),BigInt(1));
assert(drop(fibs2,100).front == "573147844013817084101"); // Yeah, rapid growth
You can use 'string' functions, as in many places in this module. In this case, the fibonacci sequence is
defined simply as:
auto fibs3 = unfold!"tuple(a,b,a+b)"(0,1); // value produced: a. Next state: (b,a+b)
// "tuple(a,b,a+b)" is templated, so this would work directly with BigInts too.
But calculating Fibonacci numbers could easily be done easily with std.range.recurrence,
because the state has a constant size (int, int).
Calculating prime numbers on the other hand, necessitates a growing state (the list of primes already calculated).
Example:
// Given a list of primes, finds the next prime number
Tuple!(ulong, ulong[]) nextPrime(ulong[] primeList) {
ulong value = primeList.back + 2; // This could be done better with a wheel
bool isPrime = false;
while(!isPrime) {
foreach(prime; primeList) {
if (prime * prime > value) {
isPrime = true;
primeList ~= value;
break; // reached sqrt(value), it's a prime, no need to go further
}
else {
if (value % prime == 0) { // not a prime, test next one
isPrime = false;
value += 2;
break;
}
}
}
}
return tuple(value, primeList);
}
ulong[] seed = [2UL,3][];
auto primesAfter3 = unfold!nextPrime(seed);
assert(equal(take(10, primesAfter3), [5,7,11,13,17,19,23,29,31,37][]));
Another example, to be compared to reduceR example: calculating the
continued fraction development
of a real.
Example:
Tuple!(int, real) toCF(real d) { return tuple(to!int(d), 1.0 / (d  trunc(d)));}
auto piCF = unfold!toCF(PI); // Continued fraction dvt for pi 3.1415926...
// taken from http://mathworld.wolfram.com/PiContinuedFraction.html
assert(equal(take(12, piCF), [3,7,15,1,292,1,1,1,2,1,3,1][]));
auto eCF = unfold!toCF(E); // For e 2.7818281828...
// It can be proven to be 2,1, 2,1,1, 4,1,1, 6,1,1, 8,1,1, ... 2n,1,1 , ...
assert(equal(take(17, eCF), [2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1][]));
double GoldenRatio = 0.5 * (1 + sqrt(5.0)); // Phi, the golden mean/ratio, about 1.618033988...
auto GRCF = unfold!toCF(GoldenRatio); // Known to be 1,1,1,1,1,1,1,1,1,1, ... ad infinitum
assert(equal(take(30, GRCF), replicate(30,1))); // Check
This example has a problem: it doesn't stop. But a number can have a finite continued development. A trivial example is
1.25 = 1 + 1/4. There is no way with unfold to stop the process, see unfold2 to do that.
See Also:
unfold2, reduce, reduceR, iterate, scan, scanR, recurrence, sequence
 struct
Unfold2
(alias fun,alias pred,T...);
Unfold2!(fun,pred,T)
unfold2
(alias fun, alias pred, T...)(T initialParameters);
 A generalization of unfold with a second function: a predicate telling it when to stop (it stops when pred(elem,state) is false).
The former unfold produces a infinite range, this version can stop when you decide it to.
It's also sometimes called an anamorphism (see Wikipedia). It's not an infinite range (in the 'enum bool empty == false' sense).
Note:
the wikipedia example stops if pred(elem) is true and acts only on the generated value, not the global state.
As such it's equivalent to takeWhile!(not!pred)(unfold!fun) and so I decided here to use a more general predicate.
Example:
Tuple!(int, int, int) fibonacci(int a, int b) { return tuple(b, b, a+b);}
auto fibs = unfold2!(fibonacci, "a > 100")(0,1); // stops when you reach 100
assert(equal(fibs, [1,1,2,3,5,8,13,21,34,55,89][])); // Generates 89. Next value would be 55+89 > 100 > stops.
// see unfold for the definition of nextPrime.
// stops when the internal array storing the primes is 10 elements long
auto primesAfter3 = unfold2!(nextPrime, "b.length == 10")(seed);
assert(equal(primesAfter3, [5,7,11,13,17,19,23][])); // Internally stores seed also, so the state is [2,3,5,7,11,13,17,19,23,29].
// 29 is the 10th element in the array, which stops the unfolding.
// Continued fraction
Tuple!(real, real) toCF(real d) { return tuple(floor(d), 1.0 / (d  floor(d)));}
auto cf = unfold2!(toCF, "isnan(a)  a > 1E+6")(3.245); // Continued fraction dvt for 3.245
// can be calculated to be 3 + 1/(4 + 1/(12 + 1/4))
assert(equal(cf, [3,4,12,3,1][])); // ends with 3,1 => 3+1/1 (ie. 4)
 CompType!(gen,pred,R)
comp
(alias gen, alias pred, R...)(R inputs);
 A list comprehension for D. List comprehensions (also called forcomprehension
in some languages) are a powerful way to create sequences from input ranges, filters and a generative function.
Here, the syntax is:
comp!(generator, predicate)(inputs...);
It will then lazily generate the combination of all inputs, filter them through the predicate
and apply the generator to produce the values.
The generator and predicate can be written in a string form, as the functions in std.algorithm.map or .filter,
only generalized to 'a''z'. 'a' refers to elements from the first input, 'b' from the second and so on...
You can use other function like sin, cos, abs (or even tuple!) to generate values.
Example:
// find the pythagorean triplets for numbers between 1 and 10
// In set notation it's {(a,b,c)  a*a+b*b==c*c, a in [1,10], b in [1,10], c in [1,10]}
input = numbers(1, 11);
auto lc = comp!("tuple(a,b,c)", "a*a+b*b == c*c && a<b")(input, input, input);
// it finds the two triplets : Tuple!(int, int,int)(3,4,5) and (6,8,10)
assert(equal(lc, [tuple(3,4,5), tuple(6,8,10)][]));
Limitations:
It cannot directly do bindings (having one of the input ranges based on another one, like input2 = take(5, (range1.front))
successively for each range1.front).
In this case, you must fall back on a combination of map, filter and flatMap. Though it should be possible
to code this.
 IntersectionType!(R)
intersection
(R...)(R ranges);
 A small application of range comprehension ('comp'): outputs the '
intersection
' of n ranges. That's the
elements present in all ranges. I say '
intersection
' (with quotes) because if some ranges are not sets
there will be duplicates.
Example:
auto r1 = [0,1,2,3,2,3];
auto r2 = [2.0,4,5,3,7,1,0];
short[] r3 = [2,3,1,0];
auto i = intersection(r1,r2,r3); // i.front is a double
assert(equal(i, [0,1][]));
auto i2 = intersection(r1,r2);
assert(equal(i2, [0,1,2,3,2,3][]));
 Without!(Chain!(R),IntersectionType!(R))
symmetricDifference
(R...)(R ranges);
 As intersection, a small oneliner to produce the symmetric difference between n ranges (ie the
elements in the ranges that are not in their intersection).
Example:
auto r1 = [0,1,2,3,7];
auto r2 = [1,2,5,6,0];
auto s = symmetricDifference(r1, r2);
assert(equal(s, [3,5,7,6][]));
 PCompType!(gen,pred,R)
pComp
(alias gen, alias pred, R...)(R inputs);
 Another kind of list comprehension, based on a Haskell proposal for parallel list comprehension. The n ranges are iterated
in parallel (in lockstep) instead of generating all combinations. They are filtered with pred and the values
are generated by applying gen to the resulting tuples.
As for comprehension and setComprehension, you can use standard functions or 'string' functions, with
letters 'a''z' representing the current value for the first, second, etc. ranges.
Example:
auto r1 = numbers(1,100);
string sentence = "The quick brown fox jumped over the lazy dog.";
auto words = split(sentence);
// get the words that are longer than a growing value and capitalize them
auto plc = pComp!("capitalize(b)", "b.length > a")(r1, words);
assert(equal(plc, ["The", "Quick", "Brown", "Jumped"]));
One interesting use case is on indexed ranges. You can use pcomp to filter on the element's indices
and expose elements (and obtaining stridelike or droplike behavior, see below), or filter on elements
and return indices (like do 'positions' and 'indices' in this module).
Example:
auto r2 = [0,1,2,3,4,5,6,7];
auto myDrop(size_t n, R)(R range) {
return pComp!("b", "a>="~to!string(n))(indexed(range));
}
assert(equal(myDrop!3(r2), [3,4,5,6,7][]));
auto myStride(size_t n, R)(R range) {
return pComp!("b", "a%"~to!string(n)~" == 0")(indexed(range));
}
assert(equal(myStride!3(r2), [0,3,6][]));
auto dropEvery(size_t n, R)(R range) {
return pComp!("b", "a%"~to!string(n)~"!="~to!string(n)~"1")(indexed(range));
}
assert(equal(dropEvery!3(r2), [0,1, 3,4, 6,7][]));
See Also:
tfilter, tmap, comp, setComprehension, select, subranges.
 AsSet!(CompType!(gen,pred,R))
setComp
(alias gen, alias pred, R...)(R inputs);
 A set comprehension for D, using asSet on comp.
auto input = numbers(1,5);
auto sc = setComp!("a+b+c", "a + b > c")(input, input, input);
assert(equal(sc, [3,4,5,6,7,8,9,10,11,12][])); // The equivalent comprehension is three times as long.
See Also:
comprehension, asSet.
 struct
Merge
(alias pred,R...) if (allSatisfy!(isForwardRange,R) && CompatibleRanges!(R));
Merge!(pred,R)
merge
(alias pred = "a<b", R...)(R ranges);
 Given a variadic list of ranges and a predicate (default: "a<b"), merge will 'merge' the ranges
according to the following algorithm: it compare all fronts, finds the front
which verifies the predicate with all other fronts (the 'smallest') and outputs
it, advancing its range.
If all ranges are sorted with the predicate, it's equivalent to the call:
sortAsArray!pred(chain(ranges)); // Which may be exactly what you want instead of 'merge'
But if the ranges are not sorted, the results are different:
Example:
auto r = [0,2,3];
auto r2 = [1,4,5];
auto r3 = [1,6,7,0];
int[] e;
auto m = merge(r,e,r2,r3);
assert(equal(m, [0,1,1,2,3,4,5,6,7,0][]));
 CommonElementType!(R1,R2)[]
merge2
(R1, R2)(R1 r1, R2 r2);
 Another version, for two ranges and with the predicate being automatically "a<b".
It's faster than the generic merge, and get rid of duplicates.
Example:
// Calculating Hamming numbers, numbers of the form 2^i * 3^j * 5^k
// see http://en.wikipedia.org/wiki/Regular_number
// Dijkstra's algorithm heavily uses merge.
T[] hamming(T)(T[] r)
{
return 1 ~ merge2(map!"2*a"(r),merge2(map!"3*a"(r),map!"5*a"(r)));
}
auto hammingNumbers()
{
return iterate!hamming([1UL][]); // develop the Hamming sequence at each iteration.
}
// 1,2,3,4,5,6,8,9,10,12,...
// For the ith iteration, the sequence is complete only up to 2^i,
// but has much more numbers already calculated.
// The algorithm finds all Hamming numbers less than 1000_000_000_000 (1E+12) in 250 ms on my computer.
// There are 3428 of them and it takes 39 iterations to find them all. At this step the generated
// Hamming sequence has more than one million numbers already calculated.
// (most may be false due to reaching ulong.max).
 bool[]
nextBoolean
(bool[] t);
 Internal helper function. Takes a number coded as
a dynamic array of bits (boolean), returns the next number.
The loworder bits are the first elements. That is, 8 is 0b1000 > [false, false, false, true].
Example:
bool[] num; // equivalent to [false];
foreach(i; 0..4) { // 0 > 1 > 2 > 3 > 4
num = nextBoolean(num);
}
assert(num == [false, false, true][]); // 4 is 0b100, here encoded as [false, false, true]
 PCompType!("b","a",bool[],R)
select
(R)(bool[] flags, R range);
 Given a dynamic array of flags (boolean), extracts the corresponding elements
and returns the corresponding subrange as a comprehension (another lazy range).
If stops at whichever is shortest between flags and range.
It works for infinite ranges, too.
See Also:
fromIndex.
Example:
auto r = [0,1,2,3];
auto s01 = select([false, true][], r);
assert(equal(s01, [1][]));
auto s13 = select([false, true,false,true][], r);
assert(equal(s13, [1,3][]));
 SubRanges!(R)
subranges
(R)(R range);
 Lazily returns all
subranges
of a range: the ranges created
by taking only some elements of the range in the same order.
For this implementation, it begins with the empty range.
For a range of length n,
subranges
has 2^^n elements.
Note:
It works for infinite ranges.
Example:
auto r = [0,1,2];
auto sr = subranges(r);
int[][] witness = [[],
[0],
[1],
[0,1],
[2],
[0,2], [1,2],
[0,1,2]];
foreach(elem; sr) {
assert(equal(elem, witness.front));
witness.popFront;
}
 ElementType!(R)[]
sortAsArray
(alias pred = "a < b", R)(R range);
 std.algorithm.sort does an efficient inplace sort, but it requires the
input range to returns its elements by reference. As it's not the case for
most of the ranges here (mainly because they simply cannot),
sortAsArray
is provided here if you need to sort a range with an ordering function.
It just calls array() on range, sorts it and return the sorted array.
See Also:
indexSorted
Example:
auto r1 = [5,1,2,3,4];
auto r2 = [4.0,3.0,2.0,1.0,0.0];
auto r3 = ["abc","def","ghi"];
auto s = knit(r1,r2,r3); // sort(s) won't work
// sort with no ordering function defined, defaults to "a < b" (it's defined on tuples)
assert(equal(sortAsArray(s), [tuple(1,3.0,"def"),tuple(2,2.0,"ghi"),tuple(5,4.0,"abc")][]));
// specifying an ordering function: sorting according to the second field
assert(equal(sortAsArray!"a.field[1] < b.field[1]"(s), [tuple(2,2.0,"ghi"),tuple(1,3.0,"def"),tuple(5,4.0,"abc")][]));
// Another kind of range, with front&back not by ref
auto st = stutter(3, r2); // st is equivalent to [5,5,5,1,1,1,2,2,2,3,3,3,4,4,4][] but cannot be sorted by sort
assert(equal(sortAsArray(st), stutter(3, sortAsArray(r2))));
 struct
Group
(R) if (isForwardRange!(R));
Group!(R)
group
(R)(R range);
 Groups a range by values and returns the grouped values as an array. It's a bidirectional range.
Example:
auto test = [0,1,1,2,2,2,3,3,3,3,4,4,4,5,5,6];
assert(equal(group(test), [[0], [1,1], [2,2,2], [3,3,3,3], [4,4,4], [5,5], [6]][]));
assert(equal(group("Mississippi"), ["M", "i", "ss", "i", "ss", "i", "pp", "i"][]));
Update:
A function with the same name already exists in std.algorithm, with a predicate, even.
No need to work further on this.
 Map!(valueLength,Group!(R))
runLengthEncode
(R)(R range);
 Given a range r, will return the runlength encoding of r, as a range of tuples(element, length).
Example:
auto test = [0,1,1,2,2,2,3,3,3,3,4,4,4,5,5,6][];
auto rle = runLengthEncode(test);
wr(rle); // will print Tuple!(int, size_t): (0,1) (1,2) (2,3) (3,4) (4,3) (5,2) (6,1)
 bool
contains
(R1, R2)(R1 range1, R2 range2);
bool
contains
(R1, E)(R1 range1, E element);
 Returns true iff range1
contains
range2 (as one block, not separated elements). Do not presumes the ranges
are sorted (so, does a linear scan).
Range2 can also be just one element.
Note:
Another version could be possible, with one of the ranges as a template arg:
contains
!"bar"(r).
That way, it could be used a predicate by filtering function like dropWhile, takeWhile and filter.
TODO:
maybe a predicate.d, containing predicates and predicateconstructing functions?
TODO:
it can be more efficient for sliceable ranges.
TODO:
maybe just use std.algo.find?
Examples:
assert("foobarbaz".contains("bar")); // true
assert("foobarbaz".contains("b")); // true
assert("foobarbaz".contains('b')); // true
//
assert(!("foobarbaz".contains("c")));// doesn't contain "c"
assert("foobarbaz".contains("")); // "" (an empty range) is in any range
assert(!("".contains("abc"))); // an empty range contains nothing
 Rotate!(R)
rotate
(R)(R range, int n = 1);
 To Be Documented.
rotates a range to the left by n positions (ie: take the first n elements and put them at the end).
R must be a forward range and have a length. If R is infinite, it just drops the first n terms.
If n is negative, it rotates it to the right.
 Chain!(R,TakeWhile!(pred,R))
rotateWhile
(alias pred, R)(R range);
 Rotates a range while the predicate holds. It works for infinite ranges also.
If the predicate is true for all elements, it will not cycle forever, but deliver a range equal
to the orginal range.
Note that the predicate can be unary, but also binary or whatever.
rotateWhile
!"a<b"(r) is possible.
See takeWhile.
Example:
auto arr = [0,1,2,3,4,3,2,1,0];
wr(rotateWhile!"true"(arr)); // 0,1,2,3,4,3,2,1,0
wr(rotateWhile!"a<2"(arr)); // 2,3,4,3,2,1,0,0,1
wr(rotateWhile!"a<b"(arr)); // 4,3,2,1,0,0,1,2,3
wr(rotateWhile!"a+b+c<10"(arr));// 3,4,3,2,1,0,0,1,2
 TMapType!(rotate!(R),Repeat!(R),Numbers)
rotations
(R)(R range);
 Infinite range producing the successive
rotations
of the input range.
 TMapType!(replacer!(ElementType!(R)),R,Repeat!(V[K]))
replace
(R, V, K)(R range, V[K] mapping);
 To Be Documented.
Replaces the elementes of range present in the AA mapping by the values in mapping.
Example:
auto r = replace([0,1,2,3,4], [1:100, 2:200]);
 IndicesType!(value,R)
indices
(alias value, R)(R range);
 Takes a value as template parameter and a range as argument, returns a (lazy) range
containing the
indices
of 'value' in the range.
auto r1 = [0,1,2,3,4,2,2];
auto i1 = indices!2(r1); // 2,5,6. finding an int in a int[]
assert(equal(indicesOf!'a'("banana"), [1,3,5][])); // finding a char in a string
string sentence = "the quick brown fox jumped over the lazy dog.";
auto i2 = indices!' '(sentence); // finding spaces in the string
assert(equal(i2, [3, 9, 15, 19, 26, 31, 35, 40][]));
auto words = split(sentence);
auto i3 = indices!"the"(words); // finding a string in a string[]
assert(equal(i3, [0,6][]));
auto r2 = map!"a*a"(cycle([1,2,3]));
auto i4 = indices!4(take(10, r2)); // inside another kind of range
assert(equal(i4, [1,4,7][]));
 PCompType!("a","b",Numbers,Map!(unaryFun!(pred),R))
positions
(alias pred, R)(R range);
 Takes a predicate as template parameter and a range as argument, returns a (lazy) range
containing the indices of the values verifying pred.
Example:
auto r1 = [0,1,2,3,4,5,6,1];
auto p1 = positions!"a%2==0"(r1);
assert(equal(p1, [0,2,4,6][]));
auto p2 = positions!"a<4"(r1);
assert(equal(p2, [0,1,2,3,7][]));
auto p3 = positions!"a>10"(r1); // predicate never verified > empty
assert(p3.empty);
auto s = "banana";
auto p4 = positions!(isOneOf!"bn")(s);
assert(equal(p4, [0,2,4][]));
int[] e;
assert(positions!"a==0"(e).empty); // on an empty range > empty
 TMapType!(atIndex!(R,ElementType!(I)),Combinations!(Once!(R),I))
fromIndex
(I, R)(I indices, R range);
 Given a (possibly infinite) range of indices and a randomaccess range, it will lazily produce
the corresponding elements.
Example:
string s = "abcdefg";
auto i1 = map!"a%4"(numbers(10)); // 0,1,2,3,0,1,2,3,0,1
auto fi1 = fromIndex(i1, s);
assert(equal(fi1, "abcdabcdab")); // equivalent to take(10, cycle(take(4, s)))
auto i2 = map!"a/4"(numbers(10)); // 0,0,0,0,1,1,1,1,2,2
auto fi2 = fromIndex(i2, s);
assert(equal(fi2, "aaaabbbbcc")); // equivalent to take(10, stutter(4, s))
 struct
ToIndex
(R) if (isForwardRange!(R));
ToIndex!(R)
toIndex
(R)(R range);
 Given a range, it will lazily produce the element's indices. If an element has the same value
than a previous element, this previous element's index will be given.
Examples:
string s = "abcdefabcdefghab";
auto ti = toIndex(s);
assert(equal(ti, [0,1,2,3,4,5,0,1,2,3,4,5,12,13,0,1][]));
assert(equal(fromIndex(ti, s), s)); // toIndex is (sort of) the opposite of fromIndex
auto r = replicate(5,5); // 5,5,5,5,5
assert(equal(toIndex(r), [0,0,0,0,0][])); // Always the first element's index (0)
 Tuple!(Filter!(unaryFun!(pred),R),Filter!(Not!(unaryFun!(pred)),R))
separate
(alias pred, R)(R range);
 Separate a range in (in tuple of) two ranges according to predicate pred. The first field
will contain the values verifying pred, the second those that do not verify it. There
is an equivalent Haskell function.
See Also:
span.
Example:
auto r = [0,1,2,3,4,5];
auto s = separate!"a<1  a>3"(r);
assert(equal(first(s), [0,4,5][]));
assert(equal(second(s), [1,2,3][]));
 Tuple!(TakeWhile!(pred,R),R)
span
(alias pred, R)(R range);
 Equivalent to Haskell's
span
: returns the tuple(takeWhile!pred(range), dropWhile!pred(range)).
See Also:
separate.
Example:
auto r = map!"a*a"([0,1,2,3,4,5,4,3,2][]);
auto s = span!"a<10"(m);
assert(equal(first(s), [0,1,4,9][]));
assert(equal(second(s), [16,25,16,9,4][]));
 ElementType!(R)[]
squeeze
(E, R)(E element, R range);
 Eliminates all duplicated occurences of 'element' from 'range'. Taken from Ruby by way of Clojure.
Useful to get rid of surnumerary spaces in strings.
Examples:
auto r1 = [0,1,2,2,3,4,5,2,2,2,3,5,6,8,3,2];
string r2 = "abcd ef g h ";
assert(equal(squeeze(2, r1), [0,1,2,3,4,5,2,3,5,6,8,3,2][]));
assert(equal(squeeze(' ', r2), "abcd ef g h "));
Note that it returns an array of ElementType!R, not a R.
 struct
Combinations
(R...) if (allSatisfy!(isForwardRange,R));
Combinations!(R)
combinations
(R...)(R ranges);
 Gives the cartesian product of a variadic number of ranges: the sequence of all tuples
created by taking one element in each range.
The order of the input ranges is important: the rightmost one
will be incremented faster than the one before it and so on:
Combinations
([0,1][], [2,3][], [4,5][]) will produce
Tuple!(int, int, int) (0,2,4), (0,2,5), (0,3,4), (0,3,5), (1,2,4), ...
If all the ranges have a length,
Combinations
also has a 'length' member
whose value is the product of all these lengths.
Example:
auto r1 = [0,1,2];
string r2 = "abcd";
auto r3 = map!"a + 3.0"(r1);
auto cb = combinations(r1,r2,r3);
assert(!is(cb.length)); // r3 has no length, so cb neither.
assert(equal(take(7, cb),
[tuple(0, 'a', 3.0), tuple(0, 'a', 4.0), tuple(0, 'a', 5.0),
tuple(0, 'b', 3.0), tuple(0, 'b', 4.0), tuple(0, 'b', 5.0), tuple(0, 'c', 3.0)][]
));
auto cb2 = combinations(r1,r2);
assert(cb2.length == r1.length * r2.length); // 12
cb2.popFront;
assert(cb2.length == r1.length * r2.length  1); // 11
 struct
Permutations
(R);
Permutations!(R)
permutations
(R)(R r);
Permutations!(R)
permutations
(R)(R r, size_t n);
Permutations!(ElementType!(R)[])
permutations
(R)(R r);
Permutations!(ElementType!(R)[])
permutations
(R)(R r, size_t n);
 Lazily generates the permutations of the first n elements in a range. By default
n is equal to the range's length, so it permutes the entire range.
It's completely based on algorithm C from Knuth's "the Art of Computer Programming", vol. IV
(found on the web here),
fascicule 2b, section 7.2.1.2 "Generating all
Permutations
".
Internally it does not use any factorial, so it's quite safe to use it on long ranges.
Its length will be n!. So permutations(r,1) returns only array(r).
On the empty range, it returns an empty range and then stops.
BUG:
Do not work on infinite ranges. Not a bug, more a limitation of the algorithm as currently coded.
Note:
The front type is an array of ElementType!R, not an R, because most ranges
do not support the slicing operations needed there. Also, it's an array
and not a tuple as most ranges'd return here, because I gather the classical
use is indeed to treat each element (a permutation) as a range latter on. Tuples
wouldn't do it.
Note:
Another possibility would be to return a lazy extract, as do subranges and variations.
Note:
A possible update would be to get rid of internal arrays and to make it usable on infinite ranges.
Example:
auto r = [0,1,2]; // array
auto m = map!"a*a"(r); // not an array...
auto p1 = permutations(r); // on an array
assert(equal(p1, [[0,1,2], [1,2,0], [2,0,1], [1,0,2], [0,2,1], [2,1,0] ][]));
auto p2 = permutations(m); // on a forward range
assert(equal(p2, [[0,1,4], [1,4,0], [4,0,1], [1,0,4], [0,4,1], [4,1,0] ][]));
auto r2 = numbers(100); // 0..100
auto p3 = permutations(r2); // quite safe, but you'll probably never exhaust it...
p3.popFront;
assert(p3.front == array(numbers(1,100)) ~ [0]);
p3.popFront;
assert(p3.front == array(numbers(2,100)) ~ [0,1]); // begins by rotating the range
auto p4 = permutations(r2, 3); // permutes only the first 3 elements.
p4.popFront;
assert(p4.front == [1,2,0] ~ array(numbers(3,100)));
p4.popFront;
assert(p4.front == [2,0,1] ~ array(numbers(3,100)));
p4.popFront;
p4.popFront;
p4.popFront;
assert(p4.empty); // only 6 elements, as it acts only on the first 3 elements of r2.
 ChooseType!(repetition,R)
choose
(uint repetition = withoutRepetition, R)(size_t n, R range);
 Chooses n elements from a range. It lazily generates all combinations of n elements (as an array) taken from range.
There are two different behaviors determined by an anonymous enum : repetition {withRepetition, withoutRepetition}
Repetition tells the algorithm if you want to reuse the elements from the range or not.
Say you want to take 3 elements from [0,1,2,3]. You take '0'. If you selected withoutRepetition (the default state)
the second element will be taken from [1,2,3], and the third from [2,3] (for example). If you selected
withRepetition, all three elements will be taken from [0,1,2,3]. So repeated values like (2,3,3) are a possibility.
For a range of length l, choosing n elements among l will give C(n,l) = (
choose
n among l) = l!/(n! * (ln)!) = l*(l1)*(l2)*...*(ln+1) / n!
Without repetition, the generated arrays are always ordered as the range's elements: choosing 3 element among [0,1,2,3,4,5]
will generate [0,1,2], [0,1,3], ... but never [3,1,0]. If you want all the orderings, do flatMap!permutations on
choose
.
You can do the same with repetition, but in this case, you need to filter out the repeated patterns with asSet.
Examples:
// A poker hand is five cards without repetition among 52 cards.
// That makes 2,598,960 possible hands.
auto ranks = "A23456789TJQK";
auto suits = ["Hearts", "Spades", "Diamonds", "Clubs"];
auto cards = combinations(ranks, suits); // ('A', "Hearts"), ('A', "Spades"), ...
assert(walkLength(cards) == 52); // OK, 52 cards.
auto c = choose(5, cards); // default is withoutRepetition
assert(walkLength(c) == 52*51*50*49*48/(5*4*3*2)); // 2,598,960
// A DNA chain is made of one of four bases (here denoted as A, C, G or T)
// A codon is a 3bases encoding for an aminoacid. How many codons are there?
auto DNA = "ACGT";
auto codons = choose!withRepetition(3, DNA); // 4*4*4 == 64 elements
assert(walkLength(codons) == 64);
 struct
Consumer
(alias nextElement,alias isSafe,alias renewState,alias buildState,alias flusher,R,St,Out);
Consumer!(nextElement,isSafe,renewState,buildState,flusher,R,St,typeof(unaryFun!(nextElement)(St.init)))
consumer
(alias nextElement, alias isSafe, alias renewState, alias buildState, alias flusher = id, R, St)(R range, St initialState);
Consumer!(nextElement,isSafe,renewState,buildState,flusher,R,St,typeof(unaryFun!(nextElement)(St.init)))
consumer
(alias nextElement, alias isSafe, alias renewState, alias buildState, alias flusher, R, St)(R range, St initialState);
 A generic consumer of ranges. It will gobble as many elements as needed from the input range
to produce its next value, the number of input elements consumed can vary from
one call to popFront to the next. Taken from the Haskell code in
this article.
It takes as input a (possibly infinite) range with element type In and an initial internal state (of type St).
Let's call Out the type consumer outputs. The idea is that you incrementaly build a valid internal state while consuming the range.
When the state is complete, nextElement can produce the output element and renewState 'discharges' the state,
making it OK for rebuilding by buildState.
Params:
nextElement 
a callable taking a St (current state) and returning an Out. Produces the possible next element (of type Out). 
isSafe 
takes the current state and the element produced by nextElement. Tells wether or not it's OK to output the element. 
renewState 
if isSafe is true, then renewState takes (state, element) and returns the state resotred to a 'pristine' state (ready to grow again). 
buildState 
if isSafe is false, buildState takes (state, range.front) and returns the new state. range.popFront is called. 
flush 
is an optional callable that is used when the input range is exhausted (so, only for finite ranges). flush is called on the current state to produce the last few elements as an array of Out. 
Example:
// to be documented.
 typeof(binaryFun!(plus)(binaryFun!(times)(ElementType!(R1).init,ElementType!(R2).init),binaryFun!(times)(ElementType!(R1).init,ElementType!(R1).init)))
innerProduct
(alias plus = "a+b", alias times = "a*b", R1, R2)(R1 r1, R2 r2);
 generic inner product of a range.
 Filter!(Not!(pred),R)
remove
(alias pred, R)(R r);
 the dual of filter
 template
reduceWhile
(alias fun,alias pred)
 reduce a range while pred holds on the intermediary values.
 template
treduce0
(alias fun)
template
treduce
(alias fun) template
treduceR0
(alias fun)
 To Be Documented.
Reducing n ranges in parallel (in the same vein than tmap, tfilter).
 template
treduceR
(alias fun)
 The rightfold pendant of treduce.
