**Go backward to** Generic Programming Using Adaptive and

Aspect-Oriented Programming

*Karl Lieberherr*

**Go up to** Programming Methodology

**Go forward to** Template Support for Variation

*Georg Trausmuth*

### Complete Traversals: Implementation and Generality

*Arturo Sánchez-Ruíz*

This talk has two parts. The first part presents the concept of
*complete traversal* (CT), which for a given a container *C* (such as a set)
is defined by the iteration scheme

**for all** *x *** in C**

*F**(x,C)*

where *F* is a function that might possibly modify *C* by
inserting new elements into it. We assume that the order in which the
elements are treated is not relevant, as long as the iteration
continues until *F* has been applied to all of the elements
currently in *C*, including those *F* has inserted. Standard
iteration mechanisms, such as the iterators provided in the C++
Standard Template Library (STL), do not directly support complete
traversals. We show generic solutions to the complete traversal
problem by means of two generic algorithms and a container adaptor. We
also discuss the complexity of these solutions, and their scope in
terms of the class of containers they support. This part is based on
a joint paper with Dave Musser and Eric Gamess published
elsewhere.^{1}
The second part of the talk addresses the question of how general this
iteration scheme (CT) is. The way of approaching this question is by
comparing the CT problem with well-known problems such as the
computation of the transitive closure (TC) of a relation, and the
computation of the closure of a set under a given relation (CR). We
formally define the meaning of *problem* and the relation *is an instance of* among problems, to prove that TC and CR are
indeed instances of the CT problem, and present a diagram which
depicts the relation *is an instance of* among CT, TC, CR, and
other well-known problems.