Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | Related Pages

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--() { declrement(); 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 Thu Jul 29 08:56:44 2004 for MathTypeLibrary(libmath++) by doxygen 1.3.7