std.algorithm.iteration - D Programming Language (original) (raw)

auto cache(Range)(Range range)
if (isInputRange!Range);

auto cacheBidirectional(Range)(Range range)
if (isBidirectionalRange!Range);

cache eagerly evaluates front of rangeon 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 callstd.range.filter or std.range.tee

cache may providebidirectional rangeiteration 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.hasSlicingtrait also checks for random access).

Examples:

import std.algorithm.comparison : equal; import std.range, std.stdio; import std.typecons : tuple;

ulong counter = 0; double fun(int x) { ++counter; return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5; } auto result1 = iota(-4, 5).map!(a =>tuple(a, fun(a)))() .filter!(a => a[1] < 0)() .map!(a => a[0])() .array();

assert(equal(result1, [-3, -2, 2]));

writeln(counter); counter = 0; auto result2 = iota(-4, 5).map!(a =>tuple(a, fun(a)))() .cache() .filter!(a => a[1] < 0)() .map!(a => a[0])();

assert(equal(result2, [-3, -2, 2]));

writeln(counter);

Examples:

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 cachemay yield a faster range.

Either way, the resulting ranges will be equivalent, but maybe not at the same cost or side effects.

import std.algorithm.comparison : equal; import std.range; int i = 0;

auto r = iota(0, 4).tee!((a){i = a;}, No.pipeOnPop); auto r1 = r.take(3).cache(); auto r2 = r.cache().take(3);

assert(equal(r1, [0, 1, 2])); assert(i == 2); assert(equal(r2, [0, 1, 2])); assert(i == 3);

template map(fun...) if (fun.length >= 1)

Implements the homonym function (also known as transform) present in many languages of functional flavor. The call map!(fun)(range)returns a range of which elements are obtained by applying fun(a)left to right for all elements a in range. The original ranges are not changed. Evaluation is done lazily.

Parameters:

Examples:

import std.algorithm.comparison : equal; import std.range : chain, only; auto squares = chain(only(1, 2, 3, 4), only(5, 6)).map!(a => a * a); assert(equal(squares, only(1, 4, 9, 16, 25, 36)));

Examples:

Multiple functions can be passed to map. In that case, the element type of map is a tuple containing one element for each function.

auto sums = [2, 4, 6, 8]; auto products = [1, 4, 9, 16];

size_t i = 0; foreach (result; [ 1, 2, 3, 4 ].map!("a + a", "a * a")) { writeln(result[0]); writeln(result[1]); ++i; }

Examples:

You may alias map with some function(s) to a symbol and use it separately:

import std.algorithm.comparison : equal; import std.conv : to;

alias stringize = map!(to!string); assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));

auto map(Range)(Range r)
if (isInputRange!(Unqual!Range));

Returns:

A range with each fun applied to all the elements. If there is more than one fun, the element type will be Tuple containing one element for each fun.

template each(alias fun = "a")

Eagerly iterates over r and calls fun with each element.

If no function to call is specified, each defaults to doing nothing but consuming the entire range. r.front will be evaluated, but that can be avoided by specifying a lambda with a lazy parameter.

each also supports opApply-based types, so it works with e.g. std.parallelism.parallel.

Normally the entire range is iterated. If partial iteration (early stopping) is desired, fun needs to return a value of type std.typecons.Flag!"each" (Yes.each to continue iteration, or No.each to stop iteration).

Parameters:

Returns:

Yes.each if the entire range was iterated, No.each in case of early stopping.

Examples:

import std.range : iota; import std.typecons : No;

int[] arr; iota(5).each!(n => arr ~= n); writeln(arr); iota(5).each!((n) { arr ~= n; return No.each; }); writeln(arr); arr.each!((ref n) => n++); writeln(arr); arr.each!"a++"; writeln(arr); auto m = arr.map!(n => n); static assert(!__traits(compiles, m.each!((ref n) => n++)));

(&m).each(); assert(m.empty);

Examples:

each can pass an index variable for iterable objects which support this

auto arr = new size_t[4];

arr.each!"a=i"(); writeln(arr); arr.each!((i, ref e) => e = i * 2); writeln(arr);

Examples:

opApply iterators work as well

static class S { int x; int opApply(scope int delegate(ref int _x) dg) { return dg(x); } }

auto s = new S; s.each!"a++"; writeln(s.x);

Flag!"each" each(Range)(Range r)
if (!isForeachIterable!Range && (isRangeIterable!Range || __traits(compiles, typeof(r.front).length)));

Flag!"each" each(Iterable)(auto ref Iterable r)
if (isForeachIterable!Iterable || __traits(compiles, Parameters!(Parameters!(r.opApply))));

Parameters:

template filter(alias predicate) if (is(typeof(unaryFun!predicate)))

filter!(predicate)(range) returns a new range containing only elements x in range for which predicate(x) returns true.

The predicate is passed to std.functional.unaryFun, and can be either a string, or any callable that can be executed via pred(element).

Parameters:

Returns:

An input range that contains the filtered elements. If range is at least a forward range, the return value of filter will also be a forward range.

Examples:

import std.algorithm.comparison : equal; import std.math.operations : isClose; import std.range;

int[] arr = [ 1, 2, 3, 4, 5 ];

auto small = filter!(a => a < 3)(arr); assert(equal(small, [ 1, 2 ]));

