nodes.h
// Math Type Library
// $Id: nodes.h,v 1.13 2002/07/02 00:56:12 cparpart Exp $
// (This file contains the expression tree specific interface)
//
// Copyright (c) 2002 by Christian Parpart <cparpart@surakware.net>
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public License
// along with this library; see the file COPYING.LIB. If not, write to
// the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
// Boston, MA 02111-1307, USA.
#ifndef libmath_nodes_h
#define libmath_nodes_h
#include <deque>
#include <string>
#include <memory>
/* EXAMPLE
* expression: 3x^4 + 2x^2 + 1
* the tree:
* ____ + ____
* / \
* ___ + ___ 1
* / \
* * *
* / \ / \
* 3 ^ 2 ^
* / \ / \
* x 4 x 2
*/
namespace math {
template<typename> class TNodeVisitor;
template<typename> class TNode;
template<typename> class TUnaryNodeOp;
template<typename> class TBinaryNodeOp;
// ISSUE : we should, perhaps, support two iterator types
// - one for the real iteration (each and every node, classic),
// - and one wich takes care about the math privileges and stays
// only in its scope
template<typename T>
class TNodeIterator {
private:
TNode<T> *FCurrent;
private:
void increment() {
// TODO : it must care about the operator privileges
if (FCurrent->right()) {
FCurrent = FCurrent->right();
while (FCurrent->left())
FCurrent = FCurrent->left();
} else {
TNode<T> *p = FCurrent->parent();
while (FCurrent == p->right()) {
FCurrent = p;
p = p->parent();
}
if (FCurrent->right() != p)
FCurrent = p;
}
}
bool decrement() {
// TODO : it must care about the operator privileges
TNode<T> *last = FCurrent;
if (FCurrent->left()) {
TNode<T> *p = FCurrent->left();
while (p->right())
p = p->right();
FCurrent = p;
} else {
TNode<T> *p = FCurrent->parent();
while (FCurrent == p->left()) {
FCurrent = p;
p = p->left();
}
FCurrent = p;
}
return FCurrent != last;
}
TNodeIterator<T>& rewind() {
while (decrement());
return *this;
}
friend class TNode<T>; // TNode<T> may access the method rewind.
public:
TNodeIterator() : FCurrent(0) {}
TNodeIterator(TNode<T> *ANode) : FCurrent(ANode) {}
TNodeIterator(const TNodeIterator<T>& v) : FCurrent(v.FCurrent) {}
TNode<T>& operator*() const { return *FCurrent; }
TNode<T> *operator->() const { return FCurrent; }
TNode<T> *get() const { return FCurrent; }
TNodeIterator<T>& operator++() { increment(); return *this; }
TNodeIterator<T>& operator--() { decrement(); return *this; }
};
template<typename T>
bool operator==(const TNodeIterator<T>& a, const TNodeIterator<T>& b) {
return a.get() == b.get();
}
template<typename T>
bool operator!=(const TNodeIterator<T>& a, const TNodeIterator<T>& b) {
return a.get() != b.get();
}
template <typename NodeType>
class TOperandIter {
public:
TOperandIter() : FOrigin(0), FCurrent(0) {}
TOperandIter(NodeType *AOperator) : FOrigin(AOperator), FCurrent(FOrigin) {
do FCurrent = FCurrent->left();
while (inScope(FCurrent));
}
TOperandIter(const TOperandIter<NodeType>& AProto) :
FOrigin(AProto.FOrigin), FCurrent(AProto.FCurrent) {}
NodeType& operator*() const { return *FCurrent; }
NodeType *operator->() const { return FCurrent; }
NodeType *get() const { return this ? FCurrent : 0; }
TOperandIter<NodeType>& end() const { return *static_cast<TOperandIter<NodeType> *>(0); }
TOperandIter<NodeType>& operator++() { increment(); return *this; }
private:
NodeType *FOrigin;
NodeType *FCurrent;
void increment() {
if (FCurrent) {
NodeType *p = FCurrent->parent();
// as long as we're the right child of p
while (p && FCurrent == p->right() && inScope(p)) {
// go one up
FCurrent = p;
p = p->parent();
}
FCurrent = p;
// reached end of iteration
if (!p || !inScope(p)) {
FCurrent = 0;
return;
}
FCurrent = FCurrent->right();
if (inScope(FCurrent)) {
do FCurrent = FCurrent->left();
while (inScope(FCurrent));
}
}
}
bool inScope(const NodeType *ANode) const {
switch (FOrigin->nodeType()) {
case NodeType::PLUS_NODE:
case NodeType::MUL_NODE:
return ANode->nodeType() == FOrigin->nodeType();
default:
return false;
}
}
};
template<typename T>
bool operator==(const TOperandIter<T>& a, const TOperandIter<T>& b) {
return a.get() == b.get();
}
template<typename T>
bool operator!=(const TOperandIter<T>& a, const TOperandIter<T>& b) {
return a.get() != b.get();
}
template <typename T>
class TNode {
public:
typedef TNodeIterator<T> iterator;
typedef const TNodeIterator<T> const_iterator;
typedef TOperandIter<TNode<T> > operand_iterator;
typedef TOperandIter<const TNode<T> > const_operand_iterator;
enum TNodeType {
// take care, the order below is hard coded
NUMBER_NODE, // numbers: 0, 3.1415, 2.17, 0.815, ... (prio: 0)
SYMBOL_NODE, // any symbol value: pi, e, ... (prio: 0)
PARAM_NODE, // the function parameter... (e.g. x) (prio: 0)
PLUS_NODE, // x + y (prio: -5)
NEG_NODE, // -x (prio: -5)
MUL_NODE, // x * y (prio: -3)
DIV_NODE, // x / y (prio: -3)
MOD_NODE, // x mod y (prio: -3)
POW_NODE, // x ^ y (prio: -1)
EQU_NODE, // x == y (prio: -10)
UNEQU_NODE, // x != y (prio: -10)
LESS_EQU_NODE, // x <= y (prio: -10)
GREATER_EQU_NODE,// x >= y (prio: -10)
LESS_NODE, // x < y (prio: -10)
GREATER_NODE, // x > y (prio: -10)
FUNC_NODE, // userfunc(x) (prio: -1)
SQRT_NODE, // sqrt(x); x ^ 0.5 (prio: -1)
SIN_NODE, // sin(x) (prio: -1)
COS_NODE, // cos(x) (prio: -1)
TAN_NODE, // tan(x) (prio: -1)
LN_NODE, // logn(x) (prio: -1)
IF_NODE // IF(cond, then, else) (prio: -1)
};
private:
TNodeType FNodeType;
short FPriority;
TNode<T> *FParent;
protected:
TNode(TNodeType ANodeType, short APriority, TNode<T> *AParentNode = 0);
TNode(const TNode<T>& n);
void parent(TNode<T> *AParent);
friend class TUnaryNodeOp<T>;
friend class TBinaryNodeOp<T>;
public:
virtual ~TNode();
TNodeType nodeType() const;
short priority() const;
TNode<T> *parent() const;
virtual TNode<T> *left() const;
virtual TNode<T> *right() const;
virtual void accept(TNodeVisitor<T>&) = 0;
virtual TNode<T> *clone() const = 0;
iterator begin() { return iterator(this).rewind(); }
iterator end() { return iterator(0); }
virtual bool equals(const TNode<T> *ANode) const = 0;
};
template<typename T> bool operator==(const TNode<T>&, const TNode<T>&);
template<typename T> bool operator!=(const TNode<T>&, const TNode<T>&);
template<typename T>
class TNumberNode : public TNode<T> {
private:
T FNumber;
public:
TNumberNode(const T& AValue);
T number() const;
virtual void accept(TNodeVisitor<T>&);
virtual TNumberNode<T> *clone() const;
virtual bool equals(const TNode<T> *ANode) const;
};
template<typename T>
class TSymbolNode : public TNode<T> {
private:
std::string FSymbol;
public:
TSymbolNode(const std::string& ASymbol);
std::string symbol() const;
virtual void accept(TNodeVisitor<T>&);
virtual TSymbolNode<T> *clone() const;
virtual bool equals(const TNode<T> *ANode) const;
};
template<typename T>
class TParamNode : public TNode<T> {
public:
TParamNode();
virtual void accept(TNodeVisitor<T>&);
virtual TParamNode<T> *clone() const;
virtual bool equals(const TNode<T> *ANode) const;
};
template<typename T>
class TUnaryNodeOp : public TNode<T> {
private:
std::auto_ptr<TNode<T> > FNode;
protected:
TUnaryNodeOp(typename TUnaryNodeOp<T>::TNodeType AType, short APriority, TNode<T> *ANode);
public:
TNode<T> *node() const;
virtual TNode<T> *right() const;
virtual bool equals(const TNode<T> *ANode) const;
};
template<typename T>
class TBinaryNodeOp : public TNode<T> {
private:
std::auto_ptr<TNode<T> > FLeft;
std::auto_ptr<TNode<T> > FRight;
protected:
TBinaryNodeOp(typename TBinaryNodeOp<T>::TNodeType AType, short APrio, TNode<T> *ALeft, TNode<T> *ARight);
public:
virtual TNode<T> *left() const;
virtual TNode<T> *right() const;
virtual bool equals(const TNode<T> *ANode) const;
};
template <typename T>
class TPlusNode : public TBinaryNodeOp<T> {
public:
TPlusNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TPlusNode<T> *clone() const;
};
template<typename T>
class TNegNode : public TUnaryNodeOp<T> {
public:
TNegNode(TNode<T> *ANode);
virtual void accept(TNodeVisitor<T>&);
virtual TNegNode<T> *clone() const;
};
template<typename T>
class TMulNode : public TBinaryNodeOp<T> {
public:
TMulNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TMulNode *clone() const;
};
template<typename T>
class TDivNode : public TBinaryNodeOp<T> {
public:
TDivNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TDivNode *clone() const;
};
template<typename T>
class TPowNode : public TBinaryNodeOp<T> {
public:
TPowNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TPowNode *clone() const;
};
template<typename T>
class TSqrtNode : public TUnaryNodeOp<T> {
public:
TSqrtNode(TNode<T> *ANode);
virtual void accept(TNodeVisitor<T>&);
virtual TSqrtNode *clone() const;
};
template<typename T>
class TSinNode : public TUnaryNodeOp<T> {
public:
TSinNode(TNode<T> *AParam);
virtual void accept(TNodeVisitor<T>&);
virtual TSinNode *clone() const;
};
template<typename T>
class TCosNode : public TUnaryNodeOp<T> {
public:
TCosNode(TNode<T> *AParam);
virtual void accept(TNodeVisitor<T>&);
virtual TCosNode *clone() const;
};
template<typename T>
class TTanNode : public TUnaryNodeOp<T> {
public:
TTanNode(TNode<T> *AParam);
virtual void accept(TNodeVisitor<T>&);
virtual TTanNode *clone() const;
};
template<typename T>
class TLnNode : public TUnaryNodeOp<T> {
public:
TLnNode(TNode<T> *AParam);
virtual void accept(TNodeVisitor<T>&);
virtual TLnNode *clone() const;
};
template<typename T>
class TFuncNode : public TUnaryNodeOp<T> {
private:
std::string FName;
public:
TFuncNode(const std::string& AName, TNode<T> *AParam);
std::string name() const;
virtual void accept(TNodeVisitor<T>&);
virtual TFuncNode<T> *clone() const;
};
template<typename T>
class TIfNode : public TBinaryNodeOp<T> {
private:
std::auto_ptr<TNode<T> > FCondition;
public:
TIfNode(TNode<T> *ACondNode, TNode<T> *AThenNode, TNode<T> *AElseNode);
TNode<T> *condition() const;
TNode<T> *trueExpr() const;
TNode<T> *falseExpr() const;
virtual void accept(TNodeVisitor<T>&);
virtual TIfNode *clone() const;
};
template<typename T>
class TEquNode : public TBinaryNodeOp<T> {
public:
TEquNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TEquNode *clone() const;
};
template<typename T>
class TUnEquNode : public TBinaryNodeOp<T> {
public:
TUnEquNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TUnEquNode *clone() const;
};
template<typename T>
class TGreaterNode : public TBinaryNodeOp<T> {
public:
TGreaterNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TGreaterNode *clone() const;
};
template<typename T>
class TLessNode : public TBinaryNodeOp<T> {
public:
TLessNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TLessNode *clone() const;
};
template<typename T>
class TGreaterEquNode : public TBinaryNodeOp<T> {
public:
TGreaterEquNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TGreaterEquNode *clone() const;
};
template<typename T>
class TLessEquNode : public TBinaryNodeOp<T> {
public:
TLessEquNode(TNode<T> *ALeft, TNode<T> *ARight);
virtual void accept(TNodeVisitor<T>&);
virtual TLessEquNode *clone() const;
};
} // namespace math
#include <math++/nodes.tcc>
#endif
math::TIfNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TGreaterNode
Definition: nodes.h:625
math::TGreaterEquNode::clone
virtual TGreaterEquNode * clone() const
clones that node
math::TTanNode
Definition: nodes.h:538
math::TNodeIterator
Definition: nodes.h:64
math::TNegNode
Definition: nodes.h:448
math::TSymbolNode::symbol
std::string symbol() const
returns the symbol&#39;s name
math::TSymbolNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TUnaryNodeOp::right
virtual TNode< T > * right() const
returns the child node (wrapper to the more declarative node() method)
math::TMulNode::clone
virtual TMulNode * clone() const
clones that node
math::TGreaterEquNode
Definition: nodes.h:643
math::TNode::nodeType
TNodeType nodeType() const
returns the type of this node
math::TFuncNode::clone
virtual TFuncNode< T > * clone() const
clones that node
math::TNode::parent
void parent(TNode< T > *AParent)
initializes the parent node with the given one
math::TEquNode::clone
virtual TEquNode * clone() const
clones that node
math::TLessEquNode
Definition: nodes.h:652
math::TPowNode
Definition: nodes.h:486
math::TDivNode
Definition: nodes.h:474
math::TGreaterNode::clone
virtual TGreaterNode * clone() const
clones that node
math::TNode::left
virtual TNode< T > * left() const
returns the left child node (returns 0 if this node doesn&#39;t support one)
math::TBinaryNodeOp
Definition: nodes.h:49
math::TPlusNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TParamNode
Definition: nodes.h:374
math::TLessNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TMulNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TParamNode::equals
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
math::TTanNode::clone
virtual TTanNode * clone() const
clones that node
math::TUnaryNodeOp::equals
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
math::TNode::priority
short priority() const
returns the node priority
math::TNode::parent
TNode< T > * parent() const
returns the parent node (returns 0 if this node is the root node)
math::TSqrtNode
Definition: nodes.h:499
math::TNode
Definition: library.h:34
math::TOperandIter
Definition: nodes.h:151
math::TUnEquNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TNumberNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TLessEquNode::clone
virtual TLessEquNode * clone() const
clones that node
math::TSymbolNode::clone
virtual TSymbolNode< T > * clone() const
clones that node
math::TDivNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TMulNode
Definition: nodes.h:461
math::TNegNode::clone
virtual TNegNode< T > * clone() const
clones that node
math::TNumberNode::clone
virtual TNumberNode< T > * clone() const
clones that node
math::TUnaryNodeOp::node
TNode< T > * node() const
returns the child node for that unary operator node.
math::TEquNode
Definition: nodes.h:607
math::TSqrtNode::clone
virtual TSqrtNode * clone() const
clones that node
math::TNode::begin
iterator begin()
iterator access to the first value node in this operator level
Definition: nodes.h:319
math::TNode::equals
virtual bool equals(const TNode< T > *ANode) const =0
returns true, if given node equals to this one
math::TBinaryNodeOp::right
virtual TNode< T > * right() const
returns the left child node of the expression tree
math::TSinNode::clone
virtual TSinNode * clone() const
clones that node
math::TTanNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TSymbolNode::equals
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
math::TUnaryNodeOp
Definition: nodes.h:48
math::TNode::TNode
TNode(TNodeType ANodeType, short APriority, TNode< T > *AParentNode=0)
initializes this node for given node type.
math::TLessNode
Definition: nodes.h:634
math::TParamNode::clone
virtual TParamNode< T > * clone() const
clones that node
math::TSinNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TNumberNode::equals
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
math::TNode::~TNode
virtual ~TNode()
each virtual class needs a virtual destructor (this one does nothing)
math::TParamNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TGreaterNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TSymbolNode
Definition: nodes.h:354
math::TUnEquNode
Definition: nodes.h:616
math::TNode::right
virtual TNode< T > * right() const
returns the right child node (returns 0 if this node doesn&#39;t support one)
math::TSqrtNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TNode::end
iterator end()
iterator access to the end
Definition: nodes.h:322
math::TCosNode
Definition: nodes.h:525
math::TBinaryNodeOp::equals
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
math::TLnNode
Definition: nodes.h:551
math::TNegNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TGreaterEquNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TNode::accept
virtual void accept(TNodeVisitor< T > &)=0
calls the visit method in TNodeVisitor&lt;&gt;
math::TBinaryNodeOp::left
virtual TNode< T > * left() const
returns the right child node of the expression tree
math::TPowNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TPowNode::clone
virtual TPowNode * clone() const
clones that node
math::TPlusNode::clone
virtual TPlusNode< T > * clone() const
clones that node
math::TLnNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TNode< T >::TNodeType
TNodeType
Definition: nodes.h:240
math::TCosNode::clone
virtual TCosNode * clone() const
clones that node
math::TEquNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TIfNode
Definition: nodes.h:586
math::TLessNode::clone
virtual TLessNode * clone() const
clones that node
math::TPlusNode
Definition: nodes.h:435
math::TSinNode
Definition: nodes.h:512
math::TNodeVisitor
Definition: nodes.h:46
math::TDivNode::clone
virtual TDivNode * clone() const
clones that node
math::TFuncNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TUnEquNode::clone
virtual TUnEquNode * clone() const
clones that node
math::TBinaryNodeOp::TBinaryNodeOp
TBinaryNodeOp(typename TBinaryNodeOp< T >::TNodeType AType, short APrio, TNode< T > *ALeft, TNode< T > *ARight)
creates an binary operator node of type AType
math::TLessEquNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TCosNode::accept
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
math::TNode::clone
virtual TNode< T > * clone() const =0
clones that node
math::TIfNode::clone
virtual TIfNode * clone() const
clones that node
math::TFuncNode
Definition: nodes.h:566
math::TUnaryNodeOp::TUnaryNodeOp
TUnaryNodeOp(typename TUnaryNodeOp< T >::TNodeType AType, short APriority, TNode< T > *ANode)
creates an unary operator node of type AType.
math::TLnNode::clone
virtual TLnNode * clone() const
clones that node
math::TNumberNode
Definition: nodes.h:335