00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00023 #ifndef libmath_nodes_h
00024 #define libmath_nodes_h
00025
00026 #include <deque>
00027 #include <string>
00028 #include <memory>
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
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
00052
00053
00054
00055
00063 template<typename T>
00064 class TNodeIterator {
00065 private:
00066 TNode<T> *FCurrent;
00067
00068 private:
00069 void increment() {
00070
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 (p && 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
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 (p && 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>;
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
00182 while (p && FCurrent == p->right() && inScope(p)) {
00183
00184 FCurrent = p;
00185 p = p->parent();
00186 }
00187 FCurrent = p;
00188
00189
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
00242
00243 NUMBER_NODE,
00244 SYMBOL_NODE,
00245 PARAM_NODE,
00246
00247 PLUS_NODE,
00248 NEG_NODE,
00249
00250 MUL_NODE,
00251 DIV_NODE,
00252 MOD_NODE,
00253
00254 POW_NODE,
00255
00256 EQU_NODE,
00257 UNEQU_NODE,
00258 LESS_EQU_NODE,
00259 GREATER_EQU_NODE,
00260 LESS_NODE,
00261 GREATER_NODE,
00262
00263 FUNC_NODE,
00264
00265 SQRT_NODE,
00266 SIN_NODE,
00267 COS_NODE,
00268 TAN_NODE,
00269 LN_NODE,
00270
00271 IF_NODE
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 }
00661
00662 #include <math++/nodes.tcc>
00663
00664 #endif