Copyright 2007-2008 Google Inc. All Rights Reserved.
Licensed under the Apache License, Version 2.0 (the "License")
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an AS IS BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
Author: madscience@google.com (Moshe Looks)
*******************************************************************************
********************************treetree library*******************************
*******************************************************************************
Requirements: g++ and boost. May work on VC as well - let me know if it does or
doesn't. Tests require boost 1.34 or later. If the library itself does/doesn't
work on a particular version of boost and/or g++, let me know... Developed
and tested with g++ 4.
*******************************************************************************
Running tests: execute ./run_tests, you should see something like:
> Running 40 test cases...
>
> *** No errors detected
*******************************************************************************
Installation: treetree is header-only, so simply copy tree.hpp,
iterator_shorthands.hpp, and, optionally, tree_io.hpp and/or tree_iterator.hpp
somewhere in your project or include path.
There is also a utility program tree_convert that munges between different
output formats - this can be simply compiled with:
g++ tree_convert.cpp -o tree_convert
*******************************************************************************
Overview: a generic tree-structured container class that generalizes a doubly
linked list - in addition to previous and next pointers, tree nodes contain a
third pointer to the list of their children. The implementation is efficient,
and the API is expressive. For example, in the code for moses (meta-optimizing
semantic evolutiony search) expressions with the form (x/y)/z are transformed
to the form (x/(y*z). This may be written as:
void transform_nested_divides(subtree<vertex> tr) {
if (tr.root()==id::div && tr.front()==id::div) {
tr.splice(tr.insert_above(tr[1],id::times).begin_child(),tr[0][1]);
tr.erase(tr.flatten(tr[0]));
}
}
Another example, transforming trees representing not(not(x) into x:
void reduce_nots()(subtree<vertex> tr) {
if (tr.root()==id::logical_not && tr.front()==id::logical_not) {
tr.splice(tr.end_child(),tr[0][0]);
tr.erase(tr.begin_child());
}
}
Constant trees may be initialized with the convenient tree_of construct (not a
macro) inspired by boost.assign, e.g.
tree<int> foo = tree_of(1)(2, 3, tree_of(4)(5, 6));
initializes foo as a tree with 1 in the root and three children; two leaf
children 2 and 3, and a subtree child with root 4 and leaf children 5 and 6.
There's much more cool stuff and some additional documentation, see tree.hpp
and test_runner.cpp.
Everything is in namespace 'the', but this can be changed if you'd like by
setting the macro TREE_TREE_NAMESPACE to whatever.
*******************************************************************************
Acknowledgements: inspired partly by Kasper Peeters' tree.hh
(http://www.aei.mpg.de/~peekas/tree/). Thanks to Ari Heljakka for some feature
suggestions.
Have fun!!
- Moshe Looks, 7/30/2008