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 local clone. Page wiki View or edit the community-maintained wiki page associated with this page.

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.find works not just for arrays, but for linked-lists, input files, incoming network data, etc.

For more detailed information about the conceptual aspect of ranges and the motivation behind them, see Andrei Alexandrescu's article On Iteration.

This module defines several templates for testing whether a given object is a range, and what kind of range it is:


isInputRange	Tests if something is an input range, defined to be something from which one can sequentially read data using the primitives front, popFront, and empty.
isOutputRange	Tests if something is an output range, defined to be something to which one can sequentially write data using the put primitive.
isForwardRange	Tests if something is a forward range, defined to be an input range with the additional capability that one can save one's current position with the save primitive, thus allowing one to iterate over the same range multiple times.
isBidirectionalRange	Tests if something is a bidirectional range, that is, a forward range that allows reverse traversal using the primitives back and popBack.
isRandomAccessRange	Tests if something is a random access range, which is a bidirectional range that also supports the array subscripting operation via the primitive opIndex.

A number of templates are provided that test for various range capabilities:


hasMobileElements	Tests if a given range's elements can be moved around using the primitives moveFront, moveBack, or moveAt.
ElementType	Returns the element type of a given range.
ElementEncodingType	Returns the encoding element type of a given range.
hasSwappableElements	Tests if a range is a forward range with swappable elements.
hasAssignableElements	Tests if a range is a forward range with mutable elements.
hasLvalueElements	Tests if a range is a forward range with elements that can be passed by reference and have their address taken.
hasLength	Tests if a given range has the length attribute.
isInfinite	Tests if a given range is an infinite range.
hasSlicing	Tests if a given range supports the array slicing operation R[x..y].
walkLength	Computes the length of any range in O(n) time.

A rich set of range creation and composition templates are provided that let you construct new ranges out of existing ranges:


retro	Iterates a bidirectional range backwards.
stride	Iterates a range with stride n.
chain	Concatenates several ranges into a single range.
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.
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.
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.
takeOne	Creates a random-access range consisting of exactly the first element of the given range.
takeNone	Creates a random-access range consisting of zero elements of the given range.
drop	Creates the range that results from discarding the first n elements from the given range.
dropExactly	Creates the range that results from discarding exactly n of the first elements from the given range.
dropOne	Creates the range that results from discarding the first elements from the given range.
repeat	Creates a range that consists of a single element repeated n times, or an infinite range repeating that element indefinitely.
cycle	Creates an infinite range that repeats the given forward range indefinitely. Good for implementing circular buffers.
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.
lockstep	Iterates n ranges in lockstep, for use in a foreach loop. Similar to zip, except that lockstep is designed especially for foreach loops.
recurrence	Creates a forward range whose values are defined by a mathematical recurrence relation.
sequence	Similar to recurrence, except that a random-access range is created.
iota	Creates a range consisting of numbers between a starting point and ending point, spaced apart by a given interval.
frontTransversal	Creates a range that iterates over the first elements of the given ranges.
transversal	Creates a range that iterates over the n'th elements of the given random-access ranges.
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.
chunks	Creates a range that returns fixed-size chunks of the original range.
only	Creates a range that iterates over the given arguments.

These range-construction tools are implemented using templates; but sometimes an object-based interface for ranges is needed. For this purpose, this module provides a number of object and interface definitions that can be used to wrap around range objects created by the above templates.


InputRange	Wrapper for input ranges.
InputAssignable	Wrapper for input ranges with assignable elements.
ForwardRange	Wrapper for forward ranges.
ForwardAssignable	Wrapper for forward ranges with assignable elements.
BidirectionalRange	Wrapper for bidirectional ranges.
BidirectionalAssignable	Wrapper for bidirectional ranges with assignable elements.
RandomAccessFinite	Wrapper for finite random-access ranges.
RandomAccessAssignable	Wrapper for finite random-access ranges with assignable elements.
RandomAccessInfinite	Wrapper for infinite random-access ranges.
OutputRange	Wrapper for output ranges.
OutputRangeObject	Class that implements the OutputRange interface and wraps the put methods in virtual functions.
InputRangeObject	Class that implements the InputRange interface and wraps the input range methods in virtual functions.
RefRange	Wrapper around a forward range that gives it reference semantics.

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

Finally, this module also defines some convenience functions for manipulating ranges:


popFrontN	Advances a given range by up to n elements.
popBackN	Advances a given bidirectional range from the right by up to n elements.
popFrontExactly	Advances a given range by up exactly n elements.
popBackExactly	Advances a given bidirectional range from the right by exactly n elements.
moveFront	Removes the front element of a range.
moveBack	Removes the back element of a bidirectional range.
moveAt	Removes the i'th element of a random-access range.

