Prev Up Next
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.


 

Prev Up Next