auto sum = arr.filter!(a => a < 3); assert(equal(sum, [ 1, 2 ]));

int[] a = [ 3, -2, 400 ]; int[] b = [ 100, -101, 102 ]; auto r = chain(a, b).filter!(a => a > 0); assert(equal(r, [ 3, 400, 100, 102 ]));

double[] c = [ 2.5, 3.0 ]; auto r1 = chain(c, a, b).filter!(a => cast(int) a != a); assert(isClose(r1, [ 2.5 ]));

auto filter(Range)(Range range)
if (isInputRange!(Unqual!Range));

Returns:

A range containing only elements x in range for which predicate(x) returns true.

template filterBidirectional(alias pred)

Similar to filter, except it defines abidirectional range. There is a speed disadvantage - the constructor spends time finding the last element in the range that satisfies the filtering condition (in addition to finding the first one). The advantage is that the filtered range can be spanned from both directions. Also,std.range.retro can be applied against the filtered range.

The predicate is passed to std.functional.unaryFun, and can either accept a string, or any callable that can be executed via pred(element).

Parameters:

Examples:

import std.algorithm.comparison : equal; import std.range;

int[] arr = [ 1, 2, 3, 4, 5 ]; auto small = filterBidirectional!("a < 3")(arr); static assert(isBidirectionalRange!(typeof(small))); writeln(small.back); assert(equal(small, [ 1, 2 ])); assert(equal(retro(small), [ 2, 1 ])); int[] a = [ 3, -2, 400 ]; int[] b = [ 100, -101, 102 ]; auto r = filterBidirectional!("a > 0")(chain(a, b)); writeln(r.back);

auto filterBidirectional(Range)(Range r)
if (isBidirectionalRange!(Unqual!Range));

Parameters:

Returns:

A range containing only the elements in r for which pred returns true.

Group!(pred, Range) group(alias pred = "a == b", Range)(Range r);

struct Group(alias pred, R) if (isInputRange!R);

Groups consecutively equivalent elements into a single tuple of the element and the number of its repetitions.

Similarly to uniq, group produces a range that iterates over unique consecutive elements of the given range. Each element of this range is a tuple of the element and the number of times it is repeated in the original range. Equivalence of elements is assessed by using the predicate pred, which defaults to "a == b". The predicate is passed to std.functional.binaryFun, and can either accept a string, or any callable that can be executed viapred(element, element).

Parameters:

Returns:

A range of elements of type Tuple!(ElementType!R, uint), representing each consecutively unique element and its respective number of occurrences in that run. This will be an input range if R is an input range, and a forward range in all other cases.

See Also:

chunkBy, which chunks an input range into subranges of equivalent adjacent elements.

Examples:

import std.algorithm.comparison : equal; import std.typecons : tuple, Tuple;

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ][]));

Examples:

Using group, an associative array can be easily generated with the count of each unique element in the range.

import std.algorithm.sorting : sort; import std.array : assocArray;

uint[string] result; auto range = ["a", "b", "a", "c", "b", "c", "c", "d", "e"]; result = range.sort!((a, b) => a < b) .group .assocArray;

writeln(result);

auto chunkBy(alias pred, Range)(Range r)
if (isInputRange!Range);

Chunks an input range into subranges of equivalent adjacent elements. In other languages this is often called partitionBy, groupBy or sliceWhen.

Equivalence is defined by the predicate pred, which can be either binary, which is passed to std.functional.binaryFun, or unary, which is passed to std.functional.unaryFun. In the binary form, two range elementsa and b are considered equivalent if pred(a,b) is true. In unary form, two elements are considered equivalent if pred(a) == pred(b) is true.

This predicate must be an equivalence relation, that is, it must be reflexive (pred(x,x) is always true), symmetric (pred(x,y) == pred(y,x)), and transitive (pred(x,y) && pred(y,z) implies pred(x,z)). If this is not the case, the range returned by chunkBy may assert at runtime or behave erratically. Use splitWhen if you want to chunk by a predicate that is not an equivalence relation.

Parameters:

Returns:

With a binary predicate, a range of ranges is returned in which all elements in a given subrange are equivalent under the given predicate. With a unary predicate, a range of tuples is returned, with the tuple consisting of the result of the unary predicate for each subrange, and the subrange itself. Copying the range currently has reference semantics, but this may change in the future.

NotesEquivalent elements separated by an intervening non-equivalent element will appear in separate subranges; this function only considers adjacent equivalence. Elements in the subranges will always appear in the same order they appear in the original range.

See Also:

group, which collapses adjacent equivalent elements into a single element.

Examples:

Showing usage with binary predicate:

import std.algorithm.comparison : equal;

auto data = [ [1, 1], [1, 2], [2, 2], [2, 3] ];

auto r1 = data.chunkBy!((a,b) => a[0] == b[0]); assert(r1.equal!equal([ [[1, 1], [1, 2]], [[2, 2], [2, 3]] ]));

auto r2 = data.chunkBy!((a,b) => a[1] == b[1]); assert(r2.equal!equal([ [[1, 1]], [[1, 2], [2, 2]], [[2, 3]] ]));

Examples:

Showing usage with unary predicate:

import std.algorithm.comparison : equal; import std.range.primitives; import std.typecons : tuple;