Source: std/range.d

License:

Boost License 1.0.

Authors:

Andrei Alexandrescu, David Simcha, and Jonathan M Davis. Credit for some of the ideas in building this module goes to Leonardo Maffi.

template isInputRange(R)

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

The semantics of an input range (not checkable during compilation) are assumed to be the following (r is an object of type R):

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.

void put(R, E)(ref R r, E e);

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.

In this table "doPut" is a method that places e into r, using the correct primitive: r.put(e) if R defines put, r.front = e if r is an input range (followed by r.popFront()), or r(e) otherwise.


Code Snippet	Scenario
r.doPut(e);	R specifically accepts an E.
r.doPut([ e ]);	R specifically accepts an E[].
r.putChar(e);	R accepts some form of string or character. put will transcode the character e accordingly.
for (; !e.empty; e.popFront()) put(r, e.front);	Copying range E into R.

Tip: put should not be used "UFCS-style", e.g. r.put(e). Doing this may call R.put directly, by-passing any transformation feature provided by Range.put. put(r, e) is prefered.

template isOutputRange(R, E)

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.

Examples:

void myprint(in char[] s) { }
static assert(isOutputRange!(typeof(&myprint), char));

static assert(!isOutputRange!(char[], char));
static assert( isOutputRange!(dchar[], wchar));
static assert( isOutputRange!(dchar[], dchar));

template isForwardRange(R)

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

Saving a range is not duplicating it; in the example above, r1 and r2 still refer to the same underlying data. They just navigate that data independently.

The semantics of a forward range (not checkable during compilation) are the same as for an input range, with the additional requirement that backtracking must be possible by saving a copy of the range object with save and using it later.

