Returns true if R is an input range. An input range must define the primitives empty, popFront, and front. The following code should compile for any input range.

R r;              // can define a range object

if (r.empty) {}   // can test for empty

r.popFront();     // can invoke popFront()

auto h = r.front; // can get the front of the range of non-void type

• r.empty returns false iff there is more data available in the range.
• r.front returns the current element in the range. It may return by value or by reference. Calling r.front is allowed only if calling r.empty has, or would have, returned false.
• r.popFront advances to the next element in the range. Calling r.popFront is allowed only if calling r.empty has, or would have, returned false.

Outputs e to r. The exact effect is dependent upon the two types. Several cases are accepted, as described below. The code snippets are attempted in order, and the first to compile "wins" and gets evaluated.

Returns true if R is an output range for elements of type E. An output range is defined functionally as a range that supports the operation put(r, e) as defined above.

Returns true if R is a forward range. A forward range is an input range r that can save "checkpoints" by saving r.save to another value of type R. Notable examples of input ranges that are not forward ranges are file/socket ranges; copying such a range will not save the position in the stream, and they most likely reuse an internal buffer as the entire stream does not sit in memory. Subsequently, advancing either the original or the copy will advance the stream, so the copies are not independent.

The following code should compile for any forward range.

static assert(isInputRange!R);
R r1;
static assert (is(typeof(r1.save) == R));

Returns true if R is a bidirectional range. A bidirectional range is a forward range that also offers the primitives back and popBack. The following code should compile for any bidirectional range.

R r;
static assert(isForwardRange!R);           // is forward range

r.popBack();                               // can invoke popBack

auto t = r.back;                           // can get the back of the range

auto w = r.front;
static assert(is(typeof(t) == typeof(w))); // same type for front and back

• r.back returns (possibly a reference to) the last element in the range. Calling r.back is allowed only if calling r.empty has, or would have, returned false.

Returns true if R is a random-access range. A random-access range is a bidirectional range that also offers the primitive opIndex, OR an infinite forward range that offers opIndex. In either case, the range must either offer length or be infinite. The following code should compile for any random-access range.

// range is finite and bidirectional or infinite and forward.

static assert(isBidirectionalRange!R ||
              isForwardRange!R && isInfinite!R);

R r = void;
auto e = r[1]; // can index

static assert(is(typeof(e) == typeof(r.front))); // same type for indexed and front

static assert(!isNarrowString!R); // narrow strings cannot be indexed as ranges

static assert(hasLength!R || isInfinite!R); // must have length or be infinite


// $ must work as it does with arrays if opIndex works with $

static if(is(typeof(r[$])))
{
    static assert(is(typeof(r.front) == typeof(r[$])));

    // $ - 1 doesn't make sense with infinite ranges but needs to work

    // with finite ones.

    static if(!isInfinite!R)
        static assert(is(typeof(r.front) == typeof(r[$ - 1])));
}

• r.opIndex(n) returns a reference to the nth element in the range.

Returns true iff R supports the moveFront primitive, as well as moveBack and moveAt if it's a bidirectional or random access range. These may be explicitly implemented, or may work via the default behavior of the module level functions moveFront and friends.

The element type of R. R does not have to be a range. The element type is determined as the type yielded by r.front for an object r of type R. For example,  ElementType!(T[]) is T if T[] isn't a narrow string; if it is, the element type is dchar. If R doesn't have front,  ElementType!R is void.

The encoding element type of R. For narrow strings (char[], wchar[] and their qualified variants including string and wstring),  ElementEncodingType is the character type of the string. For all other types,  ElementEncodingType is the same as ElementType.

Returns true if R is a forward range and has swappable elements. The following code should compile for any range with swappable elements.

R r;
static assert(isForwardRange!(R));   // range is forward

swap(r.front, r.front);              // can swap elements of the range

Returns true if R is a forward range and has mutable elements. The following code should compile for any range with assignable elements.

R r;
static assert(isForwardRange!R);  // range is forward

auto e = r.front;
r.front = e;                      // can assign elements of the range

