D Programming Language 2.0

- Comments
- D
- Search
- Home

Last update Thu Sep 16 11:26:00 2010

# std.range

This module defines a few useful range incarnations. Credit for some of the ideas in building this module goes to Leonardo Maffi.

Source:
std/range.d

License:
Boost License 1.0.

Authors:
Andrei Alexandrescu, David Simcha

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

void put(R, E)(ref R r, E e);
  Outputs e to r. The exact effect is dependent upon the two types. which must be an output range. 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 can be 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 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.

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

template isRandomAccessRange(R)
  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.

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.

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 or type R. For example, ElementType!(T[]) is T.

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));  // range is forward
      swap(r.front, r.front);              // can swap elements of the range

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));  // range is forward
      auto e = r.front;
      r.front = e;                         // can assign elements of the range

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.

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.

template isInfinite(Range)
  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;
          ...
      }

template hasSlicing(Range)
  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)));

size_t walkLength(Range)(Range range, 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.

struct Retro(R) if (isBidirectionalRange!(R) && !isRetro!(R));
Retro!(R) retro(R)(R input);
  Iterates a bidirectional range backwards.

  Example:

      int[] a = [ 1, 2, 3, 4, 5 ];
      assert(equal(retro(a), [ 5, 4, 3, 2, 1 ][]));

  bool empty();
    Forwards to input.empty.

  Retro save();
    Returns a copy of this.

  void popFront();
    Forwards to input.popBack.

  ElementType!(R) moveFront();
    Forwards to moveBack(input)

  void popBack();
    Forwards to input.popFront.

  ElementType!(R) moveBack();
    Forwards to moveFront(input).

  front(ElementType!(R) val);
    Support for assignment.

  back(ElementType!(R) val);
    Support for assignment.

  opIndex(size_t n);
    Forwards to input[input.length - n + 1]. Defined only if R is a random access range and if R defines R.length.

  void opIndexAssign(ElementType!(R) val, size_t n);
    Forwards to input[input.length - n + 1]. Defined only if R is a random access range and if R defines R.length.

  ElementType!(R) moveAt(size_t index);
    Forwards to input[input.length - n + 1]. Defined only if R is a random access range and if R defines R.length.

  typeof(this) opSlice(size_t a, size_t b);
    Forwards to input[input.length - n + 1]. Defined only if R is a random access range and if R defines R.length.

  size_t length();
    Range primitive operation that returns the length of the range. Forwards to input.length and is defined only if hasLength!(R).

struct Stride(R) if (isInputRange!(R));
Stride!(R) stride(R)(R input, 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.

  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.

  Stride save();
    Returns this.

  bool empty;
    Forwards to input.empty.

  ElementType!(R) moveFront();
    Forwards to moveFront(input).

  void popFront();
    @@@

  void popBack();
    Forwards to input.popFront.

  back();
    Forwards to input.back after getting rid of any slack items.

  ElementType!(R) moveBack();
    Forwards to moveBack(input).

    Forwards to input.back after getting rid of any slack items.

  back(ElementType!(R) val);
    Forwards to input.back after getting rid of any slack items.

  opIndex(size_t n);
    Forwards to input[input.length - n + 1]. Defined only if R is a random access range and if R defines R.length.

  ElementType!(R) moveAt(size_t n);
    Forwards to moveAt(input, n).

    Forwards to input[input.length - n + 1]. Defined only if R is a random access range and if R defines R.length.

  void opIndexAssign(ElementType!(R) val, size_t n);
    Forwards to input[input.length - n + 1]. Defined only if R is a random access range and if R defines R.length.

  typeof(this) opSlice(size_t lower, size_t upper);
    Support slicing of the Stride, if the underlying range supports this.

  size_t length();
    Range primitive operation that returns the length of the range. Forwards to input.length and is defined only if hasLength!(R).

template Chain(R...) if (allSatisfy!(isInputRange,R))
Chain!(R) chain(R...)(R input);
  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][]));

struct Radial(R) if (isRandomAccessRange!(R) && hasLength!(R));
Radial!(R) radial(R)(R r);
Radial!(R) radial(R)(R r, size_t startingIndex);
  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 ][]));

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

  Radial opSlice();
    Returns this.

  bool empty();
    Range primitive operation that returns true iff there are no more elements to be iterated.

  void popFront();
    Range primitive operation that advances the range to its next element.

  ElementType!(R) moveFront();

  front(ElementType!(R) val);

  typeof(this) save();

struct Take(R) if (isInputRange!(R) && (!hasSlicing!(R) || isNarrowString!(R)));
Take!(R) take(R)(R input, size_t n);
Take!(R) take(R)(R input, size_t n);
  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 ][]));

size_t popFrontN(Range)(ref Range r, size_t n);
  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 ]);

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.

  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(uint);
    Range primitive implementations.

Take!(Repeat!(T)) replicate(T)(T value, size_t n);
  Replicates value exactly n times. Equivalent to take(repeat(value), n).

