CTree Class Reference

A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches. More...

#include <tree.hh>

Collaboration diagram for CTree:
Collaboration graph
[legend]

List of all members.

Public Member Functions

const Nodenode () 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.

Detailed Description

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.


The documentation for this class was generated from the following files:
Generated by  doxygen 1.6.2-20100208