The Battle for Wesnoth  1.19.0-dev
GUI2 Iterator.

The iterator class allows the user to iterate over a group of widgets.

The idea is to add a visitor class later as well, where the two classes can be combined.

This page describes how the iterator class works. The iterator is build from several parts:

  • level, the part and subparts of the widget to visit.
  • walker, iterates over a single widget at several levels.
  • visit policy, whether a level should be visited or not.
  • order policy, the order in which the several levels are traversed.
  • iterator, the user interface for iteration.

Level

The levels are defined in gui2::iteration::walker_base::level. The level allows the user to only visit a part of the widget tree.

Note
At the moment when gui2::iteration::walker_base::widget is skipped the child class also skips its children. This behavior might change.

Walker

The is a group of classes inheriting from gui2::iteration::walker_base the objects are created from gui2::widget::create_walker. The walker allows to visit the several levels of the widget. This means several widgets need to override the function in a subclass. For example most simple widgets don't have a grid or children so they can use the walker created from gui2::styled_widget. But containers need to create a different walker.

Visit policy

This policy simply defines whether or not to visit the widgets at a certain level. There are two visit policies:

There are no more visit policies expected for the future. These policies are normally not used directly, but set from the Order policy.

Order policy

This policy determines in which order the widgets are traversed, children first, this level before diving down etc. tests/gui/iterator.cpp shows more information. The following policies have been defined:

The next sections describe in which order the widgets are visited. In the description we use the following widget tree.

[0]
\
[1|2|3|4]
\
[5|6|7|8]
The types are:

  • grid 0, 1
  • styled_widget 2, 3, 4, 6, 7, 8

The examples assume all levels will be visited.

Top down

The widgets visited first is the initial widget. After that it tries to go down to a child widget and will continue down. Once that fails it will visit the siblings at that level before going up again.

Todo:
Write the entire visiting algorithm.

The visiting order in our example is: 0, 1, 5, 6, 7, 8, 2, 3, 4

Bottom up

When the iterator is created the iterator tries to go down all the child widgets to get at the bottom level. That widget will be visited first. Then it will first visit all siblings before going up the the next layer.

Todo:
Write the entire visiting algorithm.

The visiting order in our example is: 5, 6, 7, 8, 1, 2, 3, 4, 0

Iterator

The iterator is the class the users should care about. The user creates the iterator with the selected policy and the root widget. Then the user can visit the widgets.

When during the iteration a widget is added to or removed from the widget-tree being walked the iterator becomes invalid. Using the iterator when it is invalid results in Undefined Behavior.

When it's certain there's at least one widget to visit a simple do while loop can be used. It the policy visits the widget, it's certain there is at least one widget to visit. Below some sample code:

iterator<policy> itor(root);
assert(!itor.at_end());
do {
...
...
} while(itor.next());

When there might be no widget to visit a simple for loop can be used:

for(iterator<policy> itor(root); !itor.at_end(); ++itor) {
...
...
}

Design

As seen in the examples above the iterator doesn't look like a iterator in the C++ standard library. The iterator is more designed after the iterator design of the Gang of Four [GoF]. The reason for the different design is that GoF design fits better to the classes as a normal C++ iterator. The rest of this section explains some of the reasons why this design is chosen. The main reason is simple; the iteration of the widgets feels better suited for the GoF-style iteration as the C++-style iteration.

The iterator is not lightweight like most C++ iterators, therefore the class in non-copyable. (This is for example also the reason why a std::list has no operator[].) Since operator++(int) should return a copy of the original object it's also omitted.

The design makes it hard to back-track the iteration (or costs more memory), so the iterator is forward only. The order policy is added to allow the wanted walking direction, but one-way only.

The iterator has a begin, but it's not easy to go back to it and the operation involves rewinding the state, which might be costly. Therefore no begin() function.

The end is known at the moment it's reached, but not upfront. That combined with the forward only, makes implementing an end() hard and therefore it is omitted.

[GoF] http://en.wikipedia.org/wiki/Design_Patterns_%28book%29