MathTypeLibrary(libmath++)  0.0.3
nodes.h
1 // Math Type Library
3 // $Id: nodes.h,v 1.13 2002/07/02 00:56:12 cparpart Exp $
4 // (This file contains the expression tree specific interface)
5 //
6 // Copyright (c) 2002 by Christian Parpart <cparpart@surakware.net>
7 //
8 // This library is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU Library General Public
10 // License as published by the Free Software Foundation; either
11 // version 2 of the License, or (at your option) any later version.
12 //
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 // Library General Public License for more details.
17 //
18 // You should have received a copy of the GNU Library General Public License
19 // along with this library; see the file COPYING.LIB. If not, write to
20 // the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
21 // Boston, MA 02111-1307, USA.
23 #ifndef libmath_nodes_h
24 #define libmath_nodes_h
25 
26 #include <deque>
27 #include <string>
28 #include <memory>
29 
30 /* EXAMPLE
31  * expression: 3x^4 + 2x^2 + 1
32  * the tree:
33  * ____ + ____
34  * / \
35  * ___ + ___ 1
36  * / \
37  * * *
38  * / \ / \
39  * 3 ^ 2 ^
40  * / \ / \
41  * x 4 x 2
42  */
43 
44 namespace math {
45 
46 template<typename> class TNodeVisitor;
47 template<typename> class TNode;
48 template<typename> class TUnaryNodeOp;
49 template<typename> class TBinaryNodeOp;
50 
51 // ISSUE : we should, perhaps, support two iterator types
52 // - one for the real iteration (each and every node, classic),
53 // - and one wich takes care about the math privileges and stays
54 // only in its scope
55 
63 template<typename T>
65 private:
66  TNode<T> *FCurrent;
67 
68 private:
69  void increment() {
70  // TODO : it must care about the operator privileges
71  if (FCurrent->right()) {
72  FCurrent = FCurrent->right();
73 
74  while (FCurrent->left())
75  FCurrent = FCurrent->left();
76  } else {
77  TNode<T> *p = FCurrent->parent();
78 
79  while (FCurrent == p->right()) {
80  FCurrent = p;
81  p = p->parent();
82  }
83 
84  if (FCurrent->right() != p)
85  FCurrent = p;
86  }
87  }
88 
89  bool decrement() {
90  // TODO : it must care about the operator privileges
91  TNode<T> *last = FCurrent;
92 
93  if (FCurrent->left()) {
94  TNode<T> *p = FCurrent->left();
95 
96  while (p->right())
97  p = p->right();
98 
99  FCurrent = p;
100  } else {
101  TNode<T> *p = FCurrent->parent();
102 
103  while (FCurrent == p->left()) {
104  FCurrent = p;
105  p = p->left();
106  }
107 
108  FCurrent = p;
109  }
110  return FCurrent != last;
111  }
112 
114  TNodeIterator<T>& rewind() {
115  while (decrement());
116 
117  return *this;
118  }
119 
120  friend class TNode<T>; // TNode<T> may access the method rewind.
121 
122 public:
123  TNodeIterator() : FCurrent(0) {}
124  TNodeIterator(TNode<T> *ANode) : FCurrent(ANode) {}
125  TNodeIterator(const TNodeIterator<T>& v) : FCurrent(v.FCurrent) {}
126 
127  TNode<T>& operator*() const { return *FCurrent; }
128  TNode<T> *operator->() const { return FCurrent; }
129 
130  TNode<T> *get() const { return FCurrent; }
131 
132  TNodeIterator<T>& operator++() { increment(); return *this; }
133  TNodeIterator<T>& operator--() { decrement(); return *this; }
134 };
135 
136 template<typename T>
137 bool operator==(const TNodeIterator<T>& a, const TNodeIterator<T>& b) {
138  return a.get() == b.get();
139 }
140 
141 template<typename T>
142 bool operator!=(const TNodeIterator<T>& a, const TNodeIterator<T>& b) {
143  return a.get() != b.get();
144 }
145 
150 template <typename NodeType>
152 public:
153  TOperandIter() : FOrigin(0), FCurrent(0) {}
154 
155  TOperandIter(NodeType *AOperator) : FOrigin(AOperator), FCurrent(FOrigin) {
156  do FCurrent = FCurrent->left();
157  while (inScope(FCurrent));
158  }
159 
160  TOperandIter(const TOperandIter<NodeType>& AProto) :
161  FOrigin(AProto.FOrigin), FCurrent(AProto.FCurrent) {}
162 
163  NodeType& operator*() const { return *FCurrent; }
164  NodeType *operator->() const { return FCurrent; }
165 
166  NodeType *get() const { return this ? FCurrent : 0; }
167 
168  TOperandIter<NodeType>& end() const { return *static_cast<TOperandIter<NodeType> *>(0); }
169 
170  TOperandIter<NodeType>& operator++() { increment(); return *this; }
171 
172 private:
173  NodeType *FOrigin;
174  NodeType *FCurrent;
175 
177  void increment() {
178  if (FCurrent) {
179  NodeType *p = FCurrent->parent();
180 
181  // as long as we're the right child of p
182  while (p && FCurrent == p->right() && inScope(p)) {
183  // go one up
184  FCurrent = p;
185  p = p->parent();
186  }
187  FCurrent = p;
188 
189  // reached end of iteration
190  if (!p || !inScope(p)) {
191  FCurrent = 0;
192  return;
193  }
194 
195  FCurrent = FCurrent->right();
196  if (inScope(FCurrent)) {
197  do FCurrent = FCurrent->left();
198  while (inScope(FCurrent));
199  }
200  }
201  }
202 
203  bool inScope(const NodeType *ANode) const {
204  switch (FOrigin->nodeType()) {
205  case NodeType::PLUS_NODE:
206  case NodeType::MUL_NODE:
207  return ANode->nodeType() == FOrigin->nodeType();
208  default:
209  return false;
210  }
211  }
212 };
213 
214 template<typename T>
215 bool operator==(const TOperandIter<T>& a, const TOperandIter<T>& b) {
216  return a.get() == b.get();
217 }
218 
219 template<typename T>
220 bool operator!=(const TOperandIter<T>& a, const TOperandIter<T>& b) {
221  return a.get() != b.get();
222 }
223 
227 template <typename T>
228 class TNode {
229 public:
230  typedef TNodeIterator<T> iterator;
231  typedef const TNodeIterator<T> const_iterator;
232 
233  typedef TOperandIter<TNode<T> > operand_iterator;
234  typedef TOperandIter<const TNode<T> > const_operand_iterator;
235 
240  enum TNodeType {
241  // take care, the order below is hard coded
242 
243  NUMBER_NODE, // numbers: 0, 3.1415, 2.17, 0.815, ... (prio: 0)
244  SYMBOL_NODE, // any symbol value: pi, e, ... (prio: 0)
245  PARAM_NODE, // the function parameter... (e.g. x) (prio: 0)
246 
247  PLUS_NODE, // x + y (prio: -5)
248  NEG_NODE, // -x (prio: -5)
249 
250  MUL_NODE, // x * y (prio: -3)
251  DIV_NODE, // x / y (prio: -3)
252  MOD_NODE, // x mod y (prio: -3)
253 
254  POW_NODE, // x ^ y (prio: -1)
255 
256  EQU_NODE, // x == y (prio: -10)
257  UNEQU_NODE, // x != y (prio: -10)
258  LESS_EQU_NODE, // x <= y (prio: -10)
259  GREATER_EQU_NODE,// x >= y (prio: -10)
260  LESS_NODE, // x < y (prio: -10)
261  GREATER_NODE, // x > y (prio: -10)
262 
263  FUNC_NODE, // userfunc(x) (prio: -1)
264 
265  SQRT_NODE, // sqrt(x); x ^ 0.5 (prio: -1)
266  SIN_NODE, // sin(x) (prio: -1)
267  COS_NODE, // cos(x) (prio: -1)
268  TAN_NODE, // tan(x) (prio: -1)
269  LN_NODE, // logn(x) (prio: -1)
270 
271  IF_NODE // IF(cond, then, else) (prio: -1)
272  };
273 
274 private:
276  TNodeType FNodeType;
278  short FPriority;
280  TNode<T> *FParent;
281 
282 protected:
284  TNode(TNodeType ANodeType, short APriority, TNode<T> *AParentNode = 0);
285  TNode(const TNode<T>& n);
286 
288  void parent(TNode<T> *AParent);
289 
290  friend class TUnaryNodeOp<T>;
291  friend class TBinaryNodeOp<T>;
292 
293 public:
295  virtual ~TNode();
296 
298  TNodeType nodeType() const;
299 
301  short priority() const;
302 
304  TNode<T> *parent() const;
305 
307  virtual TNode<T> *left() const;
308 
310  virtual TNode<T> *right() const;
311 
313  virtual void accept(TNodeVisitor<T>&) = 0;
314 
316  virtual TNode<T> *clone() const = 0;
317 
319  iterator begin() { return iterator(this).rewind(); }
320 
322  iterator end() { return iterator(0); }
323 
325  virtual bool equals(const TNode<T> *ANode) const = 0;
326 };
327 
328 template<typename T> bool operator==(const TNode<T>&, const TNode<T>&);
329 template<typename T> bool operator!=(const TNode<T>&, const TNode<T>&);
330 
334 template<typename T>
335 class TNumberNode : public TNode<T> {
336 private:
337  T FNumber;
338 
339 public:
340  TNumberNode(const T& AValue);
341 
342  T number() const;
343 
344  virtual void accept(TNodeVisitor<T>&);
345  virtual TNumberNode<T> *clone() const;
346  virtual bool equals(const TNode<T> *ANode) const;
347 };
348 
353 template<typename T>
354 class TSymbolNode : public TNode<T> {
355 private:
356  std::string FSymbol;
357 
358 public:
359  TSymbolNode(const std::string& ASymbol);
360 
362  std::string symbol() const;
363 
364  virtual void accept(TNodeVisitor<T>&);
365  virtual TSymbolNode<T> *clone() const;
366  virtual bool equals(const TNode<T> *ANode) const;
367 };
368 
373 template<typename T>
374 class TParamNode : public TNode<T> {
375 public:
376  TParamNode();
377 
378  virtual void accept(TNodeVisitor<T>&);
379  virtual TParamNode<T> *clone() const;
380  virtual bool equals(const TNode<T> *ANode) const;
381 };
382 
387 template<typename T>
388 class TUnaryNodeOp : public TNode<T> {
389 private:
390  std::auto_ptr<TNode<T> > FNode;
391 
392 protected:
394  TUnaryNodeOp(typename TUnaryNodeOp<T>::TNodeType AType, short APriority, TNode<T> *ANode);
395 
396 public:
398  TNode<T> *node() const;
399 
401  virtual TNode<T> *right() const;
402 
403  virtual bool equals(const TNode<T> *ANode) const;
404 };
405 
410 template<typename T>
411 class TBinaryNodeOp : public TNode<T> {
412 private:
413  std::auto_ptr<TNode<T> > FLeft;
414  std::auto_ptr<TNode<T> > FRight;
415 
416 protected:
418  TBinaryNodeOp(typename TBinaryNodeOp<T>::TNodeType AType, short APrio, TNode<T> *ALeft, TNode<T> *ARight);
419 
420 public:
422  virtual TNode<T> *left() const;
423 
425  virtual TNode<T> *right() const;
426 
427  virtual bool equals(const TNode<T> *ANode) const;
428 };
429 
434 template <typename T>
435 class TPlusNode : public TBinaryNodeOp<T> {
436 public:
437  TPlusNode(TNode<T> *ALeft, TNode<T> *ARight);
438 
439  virtual void accept(TNodeVisitor<T>&);
440  virtual TPlusNode<T> *clone() const;
441 };
442 
447 template<typename T>
448 class TNegNode : public TUnaryNodeOp<T> {
449 public:
450  TNegNode(TNode<T> *ANode);
451 
452  virtual void accept(TNodeVisitor<T>&);
453  virtual TNegNode<T> *clone() const;
454 };
455 
460 template<typename T>
461 class TMulNode : public TBinaryNodeOp<T> {
462 public:
463  TMulNode(TNode<T> *ALeft, TNode<T> *ARight);
464 
465  virtual void accept(TNodeVisitor<T>&);
466  virtual TMulNode *clone() const;
467 };
468 
473 template<typename T>
474 class TDivNode : public TBinaryNodeOp<T> {
475 public:
476  TDivNode(TNode<T> *ALeft, TNode<T> *ARight);
477 
478  virtual void accept(TNodeVisitor<T>&);
479  virtual TDivNode *clone() const;
480 };
481 
485 template<typename T>
486 class TPowNode : public TBinaryNodeOp<T> {
487 public:
488  TPowNode(TNode<T> *ALeft, TNode<T> *ARight);
489 
490  virtual void accept(TNodeVisitor<T>&);
491  virtual TPowNode *clone() const;
492 };
493 
498 template<typename T>
499 class TSqrtNode : public TUnaryNodeOp<T> {
500 public:
501  TSqrtNode(TNode<T> *ANode);
502 
503  virtual void accept(TNodeVisitor<T>&);
504  virtual TSqrtNode *clone() const;
505 };
506 
511 template<typename T>
512 class TSinNode : public TUnaryNodeOp<T> {
513 public:
514  TSinNode(TNode<T> *AParam);
515 
516  virtual void accept(TNodeVisitor<T>&);
517  virtual TSinNode *clone() const;
518 };
519 
524 template<typename T>
525 class TCosNode : public TUnaryNodeOp<T> {
526 public:
527  TCosNode(TNode<T> *AParam);
528 
529  virtual void accept(TNodeVisitor<T>&);
530  virtual TCosNode *clone() const;
531 };
532 
537 template<typename T>
538 class TTanNode : public TUnaryNodeOp<T> {
539 public:
540  TTanNode(TNode<T> *AParam);
541 
542  virtual void accept(TNodeVisitor<T>&);
543  virtual TTanNode *clone() const;
544 };
545 
550 template<typename T>
551 class TLnNode : public TUnaryNodeOp<T> {
552 public:
553  TLnNode(TNode<T> *AParam);
554 
555  virtual void accept(TNodeVisitor<T>&);
556  virtual TLnNode *clone() const;
557 };
558 
565 template<typename T>
566 class TFuncNode : public TUnaryNodeOp<T> {
567 private:
568  std::string FName;
569 
570 public:
571  TFuncNode(const std::string& AName, TNode<T> *AParam);
572 
573  std::string name() const;
574 
575  virtual void accept(TNodeVisitor<T>&);
576  virtual TFuncNode<T> *clone() const;
577 };
578 
585 template<typename T>
586 class TIfNode : public TBinaryNodeOp<T> {
587 private:
588  std::auto_ptr<TNode<T> > FCondition;
589 
590 public:
591  TIfNode(TNode<T> *ACondNode, TNode<T> *AThenNode, TNode<T> *AElseNode);
592 
593  TNode<T> *condition() const;
594  TNode<T> *trueExpr() const;
595  TNode<T> *falseExpr() const;
596 
597  virtual void accept(TNodeVisitor<T>&);
598  virtual TIfNode *clone() const;
599 };
600 
606 template<typename T>
607 class TEquNode : public TBinaryNodeOp<T> {
608 public:
609  TEquNode(TNode<T> *ALeft, TNode<T> *ARight);
610 
611  virtual void accept(TNodeVisitor<T>&);
612  virtual TEquNode *clone() const;
613 };
614 
615 template<typename T>
616 class TUnEquNode : public TBinaryNodeOp<T> {
617 public:
618  TUnEquNode(TNode<T> *ALeft, TNode<T> *ARight);
619 
620  virtual void accept(TNodeVisitor<T>&);
621  virtual TUnEquNode *clone() const;
622 };
623 
624 template<typename T>
625 class TGreaterNode : public TBinaryNodeOp<T> {
626 public:
627  TGreaterNode(TNode<T> *ALeft, TNode<T> *ARight);
628 
629  virtual void accept(TNodeVisitor<T>&);
630  virtual TGreaterNode *clone() const;
631 };
632 
633 template<typename T>
634 class TLessNode : public TBinaryNodeOp<T> {
635 public:
636  TLessNode(TNode<T> *ALeft, TNode<T> *ARight);
637 
638  virtual void accept(TNodeVisitor<T>&);
639  virtual TLessNode *clone() const;
640 };
641 
642 template<typename T>
643 class TGreaterEquNode : public TBinaryNodeOp<T> {
644 public:
645  TGreaterEquNode(TNode<T> *ALeft, TNode<T> *ARight);
646 
647  virtual void accept(TNodeVisitor<T>&);
648  virtual TGreaterEquNode *clone() const;
649 };
650 
651 template<typename T>
652 class TLessEquNode : public TBinaryNodeOp<T> {
653 public:
654  TLessEquNode(TNode<T> *ALeft, TNode<T> *ARight);
655 
656  virtual void accept(TNodeVisitor<T>&);
657  virtual TLessEquNode *clone() const;
658 };
659 
660 } // namespace math
661 
662 #include <math++/nodes.tcc>
663 
664 #endif
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TGreaterEquNode * clone() const
clones that node
std::string symbol() const
returns the symbol&#39;s name
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TNode< T > * right() const
returns the child node (wrapper to the more declarative node() method)
virtual TMulNode * clone() const
clones that node
TNodeType nodeType() const
returns the type of this node
virtual TFuncNode< T > * clone() const
clones that node
void parent(TNode< T > *AParent)
initializes the parent node with the given one
virtual TEquNode * clone() const
clones that node
virtual TGreaterNode * clone() const
clones that node
virtual TNode< T > * left() const
returns the left child node (returns 0 if this node doesn&#39;t support one)
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
virtual TTanNode * clone() const
clones that node
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
short priority() const
returns the node priority
TNode< T > * parent() const
returns the parent node (returns 0 if this node is the root node)
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TLessEquNode * clone() const
clones that node
virtual TSymbolNode< T > * clone() const
clones that node
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TNegNode< T > * clone() const
clones that node
virtual TNumberNode< T > * clone() const
clones that node
TNode< T > * node() const
returns the child node for that unary operator node.
virtual TSqrtNode * clone() const
clones that node
iterator begin()
iterator access to the first value node in this operator level
Definition: nodes.h:319
virtual bool equals(const TNode< T > *ANode) const =0
returns true, if given node equals to this one
virtual TNode< T > * right() const
returns the left child node of the expression tree
virtual TSinNode * clone() const
clones that node
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
TNode(TNodeType ANodeType, short APriority, TNode< T > *AParentNode=0)
initializes this node for given node type.
virtual TParamNode< T > * clone() const
clones that node
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
virtual ~TNode()
each virtual class needs a virtual destructor (this one does nothing)
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TNode< T > * right() const
returns the right child node (returns 0 if this node doesn&#39;t support one)
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
iterator end()
iterator access to the end
Definition: nodes.h:322
virtual bool equals(const TNode< T > *ANode) const
returns true, if given node equals to this one
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual void accept(TNodeVisitor< T > &)=0
calls the visit method in TNodeVisitor&lt;&gt;
virtual TNode< T > * left() const
returns the right child node of the expression tree
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TPowNode * clone() const
clones that node
virtual TPlusNode< T > * clone() const
clones that node
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TCosNode * clone() const
clones that node
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TLessNode * clone() const
clones that node
virtual TDivNode * clone() const
clones that node
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TUnEquNode * clone() const
clones that node
TBinaryNodeOp(typename TBinaryNodeOp< T >::TNodeType AType, short APrio, TNode< T > *ALeft, TNode< T > *ARight)
creates an binary operator node of type AType
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual void accept(TNodeVisitor< T > &)
calls the visit method in TNodeVisitor&lt;&gt;
virtual TNode< T > * clone() const =0
clones that node
virtual TIfNode * clone() const
clones that node
TUnaryNodeOp(typename TUnaryNodeOp< T >::TNodeType AType, short APriority, TNode< T > *ANode)
creates an unary operator node of type AType.
virtual TLnNode * clone() const
clones that node