template isBidirectionalRange(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

The semantics of a bidirectional range (not checkable during compilation) are assumed to be the following (r is an object of type R):

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.

template isRandomAccessRange(R)

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

The semantics of a random-access range (not checkable during compilation) are assumed to be the following (r is an object of type R):

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

Although char[] and wchar[] (as well as their qualified versions including string and wstring) are arrays, isRandomAccessRange yields false for them because they use variable-length encodings (UTF-8 and UTF-16 respectively). These types are bidirectional ranges only.

template hasMobileElements(R)

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.

Examples:

static struct HasPostblit
{
    this(this) {}
}

auto nonMobile = map!"a"(repeat(HasPostblit.init));
static assert(!hasMobileElements!(typeof(nonMobile)));
static assert( hasMobileElements!(int[]));
static assert( hasMobileElements!(inout(int)[]));
static assert( hasMobileElements!(typeof(iota(1000))));

template ElementType(R)

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.

Examples:

// Standard arrays: returns the type of the elements of the array
static assert(is(ElementType!(int[]) == int));

// Accessing .front retrieves the decoded dchar
static assert(is(ElementType!(char[])  == dchar)); // rvalue
static assert(is(ElementType!(dchar[]) == dchar)); // lvalue

// Ditto
static assert(is(ElementType!(string) == dchar));
static assert(is(ElementType!(dstring) == immutable(dchar)));

// For ranges it gets the type of .front.
auto range = iota(0, 10);
static assert(is(ElementType!(typeof(range)) == int));

template ElementEncodingType(R)

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.

Examples:

// internally the range stores the encoded type
static assert(is(ElementEncodingType!(char[])  == char));

static assert(is(ElementEncodingType!(wstring) == immutable(wchar)));

static assert(is(ElementEncodingType!(byte[]) == byte));

auto range = iota(0, 10);
static assert(is(ElementEncodingType!(typeof(range)) == int));

template hasSwappableElements(R)

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

Examples:

static assert(!hasSwappableElements!(const int[]));
static assert(!hasSwappableElements!(const(int)[]));
static assert(!hasSwappableElements!(inout(int)[]));
static assert( hasSwappableElements!(int[]));

template hasAssignableElements(R)

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

Examples:

static assert(!hasAssignableElements!(const int[]));
static assert(!hasAssignableElements!(const(int)[]));
static assert( hasAssignableElements!(int[]));
static assert(!hasAssignableElements!(inout(int)[]));

template hasLvalueElements(R)

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

Examples:

static assert( hasLvalueElements!(int[]));
static assert( hasLvalueElements!(const(int)[]));
static assert( hasLvalueElements!(inout(int)[]));
static assert( hasLvalueElements!(immutable(int)[]));
static assert(!hasLvalueElements!(typeof(iota(3))));

auto c = chain([1, 2, 3], [4, 5, 6]);
static assert( hasLvalueElements!(typeof(c)));

template hasLength(R)

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.

Examples:

static assert(!hasLength!(char[]));
static assert( hasLength!(int[]));
static assert( hasLength!(inout(int)[]));

struct A { ulong length; }
struct B { size_t length() { return 0; } }
struct C { @property size_t length() { return 0; } }
static assert( hasLength!(A));
static assert(!hasLength!(B));
static assert( hasLength!(C));

template isInfinite(R)

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

Examples:

static assert(!isInfinite!(int[]));
static assert( isInfinite!(Repeat!(int)));

template hasSlicing(R)

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

Examples:

static assert( hasSlicing!(int[]));
static assert( hasSlicing!(const(int)[]));
static assert(!hasSlicing!(const int[]));
static assert( hasSlicing!(inout(int)[]));
static assert(!hasSlicing!(inout int []));
static assert( hasSlicing!(immutable(int)[]));
static assert(!hasSlicing!(immutable int[]));
static assert(!hasSlicing!string);
static assert( hasSlicing!dstring);

enum rangeFuncs = "@property int front();" ~
                  "void popFront();" ~
                  "@property bool empty();" ~
                  "@property auto save() { return this; }" ~
                  "@property size_t length();";

struct A { mixin(rangeFuncs); int opSlice(size_t, size_t); }
struct B { mixin(rangeFuncs); B opSlice(size_t, size_t); }
struct C { mixin(rangeFuncs); @disable this(); C opSlice(size_t, size_t); }
struct D { mixin(rangeFuncs); int[] opSlice(size_t, size_t); }
static assert(!hasSlicing!(A));
static assert( hasSlicing!(B));
static assert( hasSlicing!(C));
static assert(!hasSlicing!(D));

struct InfOnes
{
    enum empty = false;
    void popFront() {}
    @property int front() { return 1; }
    @property InfOnes save() { return this; }
    auto opSlice(size_t i, size_t j) { return takeExactly(this, j - i); }
    auto opSlice(size_t i, Dollar d) { return this; }

    struct Dollar {}
    Dollar opDollar() const { return Dollar.init; }
}

static assert(hasSlicing!InfOnes);

auto walkLength(Range)(Range range) if (isInputRange!Range && !isInfinite!Range); auto walkLength(Range)(Range range, const size_t upTo) if (isInputRange!Range);

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.

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.

Examples:

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

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.

Throws:

Exception if n == 0.

Example:

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

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.

Example:

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

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:

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

auto radial(Range, I)(Range r, I startingIndex) if (isRandomAccessRange!(Unqual!Range) && hasLength!(Unqual!Range) && isIntegral!I); auto radial(R)(R r) if (isRandomAccessRange!(Unqual!R) && hasLength!(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.

Examples:

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

struct Take(Range) if (isInputRange!(Unqual!Range) && !(!isInfinite!(Unqual!Range) && hasSlicing!(Unqual!Range) || is(Range T == Take!T))); Take!R take(R)(R input, size_t n) if (isInputRange!(Unqual!R) && !isInfinite!(Unqual!R) && hasSlicing!(Unqual!R));

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.

Examples:

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

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.

Examples:

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));
assert(b.length == 3);
assert(b.front == 1);
assert(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 (another feature that distinguishes takeOne from take).

Examples:

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

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

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

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

Note: drop and dropBack will only pop up to n elements but will stop if the range is empty first.

Examples:

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

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.

Examples:

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

string s = "日本語";
assert(s.dropExactly(2) == "語");
assert(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.container : DList;

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

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

string s = "日本語";
assert(s.dropOne() == "本語");
assert(s.dropBackOne() == "日本");

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

size_t popFrontN(Range)(ref Range r, size_t n) if (isInputRange!Range); size_t popBackN(Range)(ref Range r, size_t n) if (isBidirectionalRange!Range);

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.

Returns:

How much r was actually advanced, which may be less than n if r did not have at least n elements.

popBackN will behave the same but instead removes elements from the back of the (bidirectional) range instead of the front.

Examples:

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

Examples:

auto LL = iota(1L, 7L);
auto r = popFrontN(LL, 2);
assert(equal(LL, [3L, 4L, 5L, 6L]));
assert(r == 2);

Examples:

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

Examples:

auto LL = iota(1L, 7L);
auto r = popBackN(LL, 2);
assert(equal(LL, [1L, 2L, 3L, 4L]));
assert(r == 2);

void popFrontExactly(Range)(ref Range r, size_t n) if (isInputRange!Range); void popBackExactly(Range)(ref Range r, size_t n) if (isBidirectionalRange!Range);

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.

Note: Unlike popFrontN, popFrontExactly will assume that the range holds at least n elements. This makes popFrontExactly faster than popFrontN, 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.

popBackExactly will behave the same but instead removes elements from the back of the (bidirectional) range instead of the front.

Examples:

auto a = [1, 2, 3];
a.popFrontExactly(1);
assert(a == [2, 3]);
a.popBackExactly(1);
assert(a == [2]);

string s = "日本語";
s.popFrontExactly(1);
assert(s == "本語");
s.popBackExactly(1);
assert(s == "本");

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

struct Repeat(T); Repeat!T repeat(T)(T value);

Repeats one value forever.

Models an infinite bidirectional and random access range, with slicing.

Examples:

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

Take!(Repeat!T) repeat(T)(T value, size_t n);

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

Examples:

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

struct Cycle(R) if (isForwardRange!R && !isInfinite!R); Cycle!R cycle(R)(R input) if (isForwardRange!R && !isInfinite!R); Cycle!R cycle(R)(R input, size_t index = 0) if (isRandomAccessRange!R && !isInfinite!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. 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.

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

Examples:

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

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

Example:

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], ' ');
}

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. For example, the following code sorts two arrays in parallel:

Examples:

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

this(R rs, StoppingPolicy s = StoppingPolicy.shortest);: Builds an object. Usually this is invoked indirectly by using the zip function.
bool empty;: Returns true if the range is at end. The test depends on the stopping policy.
@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 nth element in the composite range. Defined if all ranges offer random access.
void opIndexAssign(ElementType v, size_t n);: Assigns to the nth element in the composite range. Defined if all ranges offer random access.

Returns the nth element in the composite range. Defined if all ranges offer random access.
ElementType moveAt(size_t n);: Destructively reads the nth element in the composite range. Defined if all ranges offer random access.

Returns the nth element in the composite range. Defined if all ranges offer random access.

enum StoppingPolicy: int;

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

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

Bugs:

If a range does not offer lvalue access, but ref is used in the foreach loop, it will be silently accepted but any modifications to the variable will not be propagated to the underlying range.

// Lockstep also supports iterating with an index variable:

Example:

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

Examples:

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

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.

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.

Example:

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

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:

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

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

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.

Throws:

Exception if begin != end && step == 0, an exception is thrown.

enum TransverseOptions: int;

Options for the FrontTransversal and Transversal ranges (below).

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:

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.
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 the nth element of each of the enclosed ranges. All elements of the enclosing range must offer random access.

Examples:

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

this(RangeOfRanges input, size_t n);: Construction from an input and an index.
bool empty; @property ref auto front(); E moveFront(); @property auto front(E val); void popFront(); @property typeof(this) save();: Forward range primitives.
@property ref auto back(); void popBack(); E moveBack(); @property auto 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); @property size_t length(); alias opDollar = length;: 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 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:

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(); @property size_t length(); 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]);
assert(ind.physicalIndex(0) == 1);