auto range = [ [1, 1], [1, 1], [1, 2], [2, 2], [2, 3], [2, 3], [3, 3] ];

auto byX = chunkBy!(a => a[0])(range); auto expected1 = [ tuple(1, [[1, 1], [1, 1], [1, 2]]), tuple(2, [[2, 2], [2, 3], [2, 3]]), tuple(3, [[3, 3]]) ]; foreach (e; byX) { assert(!expected1.empty); writeln(e[0]); assert(e[1].equal(expected1.front[1])); expected1.popFront(); }

auto byY = chunkBy!(a => a[1])(range); auto expected2 = [ tuple(1, [[1, 1], [1, 1]]), tuple(2, [[1, 2], [2, 2]]), tuple(3, [[2, 3], [2, 3], [3, 3]]) ]; foreach (e; byY) { assert(!expected2.empty); writeln(e[0]); assert(e[1].equal(expected2.front[1])); expected2.popFront(); }

auto splitWhen(alias pred, Range)(Range r)
if (isForwardRange!Range);

Splits a forward range into subranges in places determined by a binary predicate.

When iterating, one element of r is compared with pred to the next element. If pred return true, a new subrange is started for the next element. Otherwise, they are part of the same subrange.

If the elements are compared with an inequality (!=) operator, considerchunkBy instead, as it's likely faster to execute.

Parameters:

Returns:

a range of subranges of r, split such that within a given subrange, calling pred with any pair of adjacent elements as arguments returns false. Copying the range currently has reference semantics, but this may change in the future.

See Also:

splitter, which uses elements as splitters instead of element-to-element relations.

Examples:

import std.algorithm.comparison : equal; import std.range : dropExactly; auto source = [4, 3, 2, 11, 0, -3, -3, 5, 3, 0];

auto result1 = source.splitWhen!((a,b) => a <= b); assert(result1.save.equal!equal([ [4, 3, 2], [11, 0, -3], [-3], [5, 3, 0] ]));

auto result2 = result1.dropExactly(2); assert(result1.save.equal!equal([ [-3], [5, 3, 0] ]));

auto joiner(RoR, Separator)(RoR r, Separator sep);

auto joiner(RoR)(RoR r)
if (isInputRange!RoR && isInputRange!(Unqual!(ElementType!RoR)));

Lazily joins a range of ranges with a separator. The separator itself is a range. If a separator is not provided, then the ranges are joined directly without anything in between them (often called flattenin other languages).

Parameters:

Returns:

A range of elements in the joined range. This will be a bidirectional range if both outer and inner ranges of RoR are at least bidirectional ranges. Else if both outer and inner ranges of RoR are forward ranges, the returned range will be likewise. Otherwise it will be only an input range. Therange bidirectionalityis propagated if no separator is specified.

See Also:

std.range.chain, which chains a sequence of ranges with compatible elements into a single range.

NoteWhen both outer and inner ranges of RoR are bidirectional and the joiner is iterated from the back to the front, the separator will still be consumed from front to back, even if it is a bidirectional range too.

Examples:

import std.algorithm.comparison : equal; import std.conv : text;

assert(["abc", "def"].joiner.equal("abcdef")); assert(["Mary", "has", "a", "little", "lamb"] .joiner("...") .equal("Mary...has...a...little...lamb")); assert(["", "abc"].joiner("xyz").equal("xyzabc")); assert([""].joiner("xyz").equal("")); assert(["", ""].joiner("xyz").equal("xyz"));

Examples:

import std.algorithm.comparison : equal; import std.range : repeat;

assert([""].joiner.equal("")); assert(["", ""].joiner.equal("")); assert(["", "abc"].joiner.equal("abc")); assert(["abc", ""].joiner.equal("abc")); assert(["abc", "def"].joiner.equal("abcdef")); assert(["Mary", "has", "a", "little", "lamb"].joiner.equal("Maryhasalittlelamb")); assert("abc".repeat(3).joiner.equal("abcabcabc"));

Examples:

joiner allows in-place mutation!

import std.algorithm.comparison : equal; auto a = [ [1, 2, 3], [42, 43] ]; auto j = joiner(a); j.front = 44; writeln(a); assert(equal(j, [44, 2, 3, 42, 43]));

Examples:

insert characters fully lazily into a string

import std.algorithm.comparison : equal; import std.range : chain, cycle, iota, only, retro, take, zip; import std.format : format;

static immutable number = "12345678"; static immutable delimiter = ","; auto formatted = number.retro .zip(3.iota.cycle.take(number.length)) .map!(z => chain(z[0].only, z[1] == 2 ? delimiter : null)) .joiner .retro; static immutable expected = "12,345,678"; assert(formatted.equal(expected));

Examples:

joiner can be bidirectional

import std.algorithm.comparison : equal; import std.range : retro;

auto a = [[1, 2, 3], [4, 5]]; auto j = a.joiner; j.back = 44; writeln(a); assert(equal(j.retro, [44, 4, 3, 2, 1]));

template reduce(fun...) if (fun.length >= 1)

