Menu

- Learn
- Documentation
  - Language Reference
  - Library Reference
  - Command-line Reference
  - Feature Overview
  - Articles
- Downloads
- Packages
- Community
  - Blog
  - Orgs using D
  - Twitter
  - Calendar
  - Forums
  - IRC
  - Community Discord
  - 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.range

This module defines the notion of a range. Ranges generalize the concept of arrays, lists, or anything that involves sequential access. This abstraction enables the same set of algorithms (see std.algorithm) to be used with a vast variety of different concrete types. For example, a linear search algorithm such as std.algorithm.searching.find works not just for arrays, but for linked-lists, input files, incoming network data, etc.

Guides There are many articles available that can bolster understanding ranges:

- Ali Çehreli's tutorial on ranges for the basics of working with and creating range-based code.
- Jonathan M. Davis Introduction to Ranges talk at DConf 2015 a vivid introduction from its core constructs to practical advice.
- The DLang Tour's chapter on ranges for an interactive introduction.
- H. S. Teoh's tutorial on component programming with ranges for a real-world showcase of the influence of range-based programming on complex algorithms.
- Andrei Alexandrescu's article On Iteration for conceptual aspect of ranges and the motivation

Submodules This module has two submodules:

The std.range.primitives submodule provides basic range functionality. It defines several templates for testing whether a given object is a range, what kind of range it is, and provides some common range operations.
The std.range.interfaces submodule provides object-based interfaces for working with ranges via runtime polymorphism.
The remainder of this module provides a rich set of range creation and composition templates that let you construct new ranges out of existing ranges:

chain | Concatenates several ranges into a single range.
choose | Chooses one of two ranges at runtime based on a boolean condition.
chooseAmong | Chooses one of several ranges at runtime based on an index.
chunks | Creates a range that returns fixed-size chunks of the original range.
cycle | Creates an infinite range that repeats the given forward range indefinitely. Good for implementing circular buffers.
drop | Creates the range that results from discarding the first n elements from the given range.
dropBack | Creates the range that results from discarding the last n elements from the given range.
dropExactly | Creates the range that results from discarding exactly n of the first elements from the given range.
dropBackExactly | Creates the range that results from discarding exactly n of the last elements from the given range.
dropOne | Creates the range that results from discarding the first element from the given range.
dropBackOne | Creates the range that results from discarding the last element from the given range.
enumerate | Iterates a range with an attached index variable.
evenChunks | Creates a range that returns a number of chunks of approximately equal length from the original range.
frontTransversal | Creates a range that iterates over the first elements of the given ranges.
generate | Creates a range by successive calls to a given function. This allows to create ranges as a single delegate.
indexed | Creates a range that offers a view of a given range as though its elements were reordered according to a given range of indices.
iota | Creates a range consisting of numbers between a starting point and ending point, spaced apart by a given interval.
lockstep | Iterates n ranges in lockstep, for use in a foreach loop. Similar to zip, except that lockstep is designed especially for foreach loops.
nullSink | An output range that discards the data it receives.
only | Creates a range that iterates over the given arguments.
padLeft | Pads a range to a specified length by adding a given element to the front of the range. Is lazy if the range has a known length.
padRight | Lazily pads a range to a specified length by adding a given element to the back of the range.
radial | Given a random-access range and a starting point, creates a range that alternately returns the next left and next right element to the starting point.
recurrence | Creates a forward range whose values are defined by a mathematical recurrence relation.
refRange | Pass a range by reference. Both the original range and the RefRange will always have the exact same elements. Any operation done on one will affect the other.
repeat | Creates a range that consists of a single element repeated n times, or an infinite range repeating that element indefinitely.
retro | Iterates a bidirectional range backwards.
roundRobin | Given n ranges, creates a new range that return the n first elements of each range, in turn, then the second element of each range, and so on, in a round-robin fashion.
sequence | Similar to recurrence, except that a random-access range is created.
slide | Creates a range that returns a fixed-size sliding window over the original range. Unlike chunks, it advances a configurable number of items at a time, not one chunk at a time.
stride | Iterates a range with stride n.
tail | Return a range advanced to within n elements of the end of the given range.
take | Creates a sub-range consisting of only up to the first n elements of the given range.
takeExactly | Like take, but assumes the given range actually has n elements, and therefore also defines the length property.
takeNone | Creates a random-access range consisting of zero elements of the given range.
takeOne | Creates a random-access range consisting of exactly the first element of the given range.
tee | Creates a range that wraps a given range, forwarding along its elements while also calling a provided function with each element.
transposed | Transposes a range of ranges.
transversal | Creates a range that iterates over the n'th elements of the given random-access ranges.
zip | Given n ranges, creates a range that successively returns a tuple of all the first elements, a tuple of all the second elements, etc.

Sortedness Ranges whose elements are sorted afford better efficiency with certain operations. For this, the assumeSorted function can be used to construct a SortedRange from a pre-sorted range. The std.algorithm.sorting.sort function also conveniently returns a SortedRange. SortedRange objects provide some additional range operations that take advantage of the fact that the range is sorted.

Source std/range/package.d

License:
Boost License 1.0.
Authors:
Andrei Alexandrescu, David Simcha, Jonathan M Davis, and Jack Stouffer. Credit for some of the ideas in building this module goes to Leonardo Maffi.

auto `retro`(Range)(Range `r`)
if (isBidirectionalRange!(Unqual!Range));
  Iterates a bidirectional range backwards. The original range can be accessed by using the source property. Applying retro twice to the same range yields the original range.
  Parameters:

  Range `r` | the bidirectional range to iterate backwards

  Returns:
  A bidirectional range with length if `r` also provides a length. Or, if `r` is a random access range, then the return value will be random access as well.
  See Also:
  std.algorithm.mutation.reverse for mutating the source range directly.
  Examples:

      import std.algorithm.comparison : equal;
      int[5] a = [ 1, 2, 3, 4, 5 ];
      int[5] b = [ 5, 4, 3, 2, 1 ];
      assert(equal(retro(a[]), b[]));
      assert(retro(a[]).source is a[]);
      assert(retro(retro(a[])) is a[]);

auto `stride`(Range)(Range `r`, size_t `n`)
if (isInputRange!(Unqual!Range));
  Iterates range `r` with stride `n`. If the range is a random-access range, moves by indexing into the range; otherwise, moves by successive calls to popFront. Applying stride twice to the same range results in a stride with a step that is the product of the two applications. It is an error for `n` to be 0.
  Parameters:

  Range `r` | the input range to stride over
  size_t `n` | the number of elements to skip over

  Returns:
  At minimum, an input range. The resulting range will adopt the range primitives of the underlying range as long as std.range.primitives.hasLength is true.
  Examples:

      import std.algorithm.comparison : equal;

      int[] a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ];
      assert(equal(stride(a, 3), [ 1, 4, 7, 10 ][]));
      writeln(stride(stride(a, 2), 3)); // stride(a, 6)

auto `chain`(Ranges...)(Ranges `rs`)
if (Ranges.length > 0 && allSatisfy!(isInputRange, staticMap!(Unqual, Ranges)) && !is(CommonType!(staticMap!(ElementType, staticMap!(Unqual, Ranges))) == void));
  Spans multiple ranges in sequence. The function `chain` takes any number of ranges and returns a Chain!(R1, R2,...) object. The ranges may be different, but they must have the same element type. The result is a range that offers the front, popFront, and empty primitives. If all input ranges offer random access and length, Chain offers them as well.
  If only one range is offered to Chain or `chain`, the Chain type exits the picture by aliasing itself directly to that range's type.
  Parameters:

  Ranges `rs` | the input ranges to chain together

  Returns:
  An input range at minimum. If all of the ranges in `rs` provide a range primitive, the returned range will also provide that range primitive.
  See Also:
  only to chain values to a range
  Examples:

      import std.algorithm.comparison : equal;

      int[] arr1 = [ 1, 2, 3, 4 ];
      int[] arr2 = [ 5, 6 ];
      int[] arr3 = [ 7 ];
      auto s = chain(arr1, arr2, arr3);
      writeln(s.length); // 7
      writeln(s[5]); // 6
      assert(equal(s, [1, 2, 3, 4, 5, 6, 7][]));

  Examples:
  Range primitives are carried over to the returned range if all of the ranges provide them

      import std.algorithm.comparison : equal;
      import std.algorithm.sorting : sort;

      int[] arr1 = [5, 2, 8];
      int[] arr2 = [3, 7, 9];
      int[] arr3 = [1, 4, 6];

      // in-place sorting across all of the arrays
      auto s = arr1.chain(arr2, arr3).sort;

      assert(s.equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));
      assert(arr1.equal([1, 2, 3]));
      assert(arr2.equal([4, 5, 6]));
      assert(arr3.equal([7, 8, 9]));

  Examples:
  Due to safe type promotion in D, chaining together different character ranges results in a uint range.
  Use byChar, byWchar, and byDchar on the ranges to get the type you need.

      import std.utf : byChar, byCodeUnit;

      auto s1 = "string one";
      auto s2 = "string two";
      // s1 and s2 front is dchar because of auto-decoding
      static assert(is(typeof(s1.front) == dchar) && is(typeof(s2.front) == dchar));

      auto r1 = s1.chain(s2);
      // chains of ranges of the same character type give that same type
      static assert(is(typeof(r1.front) == dchar));

      auto s3 = "string three".byCodeUnit;
      static assert(is(typeof(s3.front) == immutable char));
      auto r2 = s1.chain(s3);
      // chaining ranges of mixed character types gives `dchar`
      static assert(is(typeof(r2.front) == dchar));

      // use byChar on character ranges to correctly convert them to UTF-8
      auto r3 = s1.byChar.chain(s3);
      static assert(is(typeof(r3.front) == immutable char));

auto `choose`(R1, R2)(bool `condition`, return scope R1 `r1`, return scope R2 `r2`)
if (isInputRange!(Unqual!R1) && isInputRange!(Unqual!R2) && !is(CommonType!(ElementType!(Unqual!R1), ElementType!(Unqual!R2)) == void));
  Choose one of two ranges at runtime depending on a Boolean condition.
  The ranges may be different, but they must have compatible element types (i.e. CommonType must exist for the two element types). The result is a range that offers the weakest capabilities of the two (e.g. ForwardRange if R1 is a random-access range and R2 is a forward range).
  Parameters:

  bool `condition` | which range to choose: `r1` if true, `r2` otherwise
  R1 `r1` | the "true" range
  R2 `r2` | the "false" range

  Returns:
  A range type dependent on R1 and R2.
  Examples:

      import std.algorithm.comparison : equal;
      import std.algorithm.iteration : filter, map;

      auto data1 = only(1, 2, 3, 4).filter!(a => a != 3);
      auto data2 = only(5, 6, 7, 8).map!(a => a + 1);

      // choose() is primarily useful when you need to select one of two ranges
      // with different types at runtime.
      static assert(!is(typeof(data1) == typeof(data2)));

      auto chooseRange(bool pickFirst)
      {
          // The returned range is a common wrapper type that can be used for
          // returning or storing either range without running into a type error.
          return choose(pickFirst, data1, data2);

          // Simply returning the chosen range without using choose() does not
          // work, because map() and filter() return different types.
          //return pickFirst ? data1 : data2; // does not compile
      }

      auto result = chooseRange(true);
      assert(result.equal(only(1, 2, 4)));

      result = chooseRange(false);
      assert(result.equal(only(6, 7, 8, 9)));

