Programming in D - Structs and Classes with foreach

`foreach` with Structs and Classes

As you remember from the foreach Loop chapter, both how foreach works and the types and numbers of loop variables that it supports depend on the kind of collection: For slices, foreach provides access to elements with or without a counter; for associative arrays, to values with or without keys; for number ranges, to the individual values. For library types, foreach behaves in a way that is specific to that type; e.g. for File, it provides the lines of a file.

It is possible to define the behavior of foreach for user-defined types as well. There are two methods of providing this support:

Defining range member functions, which allows using the user-defined type with other range algorithms as well
Defining one or more opApply member functions

Of the two methods, opApply has priority: If it is defined, the compiler uses opApply, otherwise it considers the range member functions. However, in most cases range member functions are sufficient, easier, and more useful.

foreach need not be supported for every type. Iterating over an object makes sense only if that object defines the concept of a collection.

For example, it may not be clear what elements should foreach provide when iterating over a class that represents a student, so the class better not support foreach at all. On the other hand, a design may require that Student is a collection of grades and foreach may provide individual grades of the student.

It depends on the design of the program what types should provide this support and how.

`foreach` support by range member functions

We know that foreach is very similar to for, except that it is more useful and safer than for. Consider the following loop:

    foreach (element; myObject) {
        // ... expressions ...
    }

Behind the scenes, the compiler rewrites that foreach loop as a for loop, roughly an equivalent of the following one:

    for ( ; /* while not done */; /* skip the front element */) {

        auto element = /* the front element */;

        // ... expressions ...
    }

User-defined types that need to support foreach can provide three member functions that correspond to the three sections of the previous code: determining whether the loop is over, skipping the front element, and providing access to the front element.

Those three member functions must be named as empty, popFront, and front, respectively. The code that is generated by the compiler calls those functions:

    for ( ; !myObject.empty(); myObject.popFront()) {

        auto element = myObject.front();

        // ... expressions ...
    }

These three functions must work according to the following expectations:

.empty() must return true if the loop is over, false otherwise
.popFront() must move to the next element (in other words, skip the front element)
.front() must return the front element

Any type that defines those member functions can be used with foreach.

Example

Let's define a struct that produces numbers within a certain range. In order to be consistent with D's number ranges and slice indexes, let's have the last number be outside of the valid numbers. Under these requirements, the following struct would work exactly like D's number ranges:

struct NumberRange {
    int begin;
    int end;

    invariant() {
        // There is a bug if begin is greater than end
        assert(begin <= end);
    }

    bool empty() const {
        // The range is consumed when begin equals end
        return begin == end;
    }

    void popFront() {
        // Skipping the first element is achieved by
        // incrementing the beginning of the range
        ++begin;
    }

    int front() const {
        // The front element is the one at the beginning
        return begin;
    }
}

Note: The safety of that implementation depends solely on a single invariant block. Additional checks could be added to front and popFront to ensure that those functions are never called when the range is empty.

Objects of that struct can be used with foreach:

    foreach (element; NumberRange(3, 7)) {
        write(element, ' ');
    }

foreach uses those three functions behind the scenes and iterates until empty() returns true:

3 4 5 6

`std.range.retro` to iterate in reverse

The std.range module contains many range algorithms. retro is one of those algorithms, which iterates a range in reverse order. It requires two additional range member functions:

.popBack() must move to the element that is one before the end (skips the last element)
.back() must return the last element

However, although not directly related to reverse iteration, for retro to consider those functions at all, there must be one more function defined:

.save() must return a copy of this object

We will learn more about these member functions later in the Ranges chapter.

These three additional member functions can trivially be defined for NumberRange:

struct NumberRange {
// ...

    void popBack() {
        // Skipping the last element is achieved by
        // decrementing the end of the range.
        --end;
    }

    int back() const {
        // As the 'end' value is outside of the range, the
        // last element is one less than that
        return end - 1;
    }

    NumberRange save() const {
        // Returning a copy of this struct object
        return this;
    }
}

Objects of this type can now be used with retro:

import std.range;

// ...

    foreach (element; NumberRange(3, 7).retro) {
        write(element, ' ');
    }

The output of the program is now in reverse:

6 5 4 3

`foreach` support by `opApply` and `opApplyReverse` member functions

Everything that is said about opApply in this section is valid for opApplyReverse as well. opApplyReverse is for defining the behaviors of objects in the foreach_reverse loops.

