. Ranges generalize the concept of
arrays, lists, or anything that involves sequential access. This abstraction
enables the same set of algorithms (see
) to be used with a vast variety of different concrete types. For
example, a linear search algorithm such as
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
This module defines several templates for testing whether a given object is a
range, and what kind of range it is:
A rich set of range creation and composition templates are provided that let
you construct new ranges out of existing ranges:
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
definitions that can be used to
wrap around range objects created by the above templates.
Ranges whose elements are sorted afford better efficiency with certain
operations. For this, the
from a pre-sorted range. The
.
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:
, David Simcha,
and Jonathan M Davis. Credit for some of the ideas in building this module goes
to
.
- 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; if (r.empty) {} r.popFront(); auto h = r.front;
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); r.popBack(); auto t = r.back; auto w = r.front;
static assert(is(typeof(t) == typeof(w)));
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.
static assert(isBidirectionalRange!R ||
isForwardRange!R && isInfinite!R);
R r = void;
auto e = r[1]; static assert(is(typeof(e) == typeof(r.front))); static assert(!isNarrowString!R); static assert(hasLength!R || isInfinite!R);
static if(is(typeof(r[$])))
{
static assert(is(typeof(r.front) == typeof(r[$])));
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:
static assert(is(ElementType!(int[]) == int));
static assert(is(ElementType!(char[]) == dchar)); static assert(is(ElementType!(dchar[]) == dchar));
static assert(is(ElementType!(string) == dchar));
static assert(is(ElementType!(dstring) == immutable(dchar)));
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:
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)); swap(r.front, r.front);
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); auto e = r.front;
r.front = e;
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" ];
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:
auto fib = recurrence!("a[n-1] + a[n-2]")(1, 1);
foreach (e; take(fib, 10)) { writeln(e); }
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);
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) {
}
auto squares = map!"a * a"(iota(10));
auto squaresWrapped = inputRangeObject(squares);
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.
See Also:
inputRangeObject
- @property E front();
-
- E moveFront();
-
- void popFront();
-
- @property bool empty();
-
- int opApply(int delegate(E));
int opApply(int delegate(size_t, E));
- foreach iteration uses opApply, since one delegate call per loop
iteration is faster than three virtual function calls.
- interface ForwardRange(E): InputRange!E;
- Interface for a forward range of type E.
- @property ForwardRange!E save();
-
- interface BidirectionalRange(E): ForwardRange!E;
- Interface for a bidirectional range of type E.
- @property BidirectionalRange!E save();
-
- @property E back();
-
- E moveBack();
-
- void popBack();
-
- interface RandomAccessFinite(E): BidirectionalRange!E;
- Interface for a finite random access range of type E.
- @property RandomAccessFinite!E save();
-
- E opIndex(size_t);
-
- E moveAt(size_t);
-
- @property size_t length();
-
- alias opDollar = length;
-
- RandomAccessFinite!E opSlice(size_t, size_t);
-
- interface RandomAccessInfinite(E): ForwardRange!E;
- Interface for an infinite random access range of type E.
- E moveAt(size_t);
-
- @property RandomAccessInfinite!E save();
-
- E opIndex(size_t);
-
- interface InputAssignable(E): InputRange!E;
- Adds assignable elements to InputRange.
- @property void front(E newVal);
-
- interface ForwardAssignable(E): InputAssignable!E, ForwardRange!E;
- Adds assignable elements to ForwardRange.
- @property ForwardAssignable!E save();
-
- interface BidirectionalAssignable(E): ForwardAssignable!E, BidirectionalRange!E;
- Adds assignable elements to BidirectionalRange.
- @property BidirectionalAssignable!E save();
-
- @property void back(E newVal);
-
- interface RandomFiniteAssignable(E): RandomAccessFinite!E, BidirectionalAssignable!E;
- Adds assignable elements to RandomAccessFinite.
- @property RandomFiniteAssignable!E save();
-
- void opIndexAssign(E val, size_t index);
-
- interface OutputRange(E);
- Interface for an output range of type E. Usage is similar to the
InputRange interface and descendants.
- void put(E);
-
- class OutputRangeObject(R, E...): staticMap!(OutputRange, E);
- Implements the OutputRange interface for all types E and wraps the
put method for each type E in a virtual function.
- template MostDerivedInputRange(R) if (isInputRange!(Unqual!R))
- Returns the interface type that best matches R.
- template InputRangeObject(R) if (isInputRange!(Unqual!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.
- InputRangeObject!R inputRangeObject(R)(R range) if (isInputRange!R);
- Convenience function for creating an InputRangeObject of the proper type.
See InputRange for an example.
- template outputRangeObject(E...)
- Convenience function for creating an OutputRangeObject with a base range
of type R that accepts types E.
Examples:
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)));
- OutputRangeObject!(R, E) outputRangeObject(R)(R range);
-
- template isTwoWayCompatible(alias fn, T1, T2)
- 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());
- enum SearchPolicy: int;
- Policy used with the searching primitives lowerBound, upperBound, and equalRange of SortedRange below.
- linear
- Searches in a linear fashion.
- trot
- Searches with a step that is grows linearly (1, 2, 3,...)
leading to a quadratic search schedule (indexes tried are 0, 1,
3, 6, 10, 15, 21, 28,...) Once the search overshoots its target,
the remaining interval is searched using binary search. The
search is completed in Ο(sqrt(n)) time. Use it when you
are reasonably confident that the value is around the beginning
of the range.
- gallop
- Performs a galloping search algorithm, i.e. searches
with a step that doubles every time, (1, 2, 4, 8, ...) leading
to an exponential search schedule (indexes tried are 0, 1, 3,
7, 15, 31, 63,...) Once the search overshoots its target, the
remaining interval is searched using binary search. A value is
found in Ο(log(n)) time.
- binarySearch
- Searches using a classic interval halving policy. The search
starts in the middle of the range, and each search step cuts
the range in half. This policy finds a value in Ο(log(n))
time but is less cache friendly than gallop for large
ranges. The binarySearch policy is used as the last step
of trot, gallop, trotBackwards, and gallopBackwards strategies.
- trotBackwards
- Similar to trot but starts backwards. Use it when
confident that the value is around the end of the range.
- gallopBackwards
- Similar to gallop but starts backwards. Use it when
confident that the value is around the end of the range.
- struct SortedRange(Range, alias pred = "a < b") if (isInputRange!Range);
- Represents a sorted range. In addition to the regular range
primitives, supports additional operations that take advantage of the
ordering, such as merge and binary search. To obtain a SortedRange from an unsorted range r, use std.algorithm.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.
Examples:
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 ]);
Examples:
SortedRange could accept ranges weaker than random-access, but it
is unable to provide interesting functionality for them. Therefore,
SortedRange is currently restricted to random-access ranges.
No copy of the original range is ever made. If the underlying range is
changed concurrently with its corresponding SortedRange in ways
that break its sortedness, SortedRange will work erratically.
auto a = [ 1, 2, 3, 42, 52, 64 ];
auto r = assumeSorted(a);
assert(r.contains(42));
swap(a[3], a[5]); assert(!r.contains(42));
- @property bool empty();
@property auto save();
@property ref auto front();
void popFront();
@property ref auto back();
void popBack();
ref auto opIndex(size_t i);
auto opSlice(size_t a, size_t b);
@property size_t length();
alias opDollar = length;
- Range primitives.
- auto release();
- Releases the controlled range and returns it.
- auto lowerBound(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value) if (isTwoWayCompatible!(predFun, ElementType!Range, V) && hasSlicing!Range);
- This function uses a search with policy sp to find the
largest left subrange on which pred(x, value) is true for
all x (e.g., if pred is "less than", returns the portion of
the range with elements strictly smaller than value). The search
schedule and its complexity are documented in
SearchPolicy. See also STL's
lower_bound.
Example:
auto a = assumeSorted([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]);
auto p = a.lowerBound(4);
assert(equal(p, [ 0, 1, 2, 3 ]));
- auto upperBound(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value) if (isTwoWayCompatible!(predFun, ElementType!Range, V));
- This function searches with policy sp to find the largest right
subrange on which pred(value, x) is true for all x
(e.g., if pred is "less than", returns the portion of the range
with elements strictly greater than value). The search schedule
and its complexity are documented in SearchPolicy.
For ranges that do not offer random access, SearchPolicy.linear
is the only policy allowed (and it must be specified explicitly lest it exposes
user code to unexpected inefficiencies). For random-access searches, all
policies are allowed, and SearchPolicy.binarySearch is the default.
See Also:
STL's upper_bound.
Example:
auto a = assumeSorted([ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]);
auto p = a.upperBound(3);
assert(equal(p, [4, 4, 5, 6]));
- auto equalRange(V)(V value) if (isTwoWayCompatible!(predFun, ElementType!Range, V) && isRandomAccessRange!Range);
- Returns the subrange containing all elements e for which both pred(e, value) and pred(value, e) evaluate to false (e.g.,
if pred is "less than", returns the portion of the range with
elements equal to value). Uses a classic binary search with
interval halving until it finds a value that satisfies the condition,
then uses SearchPolicy.gallopBackwards to find the left boundary
and SearchPolicy.gallop to find the right boundary. These
policies are justified by the fact that the two boundaries are likely
to be near the first found value (i.e., equal ranges are relatively
small). Completes the entire search in Ο(log(n)) time. See also
STL's equal_range.
Example:
auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
auto r = equalRange(a, 3);
assert(equal(r, [ 3, 3, 3 ]));
- auto trisect(V)(V value) if (isTwoWayCompatible!(predFun, ElementType!Range, V) && isRandomAccessRange!Range);
- Returns a tuple r such that r[0] is the same as the result
of lowerBound(value), r[1] is the same as the result of equalRange(value), and r[2] is the same as the result of upperBound(value). The call is faster than computing all three
separately. Uses a search schedule similar to equalRange. Completes the entire search in Ο(log(n)) time.
Example:
auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
auto r = assumeSorted(a).trisect(3);
assert(equal(r[0], [ 1, 2 ]));
assert(equal(r[1], [ 3, 3, 3 ]));
assert(equal(r[2], [ 4, 4, 5, 6 ]));
- bool contains(V)(V value) if (isRandomAccessRange!Range);
- Returns true if and only if value can be found in range, which is assumed to be sorted. Performs Ο(log(r.length))
evaluations of pred. See also STL's binary_search.
- auto assumeSorted(alias pred = "a < b", R)(R r) if (isInputRange!(Unqual!R));
- Assumes r is sorted by predicate pred and returns the
corresponding SortedRange!(pred, R) having r as support. To
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.
- struct RefRange(R) if (isForwardRange!R);
- Wrapper which effectively makes it possible to pass a range by reference.
Both the original range and the RefRange will always have the exact same
elements. Any operation done on one will affect the other. So, for instance,
if it's passed to a function which would implicitly copy the original range
if it were passed to it, the original range is not copied but is
consumed as if it were a reference type.
Note 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.
Examples:
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");
- pure nothrow @safe this(R* range);
-
- auto opAssign(RefRange rhs);
- This does not assign the pointer of rhs to this RefRange.
Rather it assigns the range pointed to by rhs to the range pointed
to by this RefRange. This is because any operation on a
RefRange is the same is if it occurred to the original range. The
one exception is when a RefRange is assigned null either
directly or because rhs is null. In that case, RefRange
no longer refers to the original range but is null.
Examples:
ubyte[] buffer1 = [1, 2, 3, 4, 5];
ubyte[] buffer2 = [6, 7, 8, 9, 10];
auto wrapped1 = refRange(&buffer1);
auto wrapped2 = refRange(&buffer2);
assert(wrapped1.ptr is &buffer1);
assert(wrapped2.ptr is &buffer2);
assert(wrapped1.ptr !is wrapped2.ptr);
assert(buffer1 != buffer2);
wrapped1 = wrapped2;
assert(wrapped1.ptr is &buffer1);
assert(wrapped2.ptr is &buffer2);
assert(wrapped1.ptr !is wrapped2.ptr);
assert(buffer1 == [6, 7, 8, 9, 10]);
assert(buffer2 == [6, 7, 8, 9, 10]);
buffer2 = [11, 12, 13, 14, 15];
assert(wrapped1.ptr is &buffer1);
assert(wrapped2.ptr is &buffer2);
assert(wrapped1.ptr !is wrapped2.ptr);
assert(buffer1 == [6, 7, 8, 9, 10]);
assert(buffer2 == [11, 12, 13, 14, 15]);
wrapped2 = null;
assert(wrapped1.ptr is &buffer1);
assert(wrapped2.ptr is null);
assert(wrapped1.ptr !is wrapped2.ptr);
assert(buffer1 == [6, 7, 8, 9, 10]);
assert(buffer2 == [11, 12, 13, 14, 15]);
- auto opAssign(typeof(null) rhs);
-
- inout pure nothrow @property @safe inout(R*) ptr();
- A pointer to the wrapped range.
- @property auto front();
const @property auto front();
@property auto front(ElementType!R value);
-
- @property bool empty();
const @property bool empty();
-
- void popFront();
-
- @property auto save();
const @property auto save();
auto opSlice();
const auto opSlice();
-
- @property auto back();
const @property auto back();
@property auto back(ElementType!R value);
void popBack();
- Only defined if isBidirectionalRange!R is true.
- ref auto opIndex(IndexType)(IndexType index);
const ref auto opIndex(IndexType)(IndexType index);
- Only defined if isRandomAccesRange!R is true.
- auto moveFront();
- Only defined if hasMobileElements!R and isForwardRange!R are
true.
- auto moveBack();
- Only defined if hasMobileElements!R and isBidirectionalRange!R
are true.
- auto moveAt(IndexType)(IndexType index) if (is(typeof((*_range).moveAt(index))));
- Only defined if hasMobileElements!R and isRandomAccessRange!R
are true.
- @property auto length();
const @property auto length();
- Only defined if hasLength!R is true.
- auto opSlice(IndexType1, IndexType2)(IndexType1 begin, IndexType2 end);
const auto opSlice(IndexType1, IndexType2)(IndexType1 begin, IndexType2 end);
- Only defined if hasSlicing!R is true.
- auto refRange(R)(R* range) if (isForwardRange!R && !is(R == class));
- 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.
- struct NullSink;
- An OutputRange that discards the data it receives.
