D Programming Language
Improve this page Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone. Page wiki View or edit the community-maintained wiki page associated with this page.

# std.range.primitives

This module is a submodule of std.range.
It provides basic range functionality by defining several templates for testing whether a given object is a range, and what kind of range it is:

isInputRange | Tests if something is an input range, defined to be something from which one can sequentially read data using the primitives front, popFront, and empty.
isOutputRange | Tests if something is an output range, defined to be something to which one can sequentially write data using the put primitive.
isForwardRange | Tests if something is a forward range, defined to be an input range with the additional capability that one can save one's current position with the save primitive, thus allowing one to iterate over the same range multiple times.
isBidirectionalRange | Tests if something is a bidirectional range, that is, a forward range that allows reverse traversal using the primitives back and popBack.
isRandomAccessRange | Tests if something is a random access range, which is a bidirectional range that also supports the array subscripting operation via the primitive opIndex.

It also provides number of templates that test for various range capabilities:

hasMobileElements | Tests if a given range's elements can be moved around using the primitives moveFront, moveBack, or moveAt.
ElementType | Returns the element type of a given range.
ElementEncodingType | Returns the encoding element type of a given range.
hasSwappableElements | Tests if a range is a forward range with swappable elements.
hasAssignableElements | Tests if a range is a forward range with mutable elements.
hasLvalueElements | Tests if a range is a forward range with elements that can be passed by reference and have their address taken.
hasLength | Tests if a given range has the length attribute.
isInfinite | Tests if a given range is an infinite range.
hasSlicing | Tests if a given range supports the array slicing operation R[x..y].

Finally, it includes some convenience functions for manipulating ranges:

popFrontN | Advances a given range by up to n elements.
popBackN | Advances a given bidirectional range from the right by up to n elements.
popFrontExactly | Advances a given range by up exactly n elements.
popBackExactly | Advances a given bidirectional range from the right by exactly n elements.
moveFront | Removes the front element of a range.
moveBack | Removes the back element of a bidirectional range.
moveAt | Removes the i'th element of a random-access range.
walkLength | Computes the length of any range in O(n) time.

Source: std/range/constraints.d

License:
Boost License 1.0.
Authors:
Andrei Alexandrescu, David Simcha, and Jonathan M Davis. Credit for some of the ideas in building this module goes to Leonardo Maffi.

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 popFront()
      auto h = r.front; // can get the front of the range of non-void type

  The semantics of an input range (not checkable during compilation) are assumed to be the following (r is an object of type R):

  - r.empty returns false iff there is more data available in the range.
  - r.front returns the current element in the range. It may return by value or by reference. Calling r.front is allowed only if calling r.empty has, or would have, returned false.
  - r.popFront advances to the next element in the range. Calling r.popFront is allowed only if calling r.empty has, or would have, returned false.
void put(R, E)(ref R r, E e);
  Outputs e to r. The exact effect is dependent upon the two types. Several cases are accepted, as described below. The code snippets are attempted in order, and the first to compile "wins" and gets evaluated.
  In this table "doPut" is a method that places e into r, using the correct primitive: r.put(e) if R defines put, r.front = e if r is an input range (followed by r.popFront()), or r(e) otherwise.

  Code Snippet | Scenario
  --- | ---
  r.doPut(e); | R specifically accepts an E.
  r.doPut([ e ]); | R specifically accepts an E[].
  r.putChar(e); | R accepts some form of string or character. put will transcode the character e accordingly.
  for (; !e.empty; e.popFront()) put(r, e.front); | Copying range E into R.

  Tip: put should not be used "UFCS-style", e.g. r.put(e). Doing this may call R.put directly, by-passing any transformation feature provided by Range.put. put(r, e) is prefered.

