Module std.range
This module defines the notion of a range. Ranges generalize the concept of
arrays, lists, or anything that involves sequential access. This abstraction
enables the same set of algorithms (see std
) to be used
with a vast variety of different concrete types. For example,
a linear search algorithm such as find
works not just for arrays, but for linkedlists, input files,
incoming network data, etc.
Guides
There are many articles available that can bolster understanding ranges:
 Ali Ã‡ehreli's tutorial on ranges for the basics of working with and creating rangebased code.
 Jonathan M. Davis Introduction to Ranges talk at DConf 2015 a vivid introduction from its core constructs to practical advice.
 The DLang Tour's chapter on ranges for an interactive introduction.
 H. S. Teoh's tutorial on component programming with ranges for a realworld showcase of the influence of rangebased programming on complex algorithms.
 Andrei Alexandrescu's article On Iteration for conceptual aspect of ranges and the motivation
Submodules
This module has two submodules:
The std
submodule
provides basic range functionality. It defines several templates for testing
whether a given object is a range, what kind of range it is, and provides
some common range operations.
The std
submodule
provides objectbased interfaces for working with ranges via runtime
polymorphism.
The remainder of this module provides a rich set of range creation and composition templates that let you construct new ranges out of existing ranges:
chain 
Concatenates several ranges into a single range. 
choose 
Chooses one of two ranges at runtime based on a boolean condition. 
chooseAmong 
Chooses one of several ranges at runtime based on an index. 
chunks 
Creates a range that returns fixedsize chunks of the original range. 
cycle 
Creates an infinite range that repeats the given forward range indefinitely. Good for implementing circular buffers. 
drop 
Creates the range that results from discarding the first n elements from the given range. 
dropBack 
Creates the range that results from discarding the last n elements from the given range. 
dropExactly 
Creates the range that results from discarding exactly n of the first elements from the given range. 
dropBackExactly 
Creates the range that results from discarding exactly n of the last elements from the given range. 
dropOne 
Creates the range that results from discarding the first element from the given range. 

Creates the range that results from discarding the last element from the given range. 
enumerate 
Iterates a range with an attached index variable. 
evenChunks 
Creates a range that returns a number of chunks of approximately equal length from the original range. 
frontTransversal 
Creates a range that iterates over the first elements of the given ranges. 
generate 
Creates a range by successive calls to a given function. This allows to create ranges as a single delegate. 
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. 
iota 
Creates a range consisting of numbers between a starting point and ending point, spaced apart by a given interval. 
lockstep 
Iterates n ranges in lockstep, for use in a foreach
loop. Similar to zip , except that lockstep is designed
especially for foreach loops.

nullSink 
An output range that discards the data it receives. 
only 
Creates a range that iterates over the given arguments. 
padLeft 
Pads a range to a specified length by adding a given element to the front of the range. Is lazy if the range has a known length. 
padRight 
Lazily pads a range to a specified length by adding a given element to the back of the range. 
radial 
Given a randomaccess range and a starting point, creates a range that alternately returns the next left and next right element to the starting point. 
recurrence 
Creates a forward range whose values are defined by a mathematical recurrence relation. 
refRange 
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. 
repeat 
Creates a range that consists of a single element repeated n times, or an infinite range repeating that element indefinitely. 
retro 
Iterates a bidirectional range backwards. 
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 roundrobin fashion. 
sequence 
Similar to recurrence , except that a randomaccess range is
created.


Creates a range that returns a fixedsize sliding window over the original range. Unlike chunks, it advances a configurable number of items at a time, not one chunk at a time. 
stride 
Iterates a range with stride n. 
tail 
Return a range advanced to within n elements of the end of
the given range.

take 
Creates a subrange 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.

