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>
Include dependency graph for tree.hh:
This graph shows which files directly or indirectly include this file:

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...
class  Tabber

Typedefs

typedef CTreeTree
typedef map< Tree, Treeplist
typedef vector< Treetvec

Functions

Tree tree (const Node &n)
Tree tree (const Node &n, const Tree &a)
Tree tree (const Node &n, const Tree &a, const Tree &b)
Tree tree (const Node &n, const Tree &a, const Tree &b, const Tree &c)
Tree tree (const Node &n, const Tree &a, const Tree &b, const Tree &c, const Tree &d)
Tree tree (const Node &n, const Tree &a, const Tree &b, const Tree &c, const Tree &d, const Tree &e)
int tree2int (Tree t)
 if t has a node of type int, return it otherwise error
double tree2float (Tree t)
 if t has a node of type float, return it otherwise error
double tree2double (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
bool isTree (const Tree &t, const Node &n)
bool isTree (const Tree &t, const Node &n, Tree &a)
bool isTree (const Tree &t, const Node &n, Tree &a, Tree &b)
bool isTree (const Tree &t, const Node &n, Tree &a, Tree &b, Tree &c)
bool isTree (const Tree &t, const Node &n, Tree &a, Tree &b, Tree &c, Tree &d)
bool isTree (const Tree &t, const Node &n, Tree &a, Tree &b, Tree &c, Tree &d, Tree &e)
ostream & operator<< (ostream &s, const CTree &t)
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
Tree lift (Tree t)
Tree deBruijn2Sym (Tree t)
void updateAperture (Tree t)
ostream & operator<< (ostream &s, Tabber &t)

Variables

Tabber TABBER

Detailed Description

A tree library with hashconsing and maximal sharing capabilities.

A tree library with hashconsing and maximal sharing capabilities.

API:

Useful conversions :

Pattern matching :

Accessors :

Attributs :

Properties:

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

Definition in file tree.hh.


Typedef Documentation

typedef map<Tree, Tree> plist

Definition at line 89 of file tree.hh.

typedef CTree* Tree

Definition at line 86 of file tree.hh.

typedef vector<Tree> tvec

Definition at line 90 of file tree.hh.


Function Documentation

Tree deBruijn2Sym ( Tree  t  ) 

Definition at line 223 of file recursive-tree.cpp.

References calcDeBruijn2Sym(), CTree::getProperty(), isClosed(), and CTree::setProperty().

Referenced by calcDeBruijn2Sym(), mapPrepareEqSig(), and ScalarCompiler::prepare().

00224 {
00225     assert(isClosed(t));
00226     Tree t2 = t->getProperty(DEBRUIJN2SYM);
00227 
00228     if (!t2) {
00229         t2 = calcDeBruijn2Sym(t);
00230         t->setProperty(DEBRUIJN2SYM, t2);
00231     }
00232     return t2;
00233 }

Here is the call graph for this function:

Here is the caller graph for this function:

void* getUserData ( Tree  t  ) 

if t has a node of type symbol, return the associated user data

Definition at line 386 of file tree.cpp.

References getUserData(), isSym(), and CTree::node().

00387 {
00388     Sym s;
00389     if (isSym(t->node(), &s)) {
00390         return getUserData(s);
00391     } else {
00392         return 0;
00393     }
00394 }

Here is the call graph for this function:

bool isClosed ( Tree  t  )  [inline]

t dont contain free de Bruijn ref

Definition at line 229 of file tree.hh.

References CTree::aperture().

Referenced by calcliftn(), and deBruijn2Sym().

Here is the call graph for this function:

Here is the caller graph for this function:

bool isOpen ( Tree  t  )  [inline]

t contains free de Bruijn references

Definition at line 228 of file tree.hh.

References CTree::aperture().

Here is the call graph for this function:

bool isRec ( Tree  t,
Tree id,
Tree body 
)

is t a symbolic recursive tree

Definition at line 95 of file recursive-tree.cpp.

References CTree::getProperty(), and isTree().

00096 {
00097     if (isTree(t, SYMREC, var)) {
00098         body = t->getProperty(RECDEF);
00099         return true;
00100     } else {
00101         return false;
00102     }
00103 }

Here is the call graph for this function:

bool isRec ( Tree  t,
Tree body 
)

is t a de Bruijn recursive tree

Definition at line 59 of file recursive-tree.cpp.

References isTree().

Referenced by annotate(), calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), computePrivatisation(), DocCompiler::generateRecProj(), ScalarCompiler::generateRecProj(), getSubSignals(), infereSigOrder(), infereSigType(), ppsig::print(), printSignal(), recomputeAperture(), sigMap(), sigMapRename(), and sigvisitor::visit().