Implements the homonym function (also known as accumulate, compress, inject, or foldl) present in various programming languages of functional flavor. There is also fold which does the same thing but with the opposite parameter order. The call reduce!(fun)(seed, range) first assigns seed to an internal variable result, also called the accumulator. Then, for each element x in range, result = fun(result, x)gets evaluated. Finally, result is returned. The one-argument version reduce!(fun)(range)works similarly, but it uses the first element of the range as the seed (the range must be non-empty).

Returns:

the accumulated result

Parameters:

See Also:

Fold (higher-order function)

fold is functionally equivalent to reduce with the argument order reversed, and without the need to use tuple for multiple seeds. This makes it easier to use in UFCS chains.

sum is similar to reduce!((a, b) => a + b) that offers pairwise summing of floating point numbers.

Examples:

Many aggregate range operations turn out to be solved with reducequickly and easily. The example below illustrates reduce's remarkable power and flexibility.

import std.algorithm.comparison : max, min; import std.math.operations : isClose; import std.range;

int[] arr = [ 1, 2, 3, 4, 5 ]; auto sum = reduce!((a,b) => a + b)(0, arr); writeln(sum); sum = reduce!"a + b"(0, arr); writeln(sum); auto largest = reduce!(max)(arr); writeln(largest); largest = arr.reduce!(max); writeln(largest); auto odds = reduce!((a,b) => a + (b & 1))(0, arr); writeln(odds); auto ssquares = reduce!((a,b) => a + b * b)(0, arr); writeln(ssquares); int[] a = [ 3, 4 ]; int[] b = [ 100 ]; auto r = reduce!("a + b")(chain(a, b)); writeln(r); double[] c = [ 2.5, 3.0 ]; auto r1 = reduce!("a + b")(chain(a, b, c)); assert(isClose(r1, 112.5));

auto r2 = chain(a, b, c).reduce!("a + b"); assert(isClose(r2, 112.5));

Examples:

Sometimes it is very useful to compute multiple aggregates in one pass. One advantage is that the computation is faster because the looping overhead is shared. That's why reduce accepts multiple functions. If two or more functions are passed, reduce returns astd.typecons.Tuple object with one member per passed-in function. The number of seeds must be correspondingly increased.

import std.algorithm.comparison : max, min; import std.math.operations : isClose; import std.math.algebraic : sqrt; import std.typecons : tuple, Tuple;

double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ]; auto r = reduce!(min, max)(a); assert(isClose(r[0], 2)); assert(isClose(r[1], 11)); r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a); assert(isClose(r[0], 35)); assert(isClose(r[1], 233)); auto avg = r[0] / a.length; writeln(avg); auto stdev = sqrt(r[1] / a.length - avg * avg); writeln(cast(int)stdev);

auto reduce(R)(R r)
if (isIterable!R);

No-seed version. The first element of r is used as the seed's value.

For each function f in fun, the corresponding seed type S is Unqual!(typeof(f(e, e))), where e is an element of r: ElementType!R for ranges, and ForeachType!R otherwise.

Once S has been determined, then S s = e; and s = f(s, e); must both be legal.

Parameters:

Returns:

the final result of the accumulator applied to the iterable

Throws:

Exception if r is empty

auto reduce(S, R)(S seed, R r)
if (isIterable!R);

Seed version. The seed should be a single value if fun is a single function. If fun is multiple functions, then seed should be a std.typecons.Tuple, with one field per function in f.

For convenience, if the seed is const, or has qualified fields, thenreduce will operate on an unqualified copy. If this happens then the returned type will not perfectly match S.

Use fold instead of reduce to use the seed version in a UFCS chain.

Parameters:

Returns:

the final result of the accumulator applied to the iterable

template fold(fun...) if (fun.length >= 1)

Implements the homonym function (also known as accumulate, compress, inject, or foldl) present in various programming languages of functional flavor, iteratively calling one or more predicates.

Each predicate in fun must take two arguments:

• An accumulator value
• An element of the range r

Each predicate must return a value which implicitly converts to the type of the accumulator.

For a single predicate, the call fold!(fun)(range, seed) will:

• Use seed to initialize an internal variable result (also called the accumulator).
• For each element e in range, evaluate result = fun(result, e).
• Return result.

The one-argument version fold!(fun)(range)works similarly, but it uses the first element of the range as the seed (the range must be non-empty) and iterates over the remaining elements.

Multiple results are produced when using multiple predicates.

Parameters:

See Also:

• Fold (higher-order function)
• sum is similar to fold!((a, b) => a + b) that offers precise summing of floating point numbers.
• fold is functionally equivalent to reduce with the argument order reversed, and without the need to use tuple for multiple seeds.

Examples:

immutable arr = [1, 2, 3, 4, 5];

writeln(arr.fold!((a, e) => a + e)); writeln(arr.fold!((a, e) => a + e)(6)); import std.algorithm.comparison : min, max; import std.typecons : tuple;

writeln(arr.fold!(min, max)); writeln(arr.fold!(min, max)(0, 7)); writeln(arr.map!(a => a + 1).fold!((a, e) => a + e)); writeln(arr.fold!((a, e) => e));

auto fold(R, S...)(R r, S seeds);

Parameters:

Returns:

Either the accumulated result for a single predicate, or aTuple of results.

template cumulativeFold(fun...) if (fun.length >= 1)

