In looking for inspiration to define the new interface, it's tempting to turn to other languages such as Java and C++. On the one hand, we want to iterate the container elements, which brings to mind the iterator implementations in other languages. However, we also want to do a bit more than that, as demonstrated by the following chain of function calls:

container.getType.algorithm1.algorithm2.algorithm3.toContainer();

Conceptually, the instance returned by getType will be consumed by algorithm1, meaning that, inside the function, it will be iterated to the point where it can produce no more elements. But then, algorithm1 should return an instance of the same type, which can iterate over the same container, and which will in turn be consumed by algorithm2. The process repeats for algorithm3. This implies that instances of the new type should be able to be instantiated independent of the container they represent.

Moreover, given that D supports slicing, the role of getType could easily be played by opSlice. Iteration need not always begin with the first element of a container and end with the last; any range of elements should be supported. In fact, there's really no reason for an actual container instance to exist at all in some cases. Imagine a random number generator. We should be able to plug one into the preceding function chain just by eliminating the container and replacing getType with the generator instance. As long as it conforms to the interface we define, it doesn't matter that there is no concrete container instance backing it.

The short version of it is, we don't want to think solely in terms of iteration, as it's only a part of the problem we're trying to solve. We want a type that not only supports iteration, of either an actual container or a conceptual one, but one that also can be instantiated independently of any container, knows both its beginning and ending boundaries, and, in order to allow for lazy algorithms, can be used to generate new instances that know how to iterate over the same elements.

Considering these requirements, Iterator isn't a good fit as a name for the new type. Rather than naming it for what it does or how it's used, it seems more appropriate to name it for what it represents. There's more than one possible name that fits, but we'll go with Range (as in, a range of elements). That's it for the requirements and the type name. Now, let's move on to the API.

For any algorithm that needs to sequentially iterate a range of elements from beginning to end, three basic primitives are required:

Based on these requirements, there are several ways to approach naming the three primitives, but we'll just take a shortcut and use the same names used in D. The first primitive will be called empty and can be implemented either as a member function that returns bool or as a bool member variable. The second primitive will be called front, which again could be a member function or variable and which returns T, the element type of the range. The third primitive can only be a member function and will be called popFront, as conceptually it is removing the current front element from the sequence to ready the next element.

Wrapping an array in the Range interface is quite easy. It looks like this:

auto range(T)(T[] array) {
  struct ArrayRange(T) {
    private T[] _array;
    bool empty() {
      return _array.length == 0;
    }
    ref T front() {
      return _array[0];
    }
    void popFront() {
      _array = _array[1 .. $];
    }
  }
  return ArrayRange!T(array);
}

By implementing the iterator as a struct, there's no need to allocate GC memory for a new instance. The only member is a slice of the source array, which again avoids allocation. Look at the implementation of popFront. Rather than requiring a separate variable to track the current array index, it slices the first element out of _array so that the next element is always at index 0, consequently shortening the length of the slice by one so that, after every item has been consumed, _array.length will be 0. This makes the implementation of both empty and front dead simple.

ArrayRange can be a Voldemort type because there is no need to declare its type in any algorithm it's passed to. As long as the algorithms are implemented as templates, the compiler can infer everything that needs to be known for them to work. Moreover, thanks to UFCS, it's possible to call this function as if it were an array property. Given an array called myArray, the following is valid:

auto range = myArray.range;

Next, we need a template to go in the other direction. This needs to allocate a new array, walk the iterator, and store the result of each call to front in the new array. Its implementation is as follows:

T[] array(T, R)(R range) {
  T[] ret;
  while(!range.empty) {
    ret ~= range.front;
    range.popFront();
  }
  return ret;
}

