- 18.07 (released) ...
- Iterators and Agents
- The Notion of iterator
- Simple Examples
- Using the Iteration Library
- Building and Using Iterators
The classes of the Iteration cluster encapsulate control structures representing common traversal operations.
Iterators and Agents
Eiffel's agent mechanism offers an attractive alternative to the
The Notion of iterator
Let us first explore the role of iterators in the architecture of a system.
Iterating over data structures
Client software that uses data structures of a certain type, for example lists or trees, often needs to traverse a data structure of that type in a predetermined order so as to apply a certain action to all the items of the structure, or to all items that satisfy a certain criterion. Such a systematic traversal is called an iteration.
Cases of iteration can be found in almost any system. Here are a few typical examples:
- A text processing system may maintain a list of paragraphs. In response to a user command, such as a request to resize the column width, the system will iterate over the entire list so as to update all paragraphs.
- A business system may maintain a list of customers. If the company decides that a special promotion will target all customers satisfying a certain criterion (for example all customers that have bought at least one product over the past six months), the system will iterate over the list, generating a mailing for every list item that satisfies the criterion.
- An interactive development environment for a programming language may maintain a syntax tree. In response to a program change, the system will traverse the tree to determine what nodes are affected by the change and update them.
These examples illustrate the general properties of iteration. An iteration involves a data structure of a known general type and a particular ordering of the structure's items. For some structures, more than one ordering will be available; for example a tree iteration may use preorder, postorder or breadth-first (as defined below). The iteration involves an operation, say
item_actionto all the items in the structure. (In this case item_test is not relevant).
item_actionto all items that satisfy item_test.
item_actionto all items up to the first one that satisfies item_test.
The Iteration library provides many more, covering in particular all the standard control structures.
Iterations and control structures
You can perform iterations without any special iteration classes. For example if customers is declared as
customers: LIST [CUSTOMER]
then a class
if recent_purchases.has (customers.item) then
Such schemes are quite common. But it is precisely because they occur frequently that it is useful to rely on library classes to handle them. One of the principal tasks of object-oriented software development is to identify recurring patterns and build reusable classes that encapsulate them, so that future developers will be able to rely on ready-made solutions.
The classes of the Iteration library address this need. Using them offers two benefits:
- You avoid writing loops, in which the definition of sub-components such as exit conditions, variants and invariants is often delicate or error-prone.
- You can more easily adapt the resulting features in descendant classes. The rest of this chapter shows how to obtain these benefits.
To get a first grasp of how one can work with the Iteration library, let us look at a typical iteration class and a typical iteration client.
An example iterator routine
Here, given with its full implementation, is a typical Iteration library routine: the procedure until_do from LINEAR_ITERATOR , the class defining iteration mechanisms on linear (sequential) structures.
until_do (action: PROCEDURE [G]; test: FUNCTION [G, BOOLEAN])
-- Apply `action' to every item of `target' up to
-- but excluding first one satisfying `test'.
-- (Apply to full list if no item satisfies `test'.)
until_continue (action, test)
achieved: not exhausted implies test.item ([target.item])
until_continue (action: PROCEDURE [G]; test: FUNCTION [G, BOOLEAN])
-- Apply `action' to every item of `target' from current
-- position, up to but excluding first one satisfying `test'.
exhausted or else test.item ([target.item])
achieved: exhausted or else test.item ([target.item])
The precise form of the procedure in the class relies on a call to another procedure, until_continue, and on inherited assertions. Here the routines are shown as they are found in the current implementation of the class LINEAR_ITERATOR.
This procedure will traverse the linear structure identified by target and apply the procedure called action on every item up to but excluding the first one satisfying test.
The class similarly offers
These iteration schemes depend on the procedure
test (a_item: STRING): BOOLEAN
-- Test to be applied to a_item
Result := a_item.count > 0
This indicates that the value of the boolean function
An example use of iteration
Here now is an example illustrating the use of these mechanisms. The result will enable us to resize all the paragraphs of a text up to the first one that has been modified - as we might need to do, in a text processing system, to process an interactive user request. Assume a class
In a class
resize_paragraphs (t: TEXT)
-- Resize all the paragraphs of t up to but excluding
-- the first one that has been modified.
until_do (agent item_action, agent item_test)
item_test (p: PARAGRAPH): BOOLEAN
-- Has p been modified?
Result := p.modified
item_action (p: PARAGRAPH)
-- Resize p.
Thanks to the iteration mechanism, the procedure
- To set its argument
tas the iteration target, it uses procedure
set. (This procedure is from class ITERATOR which passes it on to all iterator classes.)
- Then it simply calls
until_doas defined above.
As presented so far, the mechanism seems to limit every descendant of an iteration class to just one form of iteration. As shown later in this chapter, it is in fact easy to generalize the technique to allow a class to use an arbitrary number of iteration schemes.
What is interesting here is that the definitions of
Using the Iteration Library
Let us now explore the classes of the Iteration library and the different ways of using them.
Overview of the classes
There are only four Iteration classes, whose simple inheritance structure appeared at the beginning of this chapter.
- ITERATOR , a deferred class which describes the most general notion.
- LINEAR_ITERATOR , for iterating over linear structures and chains.
- TWO_WAY_CHAIN_ITERATOR , a repeated heir of LINEAR_ITERATOR , for iterating in either direction over a bilinear structure.
- CURSOR_TREE_ITERATOR , for iterating over trees.
As you will remember from the presentation of the abstract overall taxonomy, the traversal hierarchy describes how data structures can be traversed; its most general class is TRAVERSABLE .
Each one of the iterator classes is paired with a traversal class (or two in one case):
|TWO_WAY_CHAIN_ITERATOR||TWO_WAY_LIST , TWO_WAY_CIRCULAR|
Each iterator class relies on the corresponding traversal class to provide the features for traversing the corresponding data structures, such as
Of course the data structure class used in connection with a given iterator class does not need to be the iterator's exact correspondent as given by the above table; it may be any one of its descendants. For example you may use LINEAR_ITERATOR to iterate over data structures described not just by LINEAR but also by such descendants as LIST , LINKED_LIST , ARRAYED_LIST , or even TWO_WAY_LIST if you do not need the backward iteration features (for which you will have to use TWO_WAY_CHAIN_ITERATOR ).
General iteration facilities
Class ITERATOR defines the features that apply to all forms of iterator.
An iterator will always apply to a certain target structure. The target is introduced in ITERATOR by the feature target: TRAVERSABLE [G]
Both the iterator classes and the traversal classes are generic, with a formal generic parameter G. The actual generic parameters will be matched through the choice of iteration target: for a generic derivation of the form
Each of the proper descendants of ITERATOR redefines the type of target to the matching proper descendant of TRAVERSABLE , to cover more specific variants of the iteration target. For example in LINEAR_ITERATOR the feature is redefined to be of type LINEAR. ITERATOR also introduces the procedure for selecting a target:
set (s: like target)
-- Make s the new target of iterations.
s /= Void
target := s
target = s
target /= Void
Another feature introduced in ITERATOR is the query
Finally, ITERATOR introduces in deferred form the general iteration routines applicable to all iteration variants. They include two queries corresponding to the quantifiers of first-order predicate calculus:
for_allwill return true if all items of the target structure satisfy test.
there_existswill return true if at least one item satisfies test.
The other routines are commands which will traverse the target structure and apply action to items selected through test:
do_allapplies actionto all items.
do_if, to those items which satisfy test.
until_do, to all items up to but excluding the first one that satisfies test.
do_until, to all items up to and including the first one that satisfies test.
while_doand do_while, to all items up to the first one that does not satisfy test. (This can also be achieved with until_door do_untilby choosing the opposite test.)
Some of these features and most of the other iteration features introduced in proper descendants of ITERATOR and described next, have either an
Linear and chain iteration
LINEAR_ITERATOR , an effective class, refines the iteration mechanisms for cases in which the target is a linear structure, such as a list in any implementation or a circular chain.
The class effects all the deferred features inherited from ITERATOR , taking advantage of the linear traversal mechanisms present in the corresponding traversal class, LINEAR . Here for example is the effecting of
This routine text relies on features
-- Is position of target off?
traversable_exists: target /= Void
Result := target.off
and similarly for the others.
In addition to effecting the general iteration features from ITERATOR , class LINEAR_ITERATOR introduces iteration features that apply to the specific case of linear structures:
search (test: FUNCTION [G, BOOLEAN]; b: BOOLEAN)moves the iteration to the first position satisfying
bhave the same value (both
Trueor both False).
- With a linear structure we can implement an iteration corresponding to the 'for' loop of traditional programming languages, defined by three integers: the starting position, the number of items to be traversed, and the step between consecutive items. This is provided by procedure
(action: PROCEDURE [G]; starting , number , step: INTEGER).
- Since with a linear target the iterator can advance the cursor step by step, the basic iteration operations are complemented by variants which pick up from the position reached by the last call:
continue_until, until_continue, continue_while, while_continue, continue_search, continue_for.
Class TWO_WAY_CHAIN_ITERATOR has all the features of LINEAR_ITERATOR , to which it adds features for iterating backward as well as forward.
The class introduces commands
An alternative design would have kept just one set of features and added two features: a command reverse to reverse the direction of future iteration operations, and a query backward to find out the direction currently in force.
Contrary to what one might at first imagine, class TWO_WAY_CHAIN_ITERATOR is extremely short and simple; its
Feature clause only contains the declarations of two features,
The trick is to use repeated inheritance. TWO_WAY_CHAIN_ITERATOR inherits twice from LINEAR_ITERATOR ; the first inheritance branch yields the forward iteration features, the second yields those for backward iteration. There is no need for any explicit declaration or redeclaration of iteration features. Here is the entire class text that yields this result:
class TWO_WAY_CHAIN_ITERATOR [G] inherit
start as finish,
forth as back,
do_all as do_all_back,
until_do as until_do_back,
do_until as do_until_back,
do_while as do_while_back,
while_do as while_do_back,
do_if as do_if_back,
do_for as do_for_back,
search as search_back,
for_all as for_all_back,
there_exists as there_exists_back,
until_continue as until_continue_back,
continue_until as continue_until_back,
while_continue as while_continue_back,
continue_while as continue_while_back,
continue_for as continue_for_back,
continue_search as continue_search_back
back, finish, target
feature -- Access
target: CHAIN [G]
feature -- Cursor movement
-- Move cursor of `target' to last position.
-- Move cursor of `target' backward one position.
This class provides a good example of the economy of expression that the full inheritance mechanism affords through the combination of renaming, redefinition, repeated inheritance rules and selection, without sacrificing clarity and maintainability.
Tree iterations, provided by class CURSOR_TREE_ITERATOR , work on trees of the cursor tree form; only with this form of tree are traversal operations possible. Three forms of iteration are provided: preorder, postorder and breadth-first. They correspond to the three traversal policies described in the discussion of trees. Here too it would seem that a rather lengthy class is needed, but repeated inheritance works wonders.
CURSOR_TREE_ITERATOR simply inherits three times from LINEAR_ITERATOR , renaming the features appropriately in each case:
pre_do_all, pre_until, and so on.
post_do_all, post_until, and so on.
breadth_do_all, breadth_until, and so on.
All it needs to do then is to redefine the type of target to be CURSOR_TREE [G] , and to redefine six features: the three renamed start (
Building and Using Iterators
To conclude this discussion, let us now put together the various mechanisms studied so far, to see how authors of client software can use the Iteration library to perform possibly complex iterations on various data structures without ever writing a single loop or test. The basic ideas were sketched above but now we have all the elements for the full view.
An application class may use one of the iteration classes in either of two ways: as a descendant (single or repeated) or as a client. The descendant technique is extremely simple but less versatile.
The single descendant technique
Assume an application class
set (t) where t represents the selected target data structure. The type of t must correspond to the iteration class selected as ancestor of
It is hard to imagine a simpler scheme: no loops, no initialization, no arguments. Feature item_action may need to rely on some variable values. Because it does not take any argument, such values will have to be treated as attributes, with the corresponding
The single descendant technique has one drawback: it provides the iterating class,
The next two techniques will remove this limitation.
Using repeated inheritance
One way to obtain several iteration schemes is a simple extension to the single descendant technique. You can use repeated inheritance to provide two or more variants. We have in fact already encountered the technique when studying how to derive TWO_WAY_CHAIN_ITERATOR and CURSOR_TREE_ITERATOR from LINEAR_ITERATOR . The general pattern, applied here to just two iteration schemes but easily generalized to more, is straightforward:
item_action as action1,
item_test as test1,
do_if as do_if1,
item_action as action2,
item_test as test2,
do_if as do_if2,
-- Action for the first scheme
-- Test for the first scheme
-- Action for the second scheme
-- Test for the second scheme
-- Execute iteration of first kind.
-- Execute iteration of second kind.
The repeated inheritance machinery takes care of the rest.
Using explicit iterator objects
To obtain maximum flexibility, classes that need iteration facilities should be clients rather than descendants of the iteration classes. The resulting scheme is completely dynamic: to perform iterations you use iterator objects as discussed earlier.
The following example illustrates the technique. Consider a deferred class
In the feature clause we want to provide the appropriate effectings for the deferred features of class
We can use loops for that purpose, for example
-- Recursively display all components of the complex
Although acceptable and even elegant, this scheme will cause significant duplication: all the
To implement this approach, define a class for iterating on complex figures:
Then for each operation to be iterated define a small class. For example:
item_action (f: FIGURE)
-- Action to be applied to each figure: display
Similarly, you may define
-- Recursively display all components of the complex
create disp.set (Current)
and similarly for all the others.
Note the use of