Classes | |
| class | MemPool |
| Pool allocator for the subtree and parse tree classes (homebrew and not compliant to ANSI allocator requirements) (c) copyright Maarten Keijzer 1999, 2000. More... | |
| class | Node_alloc |
| class | Standard_alloc |
| class | Standard_Node_alloc |
| class | Tree_alloc |
| class | parse_tree |
Functions | |
| template<class T> | |
| void | do_the_swap (T &a, T &b) |
| This ones defined because gcc does not always implement namespaces. | |
Permission to copy, use, modify, sell and distribute this software is granted provided this copyright notice appears in all copies. This software is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.
Permission to modify the code and to distribute modified code is granted, provided the above notices as well as this one are retained, and a notice that the code was modified is included with the above copyright notice.
Usage information.
class Node (your node in the tree) must have the following implemented:
Arity ******
int arity(void) const
Note: the default constructor of a Node should provide a Node with arity 0!
Evaluation ******
A parse_tree is evaluated through one of it's apply() members:
1) parse_tree::apply(RetVal)
is the simplest evaluation, it will call
RetVal Node::operator()(RetVal, subtree<Node, RetVal>::const_iterator)
(Unfortunately the first RetVal argument is mandatory (although you might not need it. This is because MSVC does not support member template functions properly. If it cannot deduce the template arguments (as is the case in templatizing over return value) you are not allowed to specify them. calling tree.apply<double>() would result in a syntax error. That is why you have to call tree.apply(double()) instead.)
2) parse_tree::apply(RetVal v, It values)
will call:
RetVal Node::operator()(RetVal, subtree<... , It values)
where It is whatever type you desire (most of the time this will be a std::vector containing the values of your variables);
3) parse_tree::apply(RetVal, It values, It2 moreValues)
will call:
RetVal Node::operator()(RetVal, subtree<... , It values, It2 moreValues)
although I do not see the immediate use of this, however...
4) parse_tree::apply(RetVal, It values, It2 args, It3 adfs)
that calls:
RetVal Node::operator()(subtree<... , It values, It2 args, It3 adfs)
can be useful for implementing adfs.
In general it is a good idea to leave the specifics of the arguments open so that different ways of evaluation remain possible. Implement the simplest eval as:
template <class it>=""> RetVal operator()(RetVal dummy, It begin) const
Internal Structure ******
A parse_tree has two template arguments: the Node and the ReturnValue produced by evaluating the node. The structure of the tree is defined through a subtree class that has the same two template arguments.
The nodes are stored in a tree like :
node4 / \ node3 node2 / \ node1 node0
where nodes 2 and 4 have arity 2 and nodes 0,1 and 3 arity 0 (terminals)
The nodes are subtrees, containing the structure of the tree, together with its size and depth. They contain a Node, the user defined template argument. To access these nodes from a subtree, use operator-> or operator*.
The numbers behind the nodes define a reverse-polish or postfix traversel through the tree. The parse_tree defines iterators on the tree such that
tree.begin() points at the subtree at node0 and tree.back() returns the subtree at node4, the complete tree
Likewise operator[] is defined on the tree, such that:
tree[0] will return the subtree at node0, while tree[2] will return the subtree at node2
Assigments of subtrees is protected so that the code:
tree[2] = tree[0];
will not crash and result in a tree structured as:
node4 / \ node3 node0
Note that the rank numbers no longer specify their place in the tree:
tree[0] still points at node0, but tree[1] now points to node3 and tree[2] points at the root node4
Embedded iterators are implemented to iterate over nodes rather than subtrees. So an easy way to copy your tree to a std::vector is:
std::vector<Node> vec(tree.size()); copy(tree.ebegin(), tree.eend(), vec.begin());
You can also copy it to an std::ostream_iterator with this technique, given that your Node implements an appropriate operator<<. Reinitializing a tree with the std::vector is also simple:
tree.clear(); copy(vec.begin(), vec.end(), back_inserter(tree));
or from an std::istream:
copy(std::istream_iterator<T>(my_stream), std::istream_iterator<T>(), back_inserter(tree));
Note that the back_inserter must be used as there is no resize member in the parse_tree. back_inserter will use the push_back member from the parse_tree
1.5.5