struct Chunks(Source) if (isForwardRange!Source); Chunks!Source chunks(Source)(Source source, size_t chunkSize) if (isForwardRange!Source);

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

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

Examples:

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);
assert(equal(retro(array(chunks)), array(retro(chunks))));

this(Source source, size_t chunkSize);: Standard constructor
@property auto front(); void popFront(); @property bool empty(); @property typeof(this) save();: Forward range primitives. Always present.
@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.

auto only(Values...)(auto ref 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.

Examples:

import std.uni;
assert(equal(only('♡'), "♡"));
assert([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(filter!isUpper(title).map!only().join(".") == "T.D.P.L");

ElementType!R moveFront(R)(R r);

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

Examples:

auto a = [ 1, 2, 3 ];
assert(moveFront(a) == 1);

// define a perfunctory input range
struct InputRange
{
    @property bool empty() { return false; }
    @property int front() { return 42; }
    void popFront() {}
    int moveFront() { return 43; }
}
InputRange r;
assert(moveFront(r) == 43);

ElementType!R moveBack(R)(R r);

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

Examples:

struct TestRange
{
    int payload = 5;
    @property bool empty() { return false; }
    @property TestRange save() { return this; }
    @property ref int front() { return payload; }
    @property ref int back() { return payload; }
    void popFront() { }
    void popBack() { }
}
static assert(isBidirectionalRange!TestRange);
TestRange r;
auto x = moveBack(r);
assert(x == 5);

ElementType!R moveAt(R, I)(R r, I i) if (isIntegral!I);

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

Examples:

auto a = [1,2,3,4];
foreach(idx, it; a)
{
    assert(it == moveAt(a, idx));
}

interface InputRange(E);

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.

Examples:

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

Limitations: These interfaces are not capable of forwarding ref access to elements.

Infiniteness of the wrapped range is not propagated.

Length is not propagated in the case of non-random access ranges.