tree.hh File Reference

A tree library with hashconsing and maximal sharing capabilities. More...

#include "symbol.hh"
#include "node.hh"
#include <vector>
#include <map>
#include <assert.h>

Go to the source code of this file.

Classes
class	CTree
	A CTree = (Node x [CTree]) is a Node associated with a list of subtrees called branches. More...
Functions
int	tree2int (Tree t)
	if t has a node of type int, return it otherwise error
float	tree2float (Tree t)
	if t has a node of type float, return it otherwise error
const char *	tree2str (Tree t)
	if t has a node of type symbol, return its name otherwise error
void *	tree2ptr (Tree t)
	if t has a node of type ptr, return it otherwise error
void *	getUserData (Tree t)
	if t has a node of type symbol, return the associated user data
Tree	rec (Tree body)
	create a de Bruijn recursive tree
Tree	rec (Tree id, Tree body)
	create a symbolic recursive tree
bool	isRec (Tree t, Tree &body)
	is t a de Bruijn recursive tree
bool	isRec (Tree t, Tree &id, Tree &body)
	is t a symbolic recursive tree
Tree	ref (int level)
	create a de Bruijn recursive reference
Tree	ref (Tree id)
	create a symbolic recursive reference
bool	isRef (Tree t, int &level)
	is t a de Bruijn recursive reference
bool	isRef (Tree t, Tree &id)
	is t a symbolic recursive reference
bool	isOpen (Tree t)
	t contains free de Bruijn references
bool	isClosed (Tree t)
	t dont contain free de Bruijn ref

---

Detailed Description

A tree library with hashconsing and maximal sharing capabilities.

A tree library with hashconsing and maximal sharing capabilities.

API:

• tree (n) : tree of node n with no branch
• tree (n, t1) : tree of node n with a branch t
• tree (n, t1,...,tm) : tree of node n with m branches t1,...,tm

Useful conversions :

• int tree2int (t) : if t has a node of type int, return it otherwise error
• float tree2float (t) : if t has a node of type float, return it otherwise error
• const char* tree2str (t) : if t has a node of type symbol, return its name otherwise error
• void* tree2ptr (t) : if t has a node of type ptr, return it otherwise error

Pattern matching :

• if (isTree (t, n)) ... : t has node n and no branches;
• if (isTree (t, n, &t1) ... : t has node n and 1 branch, t1 is set accordingly;
• if (isTree (t, n, &t1...&tm)... : t has node n and m branches, ti's are set accordingly;

Accessors :

• t->node() : the node of t { return fNode; }
• t->height() : lambda height such that H(x)=0, H(.e)=1+H(e), H(e*f)=max(H(e),H(f))
• t->arity() : the number of branches of t { return fArity; }
• t->branch(i) : the ith branch of t

Attributs :

• t->attribut() : return the attribut (also a tree) of t
• t->attribut(t') : set the attribut of t to t'

Properties:

If p and q are two CTree pointers : p != q <=> *p != *q

Definition in file tree.hh.