A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches. More...
#include <tree.hh>
Public Member Functions | |
const Node & | node () const |
return the content of the tree | |
int | arity () const |
return the number of branches (subtrees) of a tree | |
Tree | branch (int i) const |
return the ith branch (subtree) of a tree | |
unsigned int | hashkey () const |
return the hashkey of the tree | |
int | aperture () const |
return how "open" is a tree in terms of free variables | |
void | setAperture (int a) |
modify the aperture of a tree | |
ostream & | print (ostream &fout) const |
print recursively the content of a tree on a stream | |
Static Public Member Functions | |
static Tree | make (const Node &n, int ar, Tree br[]) |
return a new tree or an existing equivalent one | |
static Tree | make (const Node &n, const tvec &br) |
return a new tree or an existing equivalent one | |
static void | control () |
print the hash table content (for debug purpose) | |
Static Public Attributes | |
static bool | gDetails = false |
Ctree::print() print with more details when true. |
A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches.
A CTree = (Node x [CTree]) is the association of a content Node and a list of subtrees called branches. In order to maximize the sharing of trees, hashconsing techniques are used. Ctrees at different addresses always have a different content. A first consequence of this approach is that a fast equality test on pointers can be used as an equality test on CTrees. A second consequence is that a CTree can NEVER be modified. But a property list is associated to each CTree that can be used to attach arbitrary information to it. Due to the maximal sharing property it is therefore easy to do memoization using these property lists.
Means are also provided to do maximal sharing on recursive trees. The idea is to start from a deBruijn representation and progressively build a classical representation such that alpha-equivalent recursive CTrees are necesseraly identical (and therefore shared).
WARNING : in the current implementation CTrees are allocated but never deleted
Definition at line 109 of file tree.hh.