Menu

- Learn
- Documentation
  - Language Reference
  - Library Reference
  - Command-line Reference
  - Feature Overview
  - Articles
- Downloads
- Packages
- Community
  - Blog
  - Orgs using D
  - Twitter
  - Calendar
  - Forums
  - IRC
  - Wiki
  - GitHub
  - Issues
  - Get involved
  - Contributors
  - Foundation
  - Security Team
  - Donate
  - Sponsors
- Resources
  - Tour
  - Books
  - Tutorials
  - Tools
  - Editors
  - IDEs
  - run.dlang.io
  - Visual D
  - Acknowledgments
  - D Style
  - Glossary
  - Sitemap

Search
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using a local clone.

# std.algorithm.iteration

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

Cheat Sheet
Function Name | Description
--- | ---
cache | Eagerly evaluates and caches another range's front.
cacheBidirectional | As above, but also provides back and popBack.
chunkBy | chunkBy!((a,b) => a[1] == b[1])([[1, 1], [1, 2], [2, 2], [2, 1]]) returns a range containing 3 subranges: the first with just [1, 1]; the second with the elements [1, 2] and [2, 2]; and the third with just [2, 1].
cumulativeFold | cumulativeFold!((a, b) => a + b)([1, 2, 3, 4]) returns a lazily-evaluated range containing the successive reduced values 1, 3, 6, 10.
each | each!writeln([1, 2, 3]) eagerly prints the numbers 1, 2 and 3 on their own lines.
filter | filter!(a => a > 0)([1, -1, 2, 0, -3]) iterates over elements 1 and 2.
filterBidirectional | Similar to filter, but also provides back and popBack at a small increase in cost.
fold | fold!((a, b) => a + b)([1, 2, 3, 4]) returns 10.
group | group([5, 2, 2, 3, 3]) returns a range containing the tuples tuple(5, 1), tuple(2, 2), and tuple(3, 2).
joiner | joiner(["hello", "world!"], "; ") returns a range that iterates over the characters "hello; world!". No new string is created - the existing inputs are iterated.
map | map!(a => a * 2)([1, 2, 3]) lazily returns a range with the numbers 2, 4, 6.
mean | Colloquially known as the average, mean([1, 2, 3]) returns 2.
permutations | Lazily computes all permutations using Heap's algorithm.
reduce | reduce!((a, b) => a + b)([1, 2, 3, 4]) returns 10. This is the old implementation of fold.
splitter | Lazily splits a range by a separator.
substitute | [1, 2].substitute(1, 0.1) returns [0.1, 2].
sum | Same as fold, but specialized for accurate summation.
uniq | Iterates over the unique elements in a range, which is assumed sorted.

License:
Boost License 1.0.
Authors:
Andrei Alexandrescu

Source std/algorithm/iteration.d

