#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. | |
Private Member Functions | |
CTree (unsigned int hk, const Node &n, const tvec &br) | |
construction is private, uses tree::make instead | |
bool | equiv (const Node &n, const tvec &br) const |
used to check if an equivalent tree already exists | |
Static Private Member Functions | |
static unsigned int | calcTreeHash (const Node &n, const tvec &br) |
compute the hash key of a tree according to its node and branches | |
static int | calcTreeAperture (const Node &n, const tvec &br) |
compute how open is a tree | |
Private Attributes | |
Tree | fNext |
next tree in the same hashtable entry | |
Node | fNode |
the node content of the tree | |
void * | fType |
the type of a tree | |
plist | fProperties |
the properties list attached to the tree | |
unsigned int | fHashKey |
the hashtable key | |
int | fAperture |
how "open" is a tree (synthezised field) | |
tvec | fBranch |
the subtrees | |
Static Private Attributes | |
static const int | kHashTableSize = 510511 |
size of the hash table used for "hash consing" | |
static Tree | gHashTable [kHashTableSize] |
hash table used for "hash consing" |
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.