. 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:
| 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.
|
| 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.
|
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. Credit
for some of the ideas in building this module goes to
.
- 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.
| Code Snippet | Scenario |
|---|
| r.put(e); | R specifically defines a method
put accepting an E. |
| r.put([ e ]); | R specifically defines a
method put accepting an E[]. |
| r.front = e; r.popFront(); | R is an input
range and e is assignable to r.front. |
| for (; !e.empty; e.popFront()) put(r, e.front); | Copying range E to range R. |
| r(e); | R is e.g. a delegate accepting an E. |
| r([ e ]); | R is e.g. a delegate
accepting an E[]. |
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.
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;
R r2 = r1.save;
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.
R r;
static assert(isForwardRange!R); static assert(isBidirectionalRange!R || isInfinite!R);
auto e = 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 the range supports the moveFront primitive,
as well as moveBack and moveAt if it's a bidirectional or
random access range. These may be explicitly implemented, or may work
via the default behavior of the module level functions moveFront
and friends.
- The element type of R. R does not have to be a range. The
element type is determined as the type yielded by r.front for an
object r or type R. For example, ElementType!(T[]) is
T. If R is not a range, ElementType!R is void.
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 ranges, ElementEncodingType is the same as
ElementType.
template
hasSwappableElements(R)
- Returns true if R is a forward range and has swappable
elements. The following code should compile for any random-access
range.
R r;
static assert(isForwardRange!(R)); swap(r.front, r.front);
template
hasAssignableElements(R)
- Returns true if R is a forward range and has mutable
elements. The following code should compile for any random-access
range.
R r;
static assert(isForwardRange!R); auto e = r.front;
r.front = e;
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.
- Returns true if R has a length member that returns an
integral type. R does not have to be a range. Note that length is an optional primitive as no range must implement it. Some
ranges do not store their length explicitly, some cannot compute it
without actually exhausting the range (e.g. socket streams), and some
other ranges may be infinite.
Although narrow string types (char[], wchar[], and their
qualified derivatives) do define a length property, hasLength yields false for them. This is because a narrow
string's length does not reflect the number of characters, but instead
the number of encoding units, and as such is not useful with
range-oriented algorithms.
- Returns true if R is an infinite input range. An
infinite input range is an input range that has a statically-defined
enumerated member called empty that is always false,
for example:
struct MyInfiniteRange
{
enum bool empty = false;
...
}
- Returns true if R offers a slicing operator with
integral boundaries, that in turn returns an input range type. The
following code should compile for hasSlicing to be true:
R r;
auto s = r[1 .. 2];
static assert(isInputRange!(typeof(s)));
auto
walkLength(Range)(Range
range, const size_t
upTo = size_t.max);
- This is a best-effort implementation of length for any kind of
range.
If hasLength!(Range), simply returns range.length without
checking upTo.
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.
auto
retro(Range)(Range
r);
- 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.
Example:
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);
- Iterates range r with stride n. If the range is a
random-access range, moves by indexing into the range; otehrwise,
moves by successive calls to popFront. Applying stride twice to
the same range results in a stride that 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);
- 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);
- 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).
Example:
int[] a = [ 1, 2, 3, 4];
int[] b = [ 10, 20 ];
assert(equal(roundRobin(a, b), [1, 10, 2, 20, 3, 4]));
auto
radial(Range, I)(Range
r, I
startingIndex);
auto
radial(R)(R
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.
Example:
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)) && !(hasSlicing!(Unqual!(Range)) || is(Range T ==
Take!(T))));
Take!(R)
take(R)(R
input, size_t
n);
- 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.
Example:
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);
- 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.
If R has slicing, takeExactly simply returns a slice of range. Otherwise if R is an input range, the type of the result
is an input range with length. Finally, if R is a forward range
(including bidirectional), the type of the result is a forward range
with length.
auto
takeOne(R)(R
source);
auto
takeNone(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.
Sometimes an empty range with the same signature is needed. For such
ranges use takeNone!R(). For example:
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);
s = takeNone!(int[])();
assert(s.length == 0);
assert(s.empty);
In effect takeOne(r) is somewhat equivalent to take(r, 1) and
takeNone(r) is equivalent to take(r, 0), 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 and takeNone is a random-access
range with length regardless of R's capability (another feature
that distinguishes takeOne/takeNone from take).
R
drop(R)(R
range, size_t
n);
- Convenience function which calls popFrontN(range, n) and
returns range.
Examples:
assert(drop([0, 2, 1, 5, 0, 3], 3) == [5, 0, 3]);
assert(drop("hello world", 6) == "world");
assert(drop("hello world", 50).empty);
assert(equal(drop(take("hello world", 6), 3), "lo "));
size_t
popFrontN(Range)(ref Range
r, size_t
n);
- Eagerly advances r itself (not a copy) n times (by calling
r.popFront at most n times). The pass of r into popFrontN is by reference, so the original range is
affected. Completes in Ο(1) steps for ranges that support
slicing, and in Ο(n) time for all other ranges.
Example:
int[] a = [ 1, 2, 3, 4, 5 ];
a.popFrontN(2);
assert(a == [ 3, 4, 5 ]);
size_t
popBackN(Range)(ref Range
r, size_t
n);
- Eagerly reduces r itself (not a copy) n times from its right
side (by calling r.popBack n times). The pass of r into
popBackN is by reference, so the original range is
affected. Completes in Ο(1) steps for ranges that support
slicing, and in Ο(n) time for all other ranges.
Returns the actual number of elements popped.
Example:
int[] a = [ 1, 2, 3, 4, 5 ];
a.popBackN(2);
assert(a == [ 1, 2, 3 ]);
struct
Repeat(T);
Repeat!(T)
repeat(T)(T
value);
- Repeats one value forever.
Example:
enforce(equal(take(repeat(5), 4), [ 5, 5, 5, 5 ][]));
T
front();
T
back();
bool
empty;
void
popFront();
void
popBack();
Repeat!(T)
save();
T
opIndex(size_t);
- Range primitive implementations.
Take!(Repeat!(T))
repeat(T)(T
value, size_t
n);
- Repeats value exactly n times. Equivalent to take(repeat(value), n).
Take!(Repeat!(T))
replicate(T)(T
value, size_t
n);
- Equivalent to repeat(value, n). Scheduled for deprecation.
struct
Cycle(Range) if (isForwardRange!(Unqual!(Range)) && !isInfinite!(Unqual!(Range)));
template
Cycle(R) if (isInfinite!(R))
struct
Cycle(R) if (isStaticArray!(R));
Cycle!(R)
cycle(R)(R
input);
Cycle!(R)
cycle(R)(R
input, size_t
index);
Cycle!(R)
cycle(R)(R
input);
Cycle!(R)
cycle(R)(ref R
input, size_t
index = 0);
- 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 is specialized for statically-sized arrays,
mostly for performance reasons.
Example:
assert(equal(take(cycle([1, 2][]), 5), [ 1, 2, 1, 2, 1 ][]));
Tip:
This is a great way to implement simple circular buffers.
@property ref auto
front();
@property auto
front(ElementType!(R)
val);
bool
empty;
void
popFront();
auto
opIndexAssign(ElementType!(R)
val, size_t
n);
Cycle!(R)
save();
- Range primitive implementations.
struct
Zip(Ranges...) if (Ranges.length && allSatisfy!(isInputRange,staticMap!(Unqual,Ranges)));
auto
zip(R...)(R
ranges);
auto
zip(R...)(StoppingPolicy
sp, R
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:
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.
- Returns true if the range is at end. The test depends on the
stopping policy.
- Returns the current iterated element.
void
front(ElementType
v);
- Sets the front of all iterated ranges.
- Moves out the front.
- Returns the rightmost element.
- Moves out the back.
Returns the rightmost element.
void
back(ElementType
v);
- Returns the current iterated element.
Returns the rightmost element.
- Advances to the next element in all controlled ranges.
- Calls popBack for all controlled ranges.
- Returns the length of this range. Defined only if all ranges define
length.
- Returns the length of this range. Defined only if all ranges define
length.
Zip
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.
ElementType
moveAt(size_t
n);
- Destructively reads the nth element in the composite
range. Defined if all ranges offer random access.
- Dictates how iteration in a Zip should stop. By default stop at
the end of the shortest of all ranges.
- Stop when the shortest range is exhausted
- Stop when the longest range is exhausted
- Require that all ranges are equal
struct
Lockstep(Ranges...) if (Ranges.length > 1 && allSatisfy!(isInputRange,staticMap!(Unqual,Ranges)));
Lockstep!(Ranges)
lockstep(Ranges...)(Ranges
ranges);
Lockstep!(Ranges)
lockstep(Ranges...)(Ranges
ranges, StoppingPolicy
s);
- 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.
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.
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]);
foreach(index, a, b; lockstep(arr1, arr2)) {
writefln("Index %s: a = %s, b = %s", index, a, b);
}
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);
Sequence!(fun,Tuple!(State))
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.
Example:
auto odds = sequence!("a[0] + n * a[1]")(1, 2);
auto
iota(B, E, S)(B
begin, E
end, S
step);
auto
iota(B, E)(B
begin, E
end);
auto
iota(B, E)(B
begin, E
end);
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, then an empty range is returned. If begin != end and step == 0, an exception is thrown.
Throws:
Exception if step == 0
Example:
auto r = iota(0, 10, 1);
assert(equal(r, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9][]));
r = iota(0, 11, 3);
assert(equal(r, [0, 3, 6, 9][]));
assert(r[2] == 6);
auto rf = iota(0.0, 0.5, 0.1);
assert(approxEqual(rf, [0.0, 0.1, 0.2, 0.3, 0.4]));
- Options for the FrontTransversal and Transversal ranges
(below).
- When transversed, the elements of a range of ranges are assumed to
have different lengths (e.g. a jagged array).
- 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.
- 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.
Example:
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();
typeof(this)
save();
- Forward range primitives.
@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.
Example:
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();
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);
size_t
length();
alias
opDollar;
- 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]));
ind[0]++;
assert(ind[0] == 6);
assert(ind[5] == 6);
@property ref auto
front();
void
popFront();
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();
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
- Returns the source range.
- 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 (hasSlicing!(Source) && hasLength!(Source));
Chunks!(Source)
chunks(Source)(Source
source, size_t
chunkSize);
- This range iterates over fixed-sized chunks of size chunkSize of a
source range. Source must be an input range with slicing and length.
If source.length 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);
this(Source source, size_t chunkSize);
-
@property auto
front();
void
popFront();
bool
empty();
typeof(this)
save();
auto
opIndex(size_t
index);
typeof(this)
opSlice(size_t
lower, size_t
upper);
size_t
length();
@property auto
back();
void
popBack();
- Range primitives.
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).
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).
ElementType!(R)
moveAt(R, I)(R
r, I
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).
- 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:
class UsesRanges {
void useRange(InputRange range) {
}
}
auto squares = map!"a * a"(iota(10));
auto squaresWrapped = inputRangeObject(squares);
auto usesRanges = new UsesRanges;
usesRanges.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.
-
-
-
-
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.
-
interface
BidirectionalRange(E): ForwardRange!(E);
- Interface for a bidirectional range of type E.
BidirectionalRange!(E)
save();
-
-
-
-
interface
RandomAccessFinite(E): BidirectionalRange!(E);
- Interface for a finite random access range of type E.
RandomAccessFinite!(E)
save();
-
-
-
-
-
RandomAccessFinite!(E)
opSlice(size_t, size_t);
-
interface
RandomAccessInfinite(E): ForwardRange!(E);
- Interface for an infinite random access range of type E.
-
RandomAccessInfinite!(E)
save();
-
-
interface
InputAssignable(E): InputRange!(E);
- Adds assignable elements to InputRange.
-
interface
ForwardAssignable(E): InputAssignable!(E), ForwardRange!(E);
- Adds assignable elements to ForwardRange.
ForwardAssignable!(E)
save();
-
interface
BidirectionalAssignable(E): ForwardAssignable!(E), BidirectionalRange!(E);
- Adds assignable elements to BidirectionalRange.
BidirectionalAssignable!(E)
save();
-
-
interface
RandomFiniteAssignable(E): RandomAccessFinite!(E), BidirectionalAssignable!(E);
- Adds assignable elements to RandomAccessFinite.
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.
-
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);
- Convenience function for creating a InputRangeObject of the proper type.
template
outputRangeObject(E...)
- Convenience function for creating a 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 t1;
T2 t2;
fn(t1, t2);
fn(t2, t1);
- Policy used with the searching primitives lowerBound, upperBound, and equalRange of SortedRange below.
- 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.
- 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.
- 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.
- Similar to trot but starts backwards. Use it when
confident that the value is around the end of the range.
- 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 (isRandomAccessRange!(Range));
- Represents a sorted random-access range. In addition to the regular
range primitives, supports fast operations using binary search. To
obtain a SortedRange from an unsorted range r, use
std.algorithm.sort which sorts r in place and returns the
corresponding SortedRange. To construct a SortedRange
from a range r that is known to be already sorted, use
assumeSorted described below.
Example:
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 ]);
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.
Example:
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));
bool
empty();
@property auto
save();
@property auto
front();
void
popFront();
@property auto
back();
void
popBack();
auto
opIndex(size_t
i);
auto
opSlice(size_t
a, size_t
b);
size_t
length();
- Range primitives.
- Releases the controlled range and returns it.
auto
lowerBound(SearchPolicy sp = SearchPolicy.binarySearch, V)(V
value);
- This function uses binary 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);
- This function uses binary search 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. 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);
- 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);
- 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);
- 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.
- Deprecated alias for contains.
auto
assumeSorted(alias pred = "a < b", R)(R
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.
