#include <bddRelation.h>
Inheritance diagram for bddRelation:
It is possible that there exist bit vectors which are no valid encodings of tuples (because the cardinalities of ranges of attributes do not need to be powers of 2). For speed, these out-of-range bit vectors are not generally excluded from representation. Value mSymTab->getUniverseSize()-1 is represented by all values mSymTab->getUniverseSize()-1 ... 2**mSymTab->getBitNr()-1. This invariant keeps the comparison operations (setEqual, setContains, isEmpty) correct. However, the method for tuple count (getTupleNr) has to restrict to the set of all range tuples (mkRange).
Definition at line 54 of file bddRelation.h.
Public Member Functions | |
| bddRelation (const bddSymTab *pSymTab, bool full) | |
| double | getTupleNr (const set< string > &pFree) const |
| Returns number of tuples, restricted to the given attributes. | |
| string | getElement (unsigned pVarId) |
| Returns a value for attribute at position 'pVarId'. | |
| bool | setEqual (const bddRelation &p) const |
| bool | setContains (const bddRelation &p) const |
| Check if (*this) contains (p). | |
| bool | isEmpty () const |
| void | complement () |
| void | unite (const bddRelation &p) |
| void | intersect (const bddRelation &p) |
| void | exists (const string pAttribute) |
| Existential quantification of (pAttribute). | |
| bool | testVars (string pVarFirst, string pVarLast) |
| Check if there is any BDD node within the given range of attributes. | |
| void | rename (const string pAttributeOld, const string pAttributeNew) |
| Renaming of attributes. | |
| void | printBddInfo (ostream &pS) const |
| void | printNodesPerVarId (ostream &pS, const set< string > &pFree) const |
| Prints the number of nodes per variable id for the BDD. | |
| void | printRelation (ostream &pS, const string pTuple, vector< string > pAttributeList) const |
| Print set of tuples (plain) according to the given order of attributes. | |
| void | printGraph (ostream &pS, const set< string > &pFree) const |
| Prints output graph for BDD. | |
| void | printBDT (ostream &pS) const |
| Prints mBdd as reduced binary decision tree. | |
| bddRelation | getTupleOf (const map< unsigned, string > &pAttributeList) const |
| Cut given relation to single element for all given attributes. | |
Static Public Member Functions | |
| static bddRelation | mkEqual (const bddSymTab *pSymTab, unsigned pVarId, reprNUMBER pConst) |
| Returns all tuples satisfying pVI == pConst. | |
| static bddRelation | mkRange (const bddSymTab *pSymTab, unsigned pVarId) |
| Computes the range of valid values (see comment on top of this class). | |
| static bddRelation | mkEqual (const bddSymTab *pSymTab, const string &pVar1, const string &pVar2) |
| Returns set of all tuples satisfying pVar1 == pVar2. | |
| static bddRelation | mkLess (const bddSymTab *pSymTab, const string &pVar1, const string &pVar2) |
| Returns set of all tuples satisfying pVar1 < pVar2. | |
| static bddRelation | mkAttributeValue (const bddSymTab *pSymTab, const string &pAttributeName, const string &pAttributeValue) |
| Return all tupels where the value of attribute (pAttributeName) is (pAttributeValue). | |
Data Fields | |
| int | mArity |
| For a stronger type check, remember the arity. | |
Private Member Functions | |
| bddRelation (const bddSymTab *pSymTab, const bddBdd &pBdd) | |
| bddRelation (void *) | |
| Forbid implicite casts. | |
| void | operator, (const bddRelation &) |
| Forbid the use of some ugly standard operators. | |
| void | renameSafe (unsigned pVarIdOld, unsigned pVarIdNew, unsigned pBitNr) |
| Renaming of attributes. | |
Static Private Member Functions | |
| static bddRelation | mkEqualPure (const bddSymTab *pSymTab, unsigned pVarId, reprNUMBER pConst) |
| Returns all tuples satisfying pVI == pConst. | |
Private Attributes | |
| const bddSymTab * | mSymTab |
| Symbol table (associated). | |
| bddBdd | mBdd |
| Set of tuples. | |
| bddRelation::bddRelation | ( | const bddSymTab * | pSymTab, | |
| bool | full | |||
| ) | [inline] |
Definition at line 193 of file bddRelation.h.
Referenced by mkEqualPure(), mkRange(), and printGraph().
Here is the caller graph for this function:
Definition at line 204 of file bddRelation.h.
| bddRelation::bddRelation | ( | void * | ) | [private] |
Forbid implicite casts.
| static bddRelation bddRelation::mkEqualPure | ( | const bddSymTab * | pSymTab, | |
| unsigned | pVarId, | |||
| reprNUMBER | pConst | |||
| ) | [inline, static, private] |
Returns all tuples satisfying pVI == pConst.
Definition at line 61 of file bddRelation.h.
References bddRelation(), and bddSymTab::getBitNr().
Referenced by getTupleNr(), and mkEqual().
Here is the call graph for this function:
Here is the caller graph for this function:
| static bddRelation bddRelation::mkEqual | ( | const bddSymTab * | pSymTab, | |
| unsigned | pVarId, | |||
| reprNUMBER | pConst | |||
| ) | [inline, static] |
Returns all tuples satisfying pVI == pConst.
If (pConst) is the max value of pVI (pSymTab->getUniverseSize()-1) then the completion for out-of-range-values is applied. This is to fulfill the invariant of bddRelation (see comment on top of bddRelation.h).
Definition at line 77 of file bddRelation.h.
References complement(), bddSymTab::getUniverseSize(), mkEqualPure(), mkRange(), and unite().
Referenced by crocopat(), getTupleOf(), relStmtFor::interpret(), relNumExprUnOp::interpret(), relExprRegExTerm::interpret(), mkAttributeValue(), mkEqual(), mkLess(), and printRelation().
Here is the call graph for this function:
Here is the caller graph for this function:
| static bddRelation bddRelation::mkRange | ( | const bddSymTab * | pSymTab, | |
| unsigned | pVarId | |||
| ) | [inline, static] |
Computes the range of valid values (see comment on top of this class).
Definition at line 104 of file bddRelation.h.
References bddRelation(), bddSymTab::getBitNr(), bddSymTab::getUniverseSize(), and bddBdd::mkLessEqual().
Referenced by getTupleNr(), and mkEqual().
Here is the call graph for this function:
Here is the caller graph for this function:
| static bddRelation bddRelation::mkEqual | ( | const bddSymTab * | pSymTab, | |
| const string & | pVar1, | |||
| const string & | pVar2 | |||
| ) | [inline, static] |
Returns set of all tuples satisfying pVar1 == pVar2.
Definition at line 116 of file bddRelation.h.
References bddSymTab::getAttributePos(), bddSymTab::getUniverseSize(), intersect(), mkEqual(), and unite().
Here is the call graph for this function:
| static bddRelation bddRelation::mkLess | ( | const bddSymTab * | pSymTab, | |
| const string & | pVar1, | |||
| const string & | pVar2 | |||
| ) | [inline, static] |
Returns set of all tuples satisfying pVar1 < pVar2.
Assertion: pVar1's position <= pVar2's position in the variable order.
Definition at line 138 of file bddRelation.h.
References bddSymTab::getAttributePos(), bddSymTab::getUniverseSize(), intersect(), mkEqual(), and unite().
Referenced by crocopat().
Here is the call graph for this function:
Here is the caller graph for this function:
| static bddRelation bddRelation::mkAttributeValue | ( | const bddSymTab * | pSymTab, | |
| const string & | pAttributeName, | |||
| const string & | pAttributeValue | |||
| ) | [inline, static] |
Return all tupels where the value of attribute (pAttributeName) is (pAttributeValue).
Definition at line 166 of file bddRelation.h.
References bddSymTab::getAttributePos(), bddSymTab::getValueNum(), and mkEqual().
Referenced by createBddRelation(), relStmtAssign::interpret(), relExprClosure::interpret(), and relExprRelVar::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::operator, | ( | const bddRelation & | ) | [private] |
Forbid the use of some ugly standard operators.
| void bddRelation::renameSafe | ( | unsigned | pVarIdOld, | |
| unsigned | pVarIdNew, | |||
| unsigned | pBitNr | |||
| ) | [inline, private] |
Renaming of attributes.
Safe variant, without preconditions.
Definition at line 219 of file bddRelation.h.
References bddBdd::exists(), bddBdd::intersect(), and mBdd.
Referenced by rename().
Here is the call graph for this function:
Here is the caller graph for this function:
| double bddRelation::getTupleNr | ( | const set< string > & | pFree | ) | const [inline] |
Returns number of tuples, restricted to the given attributes.
Assuming that all free attributes are contained in 'pFree'.
Definition at line 258 of file bddRelation.h.
References bddSymTab::computeVariableOrder(), bddSymTab::getBitNr(), bddBdd::getTupleNr(), intersect(), isEmpty(), mBdd, mkEqualPure(), mkRange(), mSymTab, and bddBdd::testVars().
Referenced by relPrintExprRelInfo::interpret(), and relNumExprUnOp::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| string bddRelation::getElement | ( | unsigned | pVarId | ) | [inline] |
Returns a value for attribute at position 'pVarId'.
Assumes that the relation is not empty.
Definition at line 295 of file bddRelation.h.
References bddSymTab::getAttributeValue(), bddSymTab::getBitNr(), bddBdd::getTuple(), mBdd, and mSymTab.
Referenced by relStrExprElem::interpret(), relStmtFor::interpret(), relNumExprUnOp::interpret(), and relExprClosure::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| bool bddRelation::setEqual | ( | const bddRelation & | p | ) | const [inline] |
Definition at line 305 of file bddRelation.h.
References mBdd, and bddBdd::setEqual().
Referenced by relStmtWhile::interpret(), relStmtIf::interpret(), relExprRelOp::interpret(), relExprClosure::interpret(), and printGraph().
Here is the call graph for this function:
Here is the caller graph for this function:
| bool bddRelation::setContains | ( | const bddRelation & | p | ) | const [inline] |
Check if (*this) contains (p).
Definition at line 311 of file bddRelation.h.
References mBdd, and bddBdd::setContains().
Referenced by relExprRelOp::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| bool bddRelation::isEmpty | ( | ) | const [inline] |
Definition at line 316 of file bddRelation.h.
References bddBdd::isEmpty(), and mBdd.
Referenced by getTupleNr(), getTupleOf(), relStrExprElem::interpret(), relStmtFor::interpret(), relNumExprUnOp::interpret(), relExprTupleOf::interpret(), relExprClosure::interpret(), and printRelation().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::complement | ( | ) | [inline] |
Definition at line 321 of file bddRelation.h.
References bddBdd::complement(), and mBdd.
Referenced by crocopat(), relStmtFor::interpret(), relStmtAssign::interpret(), relNumExprUnOp::interpret(), relExprClosure::interpret(), relExprEquiv::interpret(), relExprNot::interpret(), mkEqual(), and printRelation().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::unite | ( | const bddRelation & | p | ) | [inline] |
Definition at line 326 of file bddRelation.h.
References mBdd, and bddBdd::unite().
Referenced by createBddRelation(), crocopat(), relStmtAssign::interpret(), relExprRegExTerm::interpret(), relExprClosure::interpret(), relExprEquiv::interpret(), relExprOr::interpret(), mkEqual(), and mkLess().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::intersect | ( | const bddRelation & | p | ) | [inline] |
Definition at line 331 of file bddRelation.h.
References bddBdd::intersect(), and mBdd.
Referenced by createBddRelation(), getTupleNr(), getTupleOf(), relStmtFor::interpret(), relStmtAssign::interpret(), relNumExprUnOp::interpret(), relExprClosure::interpret(), relExprEquiv::interpret(), relExprAnd::interpret(), relExprRelVar::interpret(), mkEqual(), mkLess(), and printRelation().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::exists | ( | const string | pAttribute | ) | [inline] |
Existential quantification of (pAttribute).
Definition at line 337 of file bddRelation.h.
References bddBdd::exists(), bddSymTab::getAttributePos(), bddSymTab::getBitNr(), mBdd, and mSymTab.
Referenced by relExprClosure::interpret(), and relExprRelVar::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| bool bddRelation::testVars | ( | string | pVarFirst, | |
| string | pVarLast | |||
| ) | [inline] |
Check if there is any BDD node within the given range of attributes.
Returns 'true' if any such node is found.
Definition at line 350 of file bddRelation.h.
References bddSymTab::getAttributePos(), bddSymTab::getBitNr(), mBdd, mSymTab, and bddBdd::testVars().
Referenced by relExprRelVar::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::rename | ( | const string | pAttributeOld, | |
| const string | pAttributeNew | |||
| ) | [inline] |
Renaming of attributes.
Definition at line 360 of file bddRelation.h.
References bddSymTab::getAttributePos(), bddSymTab::getBitNr(), mBdd, mSymTab, renameSafe(), bddBdd::renameVars(), and bddBdd::testVars().
Referenced by relStmtAssign::interpret(), relExprClosure::interpret(), and relExprRelVar::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::printBddInfo | ( | ostream & | pS | ) | const [inline] |
Definition at line 403 of file bddRelation.h.
References bddBdd::getFreeNodeNr(), bddBdd::getMaxNodeNr(), bddBdd::getNodeNr(), and mBdd.
Referenced by relPrintExprRelInfo::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::printNodesPerVarId | ( | ostream & | pS, | |
| const set< string > & | pFree | |||
| ) | const [inline] |
Prints the number of nodes per variable id for the BDD.
(For BDD visualization.)
Definition at line 419 of file bddRelation.h.
References bddSymTab::computeVariableOrder(), bddSymTab::getBitNr(), bddBdd::getNodesPerVarId(), mBdd, and mSymTab.
Referenced by relPrintExprNodesPerVarId::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::printRelation | ( | ostream & | pS, | |
| const string | pTuple, | |||
| vector< string > | pAttributeList | |||
| ) | const [inline] |
Print set of tuples (plain) according to the given order of attributes.
Recursiv procedure.
Definition at line 457 of file bddRelation.h.
References complement(), bddSymTab::getAttributePos(), bddSymTab::getAttributeValue(), bddSymTab::getBitNr(), bddBdd::getTuple(), intersect(), isEmpty(), bddSymTab::isQuoted(), mBdd, mkEqual(), mSymTab, and printRelation().
Referenced by relPrintExprValues::interpret(), and printRelation().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::printGraph | ( | ostream & | pS, | |
| const set< string > & | pFree | |||
| ) | const [inline] |
Prints output graph for BDD.
Definition at line 507 of file bddRelation.h.
References bddRelation(), bddSymTab::computeVariableOrder(), bddSymTab::getBitNr(), bddBdd::getGraph(), mBdd, mSymTab, and setEqual().
Referenced by relPrintExprGraph::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| void bddRelation::printBDT | ( | ostream & | pS | ) | const [inline] |
Prints mBdd as reduced binary decision tree.
Definition at line 584 of file bddRelation.h.
References mBdd, and bddBdd::print().
Referenced by relPrintExprBDT::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
| bddRelation bddRelation::getTupleOf | ( | const map< unsigned, string > & | pAttributeList | ) | const [inline] |
Cut given relation to single element for all given attributes.
Recursiv procedure.
Definition at line 591 of file bddRelation.h.
References bddSymTab::getAttributePos(), bddSymTab::getBitNr(), bddBdd::getTuple(), intersect(), isEmpty(), mBdd, mkEqual(), and mSymTab.
Referenced by relExprTupleOf::interpret().
Here is the call graph for this function:
Here is the caller graph for this function:
const bddSymTab* bddRelation::mSymTab [private] |
Symbol table (associated).
Definition at line 178 of file bddRelation.h.
Referenced by exists(), getElement(), getTupleNr(), getTupleOf(), printGraph(), printNodesPerVarId(), printRelation(), rename(), and testVars().
bddBdd bddRelation::mBdd [private] |
Set of tuples.
Definition at line 180 of file bddRelation.h.
Referenced by complement(), exists(), getElement(), getTupleNr(), getTupleOf(), intersect(), isEmpty(), printBddInfo(), printBDT(), printGraph(), printNodesPerVarId(), printRelation(), rename(), renameSafe(), setContains(), setEqual(), testVars(), and unite().
For a stronger type check, remember the arity.
'-1' for undefined arity, '0' for boolean, '1' for set, '2' for binary relation, ... This is only provided as a feature to more abstract layers; it is only partially used, and there is no guarantee that the arity is always correctly set. I.e., this attribute is not controlled by this class.
Definition at line 189 of file bddRelation.h.
Referenced by createBddRelation(), relStmtAssign::interpret(), and relExprRelVar::interpret().
1.5.1