std.algorithm.iteration

This is a submodule of std.algorithm. It contains generic iteration algorithms.

Copyright

Andrei Alexandrescu 2008-.

License

Authors

tmpl ChunkByImplIsUnary cumulativeFold each filter filterBidirectional fold hasDifferentAutodecoding map reduce ReduceSeedType substitute

enum GroupingOpType

struct _Cache ChunkByChunkImpl ChunkByGroup ChunkByImpl ChunkByImpl ChunkByOuter FilterBidiResult FilterResult Group LazyCache MapResult Permutations SplitterResult UniqResult

fn cache cacheBidirectional chunkBy group joiner lazyCache mean permutations splitter splitWhen substitute sum sumKahan sumPair sumPairwise sumPairwise16 sumPairwiseN uniq

Types 15

private struct_Cache(R, bool bidir)

Fields

R source

CacheTypes caches

Methods

E front() @property

void popFront()

Constructors

this(R range)

private structLazyCache(R, bool bidir)

Fields

R source

CacheTypes caches

bool frontCached

Methods

E front() @property

void popFront()

Constructors

this(R range)

private structMapResult(alias fun, Range)

Fields

R _input

Methods

void popFront()

@property auto ref front()

Constructors

this(R input)

private structFilterResult(alias pred, Range)

Fields

R _input

private bool _primed

Methods

private void prime()

auto opSlice()

void popFront()

@property auto ref front()

Constructors

this(R r)

this(R r, bool primed)

private structFilterBidiResult(alias pred, Range)

Fields

R _input

Methods

bool empty() @property

void popFront()

@property auto ref front()

void popBack()

@property auto ref back()

@property auto save()

Constructors

this(R r)

structGroup(alias pred, R) if (isInputRange!R)

ditto

Fields

private R _input

private Tuple!(MutableE, uint) _current

Methods

void popFront()

@property auto ref front()Returns: the front of the range

Constructors

this(R input)

this(R input, Tuple!(MutableE, uint) current)

private structChunkByChunkImpl(alias pred, Range) if (isInputRange!Range && !isForwardRange!Range)

Fields

private Range *r r

private ElementType!Range prev

Methods

bool empty() @property

ElementType!Range front() @property

void popFront()

Constructors

this(ref Range range, ElementType!Range _prev)

private structChunkByImpl(alias pred, Range) if (isInputRange!Range && !isForwardRange!Range)

Fields

bool isUnary

private Range r

private ElementType!Range _prev

private bool openChunk

Methods

bool empty() @property

@property auto front()

void popFront()

Constructors

this(Range _r)

private structChunkByOuter(Range, bool eqEquivalenceAssured)

Fields

size_t groupNum

Range current

Range next

private structChunkByGroup(alias eq, Range, bool eqEquivalenceAssured)

Fields

private size_t groupNum

private Range current

Methods

private @trusted ref cargo()

bool empty() @property

@property auto ref front()

void popFront()

@property auto save()

Constructors

this(ref RefCounted!(OuterRange) origin)

Destructors

~this

private enumGroupingOpType

binaryEquivalent

binaryAny

unary

private structChunkByImpl(alias pred, alias eq, GroupingOpType opType, Range) if (isForwardRange!Range)

Fields

bool eqEquivalenceAssured

Methods

private @trusted ref impl()

private @trusted ref implPL()

bool empty() @property

@property auto save()

Constructors

this(Range r)

Destructors

~this

private structSplitterResult(alias isTerminator, Range)

Fields

(hasLength!Range && hasSlicing!Range) || isSomeString!Range fullSlicing

private Range _input

private size_t _end

Methods

private void findTerminator()

@property auto front()

void popFront()

typeof(this) save() @property

Constructors

this(Range input)

private structUniqResult(alias pred, Range)

Fields

Range _input

Methods

auto opSlice()

void popFront()

ElementType!Range front() @property

Constructors

this(Range input)

structPermutations(Range)

ditto

Fields

private size_t[] _indices

private Range _r

private bool _empty

Methods

bool empty() @property const pure nothrow @safe @nogcReturns: `true` if the range is empty, `false` otherwise.

@property auto front()Returns: the front of the range

void popFront()

auto save()Returns: an independent copy of the permutations range.

Constructors

this(Range r)

this(size_t[] indices, size_t[] state, Range r, bool empty_)

Functions 24

fnauto cache(Range)(Range range) if (isInputRange!Range)`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-evalua...

fnauto cacheBidirectional(Range)(Range range) if (isBidirectionalRange!Range)ditto

fnauto lazyCache(Range)(Range range) if (isInputRange!Range)Similar to `cache`, but lazily evaluates the elements. Unlike `cache`, this function does not eagerly evaluate the front of the range until it's explicitly requested.

fnGroup!(pred, Range) group(alias pred = "a == b", Range)(Range r)Groups consecutively equivalent elements into a single tuple of the element and the number of its repetitions.

fnauto 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`.

auto splitWhen(alias  pred,  Range)(Range r) if (is(typeof(binaryFun!pred(r.front,  r.front)) :  bool)  &&  isForwardRange!Range)

Splits a forward range into subranges in places determined by a binary predicate called with adjacent elements.