This can be called after any operation that produces any Range in order to get an array. If the range comes at the end of one or more lazy operations, this will cause all of them to execute simply by the call to popFront (we'll see how shortly). In that case, no allocations happen except as needed in this function when elements are appended to ret. Again, the appending strategy used here is naïve, so there's room for improvement in order to reduce the potential number of allocations. Now it's time to implement an algorithm to make use of our new range interface.

The filter function isn't going to do any filtering at all. If that sounds counterintuitive, recall that we want the function to be lazy; all of the work should be delayed until it is actually needed. The way to accomplish that is to wrap the input range in a custom range that has an internal implementation of the filtering algorithm. We'll call this wrapper FilteredRange. It will be a Voldemort type, which is local to the filter function. Before seeing the entire implementation, it will help to examine it in pieces as there's a bit more to see here than with ArrayRange.

FilteredRange has only one member:

private R _source;

R is the type of the range that is passed to filter. The empty and front functions simply delegate to the source range, so we'll look at popFront next:

void popFront() {
    _source.popFront();
    skipNext();
}

This will always pop the front element from the source range before running the filtering logic, which is implemented in the private helper function skipNext:

private void skipNext() {
    while(!_source.empty && !unaryFun!predicate(_source.front))
        _source.popFront();
}

This function tests the result of _source.front against the predicate. If it doesn't match, the loop moves on to the next element, repeating the process until either a match is found or the source range is empty. So, imagine you have an array arr of the values [1,2,3,4]. Given what we've implemented so far, what would be the result of the following chain?:

arr.range.filter!(x => (x & 1) == 0).front;

As mentioned previously, front delegates to _source.front. In this case, the source range is an instance of ArrayRange; its front returns _source[0]. Since popFront was never called at any point, the first value in the array was never tested against the predicate. Therefore, the return value is 1, a value which doesn't match the predicate. The first value returned by front should be 2, since it's the first even number in the array.

In order to make this behave as expected, FilteredRange needs to ensure the wrapped range is in a state such that either the first call to front will properly return a filtered value, or empty will return true, meaning there are no values in the source range that match the predicate. This is best done in the constructor:

this(R source) {
    _source = source;
    skipNext();
}

Calling skipNext in the constructor ensures that the first element of the source range is tested against the predicate before front is ever called; however, it does mean that our filter implementation isn't completely lazy. In an extreme case, when_source contains no values that match the predicate; it's actually going to be completely eager. The source elements will be consumed as soon as the range is instantiated. Not all algorithms will lend themselves to 100 percent laziness. No matter. What we have here is lazy enough. Wrapped up inside the filter function, the whole thing looks like this:

import std.functional;
auto filter(alias predicate, R)(R source)
  if(is(typeof(unaryFun!predicate))) {
    struct FilteredRange {
      private R _source;
      this(R source) {
        _source = source;
        skipNext();
      }
      bool empty() { return _source.empty; }
      auto ref front() { return _source.front; }
      void popFront() {
        _source.popFront();
        skipNext();
      }
      private void skipNext() {
        while(!_source.empty && !unaryFun!predicate(_source.front))
          _source.popFront();
      }
    }
    return FilteredRange(source);
}

It might be tempting to take the filtering logic out of the skipNext method and add it to front, which is another way to guarantee that it's performed on every element. Then no work would need to be done in the constructor and popFront would simply become a wrapper for _source.popFront. The problem with that approach is that front can potentially be called multiple times without calling popFront in between, meaning the predicate will be tested on each call. That's unnecessary work. As a general rule, any work that needs to be done inside a range to prepare a front element should happen as a result of calling popFront, leaving front to simply focus on returning the current element.

With the implementation complete, it's time to put it through its paces. Here are a few test cases in a unittest block:

unittest {
  auto arr = [10, 13, 300, 42, 121, 20, 33, 45, 50, 109, 18];
  auto result = arr.range
                     .filter!(x => x < 100 )
                     .filter!(x => (x & 1) == 0)
                     .array!int();
  assert(result == [10,42,20,50,18]);

  arr = [1,2,3,4,5,6];
  result = arr.range.filter!(x => (x & 1) == 0).array!int;
  assert(result == [2, 4, 6]);

  arr = [1, 3, 5, 7];
  auto r = arr.range.filter!(x => (x & 1) == 0);
  assert(r.empty);

  arr = [2,4,6,8];
  result = arr.range.filter!(x => (x & 1) == 0).array!int;
  assert(result == arr);
}

Assuming all of this has been saved in a file called filter.d, the following will compile it for unit testing:

dmd -unittest -main filter

That should result in an executable called filter that, when executed, should print nothing to the screen, indicating a successful test run. Notice the test that calls empty directly on the returned range. Sometimes, we might not need to convert a range to a container at the end of the chain. For example, to print the results, it's quite reasonable to iterate a range directly. Why allocate when it isn't necessary?

This foundational range is defined to be anything from which data can be sequentially read via the three primitives empty, front, and popFront. The first two should be treated as properties, meaning they can be variables or functions. This is important to keep in mind when implementing any generic range-based algorithm yourself; calls to these two primitives should be made without parentheses. The three higher-order range interfaces, we'll see shortly, build upon the input range interface.

To reinforce a point made earlier, one general rule to live by when crafting input ranges is that consecutive calls to front should return the same value until popFront is called; popFront prepares an element to be returned and front returns it. Breaking this rule can lead to unexpected consequences when working with range-based algorithms, or even foreach.

Input ranges are somewhat special in that they are recognized by the compiler. Recall the coverage of opApply in the previous chapter; it's what enables iteration of a custom type with a foreach loop. An alternative is to provide an implementation of the input range primitives. When the compiler encounters a foreach loop, it first checks to see if the iterated instance is of a type that implements opApply. If not, it then checks for the input range interface and, if found, rewrites the loop. For example, given a range someRange:

foreach(e; someRange) { ... }

This is rewritten to something like this:

for(auto __r = range; !__r.empty; __r.popFront()) {
    auto e = __r.front;
    ...
}

This has implications. To demonstrate, let's use the ArrayRange from earlier:

auto ar = [1, 2, 3, 4, 5].range;
foreach(n; ar) {
    writeln(n);
}
if(!ar.empty) writeln(ar.front);

The last line prints 1. If you're surprised, look again at the for loop that the compiler generates. ArrayRange is a struct, so when it's assigned to __r, a copy is generated. The slices inside, ar and __r, point to the same memory, but their .ptr and .length properties are distinct. As the length of the __r slice decreases, the length of the ar slice remains the same. This behavior was covered in the discussion of slices back in Chapter 2, Building a Foundation with D Fundamentals, and again when we talked about postblit constructors in Chapter 3, Programming Objects the D Way, but it's easy to forget.

When implementing generic algorithms that loop over a source range, it's not a good idea to rely on this behavior. If the range is a class instead of struct, it will be consumed by the loop, as classes are references types. Furthermore, there are no guarantees about the internal implementation of a range. There could be struct-based ranges that are actually consumed in a foreach loop. Generic functions should always assume this is the case.

To test if a given range type R is an input range:

import std.range : isInputRange;
static assert(isInputRange!R);

There are no special requirements on the return value of the front primitive. Elements can be returned by value or by reference, they can be qualified or unqualified, they can be inferred via auto, and so on. Any qualifiers, storage classes, or attributes that can be applied to functions and their return values can be used with any range function, though it might not always make sense to do so.

The most basic of the higher-order ranges is the forward range. This is defined as an input range that allows its current point of iteration to be saved via a primitive appropriately named save. Effectively, the implementation should return a copy of the current state of the range. For ranges that are struct types, it could be as simple as:

auto save() { return this; }

For ranges that are class types, it requires allocating a new instance:

auto save() { return new MyForwardRange(this); }

Forward ranges are useful for implementing algorithms that require lookahead. For example, consider the case of searching a range for a pair of adjacent elements that pass an equality test:

auto saved = r.save;
if(!saved.empty) {
  for(saved.popFront(); !saved.empty;
              r.popFront(), saved.popFront()) {
    if(r.front == saved.front)
      return r;
  }
}
return saved;

Because this uses a for loop and not a foreach loop, the ranges are iterated directly and are going to be consumed. Before the loop begins, a copy of the current state of the range is made by calling r.save. Then, iteration begins over both the copy and the original. The original range is positioned as the first element, and the call to saved.popFront in the beginning of the loop statement positions the saved range as the second element. As the ranges are iterated in unison, the comparison is always made on adjacent elements. If a match is found, r is returned, meaning that the returned range is positioned at the first element of a matching pair. If no match is found, saved is returned—since it's one element ahead of r, it will have been consumed completely and its empty property will be true.

The preceding example is derived from a more generic implementation in Phobos, std.range.findAdjacent. It can use any binary (two-argument) Boolean condition to test adjacent elements and is constrained to only accept forward ranges.

It's important to understand that calling save usually does not mean a deep copy, but it sometimes can. If we were to add a save function to the ArrayRange from earlier, we could simply return this; the array elements would not be copied. A class-based range, on the other hand, will usually perform a deep copy because it's a reference type. When implementing generic functions, you should never make the assumption that the range does not require a deep copy. For example, let's assume a range r:

auto saved = r;         // INCORRECT!!
auto saved = r.save;    // Correct.

If r is a class, the first line is almost certainly going to result in incorrect behavior.

To test if a given range R is a forward range:

import std.range : isForwardRange;
static assert(isForwardRange!R);

A bidirectional range is a forward range that includes the primitives back and popBack, allowing a range to be sequentially iterated in reverse. The former should be a property, the latter a function. Given a bidirectional range r, the following forms of iteration are possible:

foreach_reverse(e; r) writeln(e);
for(; !r.empty; r.popBack)
    writeln(r.back);
}