00060 {
00061     return isTree(t, DEBRUIJN, body);
00062 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool isRef ( Tree  t,
Tree id 
)

is t a symbolic recursive reference

Definition at line 111 of file recursive-tree.cpp.

References isTree().

00112 {
00113     return isTree(t, SYMREC, v);
00114 }

Here is the call graph for this function:

bool isRef ( Tree  t,
int &  level 
)

is t a de Bruijn recursive reference

Definition at line 70 of file recursive-tree.cpp.

References isInt(), isTree(), and CTree::node().

Referenced by calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), infereSigOrder(), ppsig::print(), printSignal(), recomputeAperture(), sigMapRename(), and sigvisitor::visit().

00071 {
00072     Tree    u;
00073 
00074     if (isTree(t, DEBRUIJNREF, u)) {
00075         return isInt(u->node(), &level);
00076     } else {
00077         return false;
00078     }
00079 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool isTree ( const Tree t,
const Node n,
Tree a,
Tree b,
Tree c,
Tree d,
Tree e 
)

Definition at line 370 of file tree.cpp.

References CTree::arity(), CTree::branch(), and CTree::node().

00371 { 
00372     if ((t->node() == n) && (t->arity() == 5)) { 
00373         a=t->branch(0); 
00374         b=t->branch(1); 
00375         c=t->branch(2); 
00376         d=t->branch(3); 
00377         e=t->branch(4); 
00378         return true; 
00379     } else {
00380         return false;
00381     }
00382 }

Here is the call graph for this function:

bool isTree ( const Tree t,
const Node n,
Tree a,
Tree b,
Tree c,
Tree d 
)

Definition at line 357 of file tree.cpp.

References CTree::arity(), CTree::branch(), and CTree::node().

00358 { 
00359     if ((t->node() == n) && (t->arity() == 4)) { 
00360         a=t->branch(0); 
00361         b=t->branch(1); 
00362         c=t->branch(2); 
00363         d=t->branch(3); 
00364         return true; 
00365     } else {
00366         return false;
00367     }
00368 }

Here is the call graph for this function:

bool isTree ( const Tree t,
const Node n,
Tree a,
Tree b,
Tree c 
)

Definition at line 345 of file tree.cpp.

References CTree::arity(), CTree::branch(), and CTree::node().

00346 { 
00347     if ((t->node() == n) && (t->arity() == 3)) { 
00348         a=t->branch(0); 
00349         b=t->branch(1); 
00350         c=t->branch(2); 
00351         return true; 
00352     } else {
00353         return false;
00354     }
00355 }

Here is the call graph for this function:

bool isTree ( const Tree t,
const Node n,
Tree a,
Tree b 
)

Definition at line 334 of file tree.cpp.

References CTree::arity(), CTree::branch(), and CTree::node().

00335 { 
00336     if ((t->node() == n) && (t->arity() == 2)) { 
00337         a=t->branch(0); 
00338         b=t->branch(1); 
00339         return true; 
00340     } else {
00341         return false;
00342     }
00343 }

Here is the call graph for this function:

bool isTree ( const Tree t,
const Node n,
Tree a 
)

Definition at line 324 of file tree.cpp.

References CTree::arity(), CTree::branch(), and CTree::node().

00325 { 
00326     if ((t->node() == n) && (t->arity() == 1)) { 
00327         a=t->branch(0); 
00328         return true; 
00329     } else {
00330         return false;
00331     }
00332 }

Here is the call graph for this function:

bool isTree ( const Tree t,
const Node n 
)

Definition at line 319 of file tree.cpp.

References CTree::node().

Referenced by isBoxAbstr(), isBoxAccess(), isBoxAppl(), isBoxButton(), isBoxCase(), isBoxCheckbox(), isBoxComponent(), isBoxCut(), isBoxEnvironment(), isBoxError(), isBoxFConst(), isBoxFFun(), isBoxFVar(), isBoxHBargraph(), isBoxHGroup(), isBoxHSlider(), isBoxIdent(), isBoxIPar(), isBoxIProd(), isBoxISeq(), isBoxISum(), isBoxLibrary(), isBoxMerge(), isBoxModifLocalDef(), isBoxNumEntry(), isBoxPar(), isBoxPatternMatcher(), isBoxPatternVar(), isBoxPrim0(), isBoxPrim1(), isBoxPrim2(), isBoxPrim3(), isBoxPrim4(), isBoxPrim5(), isBoxRec(), isBoxSeq(), isBoxSlot(), isBoxSplit(), isBoxSymbolic(), isBoxTGroup(), isBoxVBargraph(), isBoxVGroup(), isBoxVSlider(), isBoxWire(), isBoxWithLocalDef(), isClosure(), isDocDgm(), isDocEqn(), isDocLst(), isDocMtd(), isDocNtc(), isDocTxt(), isImportFile(), isPathCurrent(), isPathParent(), isPathRoot(), isProj(), isRec(), isRef(), isSigAttach(), isSigBinOp(), isSigButton(), isSigCheckbox(), isSigDelay1(), isSigDocAccessTbl(), isSigDocConstantTbl(), isSigDocWriteTbl(), isSigFConst(), isSigFFun(), isSigFixDelay(), isSigFloatCast(), isSigFVar(), isSigGen(), isSigHBargraph(), isSigHSlider(), isSigInput(), isSigIntCast(), isSigIota(), isSigNumEntry(), isSigOutput(), isSigPrefix(), isSigRDTbl(), isSigSelect2(), isSigSelect3(), isSigTable(), isSigTuple(), isSigTupleAccess(), isSigVBargraph(), isSigVSlider(), isSigWRTbl(), isUiFolder(), and isUiWidget().

00320 { 
00321     return (t->node() == n);
00322 }

Here is the call graph for this function:

Tree lift ( Tree  t  ) 

Definition at line 149 of file recursive-tree.cpp.

References liftn().

Referenced by listLift(), and propagate().

00149 { return liftn(t, 1); }

Here is the call graph for this function:

Here is the caller graph for this function:

ostream& operator<< ( ostream &  s,
Tabber t 
) [inline]

Definition at line 253 of file tree.hh.

References Tabber::print().

00253 { return t.print(s); }

Here is the call graph for this function:

ostream& operator<< ( ostream &  s,
const CTree t 
) [inline]

Definition at line 202 of file tree.hh.

References CTree::print().

00202 { return t.print(s); }

Here is the call graph for this function:

Tree rec ( Tree  id,
Tree  body 
)

create a symbolic recursive tree

Definition at line 88 of file recursive-tree.cpp.

References CTree::setProperty(), and tree().

00089 {
00090     Tree t = tree(SYMREC, var);
00091     t->setProperty(RECDEF, body);
00092     return t;
00093 }

Here is the call graph for this function:

Tree rec ( Tree  body  ) 

create a de Bruijn recursive tree

Definition at line 54 of file recursive-tree.cpp.

References tree().

Referenced by calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), computePrivatisation(), propagate(), sigMap(), and sigMapRename().