Similar to fold, but returns a range containing the successive reduced values. The call cumulativeFold!(fun)(range, seed) first assigns seed to an internal variable result, also called the accumulator. The returned range contains the values result = fun(result, x) lazily evaluated for each element x in range. Finally, the last element has the same value as fold!(fun)(seed, range). The one-argument version cumulativeFold!(fun)(range) works similarly, but it returns the first element unchanged and uses it as seed for the next elements. This function is also known aspartial_sum,accumulate,scan,Cumulative Sum.

Parameters:

Returns:

The function returns a range containing the consecutive reduced values. If there is more than one fun, the element type will be std.typecons.Tuple containing one element for each fun.

NoteIn functional programming languages this is typically called scan, scanl,scanLeft or reductions.

Examples:

import std.algorithm.comparison : max, min; import std.array : array; import std.math.operations : isClose; import std.range : chain;

int[] arr = [1, 2, 3, 4, 5]; auto sum = cumulativeFold!((a, b) => a + b)(arr, 0); writeln(sum.array); auto sum2 = cumulativeFold!"a + b"(arr, 0); writeln(sum2.array); auto largest = cumulativeFold!max(arr); writeln(largest.array); largest = arr.cumulativeFold!max; writeln(largest.array); auto odds = arr.cumulativeFold!((a, b) => a + (b & 1))(0); writeln(odds.array); auto ssquares = arr.cumulativeFold!((a, b) => a + b * b)(0); writeln(ssquares.array); int[] a = [3, 4]; int[] b = [100]; auto r = cumulativeFold!"a + b"(chain(a, b)); writeln(r.array); double[] c = [2.5, 3.0]; auto r1 = cumulativeFold!"a + b"(chain(a, b, c)); assert(isClose(r1, [3, 7, 107, 109.5, 112.5]));

auto r2 = chain(a, b, c).cumulativeFold!"a + b"; assert(isClose(r2, [3, 7, 107, 109.5, 112.5]));

Examples:

Sometimes it is very useful to compute multiple aggregates in one pass. One advantage is that the computation is faster because the looping overhead is shared. That's why cumulativeFold accepts multiple functions. If two or more functions are passed, cumulativeFold returns a std.typecons.Tuple object with one member per passed-in function. The number of seeds must be correspondingly increased.

import std.algorithm.comparison : max, min; import std.algorithm.iteration : map; import std.math.operations : isClose; import std.typecons : tuple;

double[] a = [3.0, 4, 7, 11, 3, 2, 5]; auto r = a.cumulativeFold!(min, max); assert(isClose(r.map!"a[0]", [3, 3, 3, 3, 3, 2, 2])); assert(isClose(r.map!"a[1]", [3, 4, 7, 11, 11, 11, 11])); auto r2 = a.cumulativeFold!("a + b", "a + b * b")(tuple(0.0, 0.0)); assert(isClose(r2.map!"a[0]", [3, 7, 14, 25, 28, 30, 35])); assert(isClose(r2.map!"a[1]", [9, 25, 74, 195, 204, 208, 233]));

auto cumulativeFold(R)(R range)
if (isInputRange!(Unqual!R));

No-seed version. The first element of r is used as the seed's value. For each function f in fun, the corresponding seed type S isUnqual!(typeof(f(e, e))), where e is an element of r:ElementType!R. Once S has been determined, then S s = e; and s = f(s, e); must both be legal.

Returns:

a range containing the consecutive reduced values.

auto cumulativeFold(R, S)(R range, S seed)
if (isInputRange!(Unqual!R));

Seed version. The seed should be a single value if fun is a single function. If fun is multiple functions, then seed should be astd.typecons.Tuple, with one field per function in f. For convenience, if the seed is const, or has qualified fields, thencumulativeFold will operate on an unqualified copy. If this happens then the returned type will not perfectly match S.

Parameters:

Returns:

a range containing the consecutive reduced values.

auto splitter(alias pred = "a == b", Flag!"keepSeparators" keepSeparators = No.keepSeparators, Range, Separator)(Range r, Separator s)
if (is(typeof(binaryFun!pred(r.front, s)) : bool) && (hasSlicing!Range && hasLength!Range || isNarrowString!Range));

auto splitter(alias pred = "a == b", Flag!"keepSeparators" keepSeparators = No.keepSeparators, Range, Separator)(Range r, Separator s)
if (is(typeof(binaryFun!pred(r.front, s.front)) : bool) && (hasSlicing!Range || isNarrowString!Range) && isForwardRange!Separator && (hasLength!Separator || isNarrowString!Separator));

auto splitter(alias isTerminator, Range)(Range r)
if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(r.front))));

Lazily splits a range using an element or range as a separator. Separator ranges can be any narrow string type or sliceable range type.

Two adjacent separators are considered to surround an empty element in the split range. Use filter!(a => !a.empty) on the result to compress empty elements.

The predicate is passed to std.functional.binaryFun and accepts any callable function that can be executed via pred(element, s).

NotesIf splitting a string on whitespace and token compression is desired, consider using splitter without specifying a separator.

If no separator is passed, the predicate isTerminator decides whether to accept an element of r.

Parameters:

ConstraintsThe predicate pred needs to accept an element of r and the separator s.

Returns:

An input range of the subranges of elements between separators. If r is a forward range or bidirectional range, the returned range will be likewise. When a range is used a separator, bidirectionality isn't possible.