auto `chooseAmong`(Ranges...)(size_t `index`, return scope Ranges `rs`)
if (Ranges.length >= 2 && allSatisfy!(isInputRange, staticMap!(Unqual, Ranges)) && !is(CommonType!(staticMap!(ElementType, Ranges)) == void));
  Choose one of multiple ranges at runtime.
  The ranges may be different, but they must have compatible element types. The result is a range that offers the weakest capabilities of all Ranges.
  Parameters:

  size_t `index` | which range to choose, must be less than the number of ranges
  Ranges `rs` | two or more ranges

  Returns:
  The indexed range. If rs consists of only one range, the return type is an alias of that range's type.
  Examples:

      auto test()
      {
          import std.algorithm.comparison : equal;

          int[4] sarr1 = [1, 2, 3, 4];
          int[2] sarr2 = [5, 6];
          int[1] sarr3 = [7];
          auto arr1 = sarr1[];
          auto arr2 = sarr2[];
          auto arr3 = sarr3[];

          {
              auto s = chooseAmong(0, arr1, arr2, arr3);
              auto t = s.save;
              writeln(s.length); // 4
              writeln(s[2]); // 3
              s.popFront();
              assert(equal(t, only(1, 2, 3, 4)));
          }
          {
              auto s = chooseAmong(1, arr1, arr2, arr3);
              writeln(s.length); // 2
              s.front = 8;
              assert(equal(s, only(8, 6)));
          }
          {
              auto s = chooseAmong(1, arr1, arr2, arr3);
              writeln(s.length); // 2
              s[1] = 9;
              assert(equal(s, only(8, 9)));
          }
          {
              auto s = chooseAmong(1, arr2, arr1, arr3)[1 .. 3];
              writeln(s.length); // 2
              assert(equal(s, only(2, 3)));
          }
          {
              auto s = chooseAmong(0, arr1, arr2, arr3);
              writeln(s.length); // 4
              writeln(s.back); // 4
              s.popBack();
              s.back = 5;
              assert(equal(s, only(1, 2, 5)));
              s.back = 3;
              assert(equal(s, only(1, 2, 3)));
          }
          {
              uint[5] foo = [1, 2, 3, 4, 5];
              uint[5] bar = [6, 7, 8, 9, 10];
              auto c = chooseAmong(1, foo[], bar[]);
              writeln(c[3]); // 9
              c[3] = 42;
              writeln(c[3]); // 42
              writeln(c.moveFront()); // 6
              writeln(c.moveBack()); // 10
              writeln(c.moveAt(4)); // 10
          }
          {
              import std.range : cycle;
              auto s = chooseAmong(0, cycle(arr2), cycle(arr3));
              assert(isInfinite!(typeof(s)));
              assert(!s.empty);
              writeln(s[100]); // 8
              writeln(s[101]); // 9
              assert(s[0 .. 3].equal(only(8, 9, 8)));
          }
          return 0;
      }
      // works at runtime
      auto a = test();
      // and at compile time
      static b = test();

auto `roundRobin`(Rs...)(Rs `rs`)
if (Rs.length > 1 && allSatisfy!(isInputRange, staticMap!(Unqual, Rs)));
  roundRobin(r1, r2, r3) yields r1.front, then r2.front, then r3.front, after which it pops off one element from each and continues again from r1. For example, if two ranges are involved, it alternately yields elements off the two ranges. `roundRobin` stops after it has consumed all ranges (skipping over the ones that finish early).
  Examples:

      import std.algorithm.comparison : equal;

      int[] a = [ 1, 2, 3 ];
      int[] b = [ 10, 20, 30, 40 ];
      auto r = roundRobin(a, b);
      assert(equal(r, [ 1, 10, 2, 20, 3, 30, 40 ]));

  Examples:
  roundRobin can be used to create "interleave" functionality which inserts an element between each element in a range.

      import std.algorithm.comparison : equal;

      auto interleave(R, E)(R range, E element)
      if ((isInputRange!R && hasLength!R) || isForwardRange!R)
      {
          static if (hasLength!R)
              immutable len = range.length;
          else
              immutable len = range.save.walkLength;

          return roundRobin(
              range,
              element.repeat(len - 1)
          );
      }

      assert(interleave([1, 2, 3], 0).equal([1, 0, 2, 0, 3]));

auto `radial`(Range, I)(Range `r`, I `startingIndex`)
if (isRandomAccessRange!(Unqual!Range) && hasLength!(Unqual!Range) && hasSlicing!(Unqual!Range) && isIntegral!I);
auto `radial`(R)(R `r`)
if (isRandomAccessRange!(Unqual!R) && hasLength!(Unqual!R) && hasSlicing!(Unqual!R));
  Iterates a random-access range starting from a given point and progressively extending left and right from that point. If no initial point is given, iteration starts from the middle of the range. Iteration spans the entire range.
  When `startingIndex` is 0 the range will be fully iterated in order and in reverse order when `r`.length is given.
  Parameters:

  Range `r` | a random access range with length and slicing
  I `startingIndex` | the index to begin iteration from

  Returns:
  A forward range with length
  Examples:

      import std.algorithm.comparison : equal;
      int[] a = [ 1, 2, 3, 4, 5 ];
      assert(equal(radial(a), [ 3, 4, 2, 5, 1 ]));
      a = [ 1, 2, 3, 4 ];
      assert(equal(radial(a), [ 2, 3, 1, 4 ]));

      // If the left end is reached first, the remaining elements on the right
      // are concatenated in order:
      a = [ 0, 1, 2, 3, 4, 5 ];
      assert(equal(radial(a, 1), [ 1, 2, 0, 3, 4, 5 ]));

      // If the right end is reached first, the remaining elements on the left
      // are concatenated in reverse order:
      assert(equal(radial(a, 4), [ 4, 5, 3, 2, 1, 0 ]));

Take!R `take`(R)(R `input`, size_t `n`)
if (isInputRange!(Unqual!R));
struct `Take`(Range) if (isInputRange!(Unqual!Range) && !(!isInfinite!(Unqual!Range) && hasSlicing!(Unqual!Range) || is(Range T == `Take`!T)));
template `Take`(R) if (isInputRange!(Unqual!R) && (!isInfinite!(Unqual!R) && hasSlicing!(Unqual!R) || is(R T == `Take`!T)))
  Lazily takes only up to `n` elements of a range. This is particularly useful when using with infinite ranges.
  Unlike takeExactly, `take` does not require that there are `n` or more elements in `input`. As a consequence, length information is not applied to the result unless `input` also has length information.
  Parameters:

  R `input` | an input range to iterate over up to `n` times
  size_t `n` | the number of elements to take

  Returns:
  At minimum, an input range. If the range offers random access and length, `take` offers them as well.
  Examples:

      import std.algorithm.comparison : equal;

      int[] arr1 = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
      auto s = take(arr1, 5);
      writeln(s.length); // 5
      writeln(s[4]); // 5
      assert(equal(s, [ 1, 2, 3, 4, 5 ][]));

  Examples:
  If the range runs out before `n` elements, `take` simply returns the entire range (unlike takeExactly, which will cause an assertion failure if the range ends prematurely):

      import std.algorithm.comparison : equal;

      int[] arr2 = [ 1, 2, 3 ];
      auto t = take(arr2, 5);
      writeln(t.length); // 3
      assert(equal(t, [ 1, 2, 3 ]));

auto `takeExactly`(R)(R `range`, size_t `n`)
if (isInputRange!R);
  Similar to take, but assumes that `range` has at least n elements. Consequently, the result of takeExactly(range, n) always defines the length property (and initializes it to `n`) even when `range` itself does not define length.
  The result of `takeExactly` is identical to that of take in cases where the original range defines length or is infinite.
  Unlike take, however, it is illegal to pass a range with less than `n` elements to `takeExactly`; this will cause an assertion failure.
  Examples:

      import std.algorithm.comparison : equal;

      auto a = [ 1, 2, 3, 4, 5 ];

      auto b = takeExactly(a, 3);
      assert(equal(b, [1, 2, 3]));
      static assert(is(typeof(b.length) == size_t));
      writeln(b.length); // 3
      writeln(b.front); // 1
      writeln(b.back); // 3

auto `takeOne`(R)(R `source`)
if (isInputRange!R);
  Returns a range with at most one element; for example, takeOne([42, 43, 44]) returns a range consisting of the integer 42. Calling popFront() off that range renders it empty.
  In effect `takeOne`(r) is somewhat equivalent to take(r, 1) but in certain interfaces it is important to know statically that the range may only have at most one element.
  The type returned by `takeOne` is a random-access range with length regardless of R's capabilities, as long as it is a forward range. (another feature that distinguishes `takeOne` from take). If (D R) is an input range but not a forward range, return type is an input range with all random-access capabilities except save.
  Examples:

      auto s = takeOne([42, 43, 44]);
      static assert(isRandomAccessRange!(typeof(s)));
      writeln(s.length); // 1
      assert(!s.empty);
      writeln(s.front); // 42
      s.front = 43;
      writeln(s.front); // 43
      writeln(s.back); // 43
      writeln(s[0]); // 43
      s.popFront();
      writeln(s.length); // 0
      assert(s.empty);

auto `takeNone`(R)()
if (isInputRange!R);
  Returns an empty range which is statically known to be empty and is guaranteed to have length and be random access regardless of R's capabilities.
  Examples:

      auto range = takeNone!(int[])();
      writeln(range.length); // 0
      assert(range.empty);

auto `takeNone`(R)(R `range`)
if (isInputRange!R);
  Creates an empty range from the given range in Ο(1). If it can, it will return the same range type. If not, it will return takeExactly(range, 0).
  Examples:

      import std.algorithm.iteration : filter;
      assert(takeNone([42, 27, 19]).empty);
      assert(takeNone("dlang.org").empty);
      assert(takeNone(filter!"true"([42, 27, 19])).empty);