struct Cycle(R) if (isForwardRange!(R) && !isInfinite!(R));
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.

  front(ElementType!(R) val);
  bool empty;
  void popFront();
  opIndexAssign(ElementType!(R) val, size_t n);
  Cycle!(R) save();
    Ditto

struct Zip(R...) if (R.length && allSatisfy!(isInputRange,R));
Zip!(R) zip(R...)(R ranges);
Zip!(R) 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.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.

  bool empty;
    Returns true if the range is at end. The test depends on the stopping policy.

  ElementType front();
    Returns the current iterated element.

  void front(ElementType v);
    Sets the front of all iterated ranges.

  ElementType moveFront();
    Moves out the front.

  ElementType back();
    Returns the rightmost element.

  ElementType moveBack();
    Moves out the back.

    Returns the rightmost element.

  void back(ElementType v);
    Returns the current iterated element.

    Returns the rightmost element.

  void popFront();
    Advances to the popFront element in all controlled ranges.

  void popBack();
    Calls popBack for all controlled ranges.

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

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

      // Lockstep also supports iterating with an index variable:
      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 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); }

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:

      // a[0] = 1, a[1] = 2, a[n] = a[0] + n * a[1]
      auto odds = sequence!("a[0] + n * a[1]")(1, 2);

Iota!(CommonType!(Unqual!(B),Unqual!(E)),S) iota(B, E, S)(B begin, E end, S step);
Iota!(CommonType!(Unqual!(B),Unqual!(E)),uint) iota(B, E)(B begin, E end);
Iota!(Unqual!(E),uint) iota(E)(E end);
struct Iota(N,S) if ((isIntegral!(N) || isPointer!(N)) && isIntegral!(S));
struct Iota(N,S) if (isFloatingPoint!(N) && isNumeric!(S));
  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(approxEqual(rf, [0.0, 0.1, 0.2, 0.3, 0.4]));

enum TransverseOptions;
  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(RangeOfRanges,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(equals(ror, [ 1, 3 ][]));

  this(RangeOfRanges input);
    Construction from an input.

  bool empty;
  ElementType moveFront();
  void popFront();
  typeof(this) save();
  void popBack();
  ElementType moveBack();
  ElementType moveAt(size_t n);
  void opIndexAssign(ElementType val, size_t n);
    Forward range primitives.

  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(RangeOfRanges,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(equals(ror, [ 2, 4 ][]));

  this(RangeOfRanges input, size_t n);
    Construction from an input and an index.

  bool empty;
  E moveFront();
  front(E val);
  void popFront();
  typeof(this) save();
  void popBack();
  E moveBack();
  back(E val);
  E moveAt(size_t n);
  void opIndexAssign(E val, size_t n);
    Forward range primitives.

  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.

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)(R r, size_t 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).

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:

       class UsesRanges {
           void useRange(InputRange range) {
               // Function body.
           }
       }

       // Create a range type.
       auto squares = map!"a * a"(iota(10));

       // Wrap it in an interface.
       auto squaresWrapped = inputRangeObject(squares);

       // Use it.
       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.

  E front();

  E moveFront();

  void popFront();

  bool empty();

  int opApply(int delegate(ref E));
  int opApply(int delegate(ref size_t, ref E));
    foreach iteration uses opApply, since one delegate call per loop iteration is faster than three virtual function calls.

    BUGS:
    If a ref variable is provided as the loop variable, changes made to the loop variable will not be propagated to the underlying range. If the address of the loop variable is escaped, undefined behavior will result. This is related to DMD bug 2443.

interface ForwardRange(E): InputRange!(E);
  Interface for a forward range of type E.

  ForwardRange!(E) save();

interface BidirectionalRange(E): ForwardRange!(E);
  Interface for a bidirectional range of type E.

  BidirectionalRange!(E) save();

  E back();

  E moveBack();

  void popBack();

interface RandomAccessFinite(E): BidirectionalRange!(E);
  Interface for a finite random access range of type E.

  RandomAccessFinite!(E) save();

  E opIndex(size_t);

  E moveAt(size_t);

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

  RandomAccessInfinite!(E) save();

  E opIndex(size_t);

interface InputAssignable(E): InputRange!(E);
  Adds assignable elements to InputRange.

  void front(E newVal);

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

  void back(E newVal);

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.

  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!(R))
  Returns the interface type that best matches R.

template InputRangeObject(R) if (isInputRange!(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)));

  template outputRangeObject(R)

    OutputRangeObject!(R,E) outputRangeObject(R range);