If keepSeparators is equal to Yes.keepSeparators the output will also contain the separators.

If an empty range is given, the result is an empty range. If a range with one separator is given, the result is a range with two empty elements.

See Also:

std.regex.splitter for a version that splits using a regular expression defined separator,std.array.split for a version that splits eagerly andsplitWhen, which compares adjacent elements instead of element against separator.

Examples:

Basic splitting with characters and numbers.

import std.algorithm.comparison : equal;

assert("a|bc|def".splitter('|').equal([ "a", "bc", "def" ]));

int[] a = [1, 0, 2, 3, 0, 4, 5, 6]; int[][] w = [ [1], [2, 3], [4, 5, 6] ]; assert(a.splitter(0).equal(w));

Examples:

Basic splitting with characters and numbers and keeping sentinels.

import std.algorithm.comparison : equal; import std.typecons : Yes;

assert("a|bc|def".splitter!("a == b", Yes.keepSeparators)('|') .equal([ "a", "|", "bc", "|", "def" ]));

int[] a = [1, 0, 2, 3, 0, 4, 5, 6]; int[][] w = [ [1], [0], [2, 3], [0], [4, 5, 6] ]; assert(a.splitter!("a == b", Yes.keepSeparators)(0).equal(w));

Examples:

Adjacent separators.

import std.algorithm.comparison : equal;

assert("|ab|".splitter('|').equal([ "", "ab", "" ])); assert("ab".splitter('|').equal([ "ab" ]));

assert("a|b||c".splitter('|').equal([ "a", "b", "", "c" ])); assert("hello world".splitter(' ').equal([ "hello", "", "world" ]));

auto a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; auto w = [ [1, 2], [], [3], [4, 5], [] ]; assert(a.splitter(0).equal(w));

Examples:

Adjacent separators and keeping sentinels.

import std.algorithm.comparison : equal; import std.typecons : Yes;

assert("|ab|".splitter!("a == b", Yes.keepSeparators)('|') .equal([ "", "|", "ab", "|", "" ])); assert("ab".splitter!("a == b", Yes.keepSeparators)('|') .equal([ "ab" ]));

assert("a|b||c".splitter!("a == b", Yes.keepSeparators)('|') .equal([ "a", "|", "b", "|", "", "|", "c" ])); assert("hello world".splitter!("a == b", Yes.keepSeparators)(' ') .equal([ "hello", " ", "", " ", "world" ]));

auto a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; auto w = [ [1, 2], [0], [], [0], [3], [0], [4, 5], [0], [] ]; assert(a.splitter!("a == b", Yes.keepSeparators)(0).equal(w));

Examples:

Empty and separator-only ranges.

import std.algorithm.comparison : equal; import std.range : empty;

assert("".splitter('|').empty); assert("|".splitter('|').equal([ "", "" ])); assert("||".splitter('|').equal([ "", "", "" ]));

Examples:

Empty and separator-only ranges and keeping sentinels.

import std.algorithm.comparison : equal; import std.typecons : Yes; import std.range : empty;

assert("".splitter!("a == b", Yes.keepSeparators)('|').empty); assert("|".splitter!("a == b", Yes.keepSeparators)('|') .equal([ "", "|", "" ])); assert("||".splitter!("a == b", Yes.keepSeparators)('|') .equal([ "", "|", "", "|", "" ]));

Examples:

Use a range for splitting

import std.algorithm.comparison : equal;

assert("a=>bc=>def".splitter("=>").equal([ "a", "bc", "def" ])); assert("a|b||c".splitter("||").equal([ "a|b", "c" ])); assert("hello world".splitter(" ").equal([ "hello", "world" ]));

int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; int[][] w = [ [1, 2], [3, 0, 4, 5, 0] ]; assert(a.splitter([0, 0]).equal(w));

a = [ 0, 0 ]; assert(a.splitter([0, 0]).equal([ (int[]).init, (int[]).init ]));

a = [ 0, 0, 1 ]; assert(a.splitter([0, 0]).equal([ [], [1] ]));

Examples:

Use a range for splitting

import std.algorithm.comparison : equal; import std.typecons : Yes;

assert("a=>bc=>def".splitter!("a == b", Yes.keepSeparators)("=>") .equal([ "a", "=>", "bc", "=>", "def" ])); assert("a|b||c".splitter!("a == b", Yes.keepSeparators)("||") .equal([ "a|b", "||", "c" ])); assert("hello world".splitter!("a == b", Yes.keepSeparators)(" ") .equal([ "hello", " ", "world" ]));

int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; int[][] w = [ [1, 2], [0, 0], [3, 0, 4, 5, 0] ]; assert(a.splitter!("a == b", Yes.keepSeparators)([0, 0]).equal(w));

a = [ 0, 0 ]; assert(a.splitter!("a == b", Yes.keepSeparators)([0, 0]) .equal([ (int[]).init, [0, 0], (int[]).init ]));

a = [ 0, 0, 1 ]; assert(a.splitter!("a == b", Yes.keepSeparators)([0, 0]) .equal([ [], [0, 0], [1] ]));

Examples:

Custom predicate functions.

import std.algorithm.comparison : equal; import std.ascii : toLower;

assert("abXcdxef".splitter!"a.toLower == b"('x').equal( [ "ab", "cd", "ef" ]));

