Motivation

Traversal Library is a library for traversing and manipulating hierarchical data structures built from standard building blocks such as standard containers, tuples, structs, variants, pointers and so on. Such data structures are commonplace in modern software, describing formats such as XML, parser output, document generator input and other naturally hierarchical structures. Such programs typically consist of large amounts of boilerplate code concerned with traversing the members of the structure. Such code suffers from several disadvantages:

The Traversal Library provides generic algorithms for traversing hierarchical data structures, eliminating the need for the repetitive traversal code, and facilities for describing which operations to apply and to which points in the structure.

A quick example

How do you increase every element in a vector of vectors of vectors of ints?

typedef std::vector<int> int_v;
typedef std::vector<int_v> int_vv;
typedef std::vector<int_vv> int_vvv;

int_vvv v; // Filled in some interesting way with application data

A typical piece of code with the aid of Boost.Lambda might look like:

std::for_each(v.begin(), v.end(), 
    ll::for_each(bind(call_begin(), _1), bind(call_end(), _1), 
        protect(ll::for_each(bind(call_begin(), _1), bind(call_end(), _1), 
            protect(_1 += increase))))); // The only interesting bit

Its certainly not the simplest Boost.Lambda expression you'll ever see, and involves using some of the more advanced parts of the library, such as nested STL algorithm invocation, and the protect facility.

Alternatively, you can roll your own implementation, and do things more directly:

for(int_vvv::iterator it = v.begin(), vvv_end = v.end();
    it != vvv_end; ++it)
    for(int_vv::iterator jt = it->begin(), vv_end = it->end();
        jt != vv_end; ++jt)
        for(int_v::iterator kt = jt->begin(), v_end = jt->end();
            kt != v_end; ++kt)
                *kt += increase; // The only interesting bit

Notice the huge amount of boilerplate code required, both cases only the last line of code really involves what we originally wanted to do, the rest of the code is caught up in repetitive logic to traverse the hierarchical data structure involved.

With a little help from Boost.Lambda, the Traversal Library permits us to replace the above code with:

traversal::full(v, traversal::restrict<void(int&)>(_1 += increase));

The code states that we want to walk the full data structure, and selectively apply an increase, restricted to elements of type int. Its certainly shorter than the original implementations, and hopefully with some understanding of Traversal Library the intent will be significantly clearer.

The above example is slightly contrived. Now imagine we have a complex recursive data structure describing a company, its departments, its sub departments, the employees within them, and the details of those employees, including their names and salaries. Various components of the structure may be defined by standard containers, user defined structs, possibly Boost.Variants or Optionals, and various built in types. If we wish to increment the ints representing the salaries of all the employees by a fixed increase, obviously this will require more complex code:

traversal::full(v, traversal::restrict<void(int&)>(_1 += increase)); // Its the same thing!

We didn't need to change any code at all! How is this achieved? The Traversal Library can derive a recursive traversal over its input, based upon the structure of its argument type. This generation process mitigates the need for the user to implement boring repetitive traversal code, bound to a particular data type. This permits us to concentrate our efforts on the operations we wish to perform on parts of the data structure. This is the essence of the Traversal Library, operations that require actions only on small parts of a data structure are encoded using standard traversal strategies, and typing information is used to indentify the parts of the structure that require action. Contrast this approach with the hand coded traversal and modification implementations using either std::for_each or direct use of loops, both would need rewriting if the underlying data structure changes, as so much of the code is directly tied to the details of the specific types being used.