auto `tail`(Range)(Range `range`, size_t `n`)
if (isInputRange!Range && !isInfinite!Range && (hasLength!Range || isForwardRange!Range));
  Return a range advanced to within _n elements of the end of `range`.
  Intended as the range equivalent of the Unix tail utility. When the length of `range` is less than or equal to _n, `range` is returned as-is.
  Completes in Ο(1) steps for ranges that support slicing and have length. Completes in Ο(range.length) time for all other ranges.
  Parameters:

  Range `range` | range to get tail of
  size_t `n` | maximum number of elements to include in tail

  Returns:
  Returns the tail of `range` augmented with length information
  Examples:

      // tail -c n
      writeln([1, 2, 3].tail(1)); // [3]
      writeln([1, 2, 3].tail(2)); // [2, 3]
      writeln([1, 2, 3].tail(3)); // [1, 2, 3]
      writeln([1, 2, 3].tail(4)); // [1, 2, 3]
      writeln([1, 2, 3].tail(0).length); // 0

      // tail --lines=n
      import std.algorithm.comparison : equal;
      import std.algorithm.iteration : joiner;
      import std.exception : assumeWontThrow;
      import std.string : lineSplitter;
      assert("one\ntwo\nthree"
          .lineSplitter
          .tail(2)
          .joiner("\n")
          .equal("two\nthree")
          .assumeWontThrow);

R `drop`(R)(R `range`, size_t `n`)
if (isInputRange!R);
R `dropBack`(R)(R `range`, size_t `n`)
if (isBidirectionalRange!R);
  Convenience function which calls std.range.primitives.popFrontN(`range`, `n`) and returns `range`. `drop` makes it easier to pop elements from a range and then pass it to another function within a single expression, whereas popFrontN would require multiple statements.
  `dropBack` provides the same functionality but instead calls std.range.primitives.popBackN(`range`, `n`)

  Note `drop` and `dropBack` will only pop up to `n` elements but will stop if the range is empty first. In other languages this is sometimes called skip.

  Parameters:

  R `range` | the input range to drop from
  size_t `n` | the number of elements to drop

  Returns:
  `range` with up to `n` elements dropped
  See Also:
  std.range.primitives.popFront, std.range.primitives.popBackN
  Examples:

      import std.algorithm.comparison : equal;

      writeln([0, 2, 1, 5, 0, 3].drop(3)); // [5, 0, 3]
      writeln("hello world".drop(6)); // "world"
      assert("hello world".drop(50).empty);
      assert("hello world".take(6).drop(3).equal("lo "));

  Examples:

      import std.algorithm.comparison : equal;

      writeln([0, 2, 1, 5, 0, 3].dropBack(3)); // [0, 2, 1]
      writeln("hello world".dropBack(6)); // "hello"
      assert("hello world".dropBack(50).empty);
      assert("hello world".drop(4).dropBack(4).equal("o w"));

R `dropExactly`(R)(R `range`, size_t `n`)
if (isInputRange!R);
R `dropBackExactly`(R)(R `range`, size_t `n`)
if (isBidirectionalRange!R);
  Similar to drop and dropBack but they call range.popFrontExactly(n) and `range`.popBackExactly(`n`) instead.

  Note Unlike drop, `dropExactly` will assume that the range holds at least `n` elements. This makes `dropExactly` faster than drop, but it also means that if `range` does not contain at least `n` elements, it will attempt to call popFront on an empty range, which is undefined behavior. So, only use popFrontExactly when it is guaranteed that `range` holds at least `n` elements.

  Parameters:

  R `range` | the input range to drop from
  size_t `n` | the number of elements to drop

  Returns:
  `range` with `n` elements dropped
  See Also:
  std.range.primitives.popFrontExcatly, std.range.primitives.popBackExcatly
  Examples:

      import std.algorithm.comparison : equal;
      import std.algorithm.iteration : filterBidirectional;

      auto a = [1, 2, 3];
      writeln(a.dropExactly(2)); // [3]
      writeln(a.dropBackExactly(2)); // [1]

      string s = "日本語";
      writeln(s.dropExactly(2)); // "語"
      writeln(s.dropBackExactly(2)); // "日"

      auto bd = filterBidirectional!"true"([1, 2, 3]);
      assert(bd.dropExactly(2).equal([3]));
      assert(bd.dropBackExactly(2).equal([1]));

R `dropOne`(R)(R `range`)
if (isInputRange!R);
R `dropBackOne`(R)(R `range`)
if (isBidirectionalRange!R);
  Convenience function which calls `range`.popFront() and returns `range`. `dropOne` makes it easier to pop an element from a range and then pass it to another function within a single expression, whereas popFront would require multiple statements.
  `dropBackOne` provides the same functionality but instead calls `range`.popBack().
  Examples:

      import std.algorithm.comparison : equal;
      import std.algorithm.iteration : filterBidirectional;
      import std.container.dlist : DList;

      auto dl = DList!int(9, 1, 2, 3, 9);
      assert(dl[].dropOne().dropBackOne().equal([1, 2, 3]));

      auto a = [1, 2, 3];
      writeln(a.dropOne()); // [2, 3]
      writeln(a.dropBackOne()); // [1, 2]

      string s = "日本語";
      import std.exception : assumeWontThrow;
      assert(assumeWontThrow(s.dropOne() == "本語"));
      assert(assumeWontThrow(s.dropBackOne() == "日本"));

      auto bd = filterBidirectional!"true"([1, 2, 3]);
      assert(bd.dropOne().equal([2, 3]));
      assert(bd.dropBackOne().equal([1, 2]));

struct `Repeat`(T);
Repeat!T `repeat`(T)(T `value`);
Take!(Repeat!T) `repeat`(T)(T `value`, size_t `n`);
  Create a range which repeats one value.
  Parameters:

  T `value` | the value to repeat
  size_t `n` | the number of times to repeat `value`

  Returns:
  If `n` is not defined, an infinite random access range with slicing.
  If `n` is defined, a random access range with slicing.
  Examples:

      import std.algorithm.comparison : equal;

      assert(5.repeat().take(4).equal([5, 5, 5, 5]));

  Examples:

      import std.algorithm.comparison : equal;

      assert(5.repeat(4).equal([5, 5, 5, 5]));

  inout @property inout(T) `front`();
  inout @property inout(T) `back`();
  enum bool `empty`;
  void `popFront`();
  void `popBack`();
  inout @property auto `save`();
  inout inout(T) `opIndex`(size_t);
  auto `opSlice`(size_t `i`, size_t `j`);
  enum auto `opDollar`;
  inout auto `opSlice`(size_t, DollarToken);
    Range primitives
auto `generate`(Fun)(Fun `fun`)
if (isCallable!`fun`);
auto `generate`(alias fun)()
if (isCallable!fun);
  Given callable (std.traits.isCallable) `fun`, create as a range whose front is defined by successive calls to `fun`(). This is especially useful to call function with global side effects (random functions), or to create ranges expressed as a single delegate, rather than an entire front/popFront/empty structure. `fun` maybe be passed either a template alias parameter (existing function, delegate, struct type defining static opCall) or a run-time value argument (delegate, function object). The result range models an InputRange (std.range.primitives.isInputRange). The resulting range will call `fun`() on construction, and every call to popFront, and the cached value will be returned when front is called.
  Returns:
  an inputRange where each element represents another call to fun.
  Examples:

      import std.algorithm.comparison : equal;
      import std.algorithm.iteration : map;

      int i = 1;
      auto powersOfTwo = generate!(() => i *= 2)().take(10);
      assert(equal(powersOfTwo, iota(1, 11).map!"2^^a"()));

  Examples:

      import std.algorithm.comparison : equal;

      //Returns a run-time delegate
      auto infiniteIota(T)(T low, T high)
      {
          T i = high;
          return (){if (i == high) i = low; return i++;};
      }
      //adapted as a range.
      assert(equal(generate(infiniteIota(1, 4)).take(10), [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]));

  Examples:

      import std.format : format;
      import std.random : uniform;

      auto r = generate!(() => uniform(0, 6)).take(10);
      format("%(%s %)", r);

struct `Cycle`(R) if (isForwardRange!R && !isInfinite!R);
template `Cycle`(R) if (isInfinite!R)
struct `Cycle`(R) if (isStaticArray!R);
auto `cycle`(R)(R `input`)
if (isInputRange!R);
Cycle!R `cycle`(R)(R `input`, size_t `index` = 0)
if (isRandomAccessRange!R && !isInfinite!R);
@system Cycle!R `cycle`(R)(ref R `input`, size_t `index` = 0)
if (isStaticArray!R);
  Repeats the given forward range ad infinitum. If the original range is infinite (fact that would make `Cycle` the identity application), `Cycle` detects that and aliases itself to the range type itself. That works for non-forward ranges too. If the original range has random access, `Cycle` offers random access and also offers a constructor taking an initial position `index`. `Cycle` works with static arrays in addition to ranges, mostly for performance reasons.

  Note The input range must not be empty.

  Tip This is a great way to implement simple circular buffers.

  Examples:

      import std.algorithm.comparison : equal;
      import std.range : cycle, take;

      // Here we create an infinitive cyclic sequence from [1, 2]
      // (i.e. get here [1, 2, 1, 2, 1, 2 and so on]) then
      // take 5 elements of this sequence (so we have [1, 2, 1, 2, 1])
      // and compare them with the expected values for equality.
      assert(cycle([1, 2]).take(5).equal([ 1, 2, 1, 2, 1 ]));

  this(R `input`, size_t `index` = 0);
  @property ref auto `front`();
  const @property ref auto `front`();
  @property void `front`(ElementType!R `val`);
  enum bool `empty`;
  void `popFront`();
  ref auto `opIndex`(size_t `n`);
  const ref auto `opIndex`(size_t `n`);
  void `opIndexAssign`(ElementType!R `val`, size_t `n`);
  @property Cycle `save`();
  enum auto `opDollar`;
  auto `opSlice`(size_t `i`, size_t `j`);
  auto `opSlice`(size_t `i`, DollarToken);
    Range primitives