auto w = [ [0], [1], [2] ]; assert(w.splitter!"a.front == b"(1).equal([ [[0]], [[2]] ]));

Examples:

Custom predicate functions.

import std.algorithm.comparison : equal; import std.typecons : Yes; import std.ascii : toLower;

assert("abXcdxef".splitter!("a.toLower == b", Yes.keepSeparators)('x') .equal([ "ab", "X", "cd", "x", "ef" ]));

auto w = [ [0], [1], [2] ]; assert(w.splitter!("a.front == b", Yes.keepSeparators)(1) .equal([ [[0]], [[1]], [[2]] ]));

Examples:

Use splitter without a separator

import std.algorithm.comparison : equal; import std.range.primitives : front;

assert(equal(splitter!(a => a == '|')("a|bc|def"), [ "a", "bc", "def" ])); assert(equal(splitter!(a => a == ' ')("hello world"), [ "hello", "", "world" ]));

int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; int[][] w = [ [1, 2], [], [3], [4, 5], [] ]; assert(equal(splitter!(a => a == 0)(a), w));

a = [ 0 ]; assert(equal(splitter!(a => a == 0)(a), [ (int[]).init, (int[]).init ]));

a = [ 0, 1 ]; assert(equal(splitter!(a => a == 0)(a), [ [], [1] ]));

w = [ [0], [1], [2] ]; assert(equal(splitter!(a => a.front == 1)(w), [ [[0]], [[2]] ]));

Examples:

Leading separators, trailing separators, or no separators.

import std.algorithm.comparison : equal;

assert("|ab|".splitter('|').equal([ "", "ab", "" ])); assert("ab".splitter('|').equal([ "ab" ]));

Examples:

Leading separators, trailing separators, or no separators.

import std.algorithm.comparison : equal; import std.typecons : Yes;

assert("|ab|".splitter!("a == b", Yes.keepSeparators)('|') .equal([ "", "|", "ab", "|", "" ])); assert("ab".splitter!("a == b", Yes.keepSeparators)('|') .equal([ "ab" ]));

Examples:

Splitter returns bidirectional ranges if the delimiter is a single element

import std.algorithm.comparison : equal; import std.range : retro; assert("a|bc|def".splitter('|').retro.equal([ "def", "bc", "a" ]));

Examples:

Splitter returns bidirectional ranges if the delimiter is a single element

import std.algorithm.comparison : equal; import std.typecons : Yes; import std.range : retro; assert("a|bc|def".splitter!("a == b", Yes.keepSeparators)('|') .retro.equal([ "def", "|", "bc", "|", "a" ]));

Examples:

Splitting by word lazily

import std.ascii : isWhite; import std.algorithm.comparison : equal; import std.algorithm.iteration : splitter;

string str = "Hello World!"; assert(str.splitter!(isWhite).equal(["Hello", "World!"]));

auto splitter(Range)(Range s)
if (isSomeString!Range || isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && !isConvertibleToString!Range && isSomeChar!(ElementEncodingType!Range));

Lazily splits the character-based range s into words, using whitespace as the delimiter.

This function is character-range specific and, contrary tosplitter!(std.uni.isWhite), runs of whitespace will be merged together (no empty tokens will be produced).

Parameters:

Returns:

An input range of slices of the original range split by whitespace.

Examples:

import std.algorithm.comparison : equal; auto a = " a bcd ef gh "; assert(equal(splitter(a), ["a", "bcd", "ef", "gh"][]));

template substitute(substs...) if (substs.length >= 2 && isExpressions!substs)

auto substitute(alias pred = (a, b) => a == b, R, Substs...)(R r, Substs substs)
if (isInputRange!R && (Substs.length >= 2) && !is(CommonType!Substs == void));

Returns a range with all occurrences of substs in r. replaced with their substitution.