struct SortedRange(R,alias pred = "a < b") if (isRandomAccessRange!(R));
  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.canFind(3));
      assert(!r.canFind(32));
      auto r1 = sort!"a > b"(a);
      assert(r1.canFind(3));
      assert(!r1.canFind(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.canFind(42));
      swap(a[2], a[5]); // illegal to break sortedness of original range
      assert(!r.canFind(42)); // passes although it shouldn't

  bool empty();
  typeof(this) save();
  ElementType!(R) front();
  void popFront();
  ElementType!(R) back();
  void popBack();
  ElementType!(R) opIndex(size_t i);
  typeof(this) opSlice(size_t a, size_t b);
  size_t length();
    Range primitives.

  R release();
    Releases the controlled range and returns it.

  template lowerBound(V)
    This function assumes that range r consists of a subrange r1 of elements e1 for which pred(e1, value) is true, followed by a subrange r2 of elements e2 for which pred(e2, value) is false. Using this assumption, lowerBound uses binary search to find r1, i.e. the left subrange on which pred is always true. Performs Ο(log(r.length)) evaluations of pred. The precondition is not verified because it would deteriorate function's complexity. It is possible that the types of value and ElementType!(Range) are different, if the predicate accepts them. See also STL's lower_bound.

    Precondition:
    find!(not!(pred))(r, value).length + find!(pred)(retro(r), value).length == r.length

    Example:

           auto a = assumeSorted([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]);
           auto p = a.lowerBound(4);
           assert(p.release == [ 0, 1, 2, 3 ]);

    typeof(this) lowerBound(V value);
      This function assumes that range r consists of a subrange r1 of elements e1 for which pred(e1, value) is true, followed by a subrange r2 of elements e2 for which pred(e2, value) is false. Using this assumption, lowerBound uses binary search to find r1, i.e. the left subrange on which pred is always true. Performs Ο(log(r.length)) evaluations of pred. The precondition is not verified because it would deteriorate function's complexity. It is possible that the types of value and ElementType!(Range) are different, if the predicate accepts them. See also STL's lower_bound.

      Precondition:
      find!(not!(pred))(r, value).length + find!(pred)(retro(r), value).length == r.length

      Example:

             auto a = assumeSorted([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]);
             auto p = a.lowerBound(4);
             assert(p.release == [ 0, 1, 2, 3 ]);

  template upperBound(V)
    This function assumes that range r consists of a subrange r1 of elements e1 for which pred(value, e1) is false, followed by a subrange r2 of elements e2 for which pred(value, e2) is true. (Note the differences in subrange definition and argument order for pred compared to lowerBound.) Using this assumption, upperBound uses binary search to find r2, i.e. the right subrange on which pred is always true. Performs Ο(log(r.length)) evaluations of pred. The precondition is not verified because it would deteriorate function's complexity. It is possible that the types of value and ElementType!(Range) are different, if the predicate accepts them. See also STL's upper_bound.

    Precondition:
    find!(pred)(r, value).length + find!(not!(pred))(retro(r), value).length == r.length

    Example:

           auto a = assumeSorted([ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]);
           auto p = a.upperBound(3);
           assert(p == [4, 4, 5, 6]);

    typeof(this) upperBound(V value);
      This function assumes that range r consists of a subrange r1 of elements e1 for which pred(value, e1) is false, followed by a subrange r2 of elements e2 for which pred(value, e2) is true. (Note the differences in subrange definition and argument order for pred compared to lowerBound.) Using this assumption, upperBound uses binary search to find r2, i.e. the right subrange on which pred is always true. Performs Ο(log(r.length)) evaluations of pred. The precondition is not verified because it would deteriorate function's complexity. It is possible that the types of value and ElementType!(Range) are different, if the predicate accepts them. See also STL's upper_bound.

      Precondition:
      find!(pred)(r, value).length + find!(not!(pred))(retro(r), value).length == r.length

      Example:

             auto a = assumeSorted([ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]);
             auto p = a.upperBound(3);
             assert(p == [4, 4, 5, 6]);

  template equalRange(V)
    Assuming a range satisfying both preconditions for lowerBound!(pred)(r, value) and upperBound!(pred)(r, value), the call equalRange!(pred)(r, v) returns the subrange containing all elements e for which both pred(e, value) and pred(value, e) evaluate to false. Performs Ο(log(r.length)) evaluations of pred. See also STL's equal_range.

    Precondition:
    find!(not!(pred))(r, value).length + find!(pred)(retro(r), value).length == r.length && find!(pred)(r, value).length + find!(not!(pred))(retro(r), value).length == r.length

    Example:

           auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
           auto r = equalRange(a, 3);
           assert(r == [ 3, 3, 3 ]);

    typeof(this) equalRange(V value);
      Assuming a range satisfying both preconditions for lowerBound!(pred)(r, value) and upperBound!(pred)(r, value), the call equalRange!(pred)(r, v) returns the subrange containing all elements e for which both pred(e, value) and pred(value, e) evaluate to false. Performs Ο(log(r.length)) evaluations of pred. See also STL's equal_range.

      Precondition:
      find!(not!(pred))(r, value).length + find!(pred)(retro(r), value).length == r.length && find!(pred)(r, value).length + find!(not!(pred))(retro(r), value).length == r.length

      Example:

             auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
             auto r = equalRange(a, 3);
             assert(r == [ 3, 3, 3 ]);

  template canFind(V)
    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.

    bool canFind(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.

Copyright Andrei Alexandrescu 2008-. | Page generated by Ddoc.