Tests whether R has lvalue elements. These are defined as elements that can be passed by reference and have their address taken.

Returns true if R has a length member that returns an integral type. R does not have to be a range. Note that length is an optional primitive as no range must implement it. Some ranges do not store their length explicitly, some cannot compute it without actually exhausting the range (e.g. socket streams), and some other ranges may be infinite.

Although narrow string types (char[], wchar[], and their qualified derivatives) do define a length property,  hasLength yields false for them. This is because a narrow string's length does not reflect the number of characters, but instead the number of encoding units, and as such is not useful with range-oriented algorithms.

Returns true if R is an infinite input range. An infinite input range is an input range that has a statically-defined enumerated member called empty that is always false, for example:

struct MyInfiniteRange
{
    enum bool empty = false;
    ...
}

Returns true if R offers a slicing operator with integral boundaries that returns a forward range type.

For finite ranges, the result of opSlice must be of the same type as the original range type. If the range defines opDollar, then it must support subtraction.

For infinite ranges, when not using opDollar, the result of opSlice must be the result of take or takeExactly on the original range (they both return the same type for infinite ranges). However, when using opDollar, the result of opSlice must be that of the original range type.

The following code must compile for  hasSlicing to be true:

R r = void;

static if(isInfinite!R)
    typeof(take(r, 1)) s = r[1 .. 2];
else
{
    static assert(is(typeof(r[1 .. 2]) == R));
    R s = r[1 .. 2];
}

s = r[1 .. 2];

static if(is(typeof(r[0 .. $])))
{
    static assert(is(typeof(r[0 .. $]) == R));
    R t = r[0 .. $];
    t = r[0 .. $];

    static if(!isInfinite!R)
    {
        static assert(is(typeof(r[0 .. $ - 1]) == R));
        R u = r[0 .. $ - 1];
        u = r[0 .. $ - 1];
    }
}

static assert(isForwardRange!(typeof(r[1 .. 2])));
static assert(hasLength!(typeof(r[1 .. 2])));

This is a best-effort implementation of length for any kind of range.

If hasLength!Range, simply returns range.length without checking upTo (when specified).

Otherwise, walks the range through its length and returns the number of elements seen. Performes Ο(n) evaluations of range.empty and range.popFront(), where n is the effective length of range.

The upTo parameter is useful to "cut the losses" in case the interest is in seeing whether the range has at least some number of elements. If the parameter upTo is specified, stops if upTo steps have been taken and returns upTo.

Infinite ranges are compatible, provided the parameter upTo is specified, in which case the implementation simply returns upTo.

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.

int[] a = [ 1, 2, 3, 4, 5 ];
assert(equal(retro(a), [ 5, 4, 3, 2, 1 ][]));
assert(retro(a).source is a);
assert(retro(retro(a)) is a);

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.

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

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.

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

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

int[] a = [ 1, 2, 3, 4];
int[] b = [ 10, 20 ];
assert(equal(roundRobin(a, b), [1, 10, 2, 20, 3, 4]));

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.

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

Lazily takes only up to n elements of a range. This is particularly useful when using with infinite ranges. If the range offers random access and length,  Take offers them as well.

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

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.

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.

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

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.

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

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

assert(takeNone([42, 27, 19]).empty);
assert(takeNone("dlang.org").empty);
assert(takeNone(filter!"true"([42, 27, 19])).empty);