template isOutputRange(R, E)
  Returns true if R is an output range for elements of type E. An output range is defined functionally as a range that supports the operation put(r, e) as defined above.
  Examples:

      void myprint(in char[] s) { }
      static assert(isOutputRange!(typeof(&myprint), char));

      static assert(!isOutputRange!(char[], char));
      static assert( isOutputRange!(dchar[], wchar));
      static assert( isOutputRange!(dchar[], dchar));

template isForwardRange(R)
  Returns true if R is a forward range. A forward range is an input range r that can save "checkpoints" by saving r.save to another value of type R. Notable examples of input ranges that are not forward ranges are file/socket ranges; copying such a range will not save the position in the stream, and they most likely reuse an internal buffer as the entire stream does not sit in memory. Subsequently, advancing either the original or the copy will advance the stream, so the copies are not independent.
  The following code should compile for any forward range.

      static assert(isInputRange!R);
      R r1;
      static assert (is(typeof(r1.save) == R));

  Saving a range is not duplicating it; in the example above, r1 and r2 still refer to the same underlying data. They just navigate that data independently.

  The semantics of a forward range (not checkable during compilation) are the same as for an input range, with the additional requirement that backtracking must be possible by saving a copy of the range object with save and using it later.
  Examples:

      static assert(!isForwardRange!(int));
      static assert( isForwardRange!(int[]));
      static assert( isForwardRange!(inout(int)[]));

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

      alias R = int[];
      R r = [0,1];
      static assert(isForwardRange!R);           // is forward range
      r.popBack();                               // can invoke popBack
      auto t = r.back;                           // can get the back of the range
      auto w = r.front;
      static assert(is(typeof(t) == typeof(w))); // same type for front and back

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

      alias R = int[];

      // range is finite and bidirectional or infinite and forward.
      static assert(isBidirectionalRange!R ||
                    isForwardRange!R && isInfinite!R);

      R r = [0,1];
      auto e = r[1]; // can index
      static assert(is(typeof(e) == typeof(r.front))); // same type for indexed and front
      static assert(!isNarrowString!R); // narrow strings cannot be indexed as ranges
      static assert(hasLength!R || isInfinite!R); // must have length or be infinite

      // $ must work as it does with arrays if opIndex works with $
      static if(is(typeof(r[$])))
      {
          static assert(is(typeof(r.front) == typeof(r[$])));

          // $ - 1 doesn't make sense with infinite ranges but needs to work
          // with finite ones.
          static if(!isInfinite!R)
              static assert(is(typeof(r.front) == typeof(r[$ - 1])));
      }

template hasMobileElements(R)
  Returns true iff R is an input range that 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 following code should compile for any range with mobile elements.

      alias E = ElementType!R;
      R r;
      static assert(isInputRange!R);
      static assert(is(typeof(moveFront(r)) == E));
      static if (isBidirectionalRange!R)
          static assert(is(typeof(moveBack(r)) == E));
      static if (isRandomAccessRange!R)
          static assert(is(typeof(moveAt(r, 0)) == E));

  Examples:

      import std.algorithm : map;
      import std.range : iota, repeat;

      static struct HasPostblit
      {
          this(this) {}
      }

      auto nonMobile = map!"a"(repeat(HasPostblit.init));
      static assert(!hasMobileElements!(typeof(nonMobile)));
      static assert( hasMobileElements!(int[]));
      static assert( hasMobileElements!(inout(int)[]));
      static assert( hasMobileElements!(typeof(iota(1000))));

      static assert( hasMobileElements!( string));
      static assert( hasMobileElements!(dstring));
      static assert( hasMobileElements!( char[]));
      static assert( hasMobileElements!(dchar[]));