The member functions above allow using objects as ranges. That method is more suitable when there is only one sensible way of iterating over a range. For example, it would be easy to provide access to individual students of a Students type.

On the other hand, sometimes it makes more sense to iterate over the same object in different ways. We know this from associative arrays where it is possible to access either only to the values or to both the keys and the values:

    string[string] dictionary;    // from English to Turkish

    // ...

    foreach (inTurkish; dictionary) {
        // ... only values ...
    }

    foreach (inEnglish, inTurkish; dictionary) {
        // ... keys and values ...
    }

opApply allows using user-defined types with foreach in various and sometimes more complex ways. Before learning how to define opApply, we must first understand how it is called automatically by foreach.

The program execution alternates between the expressions inside the foreach block and the expressions inside the opApply() function. First the opApply() member function gets called, and then opApply makes an explicit call to the foreach block. They alternate in that way until the loop eventually terminates. This process is based on a convention, which I will explain soon.

Let's first observe the structure of the foreach loop one more time:

// The loop that is written by the programmer:

    foreach (/* loop variables */; myObject) {
        // ... expressions inside the foreach block ...
    }

If there is an opApply() member function that matches the loop variables, then the foreach block becomes a delegate, which is then passed to opApply().

Accordingly, the loop above is converted to the following code behind the scenes. The curly brackets that define the body of the delegate are highlighted:

// The code that the compiler generates behind the scenes:

    myObject.opApply(delegate int(/* loop variables */) {
        // ... expressions inside the foreach block ...
        return hasBeenTerminated;
    });

In other words, the foreach loop is replaced by a delegate that is passed to opApply(). Before showing an example, here are the requirements and expectations of this convention that opApply() must observe:

The body of the foreach loop becomes the body of the delegate. opApply must call this delegate for each iteration.
The loop variables become the parameters of the delegate. opApply() must define these parameters as ref. (The variables may be defined without the ref keyword as well but doing that would prevent iterating over the elements by reference.)
The return type of the delegate is int. Accordingly, the compiler injects a return statement at the end of the delegate, which determines whether the loop has been terminated (by a break or a return statement): If the return value is zero, the iteration must continue, otherwise it must terminate.
The actual iteration happens inside opApply().
opApply() must return the same value that is returned by the delegate.

The following is a definition of NumberRange that is implemented according to that convention:

struct NumberRange {
    int begin;
    int end;
                         //    (2)       (1)
    int opApply(int delegate(ref int) operations) const {
        int result = 0;

        for (int number = begin; number != end; ++number) { // (4)
            result = operations(number);  // (1)

            if (result) {
                break;                    // (3)
            }
        }

        return result;                    // (5)
    }
}

This definition of NumberRange can be used with foreach in exactly the same way as before:

    foreach (element; NumberRange(3, 7)) {
        write(element, ' ');
    }

The output is the same as the one produced by range member functions:

3 4 5 6

Overloading `opApply` to iterate in different ways

It is possible to iterate over the same object in different ways by defining overloads of opApply() that take different types of delegates. The compiler calls the overload that matches the particular set of loop variables.

As an example, let's make it possible to iterate over NumberRange by two loop variables as well:

    foreach (first, second; NumberRange(0, 15)) {
        writef("%s,%s ", first, second);
    }

Note how it is similar to the way associative arrays are iterated over by both keys and values.

For this example, let's require that when a NumberRange object is iterated by two variables, it should provide two consecutive values and that it arbitrarily increases the values by 5. So, the loop above should produce the following output:

0,1 5,6 10,11

This is achieved by an additional definition of opApply() that takes a delegate that takes two parameters. opApply() must call that delegate with two values:

    int opApply(int delegate(ref int, ref int) dg) const {
        int result = 0;

        for (int i = begin; (i + 1) < end; i += 5) {
            int first = i;
            int second = i + 1;

            result = dg(first, second);

            if (result) {
                break;
            }
        }

        return result;
    }

When there are two loop variables, this overload of opApply() gets called.

There may be as many overloads of opApply() as needed.

It is possible and sometimes necessary to give hints to the compiler on what overload to choose. This is done by specifying types of the loop variables explicitly.

For example, let's assume that there is a School type that supports iterating over the teachers and the students separately:

class School {
    int opApply(int delegate(ref Student) dg) const {
        // ...
    }

