foreach_opapply.d

Ddoc

$(DERS_BOLUMU $(IX foreach, user defined type) $(IX struct, foreach) $(IX class, foreach) $(CH4 foreach) with Structs and Classes)

$(P
As you remember from $(LINK2 /ders/d.en/foreach.html, the $(C foreach) Loop chapter), both how $(C foreach) works and the types and numbers of loop variables that it supports depend on the kind of collection: For slices, $(C 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, $(C foreach) behaves in a way that is specific to that type; e.g. for $(C File), it provides the lines of a file.
)

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

$(UL
$(LI Defining $(I range member functions), which allows using the user-defined type with other range algorithms as well)

$(LI Defining one or more $(C opApply) member functions)
)

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

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

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

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

$(H5 $(IX range, foreach) $(C foreach) support by range member functions)

$(P
$(IX empty) $(IX front) $(IX popFront) We know that $(C foreach) is very similar to $(C for), except that it is more useful and safer than $(C for). Consider the following loop:
)

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

$(P
Behind the scenes, the compiler rewrites that $(C foreach) loop as a $(C for) loop, roughly an equivalent of the following one:
)

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

        auto element = /* the front element */;

        // ... expressions ...
    }
---

$(P
User-defined types that need to support $(C 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.
)

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

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

        auto element = myObject.front();

        // ... expressions ...
    }
---

$(P
These three functions must work according to the following expectations:
)

$(UL

$(LI $(C .empty()) must return $(C true) if the loop is over, $(C false) otherwise)

$(LI $(C .popFront()) must move to the next element (in other words, skip the front element))

$(LI $(C .front()) must return the front element)

)

$(P
Any type that defines those member functions can be used with $(C foreach).
)

$(H6 Example)

$(P
Let's define a $(C 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 $(C 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;
    }
}
---

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

$(P
Objects of that $(C struct) can be used with $(C foreach):
)

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

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

$(SHELL_SMALL
3 4 5 6 
)

$(H6 $(IX retro, std.range) $(C std.range.retro) to iterate in reverse)

$(P
$(IX save) $(IX back) $(IX popBack) The $(C std.range) module contains many range algorithms. $(C retro) is one of those algorithms, which iterates a range in reverse order. It requires two additional range member functions:
)

$(UL

$(LI $(C .popBack()) must move to the element that is one before the end (skips the last element))

$(LI $(C .back()) must return the last element)

)

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

$(UL
$(LI $(C .save()) must return a copy of this object)
)

$(P
We will learn more about these member functions later in $(LINK2 /ders/d.en/ranges.html, the Ranges chapter).
)

$(P
These three additional member functions can trivially be defined for $(C 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 @property {
        // Returning a copy of this struct object
        return this;
    }
}
---

$(P
Objects of this type can now be used with $(C retro):
)

---
import std.range;

// ...

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

$(P
The output of the program is now in reverse:
)

$(SHELL_SMALL
6 5 4 3 
)

$(H5 $(IX opApply) $(IX opApplyReverse) $(C foreach) support by $(C opApply) and $(C opApplyReverse) member functions)

$(P
$(IX foreach_reverse) Everything that is said about $(C opApply) in this section is valid for $(C opApplyReverse) as well. $(C opApplyReverse) is for defining the behaviors of objects in the $(C foreach_reverse) loops.
)

$(P
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 $(C Students) type.
)

$(P
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 ...
    }
---

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

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

$(P
Let's first observe the structure of the $(C foreach) loop one more time:
)

---
// The loop that is written by the programmer:

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

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

$(P
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 */) $(HILITE {)
        // ... expressions inside the foreach block ...
        return hasBeenTerminated;
    $(HILITE }));
---

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

$(OL

$(LI The body of the $(C foreach) loop becomes the body of the delegate. $(C opApply) must call this delegate for each iteration.)

$(LI The loop variables become the parameters of the delegate. $(C opApply()) must define these parameters as $(C ref).)

$(LI The return type of the delegate is $(C int). Accordingly, the compiler injects a $(C return) statement at the end of the delegate, which determines whether the loop has been terminated (by a $(C break) or a $(C return) statement): If the return value is zero, the iteration must continue, otherwise it must terminate.)

$(LI The actual iteration happens inside $(C opApply()).)

$(LI $(C opApply()) must return the same value that is returned by the delegate.)

)

$(P
The following is a definition of $(C 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)
    }
}
---

$(P
This definition of $(C NumberRange) can be used with $(C foreach) in exactly the same way as before:
)

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

$(P
The output is the same as the one produced by range member functions:
)

$(SHELL_SMALL
3 4 5 6 
)

$(H6 Overloading $(C opApply) to iterate in different ways)

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

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

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

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

$(P
For this example, let's require that when a $(C 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:
)

$(SHELL_SMALL
0,1 5,6 10,11 
)

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

---
    int opApply(int delegate$(HILITE (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($(HILITE first, second));

            if (result) {
                break;
            }
        }

        return result;
    }
---

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

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

$(P
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.
)

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

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

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

$(P
To indicate the desired overload, the loop variable must be specified:
)

---
    foreach ($(HILITE Student) student; school) {
        // ...
    }

    foreach ($(HILITE Teacher) teacher; school) {
        // ...
    }
---

$(H5 $(IX loop counter) $(IX counter, loop) Loop counter)

$(P
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 $(C foreach) support is provided by range member functions or by $(C opApply) overloads.
)

$(H6 Loop counter with range functions)

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

---
import std.range;

// ...

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

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

$(SHELL_SMALL
0: 42
1: 43
2: 44
3: 45
4: 46
)

$(H6 Loop counter with $(C opApply))

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

$(P
As we have already seen above, an $(C opApply()) that provides access to the points of this polygon can be implemented $(I 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 $(HILITE 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);
    }
}
---

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

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

$(P
The output:
)

$(SHELL
const(Point)(0, 0)
const(Point)(1, 1)
)

$(P
Naturally, trying to use this definition of $(C Polygon) with a loop counter would cause a compilation error:
)

---
    foreach ($(HILITE i), point; polygon) {    $(DERLEME_HATASI)
        writefln("%s: %s", i, point);
    }
---

$(P
The compilation error:
)

$(SHELL
Error: cannot uniquely infer foreach argument types
)

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

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

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

            if (result) {
                break;
            }
        }

        return result;
    }
---

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

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

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

$(P
When needed, the loop counter can be defined and incremented explicitly as well. For example, because the following $(C opApply()) is implemented by a $(C 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;

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

            result = dg(counter, nextElement);

            if (result) {
                break;
            }

            ++counter;
        }

        return result;
    }
---

$(H5 Warning: The collection must not mutate during the iteration)

$(P
Regardless of whether the iteration support is provided by the range member functions or by $(C 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.)
)

$(P
Doing otherwise is undefined behavior.
)

$(PROBLEM_COK

$(PROBLEM
Design a $(C struct) that works similarly to $(C NumberRange), which also supports specifying the step size. The step size can be the third member:

---
    foreach (element; NumberRange(0, 10, $(HILITE 2))) {
        write(element, ' ');
    }
---

$(P
The expected output of the code above is every second number from 0 to 10:
)

$(SHELL_SMALL
0 2 4 6 8 
)

)

$(PROBLEM
Implement the $(C School) class that was mentioned in the text in a way that it provides access to students or teachers depending on the $(C foreach) variable.
)

)

Macros:
        SUBTITLE=Structs and Classes with foreach

        DESCRIPTION=Defining the way user-defined types behave with the foreach loop.

        KEYWORDS=d programming language tutorial book foreach opApply opApplyReverse