template ElementType(R)
  The element type of R. R does not have to be a range. The element type is determined as the type yielded by r.front for an object r of type R. For example, ElementType!(T[]) is T if T[] isn't a narrow string; if it is, the element type is dchar. If R doesn't have front, ElementType!R is void.
  Examples:

      import std.range : iota;

      // Standard arrays: returns the type of the elements of the array
      static assert(is(ElementType!(int[]) == int));

      // Accessing .front retrieves the decoded dchar
      static assert(is(ElementType!(char[])  == dchar)); // rvalue
      static assert(is(ElementType!(dchar[]) == dchar)); // lvalue

      // Ditto
      static assert(is(ElementType!(string) == dchar));
      static assert(is(ElementType!(dstring) == immutable(dchar)));

      // For ranges it gets the type of .front.
      auto range = iota(0, 10);
      static assert(is(ElementType!(typeof(range)) == int));

template ElementEncodingType(R)
  The encoding element type of R. For narrow strings (char[], wchar[] and their qualified variants including string and wstring), ElementEncodingType is the character type of the string. For all other types, ElementEncodingType is the same as ElementType.
  Examples:

      import std.range : iota;
      // internally the range stores the encoded type
      static assert(is(ElementEncodingType!(char[])  == char));

      static assert(is(ElementEncodingType!(wstring) == immutable(wchar)));

      static assert(is(ElementEncodingType!(byte[]) == byte));

      auto range = iota(0, 10);
      static assert(is(ElementEncodingType!(typeof(range)) == int));

template hasSwappableElements(R)
  Returns true if R is an input range and has swappable elements. The following code should compile for any range with swappable elements.

      R r;
      static assert(isInputRange!R);
      swap(r.front, r.front);
      static if (isBidirectionalRange!R) swap(r.back, r.front);
      static if (isRandomAccessRange!R) swap(r[], r.front);

  Examples:

      static assert(!hasSwappableElements!(const int[]));
      static assert(!hasSwappableElements!(const(int)[]));
      static assert(!hasSwappableElements!(inout(int)[]));
      static assert( hasSwappableElements!(int[]));

      static assert(!hasSwappableElements!( string));
      static assert(!hasSwappableElements!(dstring));
      static assert(!hasSwappableElements!( char[]));
      static assert( hasSwappableElements!(dchar[]));

template hasAssignableElements(R)
  Returns true if R is an input range and has mutable elements. The following code should compile for any range with assignable elements.

      R r;
      static assert(isInputRange!R);
      r.front = r.front;
      static if (isBidirectionalRange!R) r.back = r.front;
      static if (isRandomAccessRange!R) r[0] = r.front;

  Examples:

      static assert(!hasAssignableElements!(const int[]));
      static assert(!hasAssignableElements!(const(int)[]));
      static assert( hasAssignableElements!(int[]));
      static assert(!hasAssignableElements!(inout(int)[]));

      static assert(!hasAssignableElements!( string));
      static assert(!hasAssignableElements!(dstring));
      static assert(!hasAssignableElements!( char[]));
      static assert( hasAssignableElements!(dchar[]));

template hasLvalueElements(R)
  Tests whether the range R has lvalue elements. These are defined as elements that can be passed by reference and have their address taken. The following code should compile for any range with lvalue elements.

      void passByRef(ref ElementType!R stuff);
      ...
      static assert(isInputRange!R);
      passByRef(r.front);
      static if (isBidirectionalRange!R) passByRef(r.back);
      static if (isRandomAccessRange!R) passByRef(r[0]);

  Examples:

      import std.range : iota, chain;

      static assert( hasLvalueElements!(int[]));
      static assert( hasLvalueElements!(const(int)[]));
      static assert( hasLvalueElements!(inout(int)[]));
      static assert( hasLvalueElements!(immutable(int)[]));
      static assert(!hasLvalueElements!(typeof(iota(3))));

      static assert(!hasLvalueElements!( string));
      static assert( hasLvalueElements!(dstring));
      static assert(!hasLvalueElements!( char[]));
      static assert( hasLvalueElements!(dchar[]));

      auto c = chain([1, 2, 3], [4, 5, 6]);
      static assert( hasLvalueElements!(typeof(c)));

