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... | |
class | Tabber |
Typedefs | |
typedef CTree * | Tree |
typedef map< Tree, Tree > | plist |
typedef vector< Tree > | tvec |
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 |
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.
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 }
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 }
bool isClosed | ( | Tree | t | ) | [inline] |
t dont contain free de Bruijn ref
Definition at line 225 of file tree.hh.
References CTree::aperture().
Referenced by calcliftn(), and deBruijn2Sym().
bool isOpen | ( | Tree | t | ) | [inline] |
t contains free de Bruijn references
Definition at line 224 of file tree.hh.
References CTree::aperture().
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 }
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(), and sigvisitor::visit().
is t a symbolic recursive reference
Definition at line 111 of file recursive-tree.cpp.
References isTree().
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(), 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 }
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 }
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 }
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 }
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 }
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 }
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(), 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(), 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 }
Definition at line 149 of file recursive-tree.cpp.
References liftn().
Referenced by listLift(), and propagate().
00149 { return liftn(t, 1); }
ostream& operator<< | ( | ostream & | s, | |
Tabber & | t | |||
) | [inline] |
Definition at line 249 of file tree.hh.
References Tabber::print().
00249 { return t.print(s); }
ostream& operator<< | ( | ostream & | s, | |
const CTree & | t | |||
) | [inline] |
Definition at line 198 of file tree.hh.
References CTree::print().
00198 { return t.print(s); }
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 }
create a de Bruijn recursive tree
Definition at line 54 of file recursive-tree.cpp.
References tree().
Referenced by calcDeBruijn2Sym(), calcliftn(), calcsubstitute(), computePrivatisation(), propagate(), and sigMap().
create a symbolic recursive reference
Definition at line 106 of file recursive-tree.cpp.
References tree().
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(), and propagate().
00065 { 00066 assert(level > 0); 00067 return tree(DEBRUIJNREF, tree(level)); // reference to enclosing recursive tree starting from 1 00068 }
Tree tree | ( | const Node & | n, | |
const Tree & | a, | |||
const Tree & | b, | |||
const Tree & | c, | |||
const Tree & | d, | |||
const Tree & | e | |||
) | [inline] |
Definition at line 179 of file tree.hh.
References CTree::make().
00179 { Tree br[]= {a,b,c,d,e}; return CTree::make(n, 5, br); }
Tree tree | ( | const Node & | n, | |
const Tree & | a, | |||
const Tree & | b, | |||
const Tree & | c, | |||
const Tree & | d | |||
) | [inline] |
Definition at line 177 of file tree.hh.
References CTree::make().
00177 { Tree br[]= {a,b,c,d}; return CTree::make(n, 4, br); }
Definition at line 176 of file tree.hh.
References CTree::make().
00176 { Tree br[]= {a,b,c}; return CTree::make(n, 3, br); }
Definition at line 175 of file tree.hh.
References CTree::make().
00175 { Tree br[]= {a,b}; return CTree::make(n, 2, br); }
Definition at line 174 of file tree.hh.
References CTree::make().
00174 { Tree br[]= {a}; return CTree::make(n, 1, br); }
Definition at line 173 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(), 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(), declareMetadata(), divExtendedNums(), divNums(), docDgm(), docEqn(), docLst(), 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(), printdocheader(), 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(), sigNumEntry(), sigOutput(), sigPrefix(), sigProj(), sigRDTbl(), sigReal(), sigSelect2(), sigSelect3(), sigTable(), sigTuple(), sigTupleAccess(), sigVBargraph(), sigVSlider(), sigWRTbl(), simplification(), Occurrences::specificKey(), subNums(), subst(), substitute(), substkey(), tmap(), uiFolder(), uiWidget(), unquote(), and yyparse().
00173 { Tree br[1]; return CTree::make(n, 0, br); }
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 }
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 }
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 }
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 }
const char* tree2str | ( | Tree | t | ) |
if t has a node of type symbol, return its name otherwise error
Definition at line 292 of file tree.cpp.
References ERROR, isSym(), name(), and CTree::node().
Referenced by Description::addGroup(), Description::addWidget(), applyList(), DocCompiler::compileLateq(), declareMetadata(), SourceReader::expandrec(), ffincfile(), fflibfile(), ffname(), DocCompiler::generateCode(), ScalarCompiler::generateCode(), generateDiagramSchema(), generateInputSlotSchema(), generateInsideSchema(), Compiler::generateMacroInterfaceTree(), generateOutputSlotSchema(), Compiler::generateUserInterfaceTree(), Compiler::generateWidgetCode(), Compiler::generateWidgetMacro(), DocCompiler::getUIDir(), DocCompiler::getUIDocInfos(), legalFileName(), main(), mapGetEqName(), ppsig::print(), boxpp::print(), printdocheader(), realeval(), and writeSchemaFile().
00293 { 00294 Sym s; 00295 if (!isSym(t->node(), &s)) { 00296 ERROR("the node of the tree is not a symbol", t); 00297 } 00298 return name(s); 00299 }
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 }
Definition at line 87 of file tree.cpp.
Referenced by traced_simplification().