struct `Zip`(Ranges...) if (Ranges.length && allSatisfy!(isInputRange, Ranges));
auto `zip`(Ranges...)(Ranges `ranges`)
if (Ranges.length && allSatisfy!(isInputRange, Ranges));
auto `zip`(Ranges...)(StoppingPolicy `sp`, Ranges `ranges`)
if (Ranges.length && allSatisfy!(isInputRange, Ranges));
  Iterate several ranges in lockstep. The element type is a proxy tuple that allows accessing the current element in the nth range by using e[n].
  `zip` is similar to lockstep, but lockstep doesn't bundle its elements and uses the opApply protocol. lockstep allows reference access to the elements in foreach iterations.
  Parameters:

  StoppingPolicy `sp` | controls what `zip` will do if the ranges are different lengths
  Ranges `ranges` | the ranges to zip together

  Returns:
  At minimum, an input range. `Zip` offers the lowest range facilities of all components, e.g. it offers random access iff all ranges offer random access, and also offers mutation and swapping if all ranges offer it. Due to this, `Zip` is extremely powerful because it allows manipulating several ranges in lockstep.
  Throws:
  An Exception if all of the ranges are not the same length and `sp` is set to StoppingPolicy.requireSameLength.

  Limitations The @nogc and nothrow attributes cannot be inferred for the `Zip` struct because StoppingPolicy can vary at runtime. This limitation is not shared by the anonymous range returned by the `zip` function when not given an explicit StoppingPolicy as an argument.

  Examples:

      import std.algorithm.comparison : equal;
      import std.algorithm.iteration : map;

      // pairwise sum
      auto arr = only(0, 1, 2);
      auto part1 = zip(arr, arr.dropOne).map!"a[0] + a[1]";
      assert(part1.equal(only(1, 3)));

  Examples:

      import std.conv : to;

      int[] a = [ 1, 2, 3 ];
      string[] b = [ "a", "b", "c" ];
      string[] result;

      foreach (tup; zip(a, b))
      {
          result ~= tup[0].to!string ~ tup[1];
      }

      writeln(result); // ["1a", "2b", "3c"]

      size_t idx = 0;
      // unpacking tuple elements with foreach
      foreach (e1, e2; zip(a, b))
      {
          writeln(e1); // a[idx]
          writeln(e2); // b[idx]
          ++idx;
      }

  Examples:
  `zip` is powerful - the following code sorts two arrays in parallel:

      import std.algorithm.sorting : sort;

      int[] a = [ 1, 2, 3 ];
      string[] b = [ "a", "c", "b" ];
      zip(a, b).sort!((t1, t2) => t1[0] > t2[0]);

      writeln(a); // [3, 2, 1]
      // b is sorted according to a's sorting
      writeln(b); // ["b", "c", "a"]

  this(R `rs`, StoppingPolicy `s` = StoppingPolicy.shortest);
    Builds an object. Usually this is invoked indirectly by using the zip function.
  enum bool `empty`;
    Returns true if the range is at end. The test depends on the stopping policy.
  @property Zip `save`();
  @property ElementType `front`();
    Returns the current iterated element.
  @property void `front`(ElementType `v`);
    Sets the front of all iterated ranges.
  ElementType `moveFront`();
    Moves out the front.
  @property ElementType `back`();
    Returns the rightmost element.
  ElementType `moveBack`();
    Moves out the back.
    Returns the rightmost element.
  @property void `back`(ElementType `v`);
    Returns the current iterated element.
    Returns the rightmost element.
  void `popFront`();
    Advances to the next element in all controlled ranges.
  void `popBack`();
    Calls `popBack` for all controlled ranges.
  @property auto `length`();
    Returns the length of this range. Defined only if all ranges define `length`.
  alias `opDollar` = length;
    Returns the length of this range. Defined only if all ranges define length.
  auto `opSlice`(size_t `from`, size_t `to`);
    Returns a slice of the range. Defined only if all range define slicing.
  ElementType `opIndex`(size_t `n`);
    Returns the `n`th element in the composite range. Defined if all ranges offer random access.
  void `opIndexAssign`(ElementType `v`, size_t `n`);
    Assigns to the `n`th element in the composite range. Defined if all ranges offer random access.
    Returns the `n`th element in the composite range. Defined if all ranges offer random access.
  ElementType `moveAt`(size_t `n`);
    Destructively reads the `n`th element in the composite range. Defined if all ranges offer random access.
    Returns the `n`th element in the composite range. Defined if all ranges offer random access.
enum `StoppingPolicy`: int;
  Dictates how iteration in a zip and lockstep should stop. By default stop at the end of the shortest of all ranges.
  Examples:

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

      auto a = [1, 2, 3];
      auto b = [4, 5, 6, 7];

      auto shortest = zip(StoppingPolicy.shortest, a, b);
      assert(shortest.equal([
          tuple(1, 4),
          tuple(2, 5),
          tuple(3, 6)
      ]));

      auto longest = zip(StoppingPolicy.longest, a, b);
      assert(longest.equal([
          tuple(1, 4),
          tuple(2, 5),
          tuple(3, 6),
          tuple(0, 7)
      ]));

      auto same = zip(StoppingPolicy.requireSameLength, a, b);
      same.popFrontN(3);
      assertThrown!Exception(same.popFront);

  `shortest`
    Stop when the shortest range is exhausted
  `longest`
    Stop when the longest range is exhausted
  `requireSameLength`
    Require that all ranges are equal
struct `Lockstep`(Ranges...) if (Ranges.length > 1 && allSatisfy!(isInputRange, Ranges));
Lockstep!Ranges `lockstep`(Ranges...)(Ranges `ranges`)
if (allSatisfy!(isInputRange, Ranges));
Lockstep!Ranges `lockstep`(Ranges...)(Ranges `ranges`, StoppingPolicy `s`)
if (allSatisfy!(isInputRange, Ranges));
  Iterate multiple ranges in lockstep using a foreach loop. In contrast to zip it allows reference access to its elements. If only a single range is passed in, the `Lockstep` aliases itself away. If the ranges are of different lengths and `s` == StoppingPolicy.shortest stop after the shortest range is empty. If the ranges are of different lengths and `s` == StoppingPolicy.requireSameLength, throw an exception. `s` may not be StoppingPolicy.longest, and passing this will throw an exception.
  Iterating over `Lockstep` in reverse and with an index is only possible when `s` == StoppingPolicy.requireSameLength, in order to preserve indexes. If an attempt is made at iterating in reverse when `s` == StoppingPolicy.shortest, an exception will be thrown.
  By default StoppingPolicy is set to StoppingPolicy.shortest.

  Limitations The pure, @safe, @nogc, or nothrow attributes cannot be inferred for `lockstep` iteration. zip can infer the first two due to a different implementation.

  See Also:
  zip
  `lockstep` is similar to zip, but zip bundles its elements and returns a range. `lockstep` also supports reference access. Use zip if you want to pass the result to a range function.
  Examples:

      auto arr1 = [1,2,3,4,5,100];
      auto arr2 = [6,7,8,9,10];

      foreach (ref a, b; lockstep(arr1, arr2))
      {
          a += b;
      }

      writeln(arr1); // [7, 9, 11, 13, 15, 100]

      /// Lockstep also supports iterating with an index variable:
      foreach (index, a, b; lockstep(arr1, arr2))
      {
          writeln(arr1[index]); // a
          writeln(arr2[index]); // b
      }

  this(R `ranges`, StoppingPolicy `sp` = StoppingPolicy.shortest);
struct `Recurrence`(alias fun, StateType, size_t stateSize);
Recurrence!(fun, CommonType!State, State.length) `recurrence`(alias fun, State...)(State `initial`);
  Creates a mathematical sequence given the initial values and a recurrence function that computes the next value from the existing values. The sequence comes in the form of an infinite forward range. The type `Recurrence` itself is seldom used directly; most often, recurrences are obtained by calling the function recurrence.
  When calling `recurrence`, the function that computes the next value is specified as a template argument, and the initial values in the recurrence are passed as regular arguments. For example, in a Fibonacci sequence, there are two initial values (and therefore a state size of 2) because computing the next Fibonacci value needs the past two values.
  The signature of this function should be:

      auto fun(R)(R state, size_t n)

  where n will be the index of the current value, and state will be an opaque state vector that can be indexed with array-indexing notation state[i], where valid values of i range from (n - 1) to (n - State.length).
  If the function is passed in string form, the state has name "a" and the zero-based index in the recurrence has name "n". The given string must return the desired value for a[n] given a[n - 1], a[n - 2], a[n - 3],..., a[n - stateSize]. The state size is dictated by the number of arguments passed to the call to `recurrence`. The `Recurrence` struct itself takes care of managing the recurrence's state and shifting it appropriately.
  Examples:

      import std.algorithm.comparison : equal;

      // The Fibonacci numbers, using function in string form:
      // a[0] = 1, a[1] = 1, and compute a[n+1] = a[n-1] + a[n]
      auto fib = recurrence!("a[n-1] + a[n-2]")(1, 1);
      assert(fib.take(10).equal([1, 1, 2, 3, 5, 8, 13, 21, 34, 55]));

      // The factorials, using function in lambda form:
      auto fac = recurrence!((a,n) => a[n-1] * n)(1);
      assert(take(fac, 10).equal([
          1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880
      ]));

      // The triangular numbers, using function in explicit form:
      static size_t genTriangular(R)(R state, size_t n)
      {
          return state[n-1] + n;
      }
      auto tri = recurrence!genTriangular(0);
      assert(take(tri, 10).equal([0, 1, 3, 6, 10, 15, 21, 28, 36, 45]));

struct `Sequence`(alias fun, State);
auto `sequence`(alias fun, State...)(State `args`);
  `Sequence` is similar to Recurrence except that iteration is presented in the so-called closed form. This means that the nth element in the series is computable directly from the initial values and n itself. This implies that the interface offered by `Sequence` is a random-access range, as opposed to the regular Recurrence, which only offers forward iteration.
  The state of the sequence is stored as a Tuple so it can be heterogeneous.
  Examples:
  Odd numbers, using function in string form:

      auto odds = sequence!("a[0] + n * a[1]")(1, 2);
      writeln(odds.front); // 1
      odds.popFront();
      writeln(odds.front); // 3
      odds.popFront();
      writeln(odds.front); // 5

  Examples:
  Triangular numbers, using function in lambda form:

      auto tri = sequence!((a,n) => n*(n+1)/2)();

      // Note random access
      writeln(tri[0]); // 0
      writeln(tri[3]); // 6
      writeln(tri[1]); // 1
      writeln(tri[4]); // 10
      writeln(tri[2]); // 3

  Examples:
  Fibonacci numbers, using function in explicit form:

      import std.math.exponential : pow;
      import std.math.rounding : round;
      import std.math.algebraic : sqrt;
      static ulong computeFib(S)(S state, size_t n)
      {
          // Binet's formula
          return cast(ulong)(round((pow(state[0], n+1) - pow(state[1], n+1)) /
                                   state[2]));
      }
      auto fib = sequence!computeFib(
          (1.0 + sqrt(5.0)) / 2.0,    // Golden Ratio
          (1.0 - sqrt(5.0)) / 2.0,    // Conjugate of Golden Ratio
          sqrt(5.0));

      // Note random access with [] operator
      writeln(fib[1]); // 1
      writeln(fib[4]); // 5
      writeln(fib[3]); // 3
      writeln(fib[2]); // 2
      writeln(fib[9]); // 55