Like its cousin foreach, the foreach_reverse loop will be rewritten into a for loop that might not consume the original range; the for loop shown here does consume it.

To test whether a given range type R is a bidirectional range:

import std.range : isBidirectionalRange;
static assert(isBidirectionalRange!R);

A random-access range is a bidirectional range that supports indexing and is required to provide a length primitive if it isn't infinite (two topics we'll discuss shortly). For custom range types, this is achieved via the opIndex operator overload. It is assumed that r[n] returns a reference to the (n+1)th element of the range, just as when indexing an array.

To test whether a given range R is a random-access range:

import std.range : isRandomAccessRange;
static assert(isRandomAccessRange!R);

Dynamic arrays can be treated as random-access ranges by importing std.array. This pulls functions into scope that accept dynamic arrays as parameters and allows them to pass all the isRandomAccessRange checks. This makes our ArrayRange from earlier obsolete. Often, when you need a random-access range, it's sufficient just to use an array instead of creating a new range type. However, char and wchar arrays (string and wstring) are not considered random-access ranges, so they will not work with any algorithm that requires one.

The output range is the second foundational range type. It's defined as anything that can be sequentially written to via the primitive put. Generally, it should be implemented to accept a single parameter, but the parameter could be a single element, an array of elements, a pointer to elements, or another data structure containing elements. When working with output ranges, never call the range's implementation of put directly; instead, use the Phobos utility function std.range.put. It will call the range's implementation internally, but it allows for a wider range of argument types. Given a range r and element e, it would look like this:

import std.range : put;
put(r, e);

The benefit here is that, if e is anything other than a single element, such as an array or another range, the global put does what is necessary to pull elements from it and put them into r one at a time. With this, you can define and implement a simple output range that might look something like this:

MyOutputRange(T) {
  private T[] _elements;
  void put(T elem) {
    _elements ~= elem;
  }
}

Now you need not worry about calling put in a loop, or overloading it to accept collections of T. For example:

MyOutputRange!int range;
auto nums = [11, 22, 33, 44, 55];
import std.range : put;
put(range, nums);

To test whether a given range R is an output range:

import std.range : isOutputRange;
static assert(isOutputRange!(R, E));

Here, E is the type of element accepted by R.put.

In addition to the five primary range types, some algorithms in Phobos are designed to look for optional primitives that can be used as an optimization or, in some cases, a requirement. There are predicate templates in std.range that allow the same options to be used outside of Phobos.

struct IR {
    private uint _number;
    enum empty = false;
    auto front() { return _number; }
    void popFront() { ++_number; }
}

static immutable empty = false;