nodes.h

00001 
00002 //  Math Type Library
00003 //  $Id: nodes.h,v 1.13 2002/07/02 00:56:12 cparpart Exp $
00004 //  (This file contains the expression tree specific interface)
00005 //
00006 //  Copyright (c) 2002 by Christian Parpart <cparpart@surakware.net>
00007 //
00008 //  This library is free software; you can redistribute it and/or
00009 //  modify it under the terms of the GNU Library General Public
00010 //  License as published by the Free Software Foundation; either
00011 //  version 2 of the License, or (at your option) any later version.
00012 //
00013 //  This library is distributed in the hope that it will be useful,
00014 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00016 //  Library General Public License for more details.
00017 // 
00018 //  You should have received a copy of the GNU Library General Public License
00019 //  along with this library; see the file COPYING.LIB.  If not, write to
00020 //  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00021 //  Boston, MA 02111-1307, USA.
00023 #ifndef libmath_nodes_h
00024 #define libmath_nodes_h
00025 
00026 #include <deque>
00027 #include <string>
00028 #include <memory>
00029 
00030 /* EXAMPLE
00031  * expression: 3x^4 + 2x^2 + 1
00032  * the tree:
00033  *                 ____ + ____
00034  *                /           \
00035  *           ___ + ___         1
00036  *          /         \
00037  *         *           *
00038  *        / \         / \
00039  *       3   ^       2   ^
00040  *          / \         / \
00041  *         x   4       x   2
00042  */
00043 
00044 namespace math {
00045 
00046 template<typename> class TNodeVisitor;
00047 template<typename> class TNode;
00048 template<typename> class TUnaryNodeOp;
00049 template<typename> class TBinaryNodeOp;
00050 
00051 // ISSUE : we should, perhaps, support two iterator types
00052 //  - one for the real iteration (each and every node, classic),
00053 //  - and one wich takes care about the math privileges and stays 
00054 //    only in its scope
00055 
00063 template<typename T>
00064 class TNodeIterator {
00065 private:
00066     TNode<T> *FCurrent;
00067 
00068 private:
00069     void increment() {
00070         // TODO : it must care about the operator privileges
00071         if (FCurrent->right()) {
00072             FCurrent = FCurrent->right();
00073 
00074             while (FCurrent->left())
00075                 FCurrent = FCurrent->left();
00076         } else {
00077             TNode<T> *p = FCurrent->parent();
00078 
00079             while (FCurrent == p->right()) {
00080                 FCurrent = p;
00081                 p = p->parent();
00082             }
00083 
00084             if (FCurrent->right() != p)
00085                 FCurrent = p;
00086         }
00087     }
00088 
00089     bool decrement() {
00090         // TODO : it must care about the operator privileges
00091         TNode<T> *last = FCurrent;
00092 
00093         if (FCurrent->left()) {
00094             TNode<T> *p = FCurrent->left();
00095 
00096             while (p->right())
00097                 p = p->right();
00098 
00099             FCurrent = p;
00100         } else {
00101             TNode<T> *p = FCurrent->parent();
00102 
00103             while (FCurrent == p->left()) {
00104                 FCurrent = p;
00105                 p = p->left();
00106             }
00107 
00108             FCurrent = p;
00109         }
00110         return FCurrent != last;
00111     }
00112 
00114     TNodeIterator<T>& rewind() {
00115         while (decrement());
00116 
00117         return *this;
00118     }
00119     
00120     friend class TNode<T>; // TNode<T> may access the method rewind.
00121 
00122 public:
00123     TNodeIterator() : FCurrent(0) {}
00124     TNodeIterator(TNode<T> *ANode) : FCurrent(ANode) {}
00125     TNodeIterator(const TNodeIterator<T>& v) : FCurrent(v.FCurrent) {}
00126 
00127     TNode<T>& operator*() const { return *FCurrent; }
00128     TNode<T> *operator->() const { return FCurrent; }
00129 
00130     TNode<T> *get() const { return FCurrent; }
00131 
00132     TNodeIterator<T>& operator++() { increment(); return *this; }
00133     TNodeIterator<T>& operator--() { decrement(); return *this; }
00134 };
00135 
00136 template<typename T>
00137 bool operator==(const TNodeIterator<T>& a, const TNodeIterator<T>& b) {
00138     return a.get() == b.get();
00139 }
00140 
00141 template<typename T>
00142 bool operator!=(const TNodeIterator<T>& a, const TNodeIterator<T>& b) {
00143     return a.get() != b.get();
00144 }
00145 
00150 template <typename NodeType>
00151 class TOperandIter {
00152 public:
00153     TOperandIter() : FOrigin(0), FCurrent(0) {}
00154 
00155     TOperandIter(NodeType *AOperator) : FOrigin(AOperator), FCurrent(FOrigin) {
00156         do FCurrent = FCurrent->left();
00157         while (inScope(FCurrent));
00158     }
00159 
00160     TOperandIter(const TOperandIter<NodeType>& AProto) :
00161         FOrigin(AProto.FOrigin), FCurrent(AProto.FCurrent) {}
00162 
00163     NodeType& operator*() const { return *FCurrent; }
00164     NodeType *operator->() const { return FCurrent; }
00165 
00166     NodeType *get() const { return this ? FCurrent : 0; }
00167 
00168     TOperandIter<NodeType>& end() const { return *static_cast<TOperandIter<NodeType> *>(0); }
00169 
00170     TOperandIter<NodeType>& operator++() { increment(); return *this; }
00171 
00172 private:
00173     NodeType *FOrigin;
00174     NodeType *FCurrent;
00175 
00177     void increment() {
00178         if (FCurrent) {
00179             NodeType *p = FCurrent->parent();
00180 
00181             // as long as we're the right child of p
00182             while (p && FCurrent == p->right() && inScope(p)) {
00183                 // go one up
00184                 FCurrent = p;
00185                 p = p->parent();
00186             }
00187             FCurrent = p;
00188 
00189             // reached end of iteration
00190             if (!p || !inScope(p)) {
00191                 FCurrent = 0;
00192                 return;
00193             }
00194 
00195             FCurrent = FCurrent->right();
00196             if (inScope(FCurrent)) {
00197                 do FCurrent = FCurrent->left();
00198                 while (inScope(FCurrent));
00199             }
00200         }
00201     }
00202 
00203     bool inScope(const NodeType *ANode) const {
00204         switch (FOrigin->nodeType()) {
00205             case NodeType::PLUS_NODE:
00206             case NodeType::MUL_NODE:
00207                 return ANode->nodeType() == FOrigin->nodeType();
00208             default:
00209                 return false;
00210         }
00211     }
00212 };
00213 
00214 template<typename T>
00215 bool operator==(const TOperandIter<T>& a, const TOperandIter<T>& b) {
00216     return a.get() == b.get();
00217 }
00218 
00219 template<typename T>
00220 bool operator!=(const TOperandIter<T>& a, const TOperandIter<T>& b) {
00221     return a.get() != b.get();
00222 }
00223 
00227 template <typename T>
00228 class TNode {
00229 public:
00230     typedef TNodeIterator<T> iterator;
00231     typedef const TNodeIterator<T> const_iterator;
00232 
00233     typedef TOperandIter<TNode<T> > operand_iterator;
00234     typedef TOperandIter<const TNode<T> > const_operand_iterator;
00235 
00240     enum TNodeType {
00241         // take care, the order below is hard coded
00242 
00243         NUMBER_NODE,    // numbers: 0, 3.1415, 2.17, 0.815, ... (prio: 0)
00244         SYMBOL_NODE,    // any symbol value: pi, e, ...         (prio: 0)
00245         PARAM_NODE,     // the function parameter... (e.g. x)   (prio: 0)
00246 
00247         PLUS_NODE,      // x + y                    (prio: -5)
00248         NEG_NODE,       // -x                       (prio: -5)
00249 
00250         MUL_NODE,       // x * y                    (prio: -3)
00251         DIV_NODE,       // x / y                    (prio: -3)
00252         MOD_NODE,       // x mod y                  (prio: -3)
00253 
00254         POW_NODE,       // x ^ y                    (prio: -1)
00255 
00256         EQU_NODE,       // x == y                   (prio: -10)
00257         UNEQU_NODE,     // x != y                   (prio: -10)
00258         LESS_EQU_NODE,  // x <= y                   (prio: -10)
00259         GREATER_EQU_NODE,// x >= y                  (prio: -10)
00260         LESS_NODE,      // x < y                    (prio: -10)
00261         GREATER_NODE,   // x > y                    (prio: -10)
00262 
00263         FUNC_NODE,      // userfunc(x)              (prio: -1)
00264 
00265         SQRT_NODE,      // sqrt(x); x ^ 0.5         (prio: -1)
00266         SIN_NODE,       // sin(x)                   (prio: -1)
00267         COS_NODE,       // cos(x)                   (prio: -1)
00268         TAN_NODE,       // tan(x)                   (prio: -1)
00269         LN_NODE,        // logn(x)                  (prio: -1)
00270 
00271         IF_NODE         // IF(cond, then, else)     (prio: -1)
00272     };
00273 
00274 private:
00276     TNodeType FNodeType;
00278     short FPriority;
00280     TNode<T> *FParent;
00281 
00282 protected:
00284     TNode(TNodeType ANodeType, short APriority, TNode<T> *AParentNode = 0);
00285     TNode(const TNode<T>& n);
00286 
00288     void parent(TNode<T> *AParent);
00289 
00290     friend class TUnaryNodeOp<T>;
00291     friend class TBinaryNodeOp<T>;
00292 
00293 public:
00295     virtual ~TNode();
00296 
00298     TNodeType nodeType() const;
00299 
00301     short priority() const;
00302 
00304     TNode<T> *parent() const;
00305 
00307     virtual TNode<T> *left() const;
00308 
00310     virtual TNode<T> *right() const;
00311 
00313     virtual void accept(TNodeVisitor<T>&) = 0;
00314 
00316     virtual TNode<T> *clone() const = 0;
00317 
00319     iterator begin() { return iterator(this).rewind(); }
00320 
00322     iterator end() { return iterator(0); }
00323 
00325     virtual bool equals(const TNode<T> *ANode) const = 0;
00326 };
00327 
00328 template<typename T> bool operator==(const TNode<T>&, const TNode<T>&);
00329 template<typename T> bool operator!=(const TNode<T>&, const TNode<T>&);
00330 
00334 template<typename T>
00335 class TNumberNode : public TNode<T> {
00336 private:
00337     T FNumber;
00338 
00339 public:
00340     TNumberNode(const T& AValue);
00341 
00342     T number() const;
00343 
00344     virtual void accept(TNodeVisitor<T>&);
00345     virtual TNumberNode<T> *clone() const;
00346     virtual bool equals(const TNode<T> *ANode) const;
00347 };
00348 
00353 template<typename T>
00354 class TSymbolNode : public TNode<T> {
00355 private:
00356     std::string FSymbol;
00357 
00358 public:
00359     TSymbolNode(const std::string& ASymbol);
00360 
00362     std::string symbol() const;
00363 
00364     virtual void accept(TNodeVisitor<T>&);
00365     virtual TSymbolNode<T> *clone() const;
00366     virtual bool equals(const TNode<T> *ANode) const;
00367 };
00368 
00373 template<typename T>
00374 class TParamNode : public TNode<T> {
00375 public:
00376     TParamNode();
00377 
00378     virtual void accept(TNodeVisitor<T>&);
00379     virtual TParamNode<T> *clone() const;
00380     virtual bool equals(const TNode<T> *ANode) const;
00381 };
00382 
00387 template<typename T>
00388 class TUnaryNodeOp : public TNode<T> {
00389 private:
00390     std::auto_ptr<TNode<T> > FNode;
00391 
00392 protected:
00394     TUnaryNodeOp(typename TUnaryNodeOp<T>::TNodeType AType, short APriority, TNode<T> *ANode);
00395 
00396 public:
00398     TNode<T> *node() const;
00399 
00401     virtual TNode<T> *right() const;
00402 
00403     virtual bool equals(const TNode<T> *ANode) const;
00404 };
00405 
00410 template<typename T>
00411 class TBinaryNodeOp : public TNode<T> {
00412 private:
00413     std::auto_ptr<TNode<T> > FLeft;
00414     std::auto_ptr<TNode<T> > FRight;
00415 
00416 protected:
00418     TBinaryNodeOp(typename TBinaryNodeOp<T>::TNodeType AType, short APrio, TNode<T> *ALeft, TNode<T> *ARight);
00419 
00420 public:
00422     virtual TNode<T> *left() const;
00423 
00425     virtual TNode<T> *right() const;
00426 
00427     virtual bool equals(const TNode<T> *ANode) const;
00428 };
00429 
00434 template <typename T>
00435 class TPlusNode : public TBinaryNodeOp<T> {
00436 public:
00437     TPlusNode(TNode<T> *ALeft, TNode<T> *ARight);
00438 
00439     virtual void accept(TNodeVisitor<T>&);
00440     virtual TPlusNode<T> *clone() const;
00441 };
00442 
00447 template<typename T>
00448 class TNegNode : public TUnaryNodeOp<T> {
00449 public:
00450     TNegNode(TNode<T> *ANode);
00451 
00452     virtual void accept(TNodeVisitor<T>&);
00453     virtual TNegNode<T> *clone() const;
00454 };
00455 
00460 template<typename T>
00461 class TMulNode : public TBinaryNodeOp<T> {
00462 public:
00463     TMulNode(TNode<T> *ALeft, TNode<T> *ARight);
00464 
00465     virtual void accept(TNodeVisitor<T>&);
00466     virtual TMulNode *clone() const;
00467 };
00468 
00473 template<typename T>
00474 class TDivNode : public TBinaryNodeOp<T> {
00475 public:
00476     TDivNode(TNode<T> *ALeft, TNode<T> *ARight);
00477 
00478     virtual void accept(TNodeVisitor<T>&);
00479     virtual TDivNode *clone() const;
00480 };
00481 
00485 template<typename T>
00486 class TPowNode : public TBinaryNodeOp<T> {
00487 public:
00488     TPowNode(TNode<T> *ALeft, TNode<T> *ARight);
00489 
00490     virtual void accept(TNodeVisitor<T>&);
00491     virtual TPowNode *clone() const;
00492 };
00493 
00498 template<typename T>
00499 class TSqrtNode : public TUnaryNodeOp<T> {
00500 public:
00501     TSqrtNode(TNode<T> *ANode);
00502 
00503     virtual void accept(TNodeVisitor<T>&);
00504     virtual TSqrtNode *clone() const;
00505 };
00506 
00511 template<typename T>
00512 class TSinNode : public TUnaryNodeOp<T> {
00513 public:
00514     TSinNode(TNode<T> *AParam);
00515 
00516     virtual void accept(TNodeVisitor<T>&);
00517     virtual TSinNode *clone() const;
00518 };
00519 
00524 template<typename T>
00525 class TCosNode : public TUnaryNodeOp<T> {
00526 public:
00527     TCosNode(TNode<T> *AParam);
00528 
00529     virtual void accept(TNodeVisitor<T>&);
00530     virtual TCosNode *clone() const;
00531 };
00532 
00537 template<typename T>
00538 class TTanNode : public TUnaryNodeOp<T> {
00539 public:
00540     TTanNode(TNode<T> *AParam);
00541 
00542     virtual void accept(TNodeVisitor<T>&);
00543     virtual TTanNode *clone() const;
00544 };
00545 
00550 template<typename T>
00551 class TLnNode : public TUnaryNodeOp<T> {
00552 public:
00553     TLnNode(TNode<T> *AParam);
00554 
00555     virtual void accept(TNodeVisitor<T>&);
00556     virtual TLnNode *clone() const;
00557 };
00558 
00565 template<typename T>
00566 class TFuncNode : public TUnaryNodeOp<T> {
00567 private:
00568     std::string FName;
00569 
00570 public:
00571     TFuncNode(const std::string& AName, TNode<T> *AParam);
00572 
00573     std::string name() const;
00574 
00575     virtual void accept(TNodeVisitor<T>&);
00576     virtual TFuncNode<T> *clone() const;
00577 };
00578 
00585 template<typename T>
00586 class TIfNode : public TBinaryNodeOp<T> {
00587 private:
00588     std::auto_ptr<TNode<T> > FCondition;
00589 
00590 public:
00591     TIfNode(TNode<T> *ACondNode, TNode<T> *AThenNode, TNode<T> *AElseNode);
00592 
00593     TNode<T> *condition() const;
00594     TNode<T> *trueExpr() const;
00595     TNode<T> *falseExpr() const;
00596 
00597     virtual void accept(TNodeVisitor<T>&);
00598     virtual TIfNode *clone() const;
00599 };
00600 
00606 template<typename T>
00607 class TEquNode : public TBinaryNodeOp<T> {
00608 public:
00609     TEquNode(TNode<T> *ALeft, TNode<T> *ARight);
00610 
00611     virtual void accept(TNodeVisitor<T>&);
00612     virtual TEquNode *clone() const;
00613 };
00614 
00615 template<typename T>
00616 class TUnEquNode : public TBinaryNodeOp<T> {
00617 public:
00618     TUnEquNode(TNode<T> *ALeft, TNode<T> *ARight);
00619 
00620     virtual void accept(TNodeVisitor<T>&);
00621     virtual TUnEquNode *clone() const;
00622 };
00623 
00624 template<typename T>
00625 class TGreaterNode : public TBinaryNodeOp<T> {
00626 public:
00627     TGreaterNode(TNode<T> *ALeft, TNode<T> *ARight);
00628 
00629     virtual void accept(TNodeVisitor<T>&);
00630     virtual TGreaterNode *clone() const;
00631 };
00632 
00633 template<typename T>
00634 class TLessNode : public TBinaryNodeOp<T> {
00635 public:
00636     TLessNode(TNode<T> *ALeft, TNode<T> *ARight);
00637 
00638     virtual void accept(TNodeVisitor<T>&);
00639     virtual TLessNode *clone() const;
00640 };
00641 
00642 template<typename T>
00643 class TGreaterEquNode : public TBinaryNodeOp<T> {
00644 public:
00645     TGreaterEquNode(TNode<T> *ALeft, TNode<T> *ARight);
00646 
00647     virtual void accept(TNodeVisitor<T>&);
00648     virtual TGreaterEquNode *clone() const;
00649 };
00650 
00651 template<typename T>
00652 class TLessEquNode : public TBinaryNodeOp<T> {
00653 public:
00654     TLessEquNode(TNode<T> *ALeft, TNode<T> *ARight);
00655 
00656     virtual void accept(TNodeVisitor<T>&);
00657     virtual TLessEquNode *clone() const;
00658 };
00659 
00660 } // namespace math
00661 
00662 #include <math++/nodes.tcc>
00663 
00664 #endif

Generated on Mon Nov 28 20:08:59 2005 for MathTypeLibrary(libmath++) by  doxygen 1.4.5