BoolStuff 0.1

boolstuff::BoolExpr< T > Class Template Reference

Object representing a node in a boolean expression binary tree. More...

#include <BoolExpr.h>

List of all members.

Public Types

enum  Type { VALUE, AND, OR, NOT }
 

Possible types for a boolean expression tree node.

More...

Public Member Functions

 BoolExpr (const T &initValue=T())
 Creates a VALUE node with the given initial value.
 BoolExpr (Type t, BoolExpr *l, BoolExpr *r)
 Creates a node of the given type and with the given children.
 ~BoolExpr ()
 Calls delete on the left and right subtrees of this node.
Type getType () const
 Returns the type of this node.
const BoolExprgetLeft () const
 Returns the left-hand child of this node.
BoolExprgetLeft ()
 Returns the left-hand child of this node.
const BoolExprgetRight () const
 Returns the right-hand child of this node.
BoolExprgetRight ()
 Returns the right-hand child of this node.
const T & getValue () const
 Returns the value of this node.
T & getValue ()
 Returns the value of this node.
void setType (Type t)
 Changes the type of this node.
void setLeft (BoolExpr *subtree)
 Attaches a subtree as this node's left-hand child.
void setRight (BoolExpr *subtree)
 Attaches a subtree as this node's right-hand child.
void setValue (const T &v)
 Changes the value of this node.
bool isDisjunctiveNormalForm () const
 Determines if the tree rooted at this node is in the DNF.
template<class OutputIter >
OutputIter getDNFTermRoots (OutputIter dest) const
 Gets the roots of the terms of an tree in DNF form.
void getTreeVariables (std::set< T > &positives, std::set< T > &negatives) const
 Returns the variables that are used in the tree rooted at this node.
bool isDNFTermUseful () const
 Determines if this DNF term always evaluates to false.
void print (std::ostream &out) const
 Prints the boolean expression tree rooted at this node in a stream.
std::string print () const
 Prints the boolean expression tree rooted at this node in a string.

Static Public Member Functions

static BoolExprcloneTree (const BoolExpr *root)
 Returns a copy of the designated tree.
static BoolExprgetDisjunctiveNormalForm (BoolExpr *root)
 Transforms the designated tree into its Disjunctive Normal Form.
static BoolExprgetRawDNF (BoolExpr *root)
 Like getDisjunctiveNormalForm(), but without simplifications.

Friends

class BoolExprParser

Detailed Description

template<class T>
class boolstuff::BoolExpr< T >

Object representing a node in a boolean expression binary tree.

All objects of this class are expected to be allocated by operator new.

The value type T must be a concrete type with a default constructor, a copy constructor and an assignment operator. Type T must be LessThan Comparable (i.e., it supports the operators < and ==). If one of the print() methods is called, there must be a function of the form operator << (std::ostream &, const T &).

See class BoolExprParser for a way to obtain a tree from a textual boolean expression.


Member Enumeration Documentation

template<class T>
enum boolstuff::BoolExpr::Type

Possible types for a boolean expression tree node.

Enumerator:
VALUE 

Node, without subtrees, that contains a value of type T.

AND 

Conjunction node with left and right subtrees.

OR 

Disjunction node with left and right subtrees.

NOT 

Negation node with only a right subtree.


Constructor & Destructor Documentation

template<class T>
boolstuff::BoolExpr< T >::BoolExpr ( const T &  initValue = T())

Creates a VALUE node with the given initial value.

This library expects all BoolExpr objects to be allocated by operator new.

Parameters:
initValueinitial value for the created node
template<class T>
boolstuff::BoolExpr< T >::BoolExpr ( Type  t,
BoolExpr< T > *  l,
BoolExpr< T > *  r 
)

Creates a node of the given type and with the given children.

A NOT node must only have a right-hand child, while AND and OR nodes must have both left-hand and right-hand children.

Example:
BoolExpr<string> *left = new BoolExpr<string>("left subtree");
BoolExpr<string> *right = new BoolExpr<string>("right subtree");
BoolExpr<string> *root = new BoolExpr<string>( BoolExpr<string>::AND, left, right);
delete root;

Parameters:
ttype of the node (must be AND, OR or NOT)
lsubtree to attach as the left-hand child (may be NULL)
rsubtree to attach as the right-hand child (may be NULL)
template<class T>
boolstuff::BoolExpr< T >::~BoolExpr ( )

Calls delete on the left and right subtrees of this node.

This library expects all BoolExpr objects to be destroyed by operator delete.


Member Function Documentation

template<class T>
static BoolExpr* boolstuff::BoolExpr< T >::cloneTree ( const BoolExpr< T > *  root) [static]

Returns a copy of the designated tree.

All nodes in the returned tree are independent copies of those in the original tree. All the cloned nodes are created with operator new. The caller must eventually destroy the cloned tree by calling operator delete on its root node.

Parameters:
rootthe root of the tree to be copied
Returns:
the root of the created tree (NULL if root was NULL)
template<class T>
static BoolExpr* boolstuff::BoolExpr< T >::getDisjunctiveNormalForm ( BoolExpr< T > *  root) [static]

Transforms the designated tree into its Disjunctive Normal Form.

The proper way to call this method is the following:

root = BoolExpr<SomeType>::getDisjunctiveNormalForm(root);

The original tree root does not necessarily remain the root of the transformed tree.

A simplification is applied: when a term of the form a&!a&(something) is seen, it is deleted unless it is the root of the whole tree.