    int opApply(int delegate(ref Teacher) dg) const {
        // ...
    }
}

To indicate the desired overload, the loop variable must be specified:

    foreach (Student student; school) {
        // ...
    }

    foreach (Teacher teacher; school) {
        // ...
    }

Loop counter

The convenient loop counter of slices is not automatic for other types. Loop counter can be achieved for user-defined types in different ways depending on whether the foreach support is provided by range member functions or by opApply overloads.

Loop counter with range functions

If foreach support is provided by range member functions, then a loop counter can be achieved simply by enumerate from the std.range module:

import std.range;

// ...

    foreach (i, element; NumberRange(42, 47).enumerate) {
        writefln("%s: %s", i, element);
    }

enumerate is a range that produces consecutive numbers starting by default from 0. enumerate pairs each number with the elements of the range that it is applied on. As a result, the numbers that enumerate generates and the elements of the actual range (NumberRange in this case) appear in lockstep as loop variables:

Loop counter with `opApply`

On the other hand, if foreach support is provided by opApply(), then the loop counter must be defined as a separate parameter of the delegate, suitably as type size_t. Let's see this on a struct that represents a colored polygon.

As we have already seen above, an opApply() that provides access to the points of this polygon can be implemented without a counter as in the following code:

import std.stdio;

enum Color { blue, green, red }

struct Point {
    int x;
    int y;
}

struct Polygon {
    Color color;
    Point[] points;

    int opApply(int delegate(ref const(Point)) dg) const {
        int result = 0;

        foreach (point; points) {
            result = dg(point);

            if (result) {
                break;
            }
        }

        return result;
    }
}

void main() {
    auto polygon = Polygon(Color.blue,
                           [ Point(0, 0), Point(1, 1) ] );

    foreach (point; polygon) {
        writeln(point);
    }
}

Note that opApply() itself is implemented by a foreach loop. As a result, the foreach inside main() ends up making indirect use of a foreach over the points member.

Also note that the type of the delegate parameter is ref const(Point). This means that this definition of opApply() does not allow modifying the Point elements of the polygon. In order to allow user code to modify the elements, both the opApply() function itself and the delegate parameter must be defined without the const specifier.

The output:

const(Point)(0, 0)
const(Point)(1, 1)

Naturally, trying to use this definition of Polygon with a loop counter would cause a compilation error:

    foreach (i, point; polygon) {    // ← compilation ERROR
        writefln("%s: %s", i, point);
    }

The compilation error:

Error: cannot uniquely infer foreach argument types

For that to work, another opApply() overload that supports a counter must be defined:

    int opApply(int delegate(ref size_t,
                             ref const(Point)) dg) const {
        int result = 0;

        foreach (i, point; points) {
            result = dg(i, point);

            if (result) {
                break;
            }
        }

        return result;
    }

This time the foreach variables are matched to the new opApply() overload and the program prints the desired output:

0: const(Point)(0, 0)
1: const(Point)(1, 1)

Note that this implementation of opApply() takes advantage of the automatic counter over the points member. (Although the delegate variable is defined as ref size_t, the foreach loop inside main() cannot modify the counter variable over points).

When needed, the loop counter can be defined and incremented explicitly as well. For example, because the following opApply() is implemented by a while statement it must define a separate variable for the counter:

    int opApply(int delegate(ref size_t,
                             ref const(Point)) dg) const {
        int result = 0;
        bool isDone = false;

        size_t counter = 0;
        while (!isDone) {
            // ...

            result = dg(counter, nextElement);

            if (result) {
                break;
            }

            ++counter;
        }

        return result;
    }

Warning: The collection must not mutate during the iteration

Regardless of whether the iteration support is provided by the range member functions or by opApply() functions, the collection itself must not mutate. New elements must not be added to the container and the existing elements must not be removed. (Mutating the existing elements is allowed.)

Doing otherwise is undefined behavior.

Exercises

Design a struct that works similarly to NumberRange, which also supports specifying the step size. The step size can be the third member:
```
    foreach (element; NumberRange(0, 10, 2)) {
        write(element, ' ');
    }
```
The expected output of the code above is every second number from 0 to 10:
```
0 2 4 6 8 
```
Implement the School class that was mentioned in the text in a way that it provides access to students or teachers depending on the foreach variable.

... the solutions

[ ↢ Prev ] [ Next ↣ ]

foreach with Structs and Classes

foreach support by range member functions