Convenience function which calls range.popFrontN (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 range.popBackN(n).

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

//Remove all but the first two elements

auto a = DList!int(0, 1, 9, 9, 9);
a.remove(a[].drop(2));
assert(a[].equal(a[].take(2)));

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

//insert before the last two elements

auto a = DList!int(0, 1, 2, 5, 6);
a.insertAfter(a[].dropBack(2), [3, 4]);
assert(a[].equal(iota(0, 7)));

Similar to drop and dropBack but they call range.popFrontExactly (n) and range.popBackExactly(n) instead.

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

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

Eagerly advances r itself (not a copy) up to n times (by calling r.popFront).  popFrontN takes r by ref, so it mutates the original range. Completes in Ο(1) steps for ranges that support slicing and have length. Completes in Ο(n) time for all other ranges.

int[] a = [ 1, 2, 3, 4, 5 ];
a.popFrontN(2);
assert(a == [ 3, 4, 5 ]);
a.popFrontN(7);
assert(a == [ ]);

int[] a = [ 1, 2, 3, 4, 5 ];
a.popBackN(2);
assert(a == [ 1, 2, 3 ]);
a.popBackN(7);
assert(a == [ ]);

Eagerly advances r itself (not a copy) exactly n times (by calling r.popFront).  popFrontExactly takes r by ref, so it mutates the original range. Completes in Ο(1) steps for ranges that support slicing, and have either length or are infinite. Completes in Ο(n) time for all other ranges.

Repeats one value forever.

enforce(equal(take(repeat(5), 4), [ 5, 5, 5, 5 ][]));

Repeats value exactly n times. Equivalent to take( repeat(value), n).

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

assert(equal(take(cycle([1, 2][]), 5), [ 1, 2, 1, 2, 1 ][]));

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

int[] a = [ 1, 2, 3 ];
string[] b = [ "a", "b", "c" ];
// prints 1:a 2:b 3:c

foreach (e; zip(a, b))
{
write(e[0], ':', e[1], ' ');
}

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

Dictates how iteration in a Zip should stop. By default stop at the end of the shortest of all ranges.

Iterate multiple ranges in lockstep using a foreach loop. 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.

By default StoppingPolicy is set to StoppingPolicy.shortest.

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

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

assert(arr1 == [7,9,11,13,15]);

// Lockstep also supports iterating with an index variable:

foreach(index, a, b; lockstep(arr1, arr2)) {
    writefln("Index %s:  a = %s, b = %s", index, a, b);
}

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.

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.

// 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);
// print the first 10 Fibonacci numbers

foreach (e; take(fib, 10)) { writeln(e); }
// print the first 10 factorials

foreach (e; take(recurrence!("a[n-1] * n")(1), 10)) { writeln(e); }

 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.

// a[0] = 1, a[1] = 2, a[n] = a[0] + n * a[1]

auto odds = sequence!("a[0] + n * a[1]")(1, 2);

Returns a range that goes through the numbers begin, begin + step, begin + 2 * step, ..., up to and excluding end. The range offered is a random access range. The two-arguments version has step = 1. If begin < end && step < 0 or begin > end && step > 0 or begin == end, then an empty range is returned.

auto r = iota(0, 10, 1);
assert(equal(r, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9][]));
r = iota(0, 11, 3);
assert(equal(r, [0, 3, 6, 9][]));
assert(r[2] == 6);
auto rf = iota(0.0, 0.5, 0.1);
assert(approxEqual(rf, [0.0, 0.1, 0.2, 0.3, 0.4]));

Options for the FrontTransversal and Transversal ranges (below).

Given a range of ranges, iterate transversally through the first elements of each of the enclosed ranges.

int[][] x = new int[][2];
x[0] = [1, 2];
x[1] = [3, 4];
auto ror = frontTransversal(x);
assert(equal(ror, [ 1, 3 ][]));

Given a range of ranges, iterate transversally through the the nth element of each of the enclosed ranges. All elements of the enclosing range must offer random access.

int[][] x = new int[][2];
x[0] = [1, 2];
x[1] = [3, 4];
auto ror = transversal(x, 1);
assert(equal(ror, [ 2, 4 ][]));

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.

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

// When elements of indices are duplicated and Source has lvalue elements,

// these are aliased in ind.

ind[0]++;
assert(ind[0] == 6);
assert(ind[5] == 6);

This range iterates over fixed-sized chunks of size chunkSize of a source range. Source must be a forward range.

If !isInfinitite!Source and source.walkLength is not evenly divisible by chunkSize, the back element of this range will contain fewer than chunkSize elements.

auto source = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
auto chunks = chunks(source, 4);
assert(chunks[0] == [1, 2, 3, 4]);
assert(chunks[1] == [5, 6, 7, 8]);
assert(chunks[2] == [9, 10]);
assert(chunks.back == chunks[2]);
assert(chunks.front == chunks[0]);
assert(chunks.length == 3);