takeNone 
Creates a randomaccess range consisting of zero elements of the given range. 
takeOne 
Creates a randomaccess range consisting of exactly the first element of the given range. 
tee 
Creates a range that wraps a given range, forwarding along its elements while also calling a provided function with each element. 
transposed 
Transposes a range of ranges. 
transversal 
Creates a range that iterates over the n'th elements of the given randomaccess ranges. 
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. 
Sortedness
Ranges whose elements are sorted afford better efficiency with certain
operations. For this, the assumeSorted
function can be used to
construct a SortedRange
from a presorted range. The sort
function also conveniently
returns a SortedRange
. SortedRange
objects provide some additional
range operations that take advantage of the fact that the range is sorted.
Functions
Name  Description 

assumeSorted(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 ). 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
almostsorted range is likely to pass it). To check for sortedness at
cost Ο(n ), use isSorted .

bitwise(range)

Bitwise adapter over an integral type range. Consumes the range elements bit by bit, from the least significant bit to the most significant bit. 
chain(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.

choose(condition, r1, r2)

Choose one of two ranges at runtime depending on a Boolean condition. 
chooseAmong(index, rs)

Choose one of multiple ranges at runtime. 
chunks(source, chunkSize)

This range iterates over fixedsized chunks of size chunkSize of a
source range. Source must be an input range. chunkSize must be
greater than zero.

cycle(input)


drop(range, n)

Convenience function which calls
popFrontN (range, 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(range, n)

Convenience function which calls
popFrontN (range, 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.

dropBackExactly(range, n)

Similar to drop and dropBack but they call
range and range
instead.

dropBackOne(range)

Convenience function which calls
range 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.

dropExactly(range, n)

Similar to drop and dropBack but they call
range and range
instead.

dropOne(range)

Convenience function which calls
range 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.

enumerate(range, start)

Iterate over range with an attached index variable.

evenChunks(source, chunkCount)

This range splits a source range into chunkCount chunks of
approximately equal length. Source must be a forward range with
known length.

frontTransversal(rr)

Given a range of ranges, iterate transversally through the first elements of each of the enclosed ranges. 
generate(fun)

Given callable (isCallable ) fun , create as a range
whose front is defined by successive calls to fun() .
This is especially useful to call function with global side effects (random
functions), or to create ranges expressed as a single delegate, rather than
an entire front /popFront /empty structure.
fun maybe be passed either a template alias parameter (existing
function, delegate, struct type defining static opCall ) or
a runtime value argument (delegate, function object).
The result range models an InputRange
(isInputRange ).
The resulting range will call fun() on construction, and every call to
popFront , and the cached value will be returned when front is called.

indexed(source, 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.

iota(begin, end, step)

Creates a range of values that span the given starting and stopping values. 
lockstep(ranges)

Iterate multiple ranges in lockstep using a foreach loop. In contrast to
zip it allows reference access to its elements. If only a single
range is passed in, the Lockstep aliases itself away. If the
ranges are of different lengths and s == StoppingPolicy
stop after the shortest range is empty. If the ranges are of different
lengths and s == StoppingPolicy , throw an
exception. s may not be StoppingPolicy , and passing this
will throw an exception.

nullSink()

An OutputRange that discards the data it receives. 
only(values)

Assemble values into a range that carries all its
elements insitu.

padLeft(r, e, n)

Extends the length of the input range r by padding out the start of the
range with the element e . The element e must be of a common type with
the element type of the range r as defined by CommonType .
If n is less than the length of of r , then r is returned unmodified.

padRight(r, e, n)

Extend the length of the input range r by padding out the end of the range
with the element e . The element e must be of a common type with the
element type of the range r as defined by CommonType .
If n is less than the length of of r , then the contents of r are
returned.

radial(r, startingIndex)

Iterates a randomaccess 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. 
recurrence(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 .

refRange(range)

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. 
repeat(value)

Create a range which repeats one value forever. 
repeat(value, n)

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

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

roundRobin(rs)

roundRobin(r1, r2, r3) yields r1 , then r2 ,
then r3 , 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).

sequence(args)

Sequence is similar to Recurrence except that iteration is
presented in the socalled closed form. This means that the n th element in the series is
computable directly from the initial values and n itself. This
implies that the interface offered by Sequence is a randomaccess
range, as opposed to the regular Recurrence , which only offers
forward iteration.

slide(source, windowSize, stepSize)

A fixedsized sliding window iteration
of size windowSize over a source range by a custom stepSize .

stride(r, n)

Iterates range r with stride n . If the range is a
randomaccess 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. It is an error for n to be 0.

tail(range, n)

Return a range advanced to within n elements of the end of
range .

take(input, n)

Lazily takes only up to n elements of a range. This is
particularly useful when using with infinite ranges.

takeExactly(range, 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 .

takeNone()

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.

takeNone(range)

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

takeOne(source)

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.

tee(inputRange, outputRange)

Implements a "tee" style pipe, wrapping an input range so that elements of the
range can be passed to a provided function or OutputRange as they are
iterated over. This is useful for printing out intermediate values in a long
chain of range code, performing some operation with sideeffects on each call
to front or popFront , or diverting the elements of a range into an
auxiliary OutputRange .

transposed(rr)

Given a range of ranges, returns a range of ranges where the i'th subrange contains the i'th elements of the original subranges. 
transversal(rr, n)

Given a range of ranges, iterate transversally through the
n th element of each of the enclosed ranges. This function
is similar to unzip in other languages.

zip(ranges)

Iterate several ranges in lockstep. The element type is a proxy tuple
that allows accessing the current element in the n th range by
using e[n] .

Structs
Name  Description 

Chunks

This range iterates over fixedsized chunks of size chunkSize of a
source range. Source must be an input range. chunkSize must be
greater than zero.

Cycle

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. That works for nonforward ranges too.
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.

Cycle


EvenChunks

This range splits a source range into chunkCount chunks of
approximately equal length. Source must be a forward range with
known length.

FrontTransversal

Given a range of ranges, iterate transversally through the first elements of each of the enclosed ranges. 
Indexed

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.

Lockstep

Iterate multiple ranges in lockstep using a foreach loop. In contrast to
zip it allows reference access to its elements. If only a single
range is passed in, the Lockstep aliases itself away. If the
ranges are of different lengths and s == StoppingPolicy
stop after the shortest range is empty. If the ranges are of different
lengths and s == StoppingPolicy , throw an
exception. s may not be StoppingPolicy , and passing this
will throw an exception.

NullSink

An OutputRange that discards the data it receives. 
Recurrence

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 .

RefRange

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

Create a range which repeats one value forever. 
Sequence

Sequence is similar to Recurrence except that iteration is
presented in the socalled closed form. This means that the n th element in the series is
computable directly from the initial values and n itself. This
implies that the interface offered by Sequence is a randomaccess
range, as opposed to the regular Recurrence , which only offers
forward iteration.

SortedRange

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

Take

Lazily takes only up to n elements of a range. This is
particularly useful when using with infinite ranges.

Transversal

Given a range of ranges, iterate transversally through the
n th element of each of the enclosed ranges. This function
is similar to unzip in other languages.

Zip

Iterate several ranges in lockstep. The element type is a proxy tuple
that allows accessing the current element in the n th range by
using e[n] .

Enums
Name  Description 

SearchPolicy

Policy used with the searching primitives lowerBound , upperBound , and equalRange of SortedRange below.

StoppingPolicy

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

TransverseOptions

Options for the FrontTransversal and Transversal ranges
(below).

Manifest constants
Name  Type  Description 

isTwoWayCompatible

Returns true if fn accepts variables of type T1 and T2 in any order.
The following code should compile:

Aliases
Name  Type  Description 

Cycle

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. That works for nonforward ranges too.
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.

Take

R

This template simply aliases itself to R and is useful for consistency in generic code. 
Authors
Andrei Alexandrescu, David Simcha, Jonathan M Davis, and Jack Stouffer. Credit for some of the ideas in building this module goes to Leonardo Maffi.