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