template hasLength(R)
  Returns true if R has a length member that returns an integral type. R does not have to be a range. Note that length is an optional primitive as no range must implement it. Some ranges do not store their length explicitly, some cannot compute it without actually exhausting the range (e.g. socket streams), and some other ranges may be infinite.
  Although narrow string types (char[], wchar[], and their qualified derivatives) do define a length property, hasLength yields false for them. This is because a narrow string's length does not reflect the number of characters, but instead the number of encoding units, and as such is not useful with range-oriented algorithms.
  Examples:

      static assert(!hasLength!(char[]));
      static assert( hasLength!(int[]));
      static assert( hasLength!(inout(int)[]));

      struct A { ulong length; }
      struct B { size_t length() { return 0; } }
      struct C { @property size_t length() { return 0; } }
      static assert( hasLength!(A));
      static assert(!hasLength!(B));
      static assert( hasLength!(C));

template isInfinite(R)
  Returns true if R is an infinite input range. An infinite input range is an input range that has a statically-defined enumerated member called empty that is always false, for example:

      struct MyInfiniteRange
      {
          enum bool empty = false;
          ...
      }

  Examples:

      import std.range : Repeat;
      static assert(!isInfinite!(int[]));
      static assert( isInfinite!(Repeat!(int)));

template hasSlicing(R)
  Returns true if R offers a slicing operator with integral boundaries that returns a forward range type.
  For finite ranges, the result of opSlice must be of the same type as the original range type. If the range defines opDollar, then it must support subtraction.

  For infinite ranges, when not using opDollar, the result of opSlice must be the result of take or takeExactly on the original range (they both return the same type for infinite ranges). However, when using opDollar, the result of opSlice must be that of the original range type.

  The following code must compile for hasSlicing to be true:

      R r = void;

      static if(isInfinite!R)
          typeof(take(r, 1)) s = r[1 .. 2];
      else
      {
          static assert(is(typeof(r[1 .. 2]) == R));
          R s = r[1 .. 2];
      }

      s = r[1 .. 2];

      static if(is(typeof(r[0 .. $])))
      {
          static assert(is(typeof(r[0 .. $]) == R));
          R t = r[0 .. $];
          t = r[0 .. $];

          static if(!isInfinite!R)
          {
              static assert(is(typeof(r[0 .. $ - 1]) == R));
              R u = r[0 .. $ - 1];
              u = r[0 .. $ - 1];
          }
      }

      static assert(isForwardRange!(typeof(r[1 .. 2])));
      static assert(hasLength!(typeof(r[1 .. 2])));

  Examples:

      import std.range : takeExactly;
      static assert( hasSlicing!(int[]));
      static assert( hasSlicing!(const(int)[]));
      static assert(!hasSlicing!(const int[]));
      static assert( hasSlicing!(inout(int)[]));
      static assert(!hasSlicing!(inout int []));
      static assert( hasSlicing!(immutable(int)[]));
      static assert(!hasSlicing!(immutable int[]));
      static assert(!hasSlicing!string);
      static assert( hasSlicing!dstring);

      enum rangeFuncs = "@property int front();" ~
                        "void popFront();" ~
                        "@property bool empty();" ~
                        "@property auto save() { return this; }" ~
                        "@property size_t length();";

      struct A { mixin(rangeFuncs); int opSlice(size_t, size_t); }
      struct B { mixin(rangeFuncs); B opSlice(size_t, size_t); }
      struct C { mixin(rangeFuncs); @disable this(); C opSlice(size_t, size_t); }
      struct D { mixin(rangeFuncs); int[] opSlice(size_t, size_t); }
      static assert(!hasSlicing!(A));
      static assert( hasSlicing!(B));
      static assert( hasSlicing!(C));
      static assert(!hasSlicing!(D));

      struct InfOnes
      {
          enum empty = false;
          void popFront() {}
          @property int front() { return 1; }
          @property InfOnes save() { return this; }
          auto opSlice(size_t i, size_t j) { return takeExactly(this, j - i); }
          auto opSlice(size_t i, Dollar d) { return this; }

          struct Dollar {}
          Dollar opDollar() const { return Dollar.init; }
      }

      static assert(hasSlicing!InfOnes);

