std.range
This module defines a few useful range incarnations. Credit for ideas in building this module go to Leonardo Maffi. License:Boost License 1.0. Authors:
Andrei Alexandrescu Copyright Andrei Alexandrescu 2008 - 2009. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at ) http:
//www.boost.org/LICENSE_1_0.txt
- Returns true if R is an input range. An input range must
define the primitives empty, popFront, and front. The
following code should compile for any input range.
R r; // can define a range object if (r.empty) {} // can test for empty r.popFront; // can invoke next auto h = r.front; // can get the front of the range
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 popFront element in the range. Calling r.popFront is allowed only if calling r.empty has, or would have, returned false.
- Returns true if R is an output range. An output range must
define the primitive put that accepts an object of type E. The following code should compile for any output range.
R r; // can define a range object E e; r.put(e); // can write an element to the range
The semantics of an output range (not checkable during compilation) are assumed to be the following (r is an object of type R):- r.put(e) puts e in the range (in a range-dependent manner) and advances to the popFront position in the range. Successive calls to r.put add elements to the range. put may throw to signal failure.
- Returns true if R is a forward range. A forward range is an
input range that can save "checkpoints" by simply copying it to
another value of the same type. 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; // can copy a range to another
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. - 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)); // range is an input range r.popBack; // can invoke popBack auto t = r.back; // can get the back of the range
The semantics of a bidirectional range (not checkable during compilation) are assumed to be the following (r is an object of type R):- r.back returns (possibly a reference to) the last element in the range. Calling r.back is allowed only if calling r.empty has, or would have, returned false.
- Returns true if R is a random-access range. A random-access
range is a forward range that also offers the primitive opIndex, OR an infinite input range that offers opIndex. The
following code should compile for any random-access range.
R r; static assert(isForwardRange!(R)); // range is forward static assert(isBidirectionalRange!(R) || isInfinite!(R)); // range is bidirectional or infinite auto e = r[1]; // can index
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.
- 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.
- 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)); // range is forward swap(r.front, r.front); // can swap elements of the range
- Returns true if R is a forward range and has mutable
elements. The following code should compile for any random-access
range.
R r; static assert(isForwardRange!(R)); // range is forward auto e = r.front; r.front = e; // can assign elements of the range
- 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.
- Returns true if Range 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 InfiniteRange { enum bool empty = false; ... }
- Returns true if Range 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:
Range r; auto s = r[1 .. 2]; static assert(isInputRange!(typeof(s)));
- 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.
- Iterates a bidirectional range backwards.
Example:
int[] a = [ 1, 2, 3, 4, 5 ]; assert(equal(retro(a) == [ 5, 4, 3, 2, 1 ][]));
- Forwards to input.empty.
- Returns a copy of this.
- Forwards to input.popBack.
- Forwards to input.popFront.
- Forwards to input[input.length - n + 1]. Defined only if R is a random access range and if R defines R.length.
- Range primitive operation that returns the length of the range. Forwards to input.length and is defined only if hasLength!(R).
- 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.
Example:
int[] a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]; assert(equal(stride(a, 3) == [ 1, 4, 7, 10 ][]));
- this(R input, size_t n);
- Initializes the stride.
- Returns this.
- Forwards to input.empty.
- @@@
- Forwards to input.popFront.
- Forwards to input.front.
- Forwards to input.back after getting rid of any slack items.
- Forwards to input[input.length - n + 1]. Defined only if R is a random access range and if R defines R.length.
- Range primitive operation that returns the length of the range. Forwards to input.length and is defined only if hasLength!(R).
- 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][]));
- 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, 2, 4, 1, 5 ][])); a = [ 1, 2, 3, 4 ]; assert(equal(radial(a) == [ 2, 3, 1, 4 ][]));
- this(R input);
- Takes a range and starts iterating from its median point. Ranges with an even length start iterating from the element to the left of the median. The second iterated element, if any, is the one to the right of the first iterated element. A convenient way to use this constructor is by calling the helper function radial(input).
- this(R input, size_t startingPoint);
- Takes a range and starts iterating from input[mid]. The second iterated element, if any, is the one to the right of the first iterated element. If there is no element to the right of input[mid], iteration continues downwards with input[mid - 1] etc. A convenient way to use this constructor is by calling the helper function radial(input, startingPoint).
- Returns this.
- Range primitive operation that returns true iff there are no more elements to be iterated.
- Range primitive operation that advances the range to its next element.
- Range primitive operation that returns the currently iterated element. Throws if the range is empty.
- Lazily takes only up to n elements of a range. This is
particulary 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 ][]));
- Eagerly advances r itself (not a copy) n times (by calling
r.popFront 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 ]);
- 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.
Example:
int[] a = [ 1, 2, 3, 4, 5 ]; a.popBackN(2); assert(a == [ 1, 2, 3 ]);
- Repeats one value forever. Example:
enforce(equal(take(repeat(5), 4), [ 5, 5, 5, 5 ][]));
- Range primitive implementations.
- Replicates value exactly n times. Equivalent to take(repeat(value), n).
- Repeats the given forward range ad infinitum. If the original range is
infinite (fact that would make Cycle the identity application),
Cycle detects that and aliases itself to the range type
itself. If the original range has random access, Cycle offers
random access and also offers a constructor taking an initial position
index. Cycle 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. - 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.at!(n).
Example:
int[] a = [ 1, 2, 3 ]; string[] b = [ "a", "b", "c" ]; // prints 1:a 2:b 3:c foreach (e; zip(a, b)) { write(e.at!(0), ':', e.at!(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.at!(0) > b.at!(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 std.range.zip function.
- Returns true if the range is at end. The test depends on the stopping policy.
- Returns a proxy for the current iterated element.
- Returns a proxy for the rightmost element.
- Advances to the popFront 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 a slice of the range. Defined only if all range define slicing.
- Proxy type returned by the access function.
- Returns the current element in the ith range.
- Returns the current element in the ith range.
- Returns whether the current element exists in the ith range. This
function returns false if e.g. one of the ranges has exhausted in
the StoppingPolicy.longest policy.
- Returns whether the current element exists in the ith range. This function returns false if e.g. one of the ranges has exhausted in the StoppingPolicy.longest policy.
- Returns 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.
- Creates a mathematical sequence given the initial values and a
recurrence function that computes the popFront 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 popFront 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 class itself takes care of
managing the recurrence's state and shifting it appropriately.
Example:
// a[0] = 1, a[1] = 1, and compute a[n+1] = a[n-1] + a[n] auto fib = recurrence!("a[n-1] + a[n-2]")(1, 1); // print the first 10 Fibonacci numbers foreach (e; take(fib, 10)) { writeln(e); } // print the first 10 factorials foreach (e; take(recurrence!("a[n-1] * n")(1), 10)) { writeln(e); }
- 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:
// a[0] = 1, a[1] = 2, a[n] = a[0] + n * a[1] auto odds = sequence!("a[0] + n * a[1]")(1, 2);
- Returns a range that goes through the numbers begin, begin +
step, begin + 2 * step, ..., up to and excluding end. The range offered is a random access range. The two-arguments
version has step = 1.
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(equal(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.
- 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(equals(ror, [ 1, 3 ][]));
- this(RangeOfRanges input);
- Construction from an input.
- Forward range primitives.
- Bidirectional primitives. They are offered if isBidirectionalRange!RangeOfRanges.
- Random-access primitive. It is offered if isRandomAccessRange!RangeOfRanges && (opt == TransverseOptions.assumeNotJagged || opt == TransverseOptions.enforceNotJagged).
- 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(equals(ror, [ 2, 4 ][]));
- this(RangeOfRanges input, size_t n);
- Construction from an input and an index.
- Forward range primitives.
- Bidirectional primitives. They are offered if isBidirectionalRange!RangeOfRanges.
- Random-access primitive. It is offered if isRandomAccessRange!RangeOfRanges && (opt == TransverseOptions.assumeNotJagged || opt == TransverseOptions.enforceNotJagged).
- Moves the front of r out and returns it. Leaves r.front in a destroyable state that does not allocate any resources (usually equal to its .init value).
- Moves the front of r out and returns it. Leaves r.front in a destroyable state that does not allocate any resources (usually equal to its .init value).
- Moves 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).