This range iterates a single element. This is useful when a sole value must be passed to an algorithm expecting a range.

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

string title = "The D Programming Language";
assert(filter!isUpper(title).map!only().join(".") == "T.D.P.L");

Moves the front of r out and returns it. Leaves r.front in a destroyable state that does not allocate any resources (usually equal to its .init value).

Moves the back of r out and returns it. Leaves r.back in a destroyable state that does not allocate any resources (usually equal to its .init value).

Moves element at index i of r out and returns it. Leaves r.front in a destroyable state that does not allocate any resources (usually equal to its .init value).

These interfaces are intended to provide virtual function-based wrappers around input ranges with element type E. This is useful where a well-defined binary interface is required, such as when a DLL function or virtual function needs to accept a generic range as a parameter. Note that isInputRange and friends check for conformance to structural interfaces, not for implementation of these interface types.

void useRange(InputRange!int range) {
    // Function body.

}

// Create a range type.

auto squares = map!"a * a"(iota(10));

// Wrap it in an interface.

auto squaresWrapped = inputRangeObject(squares);

// Use it.

useRange(squaresWrapped);

Interface for a forward range of type E.

Interface for a bidirectional range of type E.

Interface for a finite random access range of type E.

Interface for an infinite random access range of type E.

Adds assignable elements to InputRange.

Adds assignable elements to ForwardRange.

Adds assignable elements to BidirectionalRange.

Adds assignable elements to RandomAccessFinite.

Interface for an output range of type E. Usage is similar to the InputRange interface and descendants.

Implements the OutputRange interface for all types E and wraps the put method for each type E in a virtual function.

Returns the interface type that best matches R.

Implements the most derived interface that R works with and wraps all relevant range primitives in virtual functions. If R is already derived from the InputRange interface, aliases itself away.

Convenience function for creating an InputRangeObject of the proper type. See InputRange for an example.

Convenience function for creating an OutputRangeObject with a base range of type R that accepts types E.

uint[] outputArray;
auto app = appender(&outputArray);
auto appWrapped = outputRangeObject!(uint, uint[])(app);
static assert(is(typeof(appWrapped) : OutputRange!(uint[])));
static assert(is(typeof(appWrapped) : OutputRange!(uint)));

Returns true if fn accepts variables of type T1 and T2 in any order. The following code should compile:

T1 foo();
T2 bar();

fn(foo(), bar());
fn(bar(), foo());

Policy used with the searching primitives lowerBound, upperBound, and equalRange of SortedRange below.

Represents a sorted random-access range. In addition to the regular range primitives, supports fast operations using binary search. To obtain a  SortedRange from an unsorted range r, use std.algorithm.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 described below.

auto a = [ 1, 2, 3, 42, 52, 64 ];
auto r = assumeSorted(a);
assert(r.contains(3));
assert(!r.contains(32));
auto r1 = sort!"a > b"(a);
assert(r1.contains(3));
assert(!r1.contains(32));
assert(r1.release() == [ 64, 52, 42, 3, 2, 1 ]);

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

Assumes r is sorted by predicate pred and returns the corresponding SortedRange!(pred, R) having r as support. To keep the checking costs low, the cost is Ο(1) in release mode (no checks for sortedness are performed). In debug mode, a few random elements of r are checked for sortedness. The size of the sample is proportional Ο(log(r.length)). That way, checking has no effect on the complexity of subsequent operations specific to sorted ranges (such as binary search). The probability of an arbitrary unsorted range failing the test is very high (however, an almost-sorted range is likely to pass it). To check for sortedness at cost Ο(n), use std.algorithm.isSorted.

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

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

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

auto found3 = find(wrapped2.save, 22);
assert(*found3.ptr == [22]);
assert(buffer == [45, 12, 22]);

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

Helper function for constructing a RefRange .

If the given range is not a forward range or it is a class type (and thus is already a reference type), then the original range is returned rather than a RefRange .