auto `iota`(B, E, S)(B `begin`, E `end`, S `step`)
if ((isIntegral!(CommonType!(B, E)) || isPointer!(CommonType!(B, E))) && isIntegral!S);
auto `iota`(B, E)(B `begin`, E `end`)
if (isFloatingPoint!(CommonType!(B, E)));
auto `iota`(B, E)(B `begin`, E `end`)
if (isIntegral!(CommonType!(B, E)) || isPointer!(CommonType!(B, E)));
auto `iota`(E)(E `end`)
if (is(typeof(`iota`(E(0), `end`))));
auto `iota`(B, E, S)(B `begin`, E `end`, S `step`)
if (isFloatingPoint!(CommonType!(B, E, S)));
auto `iota`(B, E)(B `begin`, E `end`)
if (!isIntegral!(CommonType!(B, E)) && !isFloatingPoint!(CommonType!(B, E)) && !isPointer!(CommonType!(B, E)) && is(typeof((ref B b) { ++b; } )) && (is(typeof(B.init < E.init)) || is(typeof(B.init == E.init))));
  Creates a range of values that span the given starting and stopping values.
  Parameters:

  B `begin` | The starting value.
  E `end` | The value that serves as the stopping criterion. This value is not included in the range.
  S `step` | The value to add to the current value at each iteration.

  Returns:
  A range that goes through the numbers `begin`, begin + step, begin + 2 * step, ..., up to and excluding `end`.
  The two-argument overloads have step = 1. If begin < end && step < 0 or begin > end && step > 0 or begin == end, then an empty range is returned. If step == 0 then begin == end is an error.
  For built-in types, the range returned is a random access range. For user-defined types that support ++, the range is an input range.
  An integral iota also supports in operator from the right. It takes the stepping into account, the integral won't be considered contained if it falls between two consecutive values of the range. contains does the same as in, but from lefthand side.

  Example

      void main()
      {
          import std.stdio;

          // The following groups all produce the same output of:
          // 0 1 2 3 4

          foreach (i; 0 .. 5)
              writef("%s ", i);
          writeln();

          import std.range : iota;
          foreach (i; iota(0, 5))
              writef("%s ", i);
          writeln();

          writefln("%(%s %|%)", iota(0, 5));

          import std.algorithm.iteration : map;
          import std.algorithm.mutation : copy;
          import std.format;
          iota(0, 5).map!(i => format("%s ", i)).copy(stdout.lockingTextWriter());
          writeln();
      }

  Examples:

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

      auto r = iota(0, 10, 1);
      assert(equal(r, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
      assert(equal(r, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]));
      assert(3 in r);
      assert(r.contains(3)); //Same as above
      assert(!(10 in r));
      assert(!(-8 in r));
      r = iota(0, 11, 3);
      assert(equal(r, [0, 3, 6, 9]));
      writeln(r[2]); // 6
      assert(!(2 in r));
      auto rf = iota(0.0, 0.5, 0.1);
      assert(isClose(rf, [0.0, 0.1, 0.2, 0.3, 0.4]));

enum `TransverseOptions`: int;
  Options for the FrontTransversal and Transversal ranges (below).
  Examples:

      import std.algorithm.comparison : equal;
      import std.exception : assertThrown;

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

      auto r1 = arr.frontTransversal!(TransverseOptions.assumeJagged);
      assert(r1.equal([1, 3]));

      // throws on construction
      assertThrown!Exception(arr.frontTransversal!(TransverseOptions.enforceNotJagged));

      auto r2 = arr.frontTransversal!(TransverseOptions.assumeNotJagged);
      assert(r2.equal([1, 3]));

      // either assuming or checking for equal lengths makes
      // the result a random access range
      writeln(r2[0]); // 1
      static assert(!__traits(compiles, r1[0]));

  `assumeJagged`
    When transversed, the elements of a range of ranges are assumed to have different lengths (e.g. a jagged array).
  `enforceNotJagged`
    The transversal enforces that the elements of a range of ranges have all the same length (e.g. an array of arrays, all having the same length). Checking is done once upon construction of the transversal range.
  `assumeNotJagged`
    The transversal assumes, without verifying, that the elements of a range of ranges have all the same length. This option is useful if checking was already done from the outside of the range.
struct `FrontTransversal`(Ror, TransverseOptions opt = TransverseOptions.assumeJagged);
FrontTransversal!(RangeOfRanges, opt) `frontTransversal`(TransverseOptions opt = TransverseOptions.assumeJagged, RangeOfRanges)(RangeOfRanges `rr`);
  Given a range of ranges, iterate transversally through the first elements of each of the enclosed ranges.
  Examples:

      import std.algorithm.comparison : equal;
      int[][] x = new int[][2];
      x[0] = [1, 2];
      x[1] = [3, 4];
      auto ror = frontTransversal(x);
      assert(equal(ror, [ 1, 3 ][]));

  this(RangeOfRanges `input`);
    Construction from an input.
  enum bool `empty`;
  @property ref auto `front`();
  ElementType `moveFront`();
  void `popFront`();
    Forward range primitives.
  @property FrontTransversal `save`();
    Duplicates this frontTransversal. Note that only the encapsulating range of range will be duplicated. Underlying ranges will not be duplicated.
  @property ref auto `back`();
  void `popBack`();
  ElementType `moveBack`();
    Bidirectional primitives. They are offered if isBidirectionalRange!RangeOfRanges.
  ref auto `opIndex`(size_t `n`);
  ElementType `moveAt`(size_t `n`);
  void `opIndexAssign`(ElementType `val`, size_t `n`);
    Random-access primitive. It is offered if isRandomAccessRange!RangeOfRanges && (opt == TransverseOptions.assumeNotJagged || opt == TransverseOptions.enforceNotJagged).
  typeof(this) `opSlice`(size_t `lower`, size_t `upper`);
    Slicing if offered if RangeOfRanges supports slicing and all the conditions for supporting indexing are met.
struct `Transversal`(Ror, TransverseOptions opt = TransverseOptions.assumeJagged);
Transversal!(RangeOfRanges, opt) `transversal`(TransverseOptions opt = TransverseOptions.assumeJagged, RangeOfRanges)(RangeOfRanges `rr`, size_t `n`);
  Given a range of ranges, iterate transversally through the `n`th element of each of the enclosed ranges. This function is similar to unzip in other languages.
  Parameters:

  opt | Controls the assumptions the function makes about the lengths of the ranges
  RangeOfRanges `rr` | An input range of random access ranges

  Returns:
  At minimum, an input range. Range primitives such as bidirectionality and random access are given if the element type of `rr` provides them.
  Examples:

      import std.algorithm.comparison : equal;
      int[][] x = new int[][2];
      x[0] = [1, 2];
      x[1] = [3, 4];
      auto ror = transversal(x, 1);
      assert(equal(ror, [ 2, 4 ]));

  Examples:
  The following code does a full unzip

      import std.algorithm.comparison : equal;
      import std.algorithm.iteration : map;
      int[][] y = [[1, 2, 3], [4, 5, 6]];
      auto z = y.front.walkLength.iota.map!(i => transversal(y, i));
      assert(equal!equal(z, [[1, 4], [2, 5], [3, 6]]));

  this(RangeOfRanges `input`, size_t `n`);
    Construction from an input and an index.
  enum bool `empty`;
  @property ref auto `front`();
  E `moveFront`();
  @property void `front`(E `val`);
  void `popFront`();
  @property typeof(this) `save`();
    Forward range primitives.
  @property ref auto `back`();
  void `popBack`();
  E `moveBack`();
  @property void `back`(E `val`);
    Bidirectional primitives. They are offered if isBidirectionalRange!RangeOfRanges.
  ref auto `opIndex`(size_t `n`);
  E `moveAt`(size_t `n`);
  void `opIndexAssign`(E `val`, size_t `n`);
    Random-access primitive. It is offered if isRandomAccessRange!RangeOfRanges && (opt == TransverseOptions.assumeNotJagged || opt == TransverseOptions.enforceNotJagged).
  typeof(this) `opSlice`(size_t `lower`, size_t `upper`);
    Slicing if offered if RangeOfRanges supports slicing and all the conditions for supporting indexing are met.
Transposed!(RangeOfRanges, opt) `transposed`(TransverseOptions opt = TransverseOptions.assumeJagged, RangeOfRanges)(RangeOfRanges `rr`)
if (isForwardRange!RangeOfRanges && isInputRange!(ElementType!RangeOfRanges) && hasAssignableElements!RangeOfRanges);
  Given a range of ranges, returns a range of ranges where the i'th subrange contains the i'th elements of the original subranges.
  Parameters:

  opt | Controls the assumptions the function makes about the lengths of the ranges (i.e. jagged or not)
  RangeOfRanges `rr` | Range of ranges

  Examples:

      import std.algorithm.comparison : equal;
      int[][] ror = [
          [1, 2, 3],
          [4, 5, 6]
      ];
      auto xp = transposed(ror);
      assert(equal!"a.equal(b)"(xp, [
          [1, 4],
          [2, 5],
          [3, 6]
      ]));

  Examples:

      int[][] x = new int[][2];
      x[0] = [1, 2];
      x[1] = [3, 4];
      auto tr = transposed(x);
      int[][] witness = [ [ 1, 3 ], [ 2, 4 ] ];
      uint i;

      foreach (e; tr)
      {
          writeln(array(e)); // witness[i++]
      }

struct `Indexed`(Source, Indices) if (isRandomAccessRange!Source && isInputRange!Indices && is(typeof(Source.init[ElementType!Indices.init])));
Indexed!(Source, Indices) `indexed`(Source, Indices)(Source `source`, Indices `indices`);
  This struct takes two ranges, `source` and `indices`, and creates a view of `source` as if its elements were reordered according to `indices`. `indices` may include only a subset of the elements of `source` and may also repeat elements.
  Source must be a random access range. The returned range will be bidirectional or random-access if Indices is bidirectional or random-access, respectively.
  Examples:

      import std.algorithm.comparison : equal;
      auto source = [1, 2, 3, 4, 5];
      auto indices = [4, 3, 1, 2, 0, 4];
      auto ind = indexed(source, indices);
      assert(equal(ind, [5, 4, 2, 3, 1, 5]));
      assert(equal(retro(ind), [5, 1, 3, 2, 4, 5]));

  @property ref auto `front`();
  void `popFront`();
  @property typeof(this) `save`();
  @property ref auto `front`(ElementType!Source `newVal`);
  auto `moveFront`();
  @property ref auto `back`();
  void `popBack`();
  @property ref auto `back`(ElementType!Source `newVal`);
  auto `moveBack`();
  ref auto `opIndex`(size_t `index`);
  typeof(this) `opSlice`(size_t `a`, size_t `b`);
  auto `opIndexAssign`(ElementType!Source `newVal`, size_t `index`);
  auto `moveAt`(size_t `index`);
    Range primitives
  @property Source `source`();
    Returns the source range.
  @property Indices `indices`();
    Returns the indices range.
  size_t `physicalIndex`(size_t `logicalIndex`);
    Returns the physical index into the source range corresponding to a given logical index. This is useful, for example, when indexing an Indexed without adding another layer of indirection.
    Examples:

        auto ind = indexed([1, 2, 3, 4, 5], [1, 3, 4]);
        writeln(ind.physicalIndex(0)); // 1

struct `Chunks`(Source) if (isInputRange!Source);
Chunks!Source `chunks`(Source)(Source `source`, size_t `chunkSize`)
if (isInputRange!Source);
  This range iterates over fixed-sized chunks of size `chunkSize` of a `source` range. Source must be an input range. `chunkSize` must be greater than zero.
  If !isInfinite!Source and `source`.walkLength is not evenly divisible by `chunkSize`, the back element of this range will contain fewer than `chunkSize` elements.
  If Source is a forward range, the resulting range will be forward ranges as well. Otherwise, the resulting chunks will be input ranges consuming the same input: iterating over front will shrink the chunk such that subsequent invocations of front will no longer return the full chunk, and calling popFront on the outer range will invalidate any lingering references to previous values of front.
  Parameters:

  Source `source` | Range from which the chunks will be selected
  size_t `chunkSize` | Chunk size

  See Also:
  slide
  Returns:
  Range of chunks.
  Examples:

      import std.algorithm.comparison : equal;
      auto source = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
      auto chunks = chunks(source, 4);
      writeln(chunks[0]); // [1, 2, 3, 4]
      writeln(chunks[1]); // [5, 6, 7, 8]
      writeln(chunks[2]); // [9, 10]
      writeln(chunks.back); // chunks[2]
      writeln(chunks.front); // chunks[0]
      writeln(chunks.length); // 3
      assert(equal(retro(array(chunks)), array(retro(chunks))));

  Examples:
  Non-forward input ranges are supported, but with limited semantics.

      import std.algorithm.comparison : equal;

      int i;

      // The generator doesn't save state, so it cannot be a forward range.
      auto inputRange = generate!(() => ++i).take(10);

      // We can still process it in chunks, but it will be single-pass only.
      auto chunked = inputRange.chunks(2);

      assert(chunked.front.equal([1, 2]));
      assert(chunked.front.empty); // Iterating the chunk has consumed it
      chunked.popFront;
      assert(chunked.front.equal([3, 4]));

  this(Source `source`, size_t `chunkSize`);
    Standard constructor
  @property auto `front`();
  void `popFront`();
  @property bool `empty`();
    Input range primitives. Always present.
  @property typeof(this) `save`();
    Forward range primitives. Only present if Source is a forward range.
  @property size_t `length`();
    Length. Only if hasLength!Source is true
  auto `opIndex`(size_t `index`);
  typeof(this) `opSlice`(size_t `lower`, size_t `upper`);
    Indexing and slicing operations. Provided only if hasSlicing!Source is true.
  @property auto `back`();
  void `popBack`();
    Bidirectional range primitives. Provided only if both hasSlicing!Source and hasLength!Source are true.
struct `EvenChunks`(Source) if (isForwardRange!Source && hasLength!Source);
EvenChunks!Source `evenChunks`(Source)(Source `source`, size_t `chunkCount`)
if (isForwardRange!Source && hasLength!Source);
  This range splits a `source` range into `chunkCount` chunks of approximately equal length. Source must be a forward range with known length.
  Unlike chunks, `evenChunks` takes a chunk count (not size). The returned range will contain zero or more source.length / chunkCount + 1 elements followed by source.length / chunkCount elements. If source.length < chunkCount, some chunks will be empty.
  `chunkCount` must not be zero, unless `source` is also empty.
  Examples:

      import std.algorithm.comparison : equal;
      auto source = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
      auto chunks = evenChunks(source, 3);
      writeln(chunks[0]); // [1, 2, 3, 4]
      writeln(chunks[1]); // [5, 6, 7]
      writeln(chunks[2]); // [8, 9, 10]

  this(Source `source`, size_t `chunkCount`);
    Standard constructor
  @property auto `front`();
  void `popFront`();
  @property bool `empty`();
  @property typeof(this) `save`();
    Forward range primitives. Always present.
  const @property size_t `length`();
    Length
  auto `opIndex`(size_t `index`);
  typeof(this) `opSlice`(size_t `lower`, size_t `upper`);
  @property auto `back`();
  void `popBack`();
    Indexing, slicing and bidirectional operations and range primitives. Provided only if hasSlicing!Source is true.
auto `slide`(Flag!"withPartial" f = Yes.withPartial, Source)(Source `source`, size_t `windowSize`, size_t `stepSize` = 1)
if (isForwardRange!Source);
  A fixed-sized sliding window iteration of size `windowSize` over a `source` range by a custom `stepSize`.
  The Source range must be at least a ForwardRange and the `windowSize` must be greater than zero.
  For `windowSize` = 1 it splits the range into single element groups (aka unflatten) For `windowSize` = 2 it is similar to zip(`source`, `source`.save.dropOne).
  Parameters:

  f | Whether the last element has fewer elements than `windowSize` it should be be ignored (No.withPartial) or added (Yes.withPartial)
  Source `source` | Range from which the slide will be selected
  size_t `windowSize` | Sliding window size
  size_t `stepSize` | Steps between the windows (by default 1)

  Returns:
  Range of all sliding windows with propagated bi-directionality, forwarding, random access, and slicing.

  Note To avoid performance overhead, bi-directionality is only available when std.range.primitives.hasSlicing and std.range.primitives.hasLength are true.

  See Also:
  chunks
  Examples:
  Iterate over ranges with windows

      import std.algorithm.comparison : equal;

      assert([0, 1, 2, 3].slide(2).equal!equal(
          [[0, 1], [1, 2], [2, 3]]
      ));

      assert(5.iota.slide(3).equal!equal(
          [[0, 1, 2], [1, 2, 3], [2, 3, 4]]
      ));

  Examples:
  set a custom stepsize (default 1)

      import std.algorithm.comparison : equal;

      assert(6.iota.slide(1, 2).equal!equal(
          [[0], [2], [4]]
      ));

      assert(6.iota.slide(2, 4).equal!equal(
          [[0, 1], [4, 5]]
      ));

      assert(iota(7).slide(2, 2).equal!equal(
          [[0, 1], [2, 3], [4, 5], [6]]
      ));

      assert(iota(12).slide(2, 4).equal!equal(
          [[0, 1], [4, 5], [8, 9]]
      ));

  Examples:
  Allow the last slide to have fewer elements than windowSize

      import std.algorithm.comparison : equal;

      assert(3.iota.slide!(No.withPartial)(4).empty);
      assert(3.iota.slide!(Yes.withPartial)(4).equal!equal(
          [[0, 1, 2]]
      ));

  Examples:
  Count all the possible substrings of length 2

      import std.algorithm.iteration : each;

      int[dstring] d;
      "AGAGA"d.slide!(Yes.withPartial)(2).each!(a => d[a]++);
      writeln(d); // ["AG"d:2, "GA"d:2]

  Examples:
  withPartial only has an effect if last element in the range doesn't have the full size

      import std.algorithm.comparison : equal;

      assert(5.iota.slide!(Yes.withPartial)(3, 4).equal!equal([[0, 1, 2], [4]]));
      assert(6.iota.slide!(Yes.withPartial)(3, 4).equal!equal([[0, 1, 2], [4, 5]]));
      assert(7.iota.slide!(Yes.withPartial)(3, 4).equal!equal([[0, 1, 2], [4, 5, 6]]));

      assert(5.iota.slide!(No.withPartial)(3, 4).equal!equal([[0, 1, 2]]));
      assert(6.iota.slide!(No.withPartial)(3, 4).equal!equal([[0, 1, 2]]));
      assert(7.iota.slide!(No.withPartial)(3, 4).equal!equal([[0, 1, 2], [4, 5, 6]]));

auto `only`(Values...)(return scope Values `values`)
if (!is(CommonType!Values == void) || Values.length == 0);
  Assemble `values` into a range that carries all its elements in-situ.
  Useful when a single value or multiple disconnected values must be passed to an algorithm expecting a range, without having to perform dynamic memory allocation.
  As copying the range means copying all elements, it can be safely returned from functions. For the same reason, copying the returned range may be expensive for a large number of arguments.
  Parameters:

  Values `values` | the values to assemble together

  Returns:
  A RandomAccessRange of the assembled values.
  See Also:
  chain to chain ranges
  Examples:

      import std.algorithm.comparison : equal;
      import std.algorithm.iteration : filter, joiner, map;
      import std.algorithm.searching : findSplitBefore;
      import std.uni : isUpper;

      assert(equal(only('♡'), "♡"));
      writeln([1, 2, 3, 4].findSplitBefore(only(3))[0]); // [1, 2]

      assert(only("one", "two", "three").joiner(" ").equal("one two three"));

      string title = "The D Programming Language";
      assert(title
          .filter!isUpper // take the upper case letters
          .map!only       // make each letter its own range
          .joiner(".")    // join the ranges together lazily
          .equal("T.D.P.L"));

auto `enumerate`(Enumerator = size_t, Range)(Range `range`, Enumerator `start` = 0)
if (isIntegral!Enumerator && isInputRange!Range);
  Iterate over `range` with an attached index variable.
  Each element is a std.typecons.Tuple containing the index and the element, in that order, where the index member is named index and the element member is named value.
  The index starts at `start` and is incremented by one on every iteration.

  Overflow If `range` has length, then it is an error to pass a value for `start` so that `start` + `range`.length is bigger than Enumerator.max, thus it is ensured that overflow cannot happen.

  If `range` does not have length, and popFront is called when front.index == Enumerator.max, the index will overflow and continue from Enumerator.min.
  Parameters:

  Range `range` | the input range to attach indexes to
  Enumerator `start` | the number to start the index counter from

  Returns:
  At minimum, an input range. All other range primitives are given in the resulting range if `range` has them. The exceptions are the bidirectional primitives, which are propagated only if `range` has length.

  Example Useful for using foreach with an index loop variable:

          import std.stdio : stdin, stdout;
          import std.range : enumerate;

          foreach (lineNum, line; stdin.byLine().enumerate(1))
              stdout.writefln("line #%s: %s", lineNum, line);

  Examples:
  Can start enumeration from a negative position:

      import std.array : assocArray;
      import std.range : enumerate;

      bool[int] aa = true.repeat(3).enumerate(-1).assocArray();
      assert(aa[-1]);
      assert(aa[0]);
      assert(aa[1]);

enum auto `isTwoWayCompatible`(alias fn, T1, T2);
  Returns true if fn accepts variables of type T1 and T2 in any order. The following code should compile:

      (ref T1 a, ref T2 b)
      {
        fn(a, b);
        fn(b, a);
      }

  Examples:

      void func1(int a, int b);
      void func2(int a, float b);

      static assert(isTwoWayCompatible!(func1, int, int));
      static assert(isTwoWayCompatible!(func1, short, int));
      static assert(!isTwoWayCompatible!(func2, int, float));

      void func3(ref int a, ref int b);
      static assert( isTwoWayCompatible!(func3, int, int));
      static assert(!isTwoWayCompatible!(func3, short, int));

enum `SearchPolicy`: int;
  Policy used with the searching primitives lowerBound, upperBound, and equalRange of SortedRange below.
  Examples:

      import std.algorithm.comparison : equal;

      auto a = assumeSorted([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
      auto p1 = a.upperBound!(SearchPolicy.binarySearch)(3);
      assert(p1.equal([4, 5, 6, 7, 8, 9]));

      auto p2 = a.lowerBound!(SearchPolicy.gallop)(4);
      assert(p2.equal([0, 1, 2, 3]));

  `linear`
    Searches in a linear fashion.
  `trot`
    Searches with a step that is grows linearly (1, 2, 3,...) leading to a quadratic search schedule (indexes tried are 0, 1, 3, 6, 10, 15, 21, 28,...) Once the search overshoots its target, the remaining interval is searched using binary search. The search is completed in Ο(sqrt(n)) time. Use it when you are reasonably confident that the value is around the beginning of the range.
  `gallop`
    Performs a galloping search algorithm, i.e. searches with a step that doubles every time, (1, 2, 4, 8, ...) leading to an exponential search schedule (indexes tried are 0, 1, 3, 7, 15, 31, 63,...) Once the search overshoots its target, the remaining interval is searched using binary search. A value is found in Ο(log(n)) time.
  `binarySearch`
    Searches using a classic interval halving policy. The search starts in the middle of the range, and each search step cuts the range in half. This policy finds a value in Ο(log(n)) time but is less cache friendly than gallop for large ranges. The `binarySearch` policy is used as the last step of trot, gallop, trotBackwards, and gallopBackwards strategies.
  `trotBackwards`
    Similar to trot but starts backwards. Use it when confident that the value is around the end of the range.
  `gallopBackwards`
    Similar to gallop but starts backwards. Use it when confident that the value is around the end of the range.
enum `SortedRangeOptions`: int;
  Options for SortedRange ranges (below).
  Examples:

      // create a SortedRange, that's checked strictly
      SortedRange!(int[],"a < b", SortedRangeOptions.checkStrictly)([ 1, 3, 5, 7, 9 ]);

  `assumeSorted`
    Assume, that the range is sorted without checking.
  `checkStrictly`
    All elements of the range are checked to be sorted. The check is performed in O(n) time.
  `checkRoughly`
    Some elements of the range are checked to be sorted. For ranges with random order, this will almost surely detect, that it is not sorted. For almost sorted ranges it's more likely to fail. The checked elements are choosen in a deterministic manner, which makes this check reproducable. The check is performed in O(log(n)) time.
struct `SortedRange`(Range, alias pred = "a < b", SortedRangeOptions opt = SortedRangeOptions.assumeSorted) if (isInputRange!Range && !isInstanceOf!(`SortedRange`, Range));
template `SortedRange`(Range, alias pred = "a < b", SortedRangeOptions opt = SortedRangeOptions.assumeSorted) if (isInstanceOf!(`SortedRange`, Range))
  Represents a sorted range. In addition to the regular range primitives, supports additional operations that take advantage of the ordering, such as merge and binary search. To obtain a SortedRange from an unsorted range r, use std.algorithm.sorting.sort which sorts r in place and returns the corresponding `SortedRange`. To construct a `SortedRange` from a range r that is known to be already sorted, use assumeSorted.
  Parameters:

  Examples:

      import std.algorithm.sorting : sort;
      auto a = [ 1, 2, 3, 42, 52, 64 ];
      auto r = assumeSorted(a);
      assert(r.contains(3));
      assert(!(32 in r));
      auto r1 = sort!"a > b"(a);
      assert(3 in r1);
      assert(!r1.contains(32));
      writeln(r1.release()); // [64, 52, 42, 3, 2, 1]

  Examples:
  `SortedRange` could accept ranges weaker than random-access, but it is unable to provide interesting functionality for them. Therefore, `SortedRange` is currently restricted to random-access ranges.
  No copy of the original range is ever made. If the underlying range is changed concurrently with its corresponding `SortedRange` in ways that break its sorted-ness, `SortedRange` will work erratically.

      import std.algorithm.mutation : swap;
      auto a = [ 1, 2, 3, 42, 52, 64 ];
      auto r = assumeSorted(a);
      assert(r.contains(42));
      swap(a[3], a[5]);         // illegal to break sortedness of original range
      assert(!r.contains(42));  // passes although it shouldn't

  Examples:
  `SortedRange` can be searched with predicates that do not take two elements of the underlying range as arguments.
  This is useful, if a range of structs is sorted by a member and you want to search in that range by only providing a value for that member.

      import std.algorithm.comparison : equal;
      static struct S { int i; }
      static bool byI(A, B)(A a, B b)
      {
          static if (is(A == S))
              return a.i < b;
          else
              return a < b.i;
      }
      auto r = assumeSorted!byI([S(1), S(2), S(3)]);
      auto lessThanTwo = r.lowerBound(2);
      assert(equal(lessThanTwo, [S(1)]));

  @property bool `empty`();
  @property auto `save`();
  @property ref auto `front`();
  void `popFront`();
  @property ref auto `back`();
  void `popBack`();
  ref auto `opIndex`(size_t `i`);
  scope auto `opSlice`(size_t `a`, size_t `b`) return;
    Range primitives.
  auto `release`();
    Releases the controlled range and returns it.
  auto `lowerBound`(SearchPolicy sp = SearchPolicy.binarySearch, V)(V `value`)
  if (isTwoWayCompatible!(predFun, ElementType!Range, V) && hasSlicing!Range);
    This function uses a search with policy sp to find the largest left subrange on which pred(x, value) is true for all x (e.g., if pred is "less than", returns the portion of the range with elements strictly smaller than `value`). The search schedule and its complexity are documented in SearchPolicy.
    Examples:

        import std.algorithm.comparison : equal;
        auto a = assumeSorted([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]);
        auto p = a.lowerBound(4);
        assert(equal(p, [ 0, 1, 2, 3 ]));

  auto `upperBound`(SearchPolicy sp = SearchPolicy.binarySearch, V)(V `value`)
  if (isTwoWayCompatible!(predFun, ElementType!Range, V));
    This function searches with policy sp to find the largest right subrange on which pred(value, x) is true for all x (e.g., if pred is "less than", returns the portion of the range with elements strictly greater than `value`). The search schedule and its complexity are documented in SearchPolicy.
    For ranges that do not offer random access, SearchPolicy.linear is the only policy allowed (and it must be specified explicitly lest it exposes user code to unexpected inefficiencies). For random-access searches, all policies are allowed, and SearchPolicy.binarySearch is the default.
    Examples:

        import std.algorithm.comparison : equal;
        auto a = assumeSorted([ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]);
        auto p = a.upperBound(3);
        assert(equal(p, [4, 4, 5, 6]));

  auto `equalRange`(V)(V `value`)
  if (isTwoWayCompatible!(predFun, ElementType!Range, V) && isRandomAccessRange!Range);
    Returns the subrange containing all elements e for which both pred(e, value) and pred(value, e) evaluate to false (e.g., if pred is "less than", returns the portion of the range with elements equal to `value`). Uses a classic binary search with interval halving until it finds a value that satisfies the condition, then uses SearchPolicy.gallopBackwards to find the left boundary and SearchPolicy.gallop to find the right boundary. These policies are justified by the fact that the two boundaries are likely to be near the first found value (i.e., equal ranges are relatively small). Completes the entire search in Ο(log(n)) time.
    Examples:

        import std.algorithm.comparison : equal;
        auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
        auto r = a.assumeSorted.equalRange(3);
        assert(equal(r, [ 3, 3, 3 ]));

  auto `trisect`(V)(V `value`)
  if (isTwoWayCompatible!(predFun, ElementType!Range, V) && isRandomAccessRange!Range && hasLength!Range);
    Returns a tuple r such that r[0] is the same as the result of lowerBound(`value`), r[1] is the same as the result of equalRange(value), and r[2] is the same as the result of upperBound(value). The call is faster than computing all three separately. Uses a search schedule similar to equalRange. Completes the entire search in Ο(log(n)) time.
    Examples:

        import std.algorithm.comparison : equal;
        auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
        auto r = assumeSorted(a).trisect(3);
        assert(equal(r[0], [ 1, 2 ]));
        assert(equal(r[1], [ 3, 3, 3 ]));
        assert(equal(r[2], [ 4, 4, 5, 6 ]));

  bool `contains`(V)(V `value`)
  if (isRandomAccessRange!Range);
    Returns true if and only if `value` can be found in range, which is assumed to be sorted. Performs Ο(log(r.length)) evaluations of pred.
  bool `opBinaryRight`(string op, V)(V `value`)
  if (op == "in" && isRandomAccessRange!Range);
    Like contains, but the value is specified before the range.
  auto `groupBy`()();
    Returns a range of subranges of elements that are equivalent according to the sorting relation.
auto `assumeSorted`(alias pred = "a < b", R)(R `r`)
if (isInputRange!(Unqual!R));
  Assumes `r` is sorted by predicate pred and returns the corresponding SortedRange!(pred, R) having `r` as support. To check for sorted-ness at cost Ο(n), use std.algorithm.sorting.isSorted.
  Examples:

      import std.algorithm.comparison : equal;

      int[] a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
      auto p = assumeSorted(a);

      assert(equal(p.lowerBound(4), [0, 1, 2, 3]));
      assert(equal(p.lowerBound(5), [0, 1, 2, 3, 4]));
      assert(equal(p.lowerBound(6), [0, 1, 2, 3, 4, 5]));
      assert(equal(p.lowerBound(6.9), [0, 1, 2, 3, 4, 5, 6]));

struct `RefRange`(R) if (isInputRange!R);
auto `refRange`(R)(R* `range`)
if (isInputRange!R);
  Wrapper which effectively makes it possible to pass a range by reference. Both the original range and the RefRange will always have the exact same elements. Any operation done on one will affect the other. So, for instance, if it's passed to a function which would implicitly copy the original range if it were passed to it, the original range is not copied but is consumed as if it were a reference type.

  Note save works as normal and operates on a new range, so if save is ever called on the `RefRange`, then no operations on the saved range will affect the original.

  Parameters:

  R* `range` | the range to construct the `RefRange` from

  Returns:
  A `RefRange`. If the given range is a class type (and thus is already a reference type), then the original range is returned rather than a `RefRange`.
  Examples:
  Basic Example

      import std.algorithm.searching : find;
      ubyte[] buffer = [1, 9, 45, 12, 22];
      auto found1 = find(buffer, 45);
      writeln(found1); // [45, 12, 22]
      writeln(buffer); // [1, 9, 45, 12, 22]

      auto wrapped1 = refRange(&buffer);
      auto found2 = find(wrapped1, 45);
      writeln(*found2.ptr); // [45, 12, 22]
      writeln(buffer); // [45, 12, 22]

      auto found3 = find(wrapped1.save, 22);
      writeln(*found3.ptr); // [22]
      writeln(buffer); // [45, 12, 22]

      string str = "hello world";
      auto wrappedStr = refRange(&str);
      writeln(str.front); // 'h'
      str.popFrontN(5);
      writeln(str); // " world"
      writeln(wrappedStr.front); // ' '
      writeln(*wrappedStr.ptr); // " world"

  Examples:
  opAssign Example.

      ubyte[] buffer1 = [1, 2, 3, 4, 5];
      ubyte[] buffer2 = [6, 7, 8, 9, 10];
      auto wrapped1 = refRange(&buffer1);
      auto wrapped2 = refRange(&buffer2);
      assert(wrapped1.ptr is &buffer1);
      assert(wrapped2.ptr is &buffer2);
      assert(wrapped1.ptr !is wrapped2.ptr);
      assert(buffer1 != buffer2);

      wrapped1 = wrapped2;

      //Everything points to the same stuff as before.
      assert(wrapped1.ptr is &buffer1);
      assert(wrapped2.ptr is &buffer2);
      assert(wrapped1.ptr !is wrapped2.ptr);

      //But buffer1 has changed due to the assignment.
      writeln(buffer1); // [6, 7, 8, 9, 10]
      writeln(buffer2); // [6, 7, 8, 9, 10]

      buffer2 = [11, 12, 13, 14, 15];

      //Everything points to the same stuff as before.
      assert(wrapped1.ptr is &buffer1);
      assert(wrapped2.ptr is &buffer2);
      assert(wrapped1.ptr !is wrapped2.ptr);

      //But buffer2 has changed due to the assignment.
      writeln(buffer1); // [6, 7, 8, 9, 10]
      writeln(buffer2); // [11, 12, 13, 14, 15]

      wrapped2 = null;

      //The pointer changed for wrapped2 but not wrapped1.
      assert(wrapped1.ptr is &buffer1);
      assert(wrapped2.ptr is null);
      assert(wrapped1.ptr !is wrapped2.ptr);

      //buffer2 is not affected by the assignment.
      writeln(buffer1); // [6, 7, 8, 9, 10]
      writeln(buffer2); // [11, 12, 13, 14, 15]

  pure nothrow @safe this(R* `range`);
  auto `opAssign`(RefRange `rhs`);
    This does not assign the pointer of `rhs` to this RefRange. Rather it assigns the range pointed to by `rhs` to the range pointed to by this RefRange. This is because any operation on a RefRange is the same is if it occurred to the original range. The one exception is when a RefRange is assigned null either directly or because `rhs` is null. In that case, RefRange no longer refers to the original range but is null.
  void `opAssign`(typeof(null) `rhs`);
  inout pure nothrow @property @safe inout(R*) `ptr`();
    A pointer to the wrapped range.
  @property auto `front`();
  const @property auto `front`();
  @property auto `front`(ElementType!R `value`);
  @property bool `empty`();
  const @property bool `empty`();
  void `popFront`();
  @property auto `save`();
  const @property auto `save`();
  auto `opSlice`();
  const auto `opSlice`();
    Only defined if isForwardRange!R is true.
  @property auto `back`();
  const @property auto `back`();
  @property auto `back`(ElementType!R `value`);
  void `popBack`();
    Only defined if isBidirectionalRange!R is true.
  ref auto `opIndex`(IndexType)(IndexType `index`);
  const ref auto `opIndex`(IndexType)(IndexType `index`);
    Only defined if isRandomAccesRange!R is true.
  auto `moveFront`();
    Only defined if hasMobileElements!R and isForwardRange!R are true.
  auto `moveBack`();
    Only defined if hasMobileElements!R and isBidirectionalRange!R are true.
  auto `moveAt`(size_t `index`);
    Only defined if hasMobileElements!R and isRandomAccessRange!R are true.
  @property size_t `length`();
  const @property size_t `length`();
  alias `opDollar` = length;
    Only defined if hasLength!R is true.
  auto `opSlice`(IndexType1, IndexType2)(IndexType1 `begin`, IndexType2 `end`);
  const auto `opSlice`(IndexType1, IndexType2)(IndexType1 `begin`, IndexType2 `end`);
    Only defined if hasSlicing!R is true.
auto `bitwise`(R)(auto ref R `range`)
if (isInputRange!R && isIntegral!(ElementType!R));
  Bitwise adapter over an integral type range. Consumes the range elements bit by bit, from the least significant bit to the most significant bit.
  Parameters:

  R | an integral input range to iterate over
  R `range` | range to consume bit by by

  Returns:
  A Bitwise input range with propagated forward, bidirectional and random access capabilities
  Examples:

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

      // 00000011 00001001
      ubyte[] arr = [3, 9];
      auto r = arr.bitwise;

      // iterate through it as with any other range
      writeln(format("%(%d%)", r)); // "1100000010010000"
      assert(format("%(%d%)", r.retro).equal("1100000010010000".retro));

      auto r2 = r[5 .. $];
      // set a bit
      r[2] = 1;
      writeln(arr[0]); // 7
      writeln(r[5]); // r2[0]

  Examples:
  You can use bitwise to implement an uniform bool generator

      import std.algorithm.comparison : equal;
      import std.random : rndGen;

      auto rb = rndGen.bitwise;
      static assert(isInfinite!(typeof(rb)));

      auto rb2 = rndGen.bitwise;
      // Don't forget that structs are passed by value
      assert(rb.take(10).equal(rb2.take(10)));

struct `NullSink`;
ref auto `nullSink`();
  An OutputRange that discards the data it receives.
  Examples:

      import std.algorithm.iteration : map;
      import std.algorithm.mutation : copy;
      [4, 5, 6].map!(x => x * 2).copy(nullSink); // data is discarded

  Examples:

      import std.csv : csvNextToken;

      string line = "a,b,c";

      // ignore the first column
      line.csvNextToken(nullSink, ',', '"');
      line.popFront;

      // look at the second column
      Appender!string app;
      line.csvNextToken(app, ',', '"');
      writeln(app.data); // "b"

auto `tee`(Flag!"pipeOnPop" pipeOnPop = Yes.pipeOnPop, R1, R2)(R1 `inputRange`, R2 `outputRange`)
if (isInputRange!R1 && isOutputRange!(R2, ElementType!R1));
auto `tee`(alias fun, Flag!"pipeOnPop" pipeOnPop = Yes.pipeOnPop, R1)(R1 `inputRange`)
if (is(typeof(fun) == void) || isSomeFunction!fun);
  Implements a "tee" style pipe, wrapping an input range so that elements of the range can be passed to a provided function or OutputRange as they are iterated over. This is useful for printing out intermediate values in a long chain of range code, performing some operation with side-effects on each call to front or popFront, or diverting the elements of a range into an auxiliary OutputRange.
  It is important to note that as the resultant range is evaluated lazily, in the case of the version of `tee` that takes a function, the function will not actually be executed until the range is "walked" using functions that evaluate ranges, such as std.array.array or std.algorithm.iteration.fold.
  Parameters:

  pipeOnPop | If Yes.pipeOnPop, simply iterating the range without ever calling front is enough to have `tee` mirror elements to `outputRange` (or, respectively, fun). Note that each popFront() call will mirror the old front value, not the new one. This means that the last value will not be forwarded if the range isn't iterated until empty. If No.pipeOnPop, only elements for which front does get called will be also sent to `outputRange`/fun. If front is called twice for the same element, it will still be sent only once. If this caching is undesired, consider using std.algorithm.iteration.map instead.
  R1 `inputRange` | The input range being passed through.
  R2 `outputRange` | This range will receive elements of `inputRange` progressively as iteration proceeds.
  fun | This function will be called with elements of `inputRange` progressively as iteration proceeds.

  Returns:
  An input range that offers the elements of `inputRange`. Regardless of whether `inputRange` is a more powerful range (forward, bidirectional etc), the result is always an input range. Reading this causes `inputRange` to be iterated and returns its elements in turn. In addition, the same elements will be passed to `outputRange` or fun as well.
  See Also:
  std.algorithm.iteration.each
  Examples:

      import std.algorithm.comparison : equal;
      import std.algorithm.iteration : filter, map;

      // Sum values while copying
      int[] values = [1, 4, 9, 16, 25];
      int sum = 0;
      auto newValues = values.tee!(a => sum += a).array;
      assert(equal(newValues, values));
      writeln(sum); // 1 + 4 + 9 + 16 + 25

      // Count values that pass the first filter
      int count = 0;
      auto newValues4 = values.filter!(a => a < 10)
                              .tee!(a => count++)
                              .map!(a => a + 1)
                              .filter!(a => a < 10);

      //Fine, equal also evaluates any lazy ranges passed to it.
      //count is not 3 until equal evaluates newValues4
      assert(equal(newValues4, [2, 5]));
      writeln(count); // 3

auto `padLeft`(R, E)(R `r`, E `e`, size_t `n`)
if ((isInputRange!R && hasLength!R || isForwardRange!R) && !is(CommonType!(ElementType!R, E) == void));
  Extends the length of the input range `r` by padding out the start of the range with the element `e`. The element `e` must be of a common type with the element type of the range `r` as defined by std.traits.CommonType. If `n` is less than the length of of `r`, then `r` is returned unmodified.
  If `r` is a string with Unicode characters in it, `padLeft` follows D's rules about length for strings, which is not the number of characters, or graphemes, but instead the number of encoding units. If you want to treat each grapheme as only one encoding unit long, then call std.uni.byGrapheme before calling this function.
  If `r` has a length, then this is Ο(1). Otherwise, it's Ο(r.length).
  Parameters:

  R `r` | an input range with a length, or a forward range
  E `e` | element to pad the range with
  size_t `n` | the length to pad to

  Returns:
  A range containing the elements of the original range with the extra padding
  See Also: std.string.leftJustifier
  Examples:

      import std.algorithm.comparison : equal;

      assert([1, 2, 3, 4].padLeft(0, 6).equal([0, 0, 1, 2, 3, 4]));
      assert([1, 2, 3, 4].padLeft(0, 3).equal([1, 2, 3, 4]));

      assert("abc".padLeft('_', 6).equal("___abc"));

auto `padRight`(R, E)(R `r`, E `e`, size_t `n`)
if (isInputRange!R && !isInfinite!R && !is(CommonType!(ElementType!R, E) == void));
  Extend the length of the input range `r` by padding out the end of the range with the element `e`. The element `e` must be of a common type with the element type of the range `r` as defined by std.traits.CommonType. If `n` is less than the length of of `r`, then the contents of `r` are returned.
  The range primitives that the resulting range provides depends whether or not `r` provides them. Except the functions back and popBack, which also require the range to have a length as well as back and popBack
  Parameters:

  R `r` | an input range with a length
  E `e` | element to pad the range with
  size_t `n` | the length to pad to

  Returns:
  A range containing the elements of the original range with the extra padding
  See Also: std.string.rightJustifier
  Examples:

      import std.algorithm.comparison : equal;

      assert([1, 2, 3, 4].padRight(0, 6).equal([1, 2, 3, 4, 0, 0]));
      assert([1, 2, 3, 4].padRight(0, 4).equal([1, 2, 3, 4]));

      assert("abc".padRight('_', 6).equal("abc___"));

Copyright © 1999-2021 by the D Language Foundation | Page generated by Ddoc on Thu Jun 3 21:31:57 2021