fnauto joiner(RoR, Separator)(RoR r, Separator sep)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 ...

fnauto joiner(RoR)(RoR r) if (isInputRange!RoR && isInputRange!(Unqual!(ElementType!RoR)))Ditto

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))

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

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))

ditto

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

Lazily splits a range `r` whenever a predicate `isTerminator` returns true for an element.

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.

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

ditto

fnauto sum(R)(R r) if (isInputRange!R && !isInfinite!R && is(typeof(r.front + r.front)))Sums elements of `r`, which must be a finite input range. Although conceptually `sum(r)` is equivalent to fold!((a, b) => a + b)(r, 0), `sum` uses specialized algorithms to maximize accuracy, as fo...

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

private fnauto sumPairwise(F, R)(R data) if (isInputRange!R && !isInfinite!R)

private fnauto sumPairwise16(F, R)(R r) if (isRandomAccessRange!R)

private fnauto sumPair(bool needEmptyChecks, F, R)(ref R r) if (isForwardRange!R && !isRandomAccessRange!R)

private fnauto sumPairwiseN(size_t N, bool needEmptyChecks, F, R)(ref R r) if (isForwardRange!R && !isRandomAccessRange!R)

private fnauto sumKahan(Result, R)(Result result, R r)

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

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

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)

ditto

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 the wikipedia.org/wiki/Uniq system utility). Equivalence of elements is assessed...

fnPermutations!Range permutations(Range)(Range r)Lazily computes all permutations of `r` using en.wikipedia.org/wiki/Heap%27salgorithm.

Templates 11

tmplmap(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

fun one or more transformation functions

Parameters

`r`	an input 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.

tmpleach(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. parallel.

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

Parameters

`fun`	function to apply to _each element of the range
`r`	range or iterable over which `each` iterates

Returns

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

stopping.

Parameters

`r`	range or iterable over which each iterates

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

ditto

tmplfilter(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 unaryFun, and can be either a string, or any callable that can be executed via pred(element).

Parameters

predicate Function to apply to each element of range

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.

Parameters

range An input range of elements

Returns

A range containing only elements x in range for

which predicate(x) returns true.

tmplfilterBidirectional(alias pred)

Similar to filter, except it defines a

bidirectional 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,

retro can be applied against the filtered range.

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

Parameters

pred Function to apply to each element of range

Functions

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

Parameters

`r`	Bidirectional range of elements

Returns

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

tmplChunkByImplIsUnary(alias pred, Range)

tmplreduce(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.

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

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, else this throws).

If range has only one element, the functions are never invoked and result and the seed is returned unchanged.

Returns

the accumulated result

Parameters

fun one or more functions of the form Acc function(Acc, ElemT)

Parameters

`r`	an iterable value as defined by `isIterable`

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 Tuple, with one field per function in f.

For convenience, if the seed is const, or has qualified fields, then reduce 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

`seed`	the initial value of the accumulator
`r`	an iterable value as defined by `isIterable`

Returns

the final result of the accumulator applied to the iterable

auto reducePreImpl(R, Args...)(R r, ref Args args)

auto reduceImpl(bool mustInitialize, R, Args...)(R r, ref Args args) if (isIterable!R)

tmplReduceSeedType(E)

tmplfold(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 function must return a value which implicitly converts to the

type of the accumulator.

For a single function,

the call fold!(fun)(range, seed) will:

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

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 functions.

If range has only one element, the functions are never invoked and result and the seed is returned unchanged.

Parameters

fun one or more functions of the form Acc function(Acc, ElemT)

Parameters

`r`	the input range to fold
`seeds`	the initial values of each accumulator (optional), one for each predicate

Returns

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

tmplcumulativeFold(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 as

partial_sum, accumulate, scan, Cumulative Sum.

Parameters

fun one or more functions of the form Acc function(Acc, ElemT)

Returns

The function returns a range containing the consecutive reduced values. If

there is more than one fun, the element type will be Tuple containing one element for each fun.

Note

In functional programming languages this is typically called scan, scanl,

scanLeft or reductions.

Functions

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 is Unqual!(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.

Parameters

range An input range

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 a

Tuple, with one field per function in f.

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

Parameters

`range`	An input range
`seed`	the initial value of the accumulator

Returns

a range containing the consecutive reduced values.

auto cumulativeFoldImpl(R, Args...)(R range, ref Args args)

tmplhasDifferentAutodecoding(Range, Needles...)

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

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

`r`	an input range
`value`	a single value which can be substituted in 1
`substs`	a set of replacements/substitutions
`pred`	the equality function to test if element(s) are equal to a substitution

Returns

a range with the substitutions replaced.

std.algorithm.iteration

Copyright

License

Authors

Types 15

Functions 24

Templates 11

Parameters

See Also

Parameters

Returns

Parameters

Returns

See Also

Parameters

Parameters

Returns

See Also

Parameters

Returns

Parameters

Parameters

Returns

Returns

Parameters

See Also

Parameters

Returns

Throws

Parameters

Returns

Parameters

See Also

Parameters

Returns

Parameters

Returns

See Also

Note

Parameters

Returns

Parameters

Returns

Parameters

Returns

See Also