00055 {
00056     return tree(DEBRUIJN, body);
00057 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree ref ( Tree  id  ) 

create a symbolic recursive reference

Definition at line 106 of file recursive-tree.cpp.

References tree().

00107 {
00108     return tree(SYMREC, id);            // reference to a symbolic id
00109 }

Here is the call graph for this function:

Tree ref ( int  level  ) 

create a de Bruijn recursive reference

Definition at line 64 of file recursive-tree.cpp.

References tree().

Referenced by calcDeBruijn2Sym(), calcliftn(), propagate(), and sigMapRename().

00065 {
00066     assert(level > 0);
00067     return tree(DEBRUIJNREF, tree(level));  // reference to enclosing recursive tree starting from 1
00068 }

Here is the call graph for this function:

Here is the caller graph for this function:

Tree tree ( const Node n,
const Tree a,
const Tree b,
const Tree c,
const Tree d,
const Tree e 
) [inline]

Definition at line 183 of file tree.hh.

References CTree::make().

00183 { Tree br[]= {a,b,c,d,e}; return CTree::make(n, 5, br); }

Here is the call graph for this function:

Tree tree ( const Node n,
const Tree a,
const Tree b,
const Tree c,
const Tree d 
) [inline]

Definition at line 181 of file tree.hh.

References CTree::make().

00181 { Tree br[]= {a,b,c,d}; return CTree::make(n, 4, br); }

Here is the call graph for this function:

Tree tree ( const Node n,
const Tree a,
const Tree b,
const Tree c 
) [inline]

Definition at line 180 of file tree.hh.

References CTree::make().

00180 { Tree br[]= {a,b,c}; return CTree::make(n, 3, br); }

Here is the call graph for this function:

Tree tree ( const Node n,
const Tree a,
const Tree b 
) [inline]

Definition at line 179 of file tree.hh.

References CTree::make().

00179 { Tree br[]= {a,b}; return CTree::make(n, 2, br); }

Here is the call graph for this function:

Tree tree ( const Node n,
const Tree a 
) [inline]

Definition at line 178 of file tree.hh.

References CTree::make().

00178 { Tree br[]= {a}; return CTree::make(n, 1, br); }

Here is the call graph for this function:

Tree tree ( const Node n  )  [inline]

Definition at line 177 of file tree.hh.

References CTree::make().

Referenced by addEnv(), addNums(), annotate(), autoName(), xtended::box(), boxAbstr(), boxAccess(), boxAppl(), boxButton(), boxCase(), boxCheckbox(), boxComplexity(), boxComponent(), boxCut(), boxEnvironment(), boxError(), boxFConst(), boxFFun(), boxFVar(), boxHBargraph(), boxHGroup(), boxHSlider(), boxIdent(), boxInt(), boxIPar(), boxIProd(), boxISeq(), boxISum(), boxLibrary(), boxMerge(), boxModifLocalDef(), boxNumEntry(), boxPar(), boxPatternMatcher(), boxPatternVar(), boxPrim0(), boxPrim1(), boxPrim2(), boxPrim3(), boxPrim4(), boxPrim5(), boxReal(), boxRec(), boxSeq(), boxSlot(), boxSplit(), boxSymbolic(), boxTGroup(), boxVBargraph(), boxVGroup(), boxVSlider(), boxWire(), boxWithLocalDef(), calcDeBruijn2Sym(), closure(), combineDivLeft(), computePrivatisation(), TanPrim::computeSigOutput(), SqrtPrim::computeSigOutput(), SinPrim::computeSigOutput(), RintPrim::computeSigOutput(), RemainderPrim::computeSigOutput(), PowPrim::computeSigOutput(), MinPrim::computeSigOutput(), MaxPrim::computeSigOutput(), LogPrim::computeSigOutput(), Log10Prim::computeSigOutput(), FmodPrim::computeSigOutput(), FloorPrim::computeSigOutput(), ExpPrim::computeSigOutput(), CosPrim::computeSigOutput(), CeilPrim::computeSigOutput(), AtanPrim::computeSigOutput(), Atan2Prim::computeSigOutput(), AsinPrim::computeSigOutput(), AcosPrim::computeSigOutput(), cons(), declareAutoDoc(), declareMetadata(), divExtendedNums(), divNums(), docDgm(), docEqn(), docLst(), docMtd(), docNtc(), docTxt(), encodeName(), ffunction(), gcd(), ScalarCompiler::generateButton(), ScalarCompiler::generateCheckbox(), ScalarCompiler::generateHBargraph(), ScalarCompiler::generateHSlider(), ScalarCompiler::generateNumEntry(), ScalarCompiler::generateVBargraph(), ScalarCompiler::generateVSlider(), getBoxType(), getEvalProperty(), getInferredType(), getPMProperty(), getSigOrder(), importFile(), infereRecType(), inverseNum(), iteratePar(), iterateProd(), iterateSeq(), iterateSum(), label2path(), liftn(), main(), makePrivatisationKey(), makePrivatisationLabel(), OccMarkup::mark(), minusNum(), mulNums(), normalizeDelay1Term(), mterm::normalizedTree(), aterm::normalizedTree(), pathCurrent(), pathParent(), pathRoot(), patternSimplification(), printheader(), Klass::printMetadata(), propagate(), pushNewLayer(), realeval(), rec(), ref(), setColorProperty(), Occurrences::setCount(), setDefNameProperty(), setDefProp(), setEvalProperty(), OccMarkup::setOcc(), setPMProperty(), ScalarCompiler::setSharingCount(), DocCompiler::setSharingCount(), setSigNickname(), shprkey(), sigAttach(), sigBinOp(), sigButton(), sigCheckbox(), sigDelay1(), sigDocAccessTbl(), sigDocConstantTbl(), sigDocWriteTbl(), sigFConst(), sigFFun(), sigFixDelay(), sigFloatCast(), sigFVar(), sigGen(), sigHBargraph(), sigHSlider(), sigInput(), sigInt(), sigIntCast(), sigIota(), sigMap(), sigMapRename(), sigNumEntry(), sigOutput(), sigPow(), sigPrefix(), sigProj(), sigRDTbl(), sigReal(), sigSelect2(), sigSelect3(), sigTable(), sigTuple(), sigTupleAccess(), sigVBargraph(), sigVSlider(), sigWRTbl(), simplification(), Occurrences::specificKey(), subNums(), subst(), substitute(), substkey(), tmap(), uiFolder(), uiWidget(), unquote(), writeSchemaFile(), and yyparse().

00177 { Tree br[1]; return CTree::make(n, 0, br); }

Here is the call graph for this function:

double tree2double ( Tree  t  ) 

if t has a node of type float, return it otherwise error

Definition at line 276 of file tree.cpp.

References ERROR, isDouble(), isInt(), and CTree::node().

Referenced by Description::addWidget().

00277 {
00278     double   x;
00279     int     i;
00280 
00281     if (isInt(t->node(), &i)) {
00282         x = double(i);
00283     } else if (isDouble(t->node(), &x)) {
00284         //nothing to do
00285     } else {
00286         ERROR("the node of the tree is not a float nor an int", t);
00287     }
00288     return double(x);
00289 }   

Here is the call graph for this function:

Here is the caller graph for this function:

double tree2float ( Tree  t  ) 

if t has a node of type float, return it otherwise error

Definition at line 260 of file tree.cpp.

References ERROR, isDouble(), isInt(), and CTree::node().

Referenced by eval2double(), ScalarCompiler::generateHSlider(), ScalarCompiler::generateNumEntry(), ScalarCompiler::generateVSlider(), Compiler::generateWidgetCode(), Compiler::generateWidgetMacro(), infereSigType(), and DocCompiler::prepareIntervallicUI().

00261 {
00262     double   x;
00263     int     i;
00264 
00265     if (isInt(t->node(), &i)) {
00266         x = double(i);
00267     } else if (isDouble(t->node(), &x)) {
00268         //nothing to do
00269     } else {
00270         ERROR("the node of the tree is not a float nor an int", t);
00271     }
00272     return x;
00273 }   

Here is the call graph for this function:

Here is the caller graph for this function:

int tree2int ( Tree  t  ) 

if t has a node of type int, return it otherwise error

Definition at line 244 of file tree.cpp.

References ERROR, isDouble(), isInt(), and CTree::node().

Referenced by Description::addGroup(), annotate(), boxComplexity(), eval2int(), ffargtype(), ffrestype(), Compiler::generateUserInterfaceTree(), getRecursivness(), getSigOrder(), infereFConstType(), infereFVarType(), and isBoxPatternMatcher().

00245 {
00246     double  x;
00247     int     i;
00248 
00249     if (isInt(t->node(), &i)) {
00250         // nothing to do
00251     } else if (isDouble(t->node(), &x)) {
00252         i = int(x);
00253     } else {
00254         ERROR("the node of the tree is not an int nor a float", t);
00255     }
00256     return i;
00257 }   

Here is the call graph for this function:

Here is the caller graph for this function:

void* tree2ptr ( Tree  t  ) 

if t has a node of type ptr, return it otherwise error

Definition at line 302 of file tree.cpp.

References ERROR, isPointer(), and CTree::node().

Referenced by getColorProperty(), getInferredType(), OccMarkup::getOcc(), isBoxPatternMatcher(), isInEnv(), and searchEnv().

00303 {
00304     void*   x;
00305     if (! isPointer(t->node(), &x)) {
00306         ERROR("the node of the tree is not a pointer", t);
00307     }
00308     return x;
00309 }   

Here is the call graph for this function:

Here is the caller graph for this function:

const char* tree2str ( Tree  t  ) 
void updateAperture ( Tree  t  ) 

Definition at line 320 of file recursive-tree.cpp.

References markOpen(), and recomputeAperture().

00321 {
00322     markOpen(t);
00323     recomputeAperture(t, NULL);
00324 }

Here is the call graph for this function:


Variable Documentation

Definition at line 87 of file tree.cpp.

Referenced by traced_simplification().

Generated on Thu Jul 15 16:15:52 2010 for FAUST compiler by  doxygen 1.6.3