auto walkLength(Range)(Range range) if (isInputRange!Range && !isInfinite!Range);
auto walkLength(Range)(Range range, const size_t upTo) if (isInputRange!Range);
  This is a best-effort implementation of length for any kind of range.
  If hasLength!Range, simply returns range.length without checking upTo (when specified).

  Otherwise, walks the range through its length and returns the number of elements seen. Performes Ο(n) evaluations of range.empty and range.popFront(), where n is the effective length of range.

  The upTo parameter is useful to "cut the losses" in case the interest is in seeing whether the range has at least some number of elements. If the parameter upTo is specified, stops if upTo steps have been taken and returns upTo.

  Infinite ranges are compatible, provided the parameter upTo is specified, in which case the implementation simply returns upTo.
size_t popFrontN(Range)(ref Range r, size_t n) if (isInputRange!Range);
size_t popBackN(Range)(ref Range r, size_t n) if (isBidirectionalRange!Range);
  Eagerly advances r itself (not a copy) up to n times (by calling r.popFront). popFrontN takes r by ref, so it mutates the original range. Completes in Ο(1) steps for ranges that support slicing and have length. Completes in Ο(n) time for all other ranges.
  Returns:
  How much r was actually advanced, which may be less than n if r did not have at least n elements.

  popBackN will behave the same but instead removes elements from the back of the (bidirectional) range instead of the front.
  Examples:

      int[] a = [ 1, 2, 3, 4, 5 ];
      a.popFrontN(2);
      assert(a == [ 3, 4, 5 ]);
      a.popFrontN(7);
      assert(a == [ ]);

  Examples:

      import std.algorithm : equal;
      import std.range : iota;
      auto LL = iota(1L, 7L);
      auto r = popFrontN(LL, 2);
      assert(equal(LL, [3L, 4L, 5L, 6L]));
      assert(r == 2);

  Examples:

      int[] a = [ 1, 2, 3, 4, 5 ];
      a.popBackN(2);
      assert(a == [ 1, 2, 3 ]);
      a.popBackN(7);
      assert(a == [ ]);

  Examples:

      import std.algorithm : equal;
      import std.range : iota;
      auto LL = iota(1L, 7L);
      auto r = popBackN(LL, 2);
      assert(equal(LL, [1L, 2L, 3L, 4L]));
      assert(r == 2);

void popFrontExactly(Range)(ref Range r, size_t n) if (isInputRange!Range);
void popBackExactly(Range)(ref Range r, size_t n) if (isBidirectionalRange!Range);
  Eagerly advances r itself (not a copy) exactly n times (by calling r.popFront). popFrontExactly takes r by ref, so it mutates the original range. Completes in Ο(1) steps for ranges that support slicing, and have either length or are infinite. Completes in Ο(n) time for all other ranges.

  Note: Unlike popFrontN, popFrontExactly will assume that the range holds at least n elements. This makes popFrontExactly faster than popFrontN, but it also means that if range does not contain at least n elements, it will attempt to call popFront on an empty range, which is undefined behavior. So, only use popFrontExactly when it is guaranteed that range holds at least n elements.

  popBackExactly will behave the same but instead removes elements from the back of the (bidirectional) range instead of the front.
  Examples:

      import std.algorithm : filterBidirectional, equal;

      auto a = [1, 2, 3];
      a.popFrontExactly(1);
      assert(a == [2, 3]);
      a.popBackExactly(1);
      assert(a == [2]);

      string s = "日本語";
      s.popFrontExactly(1);
      assert(s == "本語");
      s.popBackExactly(1);
      assert(s == "本");

      auto bd = filterBidirectional!"true"([1, 2, 3]);
      bd.popFrontExactly(1);
      assert(bd.equal([2, 3]));
      bd.popBackExactly(1);
      assert(bd.equal([2]));