CAUTION: this method can return a NULL pointer; such a result should be interpreted as a "false" boolean expression. Examples are when the original (or resulting) tree is a&!a, or a&!a|b&!b. This method also returns NULL if 'root' is NULL.

Parameters:
rootroot of the tree to transform
Returns:
the root of the transformed tree (may be NULL)
template<class T>
template<class OutputIter >
OutputIter boolstuff::BoolExpr< T >::getDNFTermRoots ( OutputIter  dest) const

Gets the roots of the terms of an tree in DNF form.

The DNF is a sum of products. Each term in this sum is represented by a subtree of the tree rooted at the current node. This method produces the BoolExpr<T> pointers that represent the roots of the term subtrees.

Returns the iterator at the position past the last insertion.

The tree must first be in DNF. See getDisjunctiveNormalForm().

For example, if the current node is the root a of DNF tree representing the expression a&b | c | d&e, then three pointers will be stored: one for the 'a&b' subtree, one for the 'c' subtree (a single node) and one for the 'd&e' subtree.

If the tree is a single node, then 'this' designates the only term in the sum and it is returned as the root of the unique term.

The stored pointers must not be destroyed directly.

Example:
vector<const BoolExpr<string> *> termRoots; dnfRoot->getDNFTermRoots(inserter(termRoots, termRoots.end()));

Parameters:
destoutput iterator that supports the notation *dest++, where the expression *dest is of type 'const BoolExpr<T> *'.
Returns:
the output iterator that designates the end of the produced sequence
template<class T>
const BoolExpr* boolstuff::BoolExpr< T >::getLeft ( ) const

Returns the left-hand child of this node.

template<class T>
BoolExpr* boolstuff::BoolExpr< T >::getLeft ( )

Returns the left-hand child of this node.

Operator delete should not be called on the subtrees returned by getLeft(). Only the root of a tree should be the target of a destruction.

template<class T>
const BoolExpr* boolstuff::BoolExpr< T >::getRight ( ) const

Returns the right-hand child of this node.

template<class T>
BoolExpr* boolstuff::BoolExpr< T >::getRight ( )

Returns the right-hand child of this node.

Operator delete should not be called on the subtrees returned by getRight(). Only the root of a tree should be the target of a destruction.

template<class T>
void boolstuff::BoolExpr< T >::getTreeVariables ( std::set< T > &  positives,
std::set< T > &  negatives 
) const

Returns the variables that are used in the tree rooted at this node.

Example: with T == string and the expression a&b&!a&!c, the 'positives' set will contain "a" and "b" and the 'negatives' set will contain "a" and "c".

When the intersection between the two sets is not empty and the only binary operator used in the tree is AND, the tree always evaluates to false (because we have an expression of the form (a&!a)&(whatever)). If the only binary operator is OR, the tree always evaluates to true.

Parameters:
positivesset that receives the T values of the variables that are used positively
negativesset that receives the T values of the variables that are used negatively
template<class T>
Type boolstuff::BoolExpr< T >::getType ( ) const

Returns the type of this node.

template<class T>
const T& boolstuff::BoolExpr< T >::getValue ( ) const

Returns the value of this node.

getValue() should only be called on a node for which getType() returns BoolExpr::VALUE.

template<class T>
T& boolstuff::BoolExpr< T >::getValue ( )

Returns the value of this node.

getValue() should only be called on a node for which getType() returns BoolExpr::VALUE.

template<class T>
bool boolstuff::BoolExpr< T >::isDisjunctiveNormalForm ( ) const

Determines if the tree rooted at this node is in the DNF.

Returns:
true or false
template<class T>
bool boolstuff::BoolExpr< T >::isDNFTermUseful ( ) const

Determines if this DNF term always evaluates to false.

Must only be called on a term of a DNF tree, which can be obtained with the getDNFTermRoots() method. (e.g., a&b&!a).

Returns:
true if and only if this term always evaluates to false
template<class T>
void boolstuff::BoolExpr< T >::print ( std::ostream &  out) const

Prints the boolean expression tree rooted at this node in a stream.

Does not print a newline afterwards. Uses no unnecessary parentheses. Uses '!', '|' and '&' as the NOT, OR and AND operator.

If this method is called, there must be a function of the form operator << (ostream &, const T &).

Parameters:
outstream into which the tree representation is written
template<class T>
std::string boolstuff::BoolExpr< T >::print ( ) const

Prints the boolean expression tree rooted at this node in a string.

If this method is called, there must be a method of the form operator << (ostream &, const T &).

Returns:
the string representation of this tree
template<class T>
void boolstuff::BoolExpr< T >::setLeft ( BoolExpr< T > *  subtree)

Attaches a subtree as this node's left-hand child.

If this node already had a non null left-hand child, it is not destroyed before attaching the new child.

Parameters:
subtreethe subtree to attach (may be NULL)
template<class T>
void boolstuff::BoolExpr< T >::setRight ( BoolExpr< T > *  subtree)

Attaches a subtree as this node's right-hand child.

If this node already had a non null right-hand child, it is not destroyed before attaching the new child.

Parameters:
subtreethe subtree to attach (may be NULL)
template<class T>
void boolstuff::BoolExpr< T >::setType ( Type  t)

Changes the type of this node.

Parameters:
tthe type to this to this node
template<class T>
void boolstuff::BoolExpr< T >::setValue ( const T &  v)

Changes the value of this node.

This method should only be called on a node of type VALUE. The given value is copied into this node's value field.

Parameters:
vvalue to give to this node

The documentation for this class was generated from the following file:

Generated for BoolStuff by doxygen 1.7.3