Single value replacements ('ö'.substitute!('ä', 'a', 'ö', 'o', 'ü', 'u)) are supported as well and in Ο(1).

Parameters:

Returns:

a range with the substitutions replaced.

Examples:

import std.algorithm.comparison : equal;

assert("do_it".substitute('_', ' ').equal("do it"));

assert("do_it".substitute('_', ' ', 'd', 'g', 'i', 't', 't', 'o') .equal("go to"));

assert("do_it".substitute("_", " ", "do", "done") .equal("done it"));

int[] x = [1, 2, 3]; auto y = x.substitute(1, 0.1); assert(y.equal([0.1, 2, 3])); static assert(is(typeof(y.front) == double));

import std.range : retro; assert([1, 2, 3].substitute(1, 0.1).retro.equal([3, 2, 0.1]));

Examples:

Use the faster compile-time overload

import std.algorithm.comparison : equal;

assert("apple_tree".substitute!("apple", "banana", "tree", "shrub").equal("banana_shrub"));

assert("apple_tree".substitute!('a', 'b', 't', 'f').equal("bpple_free"));

writeln('a'.substitute!('a', 'b', 't', 'f'));

Examples:

Multiple substitutes

import std.algorithm.comparison : equal; import std.range.primitives : ElementType;

int[3] x = [1, 2, 3]; auto y = x[].substitute(1, 0.1) .substitute(0.1, 0.2); static assert(is(typeof(y.front) == double)); assert(y.equal([0.2, 2, 3]));

auto z = "42".substitute('2', '3') .substitute('3', '1'); static assert(is(ElementType!(typeof(z)) == dchar)); assert(equal(z, "41"));

auto substitute(Value)(Value value)
if (isInputRange!Value || !is(CommonType!(Value, typeof(substs[0])) == void));

Substitute single values with compile-time substitution mappings.

Complexity Ο(1) due to D's switch guaranteeing Ο(1);

auto sum(R)(R r)
if (isInputRange!R && !isInfinite!R && is(typeof(r.front + r.front)));

auto sum(R, E)(R r, E seed)
if (isInputRange!R && !isInfinite!R && is(typeof(seed = seed + r.front)));

Sums elements of r, which must be a finiteinput range. Although conceptually sum(r) is equivalent to fold!((a, b) => a + b)(r, 0), sum uses specialized algorithms to maximize accuracy, as follows.

• If std.range.primitives.ElementType!R is a floating-point type and R is arandom-access range with length and slicing, then sum uses thepairwise summationalgorithm.
• If ElementType!R is a floating-point type and R is a finite input range (but not a random-access range with slicing), thensum uses the Kahan summation algorithm.
• In all other cases, a simple element by element addition is done.

For floating point inputs, calculations are made inrealprecision for real inputs and in double precision otherwise (Note this is a special case that deviates from fold's behavior, which would have kept float precision for a float range). For all other types, the calculations are done in the same type obtained from from adding two elements of the range, which may be a different type from the elements themselves (for example, in case ofintegral promotion).

A seed may be passed to sum. Not only will this seed be used as an initial value, but its type will override all the above, and determine the algorithm and precision used for summation. If a seed is not passed, one is created with the value of typeof(r.front + r.front)(0), or typeof(r.front + r.front).zeroif no constructor exists that takes an int.

Note that these specialized summing algorithms execute more primitive operations than vanilla summation. Therefore, if in certain cases maximum speed is required at expense of precision, one can use fold!((a, b) => a + b)(r, 0), which is not specialized for summation.

Parameters:

Returns:

The sum of all the elements in the range r.

Examples:

Ditto

import std.range;

writeln(sum([1, 2, 3, 4])); writeln(sum([false, true, true, false, true])); writeln(sum(ubyte.max.repeat(100))); writeln(uint.max.repeat(3).sum()); writeln(uint.max.repeat(3).sum(ulong.init)); writeln(sum([1.0, 2.0, 3.0, 4.0])); static assert(is(typeof(sum([1F, 2F, 3F, 4F])) == double)); writeln(sum([1F, 2, 3, 4])); import std.math.operations : isClose; assert(iota(ulong.max / 2, ulong.max / 2 + 4096).sum(0.0) .isClose((ulong.max / 2) * 4096.0 + 4096^^2 / 2));

T mean(T = double, R)(R r)
if (isInputRange!R && isNumeric!(ElementType!R) && !isInfinite!R);

auto mean(R, T)(R r, T seed)
if (isInputRange!R && !isNumeric!(ElementType!R) && is(typeof(r.front + seed)) && is(typeof(r.front / size_t(1))) && !isInfinite!R);

Finds the mean (colloquially known as the average) of a range.

For built-in numerical types, accurate Knuth & Welford mean calculation is used. For user-defined types, element by element summation is used. Additionally an extra parameter seed is needed in order to correctly seed the summation with the equivalent to 0.

The first overload of this function will return T.init if the range is empty. However, the second overload will return seed on empty ranges.

This function is Ο(r.length).

Parameters:

Returns:

The mean of r when r is non-empty.

Examples:

import std.math.operations : isClose; import std.math.traits : isNaN;

static immutable arr1 = [1, 2, 3]; static immutable arr2 = [1.5, 2.5, 12.5];

assert(arr1.mean.isClose(2)); assert(arr2.mean.isClose(5.5));

assert(arr1[0 .. 0].mean.isNaN);

auto uniq(alias pred = "a == b", Range)(Range r)
if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, r.front)) == bool));

Lazily iterates unique consecutive elements of the given range, which is assumed to be sorted (functionality akin to theuniq system utility). Equivalence of elements is assessed by using the predicatepred, by default "a == b". The predicate is passed tostd.functional.binaryFun, and can either accept a string, or any callable that can be executed via pred(element, element). If the given range is bidirectional, uniq also yields abidirectional range.

Parameters:

Returns:

An input range of consecutively unique elements in the original range. If r is also a forward range or bidirectional range, the returned range will be likewise.

Examples:

import std.algorithm.comparison : equal; import std.algorithm.mutation : copy;

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));

arr.length -= arr.uniq().copy(arr).length; writeln(arr); assert(equal(uniq([ 1, 1, 2, 1, 1, 3, 1]), [1, 2, 1, 3, 1]));

Permutations!Range permutations(Range)(Range r);

struct Permutations(Range);

Examples:

import std.algorithm.comparison : equal; import std.range : iota; assert(equal!equal(iota(3).permutations, [[0, 1, 2], [1, 0, 2], [2, 0, 1], [0, 2, 1], [1, 2, 0], [2, 1, 0]]));

Copyright © 1999-2025 by the D Language Foundation | Page generated byDdoc on Sun Jun 15 08:06:03 2025