ElementType!R moveFront(R)(R r);
  Moves the front of r out and returns it. Leaves r.front in a destroyable state that does not allocate any resources (usually equal to its .init value).
  Examples:

      auto a = [ 1, 2, 3 ];
      assert(moveFront(a) == 1);

      // define a perfunctory input range
      struct InputRange
      {
          @property bool empty() { return false; }
          @property int front() { return 42; }
          void popFront() {}
          int moveFront() { return 43; }
      }
      InputRange r;
      assert(moveFront(r) == 43);

ElementType!R moveBack(R)(R r);
  Moves the back of r out and returns it. Leaves r.back in a destroyable state that does not allocate any resources (usually equal to its .init value).
  Examples:

      struct TestRange
      {
          int payload = 5;
          @property bool empty() { return false; }
          @property TestRange save() { return this; }
          @property ref int front() return { return payload; }
          @property ref int back() return { return payload; }
          void popFront() { }
          void popBack() { }
      }
      static assert(isBidirectionalRange!TestRange);
      TestRange r;
      auto x = moveBack(r);
      assert(x == 5);

ElementType!R moveAt(R, I)(R r, I i) if (isIntegral!I);
  Moves element at index i of r out and returns it. Leaves r.front in a destroyable state that does not allocate any resources (usually equal to its .init value).
  Examples:

      auto a = [1,2,3,4];
      foreach(idx, it; a)
      {
          assert(it == moveAt(a, idx));
      }

pure nothrow @property @safe bool empty(T)(in T[] a);
  Implements the range interface primitive empty for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.empty is equivalent to empty(array).
  Examples:

      auto a = [ 1, 2, 3 ];
      assert(!a.empty);
      assert(a[3 .. $].empty);

pure nothrow @property @safe T[] save(T)(T[] a);
  Implements the range interface primitive save for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.save is equivalent to save(array). The function does not duplicate the content of the array, it simply returns its argument.
  Examples:

      auto a = [ 1, 2, 3 ];
      auto b = a.save;
      assert(b is a);

pure nothrow @safe void popFront(T)(ref T[] a) if (!isNarrowString!(T[]) && !is(T[] == void[]));
  Implements the range interface primitive popFront for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.popFront is equivalent to popFront(array). For narrow strings, popFront automatically advances to the next code point.
  Examples:

      auto a = [ 1, 2, 3 ];
      a.popFront();
      assert(a == [ 2, 3 ]);

pure nothrow @safe void popBack(T)(ref T[] a) if (!isNarrowString!(T[]) && !is(T[] == void[]));
  Implements the range interface primitive popBack for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.popBack is equivalent to popBack(array). For narrow strings, popFront automatically eliminates the last code point.
  Examples:

      auto a = [ 1, 2, 3 ];
      a.popBack();
      assert(a == [ 1, 2 ]);

pure nothrow @property ref @safe T front(T)(T[] a) if (!isNarrowString!(T[]) && !is(T[] == void[]));
  Implements the range interface primitive front for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.front is equivalent to front(array). For narrow strings, front automatically returns the first code point as a dchar.
  Examples:

      int[] a = [ 1, 2, 3 ];
      assert(a.front == 1);

pure nothrow @property ref @safe T back(T)(T[] a) if (!isNarrowString!(T[]));
  Implements the range interface primitive back for built-in arrays. Due to the fact that nonmember functions can be called with the first argument using the dot notation, array.back is equivalent to back(array). For narrow strings, back automatically returns the last code point as a dchar.
  Examples:

      int[] a = [ 1, 2, 3 ];
      assert(a.back == 3);
      a.back += 4;
      assert(a.back == 7);

Copyright by authors 2008-. | Page generated by Ddoc on Sat Apr 25 12:22:53 2015