std.range.primitives

enum bool 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 following are rules of input ranges are assumed to hold true in all Phobos code. These rules are not checkable at compile-time, so not conforming to these rules when writing ranges or range based code will result in undefined behavior.

• r.empty returns false if and only if there is more data available in the range.
• r.empty evaluated multiple times, without calling r.popFront, or otherwise mutating the range object or the underlying data, yields the same result for every evaluation.
• r.front returns the current element in the range. It may return by value or by reference.
• r.front can be legally evaluated if and only if evaluating r.empty has, or would have, equaled false.
• r.front evaluated multiple times, without calling r.popFront, or otherwise mutating the range object or the underlying data, yields the same result for every evaluation.
• r.popFront advances to the next element in the range.
• r.popFront can be called if and only if evaluating r.empty has, or would have, equaled false.

Also, note that Phobos code assumes that the primitives r.front and r.empty are Ο(1) time complexity wise or "cheap" in terms of running time. Ο() statements in the documentation of range functions are made with this assumption.

Parameters:

R	type to be tested

Returns:

true if R is an InputRange, false if not

Examples:

struct A {}
struct B
{
    void popFront();
    @property bool empty();
    @property int front();
}
static assert(!isInputRange!A);
static assert( isInputRange!B);
static assert( isInputRange!(int[]));
static assert( isInputRange!(char[]));
static assert(!isInputRange!(char[4]));
static assert( isInputRange!(inout(int)[]));

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.

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

enum bool 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;
auto s1 = r1.save;
static assert (is(typeof(s1) == 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.

Examples:

static assert(!isForwardRange!(int));
static assert( isForwardRange!(int[]));
static assert( isForwardRange!(inout(int)[]));

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

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.

Examples:

alias R = int[];
R r = [0,1];
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

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

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.

Examples:

import std.traits : isNarrowString;

alias R = int[];

// range is finite and bidirectional or infinite and forward.
static assert(isBidirectionalRange!R ||
              isForwardRange!R && isInfinite!R);

R r = [0,1];
auto e = r[1]; // can index
auto f = r.front;
static assert(is(typeof(e) == typeof(f))); // 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(f) == 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(f) == typeof(r[$ - 1])));
}

enum bool hasMobileElements(R);

Returns true iff R is an input range that 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 following code should compile for any range with mobile elements.

alias E = ElementType!R;
R r;
static assert(isInputRange!R);
static assert(is(typeof(moveFront(r)) == E));
static if (isBidirectionalRange!R)
    static assert(is(typeof(moveBack(r)) == E));
static if (isRandomAccessRange!R)
    static assert(is(typeof(moveAt(r, 0)) == E));

Examples:

import std.algorithm.iteration : map;
import std.range : iota, repeat;

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

static assert( hasMobileElements!( string));
static assert( hasMobileElements!(dstring));
static assert( hasMobileElements!( char[]));
static assert( hasMobileElements!(dchar[]));

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:

import std.range : iota;

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

import std.range : iota;
// 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));

enum bool hasSwappableElements(R);

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

R r;
static assert(isInputRange!R);
swap(r.front, r.front);
static if (isBidirectionalRange!R) swap(r.back, r.front);
static if (isRandomAccessRange!R) swap(r[], r.front);

Examples:

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

static assert(!hasSwappableElements!( string));
static assert(!hasSwappableElements!(dstring));
static assert(!hasSwappableElements!( char[]));
static assert( hasSwappableElements!(dchar[]));

enum bool hasAssignableElements(R);

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

R r;
static assert(isInputRange!R);
r.front = r.front;
static if (isBidirectionalRange!R) r.back = r.front;
static if (isRandomAccessRange!R) r[0] = r.front;

Examples:

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

static assert(!hasAssignableElements!( string));
static assert(!hasAssignableElements!(dstring));
static assert(!hasAssignableElements!( char[]));
static assert( hasAssignableElements!(dchar[]));

enum bool hasLvalueElements(R);

Tests whether the range R has lvalue elements. These are defined as elements that can be passed by reference and have their address taken. The following code should compile for any range with lvalue elements.

void passByRef(ref ElementType!R stuff);
...
static assert(isInputRange!R);
passByRef(r.front);
static if (isBidirectionalRange!R) passByRef(r.back);
static if (isRandomAccessRange!R) passByRef(r[0]);

Examples:

import std.range : iota, chain;

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

static assert(!hasLvalueElements!( string));
static assert( hasLvalueElements!(dstring));
static assert(!hasLvalueElements!( char[]));
static assert( hasLvalueElements!(dchar[]));

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

enum bool 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:

import std.range : Repeat;
static assert(!isInfinite!(int[]));
static assert( isInfinite!(Repeat!(int)));

enum bool 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:

import std.range : takeExactly;
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.

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:

import std.algorithm.comparison : equal;
import std.range : iota;
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:

import std.algorithm.comparison : equal;
import std.range : iota;
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:

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

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

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);
assert(a.length == 3);

// define a perfunctory input range
struct InputRange
{
    enum bool empty = false;
    enum int front = 7;
    void popFront() {}
    int moveFront() { return 43; }
}
InputRange r;
// calls r.moveFront
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 { return payload; }
    @property ref int back() return { return payload; }
    void popFront() { }
    void popBack() { }
}
static assert(isBidirectionalRange!TestRange);
TestRange r;
auto x = moveBack(r);
assert(x == 5);

ElementType!R moveAt(R)(R r, size_t i);

Moves element at index i of r out and returns it. Leaves r[i] 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));
}

pure nothrow @nogc @property @safe bool empty(T)(in T[] a);

Implements the range interface primitive empty for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.empty is equivalent to empty(array).

Examples:

auto a = [ 1, 2, 3 ];
assert(!a.empty);
assert(a[3 .. $].empty);

pure nothrow @nogc @property @safe T[] save(T)(T[] a);

Implements the range interface primitive save for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.save is equivalent to save(array). The function does not duplicate the content of the array, it simply returns its argument.

Examples:

auto a = [ 1, 2, 3 ];
auto b = a.save;
assert(b is a);

pure nothrow @nogc @safe void popFront(T)(ref T[] a)
if (!isNarrowString!(T[]) && !is(T[] == void[]));

pure nothrow @trusted void popFront(C)(ref C[] str)
if (isNarrowString!(C[]));

Implements the range interface primitive popFront for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.popFront is equivalent to popFront(array). For narrow strings, popFront automatically advances to the next code point.

Examples:

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

pure nothrow @nogc @safe void popBack(T)(ref T[] a)
if (!isNarrowString!(T[]) && !is(T[] == void[]));

pure @safe void popBack(T)(ref T[] a)
if (isNarrowString!(T[]));

Implements the range interface primitive popBack for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.popBack is equivalent to popBack(array). For narrow strings, popFront automatically eliminates the last code point.

Examples:

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

pure nothrow @nogc @property ref @safe T front(T)(T[] a)
if (!isNarrowString!(T[]) && !is(T[] == void[]));

pure @property @safe dchar front(T)(T[] a)
if (isNarrowString!(T[]));

Implements the range interface primitive front for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.front is equivalent to front(array). For narrow strings, front automatically returns the first code point as a dchar.

Examples:

int[] a = [ 1, 2, 3 ];
assert(a.front == 1);

pure nothrow @nogc @property ref @safe T back(T)(T[] a)
if (!isNarrowString!(T[]) && !is(T[] == void[]));

pure @property @safe dchar back(T)(T[] a)
if (isNarrowString!(T[]));

Implements the range interface primitive back for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.back is equivalent to back(array). For narrow strings, back automatically returns the last code point as a dchar.

Examples:

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