auto `cache`(Range)(Range `range`)
if (isInputRange!Range);
auto `cacheBidirectional`(Range)(Range `range`)
if (isBidirectionalRange!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-evaluated.
  This can be a useful function to place in a chain, after functions that have expensive evaluation, as a lazy alternative to std.array.array. In particular, it can be placed after a call to map, or before a call std.range.filter or std.range.tee
  `cache` may provide bidirectional range iteration if needed, but since this comes at an increased cost, it must be explicitly requested via the call to `cacheBidirectional`. Furthermore, a bidirectional cache will evaluate the "center" element twice, when there is only one element left in the range.
  `cache` does not provide random access primitives, as `cache` would be unable to cache the random accesses. If Range provides slicing primitives, then `cache` will provide the same slicing primitives, but hasSlicing!Cache will not yield true (as the std.range.primitives.hasSlicing trait also checks for random access).
  Parameters:

  Range `range` | an input range

  Returns:
  An input range with the cached values of range
  Examples:

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

      ulong counter = 0;
      double fun(int x)
      {
          ++counter;
          // http://en.wikipedia.org/wiki/Quartic_function
          return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5;
      }
      // Without cache, with array (greedy)
      auto result1 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()
                               .filter!(a => a[1] < 0)()
                               .map!(a => a[0])()
                               .array();

      // the values of x that have a negative y are:
      assert(equal(result1, [-3, -2, 2]));

      // Check how many times fun was evaluated.
      // As many times as the number of items in both source and result.
      writeln(counter); // iota(-4, 5).length + result1.length

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

      // the values of x that have a negative y are:
      assert(equal(result2, [-3, -2, 2]));

      // Check how many times fun was evaluated.
      // Only as many times as the number of items in source.
      writeln(counter); // iota(-4, 5).length

  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 `cache` may 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); //The last "seen" element was 2. The data in cache has been cleared.

      assert(equal(r2, [0, 1, 2]));
      assert(i == 3); //cache has accessed 3. It is still stored internally by cache.

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:

  fun | one or more transformation functions

  See Also:
  Map (higher-order function)
  Examples:

      import std.algorithm.comparison : equal;
      import std.range : chain;
      int[] arr1 = [ 1, 2, 3, 4 ];
      int[] arr2 = [ 5, 6 ];
      auto squares = map!(a => a * a)(chain(arr1, arr2));
      assert(equal(squares, [ 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]); // sums[i]
          writeln(result[1]); // products[i]
          ++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));
    Parameters:

    Range `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.
template `each`(alias fun = "a")
  Eagerly iterates over r and calls fun over 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:

  fun | function to apply to each element of the range
  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.
  See Also:
  std.range.tee
  Examples:

      import std.range : iota;
      import std.typecons : Flag, Yes, No;

      long[] arr;
      iota(5).each!(n => arr ~= n);
      writeln(arr); // [0, 1, 2, 3, 4]
      iota(5).each!((n) { arr ~= n; return No.each; });
      writeln(arr); // [0, 1, 2, 3, 4, 0]

      // If the range supports it, the value can be mutated in place
      arr.each!((ref n) => n++);
      writeln(arr); // [1, 2, 3, 4, 5, 1]

      arr.each!"a++";
      writeln(arr); // [2, 3, 4, 5, 6, 2]

      // by-ref lambdas are not allowed for non-ref ranges
      static assert(!is(typeof(arr.map!(n => n).each!((ref n) => n++))));

      // The default predicate consumes the range
      auto m = arr.map!(n => n);
      (&m).each();
      assert(m.empty);

      // Indexes are also available for in-place mutations
      arr[] = 0;
      arr.each!"a=i"();
      writeln(arr); // [0, 1, 2, 3, 4, 5]

      // 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); // 1

  Examples:
  `each` works with iterable objects which provide an index variable, along with each element

      import std.range : iota, lockstep;

      auto arr = [1, 2, 3, 4];

      // 1 ref parameter
      arr.each!((ref e) => e = 0);
      writeln(arr.sum); // 0

      // 1 ref parameter and index
      arr.each!((i, ref e) => e = cast(int) i);
      writeln(arr.sum); // 4.iota.sum

  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:

    Range `r` | range or iterable over which each iterates

template `filter`(alias predicate) if (is(typeof(unaryFun!predicate)))
  Implements the higher order filter function. 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:

  predicate | Function to apply to each element of range

  Returns:
  `filter`!(predicate)(range) returns a new range containing only elements x in range for which predicate(x) returns true.
  See Also:
  Filter (higher-order function)
  Examples:

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

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

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

      // Filter again, but with Uniform Function Call Syntax (UFCS)
      auto sum = arr.filter!(a => a < 3);
      assert(equal(sum, [ 1, 2 ]));

      // In combination with chain() to span multiple ranges
      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 ]));

      // Mixing convertible types is fair game, too
      double[] c = [ 2.5, 3.0 ];
      auto r1 = chain(c, a, b).filter!(a => cast(int) a != a);
      assert(approxEqual(r1, [ 2.5 ]));

  auto `filter`(Range)(Range `range`)
  if (isInputRange!(Unqual!Range));
    Parameters:

    Range `range` | An input range of elements

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

  pred | Function to apply to each element of range

  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); // 2
      assert(equal(small, [ 1, 2 ]));
      assert(equal(retro(small), [ 2, 1 ]));
      // In combination with chain() to span multiple ranges
      int[] a = [ 3, -2, 400 ];
      int[] b = [ 100, -101, 102 ];
      auto r = filterBidirectional!("a > 0")(chain(a, b));
      writeln(r.back); // 102

  auto `filterBidirectional`(Range)(Range `r`)
  if (isBidirectionalRange!(Unqual!Range));
    Parameters:

    Range `r` | Bidirectional range of elements

    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 via pred(element, element).
  Parameters:

  pred | Binary predicate for determining equivalence of two elements.
  R | The range type
  Range `r` | The input range to iterate over.

  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); // ["a":2U, "b":2U, "c":3U, "d":1U, "e":1U]

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 elements a 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.
  Parameters:

  pred | Predicate for determining equivalence.
  Range `r` | An input range to be chunked.

  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.

  Notes Equivalent 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;

      // Grouping by particular attribute of each element:
      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;

      // Grouping by particular attribute of each element:
      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]); // expected1.front[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]); // expected2.front[0]
          assert(e[1].equal(expected2.front[1]));
          expected2.popFront();
      }

auto `joiner`(RoR, Separator)(RoR `r`, Separator `sep`)
if (isInputRange!RoR && isInputRange!(ElementType!RoR) && isForwardRange!Separator && is(ElementType!Separator : ElementType!(ElementType!RoR)));
auto `joiner`(RoR)(RoR `r`)
if (isInputRange!RoR && isInputRange!(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 flatten in other languages).
  Parameters:

  RoR `r` | An input range of input ranges to be joined.
  Separator `sep` | A forward range of element(s) to serve as separators in the joined range.

  Returns:
  A range of elements in the joined range. This will be a forward range if both outer and inner ranges of RoR are forward ranges; otherwise it will be only an input range. The range bidirectionality is propagated if no separator is specified.
  See Also:
  std.range.chain, which chains a sequence of ranges with compatible elements into a single range.
  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); // [[44, 2, 3], [42, 43]]
      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); // [[1, 2, 3], [4, 44]]
      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:

  fun | one or more functions

  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 `reduce` quickly and easily. The example below illustrates `reduce`'s remarkable power and flexibility.

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

      int[] arr = [ 1, 2, 3, 4, 5 ];
      // Sum all elements
      auto sum = reduce!((a,b) => a + b)(0, arr);
      writeln(sum); // 15

      // Sum again, using a string predicate with "a" and "b"
      sum = reduce!"a + b"(0, arr);
      writeln(sum); // 15

      // Compute the maximum of all elements
      auto largest = reduce!(max)(arr);
      writeln(largest); // 5

      // Max again, but with Uniform Function Call Syntax (UFCS)
      largest = arr.reduce!(max);
      writeln(largest); // 5

      // Compute the number of odd elements
      auto odds = reduce!((a,b) => a + (b & 1))(0, arr);
      writeln(odds); // 3

      // Compute the sum of squares
      auto ssquares = reduce!((a,b) => a + b * b)(0, arr);
      writeln(ssquares); // 55

      // Chain multiple ranges into seed
      int[] a = [ 3, 4 ];
      int[] b = [ 100 ];
      auto r = reduce!("a + b")(chain(a, b));
      writeln(r); // 107

      // Mixing convertible types is fair game, too
      double[] c = [ 2.5, 3.0 ];
      auto r1 = reduce!("a + b")(chain(a, b, c));
      assert(approxEqual(r1, 112.5));

      // To minimize nesting of parentheses, Uniform Function Call Syntax can be used
      auto r2 = chain(a, b, c).reduce!("a + b");
      assert(approxEqual(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 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.math : approxEqual, sqrt;
      import std.typecons : tuple, Tuple;

      double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
      // Compute minimum and maximum in one pass
      auto r = reduce!(min, max)(a);
      // The type of r is Tuple!(int, int)
      assert(approxEqual(r[0], 2));  // minimum
      assert(approxEqual(r[1], 11)); // maximum

      // Compute sum and sum of squares in one pass
      r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
      assert(approxEqual(r[0], 35));  // sum
      assert(approxEqual(r[1], 233)); // sum of squares
      // Compute average and standard deviation from the above
      auto avg = r[0] / a.length;
      writeln(avg); // 5
      auto stdev = sqrt(r[1] / a.length - avg * avg);
      writeln(cast(int)stdev); // 2

  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:

    R `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 std.typecons.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:

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

    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. The call `fold`!(fun)(range, seed) 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 `fold`!(fun)(range) works similarly, but it uses the first element of the range as the seed (the range must be non-empty).
  Parameters:

  fun | the predicate function(s) to apply to the elements

  See Also:
  Fold (higher-order function)
  sum is similar to `fold`!((a, b) => a + b) that offers precise summing of floating point numbers.
  This 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];

      // Sum all elements
      writeln(arr.fold!( (a, b) => a + b)); // 15

      // Sum all elements with explicit seed
      writeln(arr.fold!( (a, b) => a + b)(6)); // 21

      import std.algorithm.comparison : min, max;
      import std.typecons : tuple;

      // Compute minimum and maximum at the same time
      writeln(arr.fold!(min, max)); // tuple(1, 5)

      // Compute minimum and maximum at the same time with seeds
      writeln(arr.fold!(min, max)(0, 7)); // tuple(0, 7)

      // Can be used in a UFCS chain
      writeln(arr.map!(a => a + 1).fold!( (a, b) => a + b)); // 20

      // Return the last element of any range
      writeln(arr.fold!( (a, b) => b)); // 5

  auto `fold`(R, S...)(R `r`, S `seed`);
    Parameters:

    R `r` | the input range to fold
    S `seed` | the initial value of the accumulator

    Returns:
    the accumulated result
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 as partial_sum, accumulate, scan, Cumulative Sum.
  Parameters:

  fun | one or more functions to use as fold operation

  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.
  See Also:
  Prefix Sum

  Note In 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 : approxEqual;
      import std.range : chain;

      int[] arr = [1, 2, 3, 4, 5];
      // Partial sum of all elements
      auto sum = cumulativeFold!((a, b) => a + b)(arr, 0);
      writeln(sum.array); // [1, 3, 6, 10, 15]

      // Partial sum again, using a string predicate with "a" and "b"
      auto sum2 = cumulativeFold!"a + b"(arr, 0);
      writeln(sum2.array); // [1, 3, 6, 10, 15]

      // Compute the partial maximum of all elements
      auto largest = cumulativeFold!max(arr);
      writeln(largest.array); // [1, 2, 3, 4, 5]

      // Partial max again, but with Uniform Function Call Syntax (UFCS)
      largest = arr.cumulativeFold!max;
      writeln(largest.array); // [1, 2, 3, 4, 5]

      // Partial count of odd elements
      auto odds = arr.cumulativeFold!((a, b) => a + (b & 1))(0);
      writeln(odds.array); // [1, 1, 2, 2, 3]

      // Compute the partial sum of squares
      auto ssquares = arr.cumulativeFold!((a, b) => a + b * b)(0);
      writeln(ssquares.array); // [1, 5, 14, 30, 55]

      // Chain multiple ranges into seed
      int[] a = [3, 4];
      int[] b = [100];
      auto r = cumulativeFold!"a + b"(chain(a, b));
      writeln(r.array); // [3, 7, 107]

      // Mixing convertible types is fair game, too
      double[] c = [2.5, 3.0];
      auto r1 = cumulativeFold!"a + b"(chain(a, b, c));
      assert(approxEqual(r1, [3, 7, 107, 109.5, 112.5]));

      // To minimize nesting of parentheses, Uniform Function Call Syntax can be used
      auto r2 = chain(a, b, c).cumulativeFold!"a + b";
      assert(approxEqual(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 : approxEqual;
      import std.typecons : tuple;

      double[] a = [3.0, 4, 7, 11, 3, 2, 5];
      // Compute minimum and maximum in one pass
      auto r = a.cumulativeFold!(min, max);
      // The type of r is Tuple!(int, int)
      assert(approxEqual(r.map!"a[0]", [3, 3, 3, 3, 3, 2, 2]));     // minimum
      assert(approxEqual(r.map!"a[1]", [3, 4, 7, 11, 11, 11, 11])); // maximum

      // Compute sum and sum of squares in one pass
      auto r2 = a.cumulativeFold!("a + b", "a + b * b")(tuple(0.0, 0.0));
      assert(approxEqual(r2.map!"a[0]", [3, 7, 14, 25, 28, 30, 35]));      // sum
      assert(approxEqual(r2.map!"a[1]", [9, 25, 74, 195, 204, 208, 233])); // sum of squares

  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:

    R `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 std.typecons.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:

    R `range` | An input range
    S `seed` | the initial value of the accumulator

    Returns:
    a range containing the consecutive reduced values.
auto `splitter`(alias pred = "a == b", 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", 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`).

  Notes If 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:

  pred | The predicate for comparing each element with the separator, defaulting to "a == b".
  Range `r` | The input range to be split. Must support slicing and .length or be a narrow string type.
  Separator `s` | The element (or range) to be treated as the separator between range segments to be split.
  isTerminator | The predicate for deciding where to split the range when no separator is passed

  Constraints The 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 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 and std.array.split for a version that splits eagerly.
  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:
  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:
  Empty and separator-only ranges.

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

      assert("".splitter('|').empty);
      assert("|".splitter('|').equal([ "", "" ]));
      assert("||".splitter('|').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:
  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:
  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:
  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:
  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`(C)(C[] `s`)
if (isSomeChar!C);
  Lazily splits the string `s` into words, using whitespace as the delimiter.
  This function is string specific and, contrary to `splitter`!(std.uni.isWhite), runs of whitespace will be merged together (no empty tokens will be produced).
  Parameters:

  C[] `s` | The string to be split.

  Returns:
  An input range of slices of the original string 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:

  R `r` | an input range
  Value value | a single value which can be substituted in Ο(1)
  Substs `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.
  See Also:
  std.array.replace for an eager replace algorithm or std.string.translate, and std.string.tr for string algorithms with translation tables.
  Examples:

      import std.algorithm.comparison : equal;

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

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

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

      // substitution works for any ElementType
      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;

      // substitute subranges of a range
      assert("apple_tree".substitute!("apple", "banana",
                                      "tree", "shrub").equal("banana_shrub"));

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

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

  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 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 follows.
  - If std.range.primitives.ElementType!R is a floating-point type and R is a random-access range with length and slicing, then `sum` uses the pairwise summation algorithm.
  - If ElementType!R is a floating-point type and R is a finite input range (but not a random-access range with slicing), then `sum` uses the Kahan summation algorithm.
  - In all other cases, a simple element by element addition is done.
  For floating point inputs, calculations are made in real precision 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 of integral 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.
  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:

  E `seed` | the initial value of the summation
  R `r` | a finite input range

  Returns:
  The sum of all the elements in the range r.
  Examples:
  Ditto

      import std.range;

      //simple integral sumation
      writeln(sum([1, 2, 3, 4])); // 10

      //with integral promotion
      writeln(sum([false, true, true, false, true])); // 3
      writeln(sum(ubyte.max.repeat(100))); // 25500

      //The result may overflow
      writeln(uint.max.repeat(3).sum()); // 4294967293U
      //But a seed can be used to change the sumation primitive
      writeln(uint.max.repeat(3).sum(ulong.init)); // 12884901885UL

      //Floating point sumation
      writeln(sum([1.0, 2.0, 3.0, 4.0])); // 10

      //Floating point operations have double precision minimum
      static assert(is(typeof(sum([1F, 2F, 3F, 4F])) == double));
      writeln(sum([1F, 2, 3, 4])); // 10

      //Force pair-wise floating point sumation on large integers
      import std.math : approxEqual;
      assert(iota(ulong.max / 2, ulong.max / 2 + 4096).sum(0.0)
                 .approxEqual((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:

  T | The type of the return value.
  R `r` | An input range
  T `seed` | For user defined types. Should be equivalent to 0.

  Returns:
  The mean of `r` when `r` is non-empty.
  Examples:

      import std.math : approxEqual, isNaN;

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

      assert(arr1.mean.approxEqual(2));
      assert(arr2.mean.approxEqual(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 (functionality akin to the uniq system utility). Equivalence of elements is assessed by using the predicate pred, by default "a == b". The predicate is passed to std.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 a bidirectional range.
  Parameters:

  pred | Predicate for determining equivalence between range elements.
  Range `r` | An input range of elements to filter.

  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 ][]));

      // Filter duplicates in-place using copy
      arr.length -= arr.uniq().copy(arr).length;
      writeln(arr); // [1, 2, 3, 4, 5]

      // Note that uniqueness is only determined consecutively; duplicated
      // elements separated by an intervening different element will not be
      // eliminated:
      assert(equal(uniq([ 1, 1, 2, 1, 1, 3, 1]), [1, 2, 1, 3, 1]));

Permutations!Range `permutations`(Range)(Range `r`)
if (isRandomAccessRange!Range && hasLength!Range);
struct `Permutations`(Range) if (isRandomAccessRange!Range && hasLength!Range);
  Lazily computes all permutations of `r` using Heap's algorithm.
  Parameters:

  Range | the range type
  Range `r` | the random access range to find the permutations for.

  Returns:
  A forward range of elements of which are an std.range.indexed view into `r`.
  See Also:
  std.algorithm.sorting.nextPermutation.
  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-2018 by the D Language Foundation | Page generated by Ddoc on Sat Dec 8 15:30:08 2018