COPASI API  4.16.103
CNormalTranslation.cpp
Go to the documentation of this file.
1 // Begin CVS Header
2 // $Source: /Volumes/Home/Users/shoops/cvs/copasi_dev/copasi/compareExpressions/CNormalTranslation.cpp,v $
3 // $Revision: 1.50 $
4 // $Name: $
5 // $Author: shoops $
6 // $Date: 2012/05/15 15:56:21 $
7 // End CVS Header
8 
9 // Copyright (C) 2012 - 2010 by Pedro Mendes, Virginia Tech Intellectual
10 // Properties, Inc., University of Heidelberg, and The University
11 // of Manchester.
12 // All rights reserved.
13 
14 // Copyright (C) 2008 by Pedro Mendes, Virginia Tech Intellectual
15 // Properties, Inc., EML Research, gGmbH, University of Heidelberg,
16 // and The University of Manchester.
17 // All rights reserved.
18 
19 // Copyright (C) 2001 - 2007 by Pedro Mendes, Virginia Tech Intellectual
20 // Properties, Inc. and EML Research, gGmbH.
21 // All rights reserved.
22 
23 #ifdef WIN32
24 # pragma warning (disable: 4786)
25 # pragma warning (disable: 4243)
26 // warning C4355: 'this' : used in base member initializer list
27 # pragma warning (disable: 4355)
28 #endif // WIN32
29 
30 #include <algorithm>
31 #include <iostream>
32 #include <set>
33 #include <string>
34 #include <sstream>
35 #include <vector>
36 
37 #include "copasi.h"
38 
39 #include "CNormalBase.h"
41 #include "CNormalTranslation.h"
42 #include "CNormalFraction.h"
43 #include "CNormalSum.h"
44 #include "CNormalProduct.h"
45 #include "CNormalLogical.h"
46 
49 
50 const double CNormalTranslation::ZERO = 1e-100;
51 const unsigned int CNormalTranslation::RECURSION_LIMIT = 20;
52 const CEvaluationNode CNormalTranslation::NEUTRAL_ELEMENT_ADD = CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "0.0");
53 const CEvaluationNode CNormalTranslation::NEUTRAL_ELEMENT_MULTIPLY = CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "1.0");
54 const CEvaluationNode CNormalTranslation::NEUTRAL_ELEMENT_OR = CEvaluationNodeConstant(CEvaluationNodeConstant::FALSE, "FALSE");
55 const CEvaluationNode CNormalTranslation::NEUTRAL_ELEMENT_AND = CEvaluationNodeConstant(CEvaluationNodeConstant::TRUE, "TRUE");
56 const CEvaluationNode CNormalTranslation::ZERO_NODE = CNormalTranslation::NEUTRAL_ELEMENT_ADD;
57 const CEvaluationNode CNormalTranslation::ONE_NODE = CNormalTranslation::NEUTRAL_ELEMENT_MULTIPLY;
58 const CEvaluationNode CNormalTranslation::PLUS_NODE = CEvaluationNodeOperator(CEvaluationNodeOperator::PLUS, "+");
59 const CEvaluationNode CNormalTranslation::TIMES_NODE = CEvaluationNodeOperator(CEvaluationNodeOperator::MULTIPLY, "*");
60 
62 {}
63 
64 /**
65  * Simplify an evaluation tree given by the root node by creating a new simplified tree from the original one.
66  * The tree itself is actually not created!
67  * @return CEvaluationNode*, pointer to root node of the newly created tree.
68  */
70 {
71  const CEvaluationNode * child = dynamic_cast<const CEvaluationNode*>(node->getChild());
72  CEvaluationNode * newchild = NULL;
73  std::vector<CEvaluationNode*> children;
74 
75  while (child != NULL)
76  {
77  newchild = simplifyTree(child);
78  child = dynamic_cast<const CEvaluationNode*>(child->getSibling());
79  children.push_back(newchild);
80  }
81 
82  CEvaluationNode* newnode = node->simplifyNode(children);
83  return newnode;
84 }
85 
86 /**
87  * Creating a simplified tree by calling simplifyTree repeatedly until it cannot be simplified further.
88  * The tree itself is actually not created!
89  * @return CEvaluationNode*, pointer to root node of the newly created tree.
90  */
92 {
93  CEvaluationNode * root1 = simplifyTree(root0);
94 
95  if (root1->buildInfix() != root0->buildInfix())
96  {
97  CEvaluationNode * root2 = simplifyTreeReptdly(root1);
98  delete root1;
99  return root2;
100  }
101  else
102  {
103  return root1;
104  }
105 }
106 
107 /**
108  * Translate and simplify a tree given by the root node into CNormal structure
109  * @return CNormalFraction*
110  */
112 {
113  //CEvaluationNode * root1 = simplifyTreeReptdly(root0);
116  delete root1;
118  base->simplify();
119 
120  delete root2;
121 
122  return base;
123 }
124 
125 /**
126  * Translate and simplify a tree by calling normAndSimplify repeatedly until it cannot be simplified further
127  * @return CNormalFraction*
128  */
130 {
132 
133  const CEvaluationNode* root0 = tree0->getRoot();
134 
135  CNormalFraction * base0 = normAndSimplify(root0);
136 
137  std::stringstream tmp;
138  tmp << base0->toString();
139 
140  CEvaluationTree * tree1 = new CEvaluationTree("second tree", NULL, CEvaluationTree::Function);
141 
142  tree1->setInfix(tmp.str());
143 
144  if (tree1->getInfix() != tree0->getInfix())
145  {
146  CNormalFraction * base1 = normAndSimplifyReptdly(tree1, ++depth);
147  delete tree1;
148  delete base0;
149  return base1;
150  }
151  else
152  {
153  delete tree1;
154  return base0;
155  }
156 }
157 
158 /**
159  * Translate and simplify a tree by calling normAndSimplify repeatedly until it cannot be simplified further
160  * @return CNormalFraction*
161  */
163 {
165 
166  CNormalFraction * base0 = normAndSimplify(root0);
167 
168  std::stringstream tmp;
169 
170  //CEvaluationTree * tree1 = new CEvaluationTree("second tree", NULL, CEvaluationTree::Function);
171  CEvaluationNode* pTmpNode = convertToCEvaluationNode(*base0);
172  assert(pTmpNode != NULL);
173  CNormalFraction* pFraction = dynamic_cast<CNormalFraction*>(base0);
174  assert(pFraction != NULL);
175 
176  if (pTmpNode->buildInfix() != root0->buildInfix())
177  {
178  CNormalFraction * base1 = normAndSimplifyReptdly(pTmpNode, ++depth);
179  delete pTmpNode;
180  delete base0;
181  return base1;
182  }
183  else
184  {
185  delete pTmpNode;
186  return base0;
187  }
188 }
189 
190 
191 
192 /**
193  * Takes a node and expands expressions like x^(n+m) to x^n * x^m
194  * If some of the exponent summands are negative numbers, the expression is divided
195  * by the positive exponent expression (x^(n-5) -> x^n / x^5
196  */
198 {
199  CEvaluationNode* pResult = NULL;
200  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pRoot->getChild());
201  std::vector<CEvaluationNode*> children;
202 
203  // go through this depth first and expand the power exponents in children
204  while (pChild != NULL)
205  {
207  children.push_back(pNewChild);
208  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
209  }
210 
212  {
213  assert(children.size() == 2);
214  std::vector<const CEvaluationNode*> summands;
215  CNormalTranslation::findSummands(children[1], summands);
216  // for each summand create a power node with a copy of the first child
217  // in children as child 1 and a copy of the summand as child 2
218  std::vector<CEvaluationNode*> numeratorNodes;
219  std::vector<CEvaluationNode*> denominatorNodes;
220  std::vector<const CEvaluationNode*>::iterator it = summands.begin(), endit = summands.end();
221 
222  while (it != endit)
223  {
225  pPowerNode->addChild(children[0]->copyBranch());
226 
228  {
229  pPowerNode->addChild(dynamic_cast<const CEvaluationNode*>((*it)->getChild())->copyBranch());
230  denominatorNodes.push_back(pPowerNode);
231  }
232  else if ((CEvaluationNode::type((*it)->getType()) == CEvaluationNode::NUMBER && dynamic_cast<const CEvaluationNodeNumber*>((*it))->getValue() < 0.0))
233  {
234  std::ostringstream os;
235  os.precision(18);
236  os << fabs(dynamic_cast<const CEvaluationNodeNumber*>(*it)->getValue());
237  pPowerNode->addChild(new CEvaluationNodeNumber((CEvaluationNodeNumber::SubType)CEvaluationNode::subType((*it)->getType()), os.str().c_str()));
238  denominatorNodes.push_back(pPowerNode);
239  }
240  else
241  {
242  pPowerNode->addChild((*it)->copyBranch());
243  numeratorNodes.push_back(pPowerNode);
244  }
245 
246  ++it;
247  }
248 
249  delete children[0];
250  delete children[1];
251 
252  // create the numerator chain
253  if (numeratorNodes.empty())
254  {
256  }
257  else
258  {
259  pResult = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, numeratorNodes);
260  }
261 
262  assert(pResult != NULL);
263 
264  // if there are items in the denominator vector create the denominator
265  // chain and divide the numerator chain by the denominator chain
266  if (!denominatorNodes.empty())
267  {
269  pDivision->addChild(pResult);
270  pDivision->addChild(CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, denominatorNodes));
271  pResult = pDivision;
272  }
273  }
274  else
275  {
276  // copy the node and add the children
277  pResult = CEvaluationNode::create(pRoot->getType(), pRoot->getData());
278  std::vector<CEvaluationNode*>::iterator it = children.begin(), endit = children.end();
279 
280  while (it != endit)
281  {
282  pResult->addChild(*it);
283  ++it;
284  }
285  }
286 
287  return pResult;
288 }
289 
290 
291 /**
292  * Concatenates the goven nodes by the given operation.
293  * So if the nodes are node1, node2,node3 and the operation is multiplication,
294  * this will create node1 * node2 * node3
295  * The node that is returned contains copies of the original nodes and the caller is responsible
296  * for freeing the memory.
297  */
298 CEvaluationNode* CNormalTranslation::createOperatorChain(CEvaluationNodeOperator::SubType type, const char* data, const std::vector<const CEvaluationNode*>& nodes)
299 {
300  CEvaluationNode* pResult = NULL;
301 
302  if (nodes.size() == 0)
303  {
305  }
306  else if (nodes.size() == 1)
307  {
308  pResult = nodes[0]->copyBranch();
309  }
310  else
311  {
312  // start from the back to create the deepest nodes first
313  std::vector<const CEvaluationNode*>::const_reverse_iterator it = nodes.rbegin(), endit = nodes.rend();
314  CEvaluationNode* pOperator = new CEvaluationNodeOperator(type, data);
315  CEvaluationNode* pChild2 = (*it)->copyBranch();
316  ++it;
317  CEvaluationNode* pChild1 = (*it)->copyBranch();
318  pOperator->addChild(pChild1);
319  pOperator->addChild(pChild2);
320  ++it;
321  pChild2 = pOperator;
322 
323  while (it != endit)
324  {
325  pOperator = new CEvaluationNodeOperator(type, data);
326  pOperator->addChild((*it)->copyBranch());
327  pOperator->addChild(pChild2);
328  pChild2 = pOperator;
329  ++it;
330  }
331 
332  pResult = pOperator;
333  }
334 
335  return pResult;
336 }
337 
338 
339 /**
340  * This method takes a node and if the node is the node is an addition operator,
341  * the method goes through the children of the node and check for more addition operators.
342  * All children of addition operators are added to the given summands vector.
343  * If the given node is not an addition operator, the methods adds the node itself to the vector
344  * of summands.
345  * The nodes that are added to the vector are the original nodes and not copies.
346  */
347 void CNormalTranslation::findSummands(const CEvaluationNode* pRoot, std::vector<const CEvaluationNode*>& summands)
348 {
350  {
351  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pRoot->getChild());
352  assert(pChild1 != NULL);
353 
354  if (pChild1 != NULL)
355  {
356  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
357  assert(pChild2 != NULL);
358 
359  if (pChild2 != NULL)
360  {
361  assert(pChild2->getSibling() == NULL);
362 
364  {
365  CNormalTranslation::findSummands(pChild1, summands);
366  }
367  else
368  {
369  summands.push_back(pChild1);
370  }
371 
373  {
374  CNormalTranslation::findSummands(pChild2, summands);
375  }
376  else
377  {
378  summands.push_back(pChild2);
379  }
380  }
381  }
382  }
383  else
384  {
385  summands.push_back(pRoot);
386  }
387 }
388 
389 // new routines
390 
391 /**
392  * This method elminates subexpressions from an expression
393  * It calls:
394  * elementaryElimination
395  * eliminateNestedPowers
396  * eliminatePowersOfFractions
397  * eliminateDirectlyNestedFunctions
398  * cancel
399  *
400  * These functions are called as long as the resulting tree contains changes
401  */
403 {
404  CEvaluationNode* pResult = pOrig->copyBranch();
405  CEvaluationNode* pTmp = NULL;
406  std::string infix = pResult->buildInfix(); //base->toString();
407  //delete base;
408  bool changed = true;
409 
410  while (changed)
411  {
412  // first make elementary eliminations
414 
415  if (pTmp != pResult) delete pResult;
416 
417  // now get rid of nested powers a^b^c
419 
420  if (pResult != NULL)
421  {
422  delete pTmp;
423  pTmp = pResult;
424  }
425 
426  // eliminate fractions within powers
427  // (a/b)^3 -> a^3 / b^3
428  // now get rid of directly nested fractions
430 
431  if (pResult != NULL)
432  {
433  delete pTmp;
434  pTmp = pResult;
435  }
436 
438 
439  if (pResult != NULL)
440  {
441  delete pTmp;
442  }
443  else
444  {
445  pResult = pTmp;
446  }
447 
448  // now cancel since cancelation can lead to new nodes for which
449  // elementary elimination would be possible, we might have to run
450  // this loop again
451  pTmp = CNormalTranslation::newCancel(pResult);
452  //std::cout << "Before: " << pResult->buildInfix() << std::endl;
453 
454 
455  if (pTmp != NULL)
456  {
457  delete pResult;
458  }
459  else
460  {
461  pTmp = pResult;
462  }
463 
464  //std::cout << "Finished: " << pTmp->buildInfix() << std::endl;
465  //delete pResult;
466 
467  // check if we are done
468  // we are done if the infix has not changed over one loop run
469  if (/*base->toString()*/pTmp->buildInfix() == infix)
470  {
471  changed = false;
472  }
473  else
474  {
475  infix = pTmp->buildInfix(); //base->toString();
476  }
477 
478  pResult = pTmp;
479  //delete base;
480  //base = NULL;
481  }
482 
483  return pResult;
484 }
485 
486 /**
487  * This routine is responsible for recursively simplifying a given
488  * CEvaluationNode based tree.
489  *
490  * Calls:
491  * eliminate
492  * newEvaluateNumbers
493  * cancel
494  * expandPowerBases
495  * expandPowerNodes
496  * expandProducts
497  *
498  * These methods are called as long as there are changes in the expression tree.
499  */
501 {
502  CEvaluationNode* pResult = NULL;
503  bool finished = false;
504  //CNormalFraction* base = createNormalRepresentation(pOrig);
505  //assert(base != NULL);
506  std::string infix = pOrig->buildInfix(); //base->toString();
507  std::string infix2 = infix;
508  CEvaluationNode* pTmp = pOrig->copyBranch();
509  unsigned int counter = 0;
510 
511  while (!finished)
512  {
513  ++counter;
514 
516 
517  pResult = CNormalTranslation::eliminate(pTmp);
518  delete pTmp;
519  // now we evaluate everything that can be evaluated, e.g. operations on
520  // numbers
522 
523  if (pTmp != NULL)
524  {
525  delete pResult;
526  }
527  else
528  {
529  pTmp = pResult;
530  }
531 
532  // this method combines identical multiplicants and summands
533  pResult = CNormalTranslation::newCancel(pTmp);
534  //std::cout << "Before: " << pTmp->buildInfix() << std::endl;
535 
536  if (pResult != NULL)
537  {
538  delete pTmp;
539  }
540  else
541  {
542  pResult = pTmp;
543  }
544 
545  //std::cout << "Finished: " << pResult->buildInfix() << std::endl;
546  //delete pTmp;
547  // now expand products in bases to power operators
548  pTmp = CNormalTranslation::expandPowerBases(pResult);
549 
550  if (pTmp != NULL)
551  {
552  delete pResult;
553  }
554  else
555  {
556  pTmp = pResult;
557  }
558 
559  // now expand the exponents in the power nodes and multiply products
560  // expansions can lead to new cancelations being possible so we might
561  // need to rerun the whole loop
562  pResult = CNormalTranslation::expandPowerNodes(pTmp);
563 
564  if (pResult != NULL)
565  {
566  delete pTmp;
567  }
568  else
569  {
570  pResult = pTmp;
571  }
572 
573  pTmp = CNormalTranslation::expandProducts(pResult);
574 
575  if (pTmp != NULL)
576  {
577  delete pResult;
578  pResult = pTmp;
579  }
580 
581  // check if we are done
582  // we are done, once the infix has not changed during one loop run
583  //std::cout << "infix old: " << infix << std::endl;
584  //std::cout << "infix new: " << pResult->buildInfix() << std::endl;
585  if (/*base->toString()*/pResult->buildInfix() == infix)
586  {
587  finished = true;
588  }
589  else
590  {
591  infix = pResult->buildInfix(); //base->toString();
592  }
593 
594  //std::cout << "infix: " << infix << std::endl;
595  pTmp = pResult;
596  }
597 
598  pTmp = CNormalTranslation::product2fraction(pResult);
599  delete pResult;
600  pResult = pTmp;
601  return pResult;
602 }
603 
604 /**
605  * This routine is responsible for all elementary eliminations, e.g. addition
606  * of 0.
607  * These steps can not lead to new simplifications in the children of the node
608  * being simplified, so it is not necessary to run this on the children again.
609  *
610  * Calls one of the following:
611  * elementaryEliminationPower
612  * elementaryEliminationModulus
613  * elementaryEliminationMultiply
614  * elementaryEliminationDivide
615  * elementaryEliminationPlus
616  * elementaryEliminationMinus
617  * elementaryEliminationFunction
618  *
619  * Which method is called depends on the node passed to the method.
620  * The method is called recursively on the children of the passed in node.
621  */
623 {
624  // this is done depth first
625  CEvaluationNode* pResult = pOrig;
626  CEvaluationNode* pChild = dynamic_cast<CEvaluationNode*>(pOrig->getChild());
627  CEvaluationNode* pLastChild = pOrig;
628 
629  while (pChild != NULL)
630  {
631  CEvaluationNode* pNewChild = elementaryElimination(pChild);
632  assert(pNewChild != NULL);
633 
634  if (pNewChild != pChild)
635  {
636  // remove the old child and add the new one
637  pOrig->removeChild(pChild);
638  delete pChild;
639  pChild = pNewChild;
640  pOrig->addChild(pNewChild, pLastChild);
641  }
642 
643  pLastChild = pChild;
644  pChild = dynamic_cast<CEvaluationNode*>(pChild->getSibling());
645  }
646 
648  {
649  // check if we can eliminate anything
650  // check if one of the children is (-)0, (-)1, NaN or INFINITY
652  {
655  break;
658  break;
661  break;
664  break;
667  break;
670  break;
671  default:
672  // we should never end up here
673  fatalError();
674  break;
675  }
676  }
678  {
680  }
681 
682  if (pResult == NULL)
683  {
684  pResult = pOrig;
685  }
686 
687  return pResult;
688 }
689 
690 /**
691  * This method makes elementary eliminations on function nodes
692  * The elimiation made here are:
693  *
694  * a) unary plus nodes are replaced by their child
695  * b) unary minus nodes of numbers are replaced by the corresponding number * -1
696  * c) Function calls to NaN nodes are replaced by NaN
697  *
698  * The node returned by this method is a new node and the caller is responsible for freeing the memory.
699  */
701 {
702  // PLUS(X) -> X
703  // X(NaN) -> NaN
704  // MINUX(X) where X is a number -> -X
705  CEvaluationNode* pResult = NULL;
706  const CEvaluationNode* pChild = NULL;
707 
709  {
711  break;
713  pChild = dynamic_cast<const CEvaluationNode*>(pFunctionNode->getChild());
714  assert(pChild != NULL);
715  assert(pChild->getSibling() == NULL);
716  pResult = pChild->copyBranch();
717  break;
719  pChild = dynamic_cast<const CEvaluationNode*>(pFunctionNode->getChild());
720  assert(pChild != NULL);
721  assert(pChild->getSibling() == NULL);
722 
724  {
725  std::ostringstream os;
726  os.precision(18);
727  os << -1.0*dynamic_cast<const CEvaluationNodeNumber*>(pChild)->getValue();
728  pResult = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
729  }
732  {
734  }
735 
736  if (pResult == NULL)
737  {
738  // MINUS(X) -> -1.0 * X
740  pResult->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "-1.0"));
741  pResult->addChild(pChild->copyBranch());
742  }
743 
744  break;
745  default:
746  pChild = dynamic_cast<const CEvaluationNode*>(pFunctionNode->getChild());
747 
748  while (pChild != NULL)
749  {
751  {
753  break;
754  }
755 
756  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
757  }
758 
759  break;
760  }
761 
762  return pResult;
763 }
764 
765 /**
766  * This method makes the elementary elimination on a power node.
767  * This method makes the following elimination
768  * a) x^NaN -> NaN
769  * b) 0^0 -> NaN
770  * c) 0^(-x) -> NaN
771  * d) 0^x -> 0
772  * e) 1^x -> 1
773  * f) NaN^x -> NaN
774  * g) NFINITY^(-NaN) -> NaN
775  * i) INFINITY^-x -> 0.0 // x being a positive number
776  * j) INFINITY^x -> INFINITY // x being a positive number
777  * k) INFINITY^0 -> 1
778  * l) INFINITY^0 -> 1.0
779  * m) INFINITY^(-x) -> 0.0
780  * n) INFINITY^x -> INFINITY
781  * o) INFINITY ^ x -> INFINITY
782  * p) x^0 -> 1
783  * q) x^1 -> x
784  *
785  * The caller is responsible for releasing the memory for the returned object.
786  */
788 {
789  CEvaluationNode* pResult = NULL;
790  assert(CEvaluationNode::type(pPowerNode->getType()) == CEvaluationNode::OPERATOR);
792  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pPowerNode->getChild());
793  assert(pChild1 != NULL);
794  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
795  assert(pChild2 != NULL);
796  assert(pChild2->getSibling() == NULL);
797 
798  if (CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER)
799  {
800  // 0 and 1
801  const CEvaluationNodeNumber* pNumberNode = dynamic_cast<const CEvaluationNodeNumber*>(pChild1);
802  assert(pNumberNode != NULL);
803  double value = pNumberNode->getValue();
804 
805  if (fabs(value) < ZERO)
806  {
807  // 0^(NaN) -> NaN
809  {
811  }
812  else if (pChild2->getType() == CEvaluationNode::NUMBER)
813  {
814  const CEvaluationNodeNumber* pNumberNode2 = dynamic_cast<const CEvaluationNodeNumber*>(pChild2);
815  double value = pNumberNode2->getValue();
816 
817  // 0^0 -> NaN
818  // 0^(-x) -> NaN
819  if (fabs(value) < ZERO || value < 0.0)
820  {
822  }
823  }
824 
825  // 0^x -> 0
826  if (pResult == pPowerNode)
827  {
829  }
830  }
831  else if (fabs(value - 1.0) < ZERO)
832  {
833  // 1^NaN -> NaN
834  // 1^x -> 1
836  {
838  }
839 
840  if (pResult == NULL)
841  {
843  }
844  }
845 
846  /* ignore -1 for now
847  else if(fabs(value + 1.0) < ZERO)
848  {
849  }
850  */
851  }
852  else if (CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::CONSTANT)
853  {
854  // infinity and NaN
856  {
857  // NaN^x -> NaN
859  }
861  {
862  // INFINITY^(-NaN) -> NaN
863  // INFINITY^-x -> 0.0 // x being a positive number
864  // INFINITY^x -> INFINITY // x being a positive number
865  // INFINITY^0 -> 1
867  {
868  const CEvaluationNodeNumber* pNumberNode2 = dynamic_cast<const CEvaluationNodeNumber*>(pChild2);
869  assert(pNumberNode2 != NULL);
870  double value = pNumberNode2->getValue();
871 
872  // INFINITY^0 -> 1
873  if (fabs(value) < ZERO)
874  {
876  }
877  // INFINITY^x -> INFINITY // x being a positive number
878  else if (value > 0.0)
879  {
881  }
882  // INFINITY^-x -> 0.0 // x being a positive number
883  else
884  {
886  }
887  }
889  {
890  // INFINITY^NaN -> NaN
892  }
893  /* the minus function is eliminated
894  else if(CEvaluationNode::type(pChild2->getType())==CEvaluationNode::FUNCTION && ((CEvaluationNodeFunction::SubType)CEvaluationNode::subType(pChild2->getType()))==CEvaluationNodeFunction::MINUS)
895  {
896  CEvaluationNode* pChild=dynamic_cast<CEvaluationNode*>(pChild2->getChild());
897  // INFINITY^(-CONSTANT) -> 0.0 // where CONSTANT != NaN
898  if(CEvaluationNode::type(pChild->getType())==CEvaluationNode::CONSTANT)
899  {
900  pResult=new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE,"0.0");
901  }
902  }
903  */
904  else if (CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER)
905  {
906  const CEvaluationNodeNumber* pNumberNode2 = dynamic_cast<const CEvaluationNodeNumber*>(pChild2);
907  assert(pNumberNode2 != NULL);
908  double value = pNumberNode2->getValue();
909 
910  // INFINITY^0 -> 1.0
911  if (fabs(value) < ZERO)
912  {
914  }
915  // INFINITY^(-x) -> 0.0
916  else if (value > 0.0)
917  {
919  }
920  // INFINITY^x -> INFINITY
921  else
922  {
924  }
925  }
926 
927  // INFINITY ^ x -> INFINITY
928  if (pResult == NULL)
929  {
931  }
932  }
933  }
934  else if (CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER)
935  {
936  // 0 and 1
937  const CEvaluationNodeNumber* pNumberNode2 = dynamic_cast<const CEvaluationNodeNumber*>(pChild2);
938  assert(pNumberNode2 != NULL);
939  double value = pNumberNode2->getValue();
940 
941  // x^0 -> 1.0
942  if (fabs(value) < ZERO)
943  {
945  }
946  else if (fabs(value - 1.0) < ZERO)
947  {
948  // make a deep copy of the first child
949  pResult = pChild1->copyBranch();
950  }
951 
952  /* ignore -1 since this may interfere with other simplification
953  * mechanisms.
954  * Negative exponents will be eliminated in the end.
955  else if(fabs(value + 1.0) < ZERO)
956  {
957  }
958  */
959  }
961  {
962  // infinity and NaN
964  {
965  pResult = pChild2->copyBranch();
966  }
968  {
969  pResult = pChild2->copyBranch();
970  }
971  }
972 
973  return pResult;
974 }
975 
976 /**
977  * This method makes the elementary elimination on a modulus node.
978  * The following eliminations are made:
979  * a) NaN%x -> NaN
980  * b) x%NaN -> NaN
981  * c) x%x -> 0
982  * d) 0%x -> 0
983  * e) 1%n -> 1 (n is a number, other than 1)
984  *
985  * The caller is responsible for freeing the memory of the returned object.
986  */
988 {
989  CEvaluationNode* pResult = NULL;
990  assert(CEvaluationNode::type(pModulusNode->getType()) == CEvaluationNode::OPERATOR);
992  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pModulusNode->getChild());
993  assert(pChild1 != NULL);
994  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
995  assert(pChild2 != NULL);
996  assert(pChild2->getSibling() == NULL);
997 
998  // if one child is NaN, the result is NaN
999  if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::CONSTANT &&
1003  {
1005  }
1006 
1007  // X%X -> 0
1008  CNormalFraction* base1 = createNormalRepresentation(pChild1);
1009  CNormalFraction* base2 = createNormalRepresentation(pChild2);
1010 
1011  if (base1->toString() == base2->toString())
1012  {
1014  }
1015  else if (CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER)
1016  {
1017  // 0 and 1
1018  const CEvaluationNodeNumber* pNumberNode = dynamic_cast<const CEvaluationNodeNumber*>(pChild1);
1019  assert(pNumberNode != NULL);
1020  double value = pNumberNode->getValue();
1021 
1022  if (fabs(value) < ZERO)
1023  {
1025  }
1026  else if (fabs(value - 1.0) < ZERO)
1027  {
1028  // 1%X where X is any number other than 1 will give 1.0
1029  // the case where X is 1 is already covered above
1031  {
1033  }
1034  }
1035 
1036  // ignore the rest
1037  }
1038  else if (CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER)
1039  {
1040  // 0 and 1
1041  }
1042 
1043  delete base1;
1044  delete base2;
1045  base1 = NULL;
1046  base2 = NULL;
1047  return pResult;
1048 }
1049 
1050 /**
1051  * This method makes the elementary elimination on a multiply node.
1052  * The following eliminations are made:
1053  * a) NaN * x -> NaN
1054  * b) 0 * x -> 0
1055  * c) 1 * x -> x
1056  *
1057  * The caller is responsible for freeing the memory of the returned object.
1058  *
1059  */
1061 {
1062  CEvaluationNode* pResult = NULL;
1063  assert(CEvaluationNode::type(pMultiplyNode->getType()) == CEvaluationNode::OPERATOR);
1065  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pMultiplyNode->getChild());
1066  assert(pChild1 != NULL);
1067  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
1068  assert(pChild2 != NULL);
1069  assert(pChild2->getSibling() == NULL);
1070 
1071  // if one child is NaN, the result is NaN
1072  if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::CONSTANT &&
1076  {
1078  }
1079  // if one child is 0, the result is 0
1080  else if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER &&
1081  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild1)->getValue()) < ZERO) ||
1083  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild2)->getValue()) < ZERO))
1084  {
1086  }
1087  // if one child is 1, the result is the other child
1088  else if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER &&
1089  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild1)->getValue() - 1.0) < ZERO))
1090  {
1091  pResult = pChild2->copyBranch();
1092  }
1093  else if ((CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER &&
1094  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild2)->getValue() - 1.0) < ZERO))
1095  {
1096  pResult = pChild1->copyBranch();
1097  }
1098 
1099  return pResult;
1100 }
1101 
1102 /**
1103  * This method makes the elementary elimination on a divide node.
1104  *
1105  * The following eliminations are made:
1106  * a) Nan / x -> Nan
1107  * b) x / NaN -> NaN
1108  * c) x / 0 -> NaN
1109  * d) 0 / x -> 0
1110  * e) x / x -> 1
1111  * f) x / 1 -> x
1112  *
1113  * The caller is responsible for freeing the memory for the returned object.
1114  *
1115  */
1117 {
1118  CEvaluationNode* pResult = NULL;
1119  assert(CEvaluationNode::type(pDivideNode->getType()) == CEvaluationNode::OPERATOR);
1121  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pDivideNode->getChild());
1122  assert(pChild1 != NULL);
1123  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
1124  assert(pChild2 != NULL);
1125  assert(pChild2->getSibling() == NULL);
1126  // if one of the children is NaN, the result is NaN
1127  CNormalFraction* base1 = createNormalRepresentation(pChild1);
1128  CNormalFraction* base2 = createNormalRepresentation(pChild2);
1129 
1130  if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::CONSTANT &&
1134  {
1136  }
1137  // the second child is 0, the result is NaN
1138  else if ((CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER &&
1139  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild2)->getValue()) < ZERO))
1140  {
1142  }
1143  // if the first child is 0, the result is 0
1144  else if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER &&
1145  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild1)->getValue()) < ZERO))
1146  {
1148  }
1149  // if both children are the same, the result is 1
1150  else if (base1->toString() == base2->toString())
1151  {
1153  }
1154  // if the second child is 1, the result is the first child
1155  else if ((CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER &&
1156  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild2)->getValue() - 1.0) < ZERO))
1157  {
1158  pResult = pChild1->copyBranch();
1159  }
1160 
1161  delete base1;
1162  delete base2;
1163  base1 = NULL;
1164  base2 = NULL;
1165  return pResult;
1166 }
1167 
1168 /**
1169  * This method makes the elementary elimination on a plus node.
1170  * The following eliminations are made:
1171  * a) NaN + x -> NaN
1172  * b) 0 + x -> x (also x + 0)
1173  *
1174  * The caller is responsible for freeing the memory for the returned object.
1175  */
1177 {
1178  CEvaluationNode* pResult = NULL;
1179  assert(CEvaluationNode::type(pPlusNode->getType()) == CEvaluationNode::OPERATOR);
1181  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pPlusNode->getChild());
1182  assert(pChild1 != NULL);
1183  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
1184  assert(pChild2 != NULL);
1185  assert(pChild2->getSibling() == NULL);
1186 
1187  // if one child is NaN, the result is NaN
1188  if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::CONSTANT &&
1192  {
1194  }
1195  // the second child is 0, the result is the first child
1196  else if ((CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER &&
1197  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild2)->getValue()) < ZERO))
1198  {
1199  pResult = pChild1->copyBranch();
1200  }
1201  // if the first child is 0, the result is the second child
1202  else if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER &&
1203  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild1)->getValue()) < ZERO))
1204  {
1205  pResult = pChild2->copyBranch();
1206  }
1207 
1208  return pResult;
1209 }
1210 
1211 /**
1212  * This method makes the elementary elimination on a minus node.
1213  * The following eliminations are made:
1214  * a) NaN - x -> NaN
1215  * b) x - NaN -> NaN
1216  * c) x - x -> 0
1217  * d) x - 0 -> x
1218  * e) 0 - x -> -1 * x
1219  *
1220  * The caller is responsible for freeing the memory of the returned object.
1221  */
1223 {
1224  CEvaluationNode* pResult = NULL;
1225  assert(CEvaluationNode::type(pMinusNode->getType()) == CEvaluationNode::OPERATOR);
1227  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pMinusNode->getChild());
1228  assert(pChild1 != NULL);
1229  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
1230  assert(pChild2 != NULL);
1231  assert(pChild2->getSibling() == NULL);
1232  // if one child is NaN, the result is NaN (one could also consider to put
1233  // the second condition first so that to NaN would cancel each other out
1234  CNormalFraction* base1 = createNormalRepresentation(pChild1);
1235  CNormalFraction* base2 = createNormalRepresentation(pChild2);
1236 
1237  if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::CONSTANT &&
1241  {
1243  }
1244  // if both nodes are equal, the result is 0.0
1245  else if (base1->toString() == base2->toString())
1246  {
1248  }
1249  // the second child is 0, the result is the first child
1250  else if ((CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER &&
1251  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild2)->getValue()) < ZERO))
1252  {
1253  pResult = pChild1->copyBranch();
1254  }
1255  // if the first child is 0, the result is -1 times the second child
1256  else if ((CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER &&
1257  fabs(dynamic_cast<const CEvaluationNodeNumber*>(pChild1)->getValue()) < ZERO))
1258  {
1261  pResult->addChild(pChild2->copyBranch());
1262  }
1263 
1264  delete base1;
1265  delete base2;
1266  base1 = NULL;
1267  base2 = NULL;
1268  return pResult;
1269 }
1270 
1271 
1272 /**
1273  * This method replaces operations on two (or more) number nodes
1274  * by the resulting number node.
1275  * The returned node is either NULL, or a new node.
1276  * If the returned node is not NULL, the caller is responsible for freeing the memory
1277  * of the object.
1278  *
1279  * Obsolete recursive version
1280  */
1281 //CEvaluationNode* CNormalTranslation::evaluateNumbers(const CEvaluationNode* pOrig)
1282 //{
1283 //
1284 // // TODO we could probably make this a lot more efficient if we only executed the code for products and sums if the parent
1285 // // TODO is not of the same class, this way we would only have to execute the code once for the topmost multiplication/division
1286 // // TODO or addition/subtraction
1287 // // TODO another optimisation would be to not make this method recursive, but to got through the tree depth first
1288 // // TODO this would mean that we have to make a copy in the beginning and if nothin was changed, we delete the copy in the end
1289 // // TODO since we only do this once per call and not on every recursion level, this shouldn't be to bad
1290 //
1291 // // if the node is unmodified, return NULL
1292 // // else try to make the modifications in place instead of copying the whole
1293 // // subtree
1294 // CEvaluationNode* pResult = NULL;
1295 // const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pOrig->getChild());
1296 // const CEvaluationNode* pTmpOrig = pOrig;
1297 // CEvaluationNode* pNewChild = NULL;
1298 // std::vector<CEvaluationNode*> children;
1299 // bool childrenChanged = false;
1300 //
1301 // while (pChild != NULL)
1302 // {
1303 // pNewChild = CNormalTranslation::evaluateNumbers(pChild);
1304 //
1305 // if (pNewChild != NULL)
1306 // {
1307 // childrenChanged = true;
1308 // }
1309 //
1310 // children.push_back(pNewChild);
1311 // pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
1312 // }
1313 //
1314 // if (childrenChanged == true)
1315 // {
1316 // pChild = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
1317 // std::vector<CEvaluationNode*>::iterator it = children.begin(), endit = children.end();
1318 //
1319 // while (it != endit)
1320 // {
1321 // if ((*it) == NULL)
1322 // {
1323 // (*it) = pChild->copyBranch();
1324 // }
1325 //
1326 // pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
1327 // ++it;
1328 // }
1329 //
1330 // assert(pChild == NULL);
1331 // pResult = pTmpOrig->copyNode(children);
1332 // pTmpOrig = pResult;
1333 // }
1334 //
1335 //
1336 // if (CEvaluationNode::type(pTmpOrig->getType()) == CEvaluationNode::OPERATOR)
1337 // {
1338 // const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
1339 // assert(pChild1 != NULL);
1340 // const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
1341 // assert(pChild2 != NULL);
1342 //
1343 // switch ((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pTmpOrig->getType()))
1344 // {
1345 // case CEvaluationNodeOperator::POWER:
1346 //
1347 // if (CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER && CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER)
1348 // {
1349 // std::ostringstream os;
1350 // const CEvaluationNodeNumber* pNumberNode1 = dynamic_cast<const CEvaluationNodeNumber*>(pChild1);
1351 // assert(pNumberNode1 != NULL);
1352 // const CEvaluationNodeNumber* pNumberNode2 = dynamic_cast<const CEvaluationNodeNumber*>(pChild2);
1353 // assert(pNumberNode1 != NULL);
1354 // os << pow(pNumberNode1->getValue(), pNumberNode2->getValue());
1355 // pTmpOrig = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1356 //
1357 // if (pResult != NULL)
1358 // {
1359 // delete pResult;
1360 // }
1361 //
1362 // pResult = const_cast<CEvaluationNode*>(pTmpOrig);
1363 // }
1364 //
1365 // break;
1366 // case CEvaluationNodeOperator::MODULUS:
1367 //
1368 // if (CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER && CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER)
1369 // {
1370 // std::ostringstream os;
1371 // const CEvaluationNodeNumber* pNumberNode1 = dynamic_cast<const CEvaluationNodeNumber*>(pChild1);
1372 // assert(pNumberNode1 != NULL);
1373 // const CEvaluationNodeNumber* pNumberNode2 = dynamic_cast<const CEvaluationNodeNumber*>(pChild2);
1374 // assert(pNumberNode2 != NULL);
1375 // os << ((int)pNumberNode1->getValue()) % ((int)pNumberNode2->getValue());
1376 // pTmpOrig = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1377 //
1378 // if (pResult != NULL)
1379 // {
1380 // delete pResult;
1381 // }
1382 //
1383 // pResult = const_cast<CEvaluationNode*>(pTmpOrig);
1384 // }
1385 //
1386 // break;
1387 // case CEvaluationNodeOperator::MULTIPLY:
1388 // case CEvaluationNodeOperator::DIVIDE:
1389 // {
1390 // std::vector<const CEvaluationNode*> multiplications, divisions;
1391 // // multiplications and divisions contain the original nodes,
1392 // // splitProduct doesn't copy nodes
1393 // CNormalTranslation::splitProduct(pTmpOrig, multiplications, divisions, false);
1394 // std::set<const CEvaluationNode*> multiplicationNumberNodes;
1395 // unsigned int i, iMax = multiplications.size();
1396 // const CEvaluationNode* pNode = NULL;
1397 //
1398 // for (i = 0; i < iMax; ++i)
1399 // {
1400 // pNode = multiplications[i];
1401 //
1402 // if (CEvaluationNode::type(pNode->getType()) == CEvaluationNode::NUMBER)
1403 // {
1404 // multiplicationNumberNodes.insert(pNode);
1405 // }
1406 // }
1407 //
1408 // std::set<const CEvaluationNode*> divisionNumberNodes;
1409 // iMax = divisions.size();
1410 //
1411 // for (i = 0; i < iMax; ++i)
1412 // {
1413 // pNode = divisions[i];
1414 //
1415 // if (CEvaluationNode::type(pNode->getType()) == CEvaluationNode::NUMBER)
1416 // {
1417 // divisionNumberNodes.insert(pNode);
1418 // }
1419 // }
1420 //
1421 // if ((multiplicationNumberNodes.size() + divisionNumberNodes.size()) > 1)
1422 // {
1423 // // there are at least two number nodes, so we have to evaluate
1424 // // the numbers
1425 // double value = 1.0;
1426 // std::set<const CEvaluationNode*>::iterator it = multiplicationNumberNodes.begin(), endit = multiplicationNumberNodes.end();
1427 //
1428 // while (it != endit)
1429 // {
1430 // value *= (*it)->getValue();
1431 // ++it;
1432 // }
1433 //
1434 // it = divisionNumberNodes.begin();
1435 // endit = divisionNumberNodes.end();
1436 //
1437 // while (it != endit)
1438 // {
1439 // value /= (*it)->getValue();
1440 // ++it;
1441 // }
1442 //
1443 // std::vector<CEvaluationNode*> newMultiplications, newDivisions;
1444 //
1445 // if (fabs((value - 1.0)) >= ZERO)
1446 // {
1447 // std::ostringstream os;
1448 // os.precision(18);
1449 //
1450 // if (fabs(value) < 1.0)
1451 // {
1452 // os << 1.0 / value;
1453 // CEvaluationNodeNumber* pEvaluated = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1454 // newDivisions.push_back(pEvaluated);
1455 // }
1456 // else
1457 // {
1458 // os << value;
1459 // CEvaluationNodeNumber* pEvaluated = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1460 // newMultiplications.push_back(pEvaluated);
1461 // }
1462 // }
1463 //
1464 // // now we have to copy all nonnumber nodes
1465 // std::vector<const CEvaluationNode*>::iterator it2 = multiplications.begin(), endit2 = multiplications.end();
1466 //
1467 // while (it2 != endit2)
1468 // {
1469 // // if the node is not in multiplicationNumberNodes, we copy
1470 // // it
1471 // it = multiplicationNumberNodes.find(*it2);
1472 //
1473 // if (it == multiplicationNumberNodes.end())
1474 // {
1475 // newMultiplications.push_back((*it2)->copyBranch());
1476 // }
1477 //
1478 // ++it2;
1479 // }
1480 //
1481 // it2 = divisions.begin();
1482 // endit2 = divisions.end();
1483 //
1484 // while (it2 != endit2)
1485 // {
1486 // // if the node is not in multiplicationNumberNodes, we copy
1487 // // it
1488 // it = divisionNumberNodes.find(*it2);
1489 //
1490 // if (it == divisionNumberNodes.end())
1491 // {
1492 // newDivisions.push_back((*it2)->copyBranch());
1493 // }
1494 //
1495 // ++it2;
1496 // }
1497 //
1498 // // now we create a new result node from the newMultiplications
1499 // // and newDivisions
1500 // if (newMultiplications.empty())
1501 // {
1502 // pTmpOrig = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "1.0");
1503 // }
1504 // else
1505 // {
1506 // pTmpOrig = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, newMultiplications);
1507 // }
1508 //
1509 // if (pResult != NULL)
1510 // {
1511 // delete pResult;
1512 // }
1513 //
1514 // pResult = const_cast<CEvaluationNode*>(pTmpOrig);
1515 //
1516 // if (!newDivisions.empty())
1517 // {
1518 // CEvaluationNode* pTmpNode = new CEvaluationNodeOperator(CEvaluationNodeOperator::DIVIDE, "/");
1519 // pTmpNode->addChild(pResult);
1520 // pResult = pTmpNode;
1521 // pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, newDivisions);
1522 // pResult->addChild(pTmpNode);
1523 // }
1524 // }
1525 // }
1526 // break;
1527 // case CEvaluationNodeOperator::PLUS:
1528 // case CEvaluationNodeOperator::MINUS:
1529 // {
1530 // std::vector<CEvaluationNode*> additions, subtractions;
1531 // // splitSum copies the nodes that are returned
1532 // CNormalTranslation::splitSum(pTmpOrig, additions, subtractions, false);
1533 // CNormalTranslation::swapNegativeNumbers(additions, subtractions);
1534 // std::set<const CEvaluationNode*> additionNumberNodes;
1535 // unsigned int i, iMax = additions.size();
1536 // const CEvaluationNode* pNode = NULL;
1537 //
1538 // for (i = 0; i < iMax; ++i)
1539 // {
1540 // pNode = additions[i];
1541 //
1542 // if (CEvaluationNode::type(pNode->getType()) == CEvaluationNode::NUMBER)
1543 // {
1544 // additionNumberNodes.insert(pNode);
1545 // }
1546 // }
1547 //
1548 // std::set<const CEvaluationNode*> subtractionNumberNodes;
1549 // iMax = subtractions.size();
1550 //
1551 // for (i = 0; i < iMax; ++i)
1552 // {
1553 // pNode = subtractions[i];
1554 //
1555 // if (CEvaluationNode::type(pNode->getType()) == CEvaluationNode::NUMBER)
1556 // {
1557 // subtractionNumberNodes.insert(pNode);
1558 // }
1559 // }
1560 //
1561 // if ((additionNumberNodes.size() + subtractionNumberNodes.size()) > 1)
1562 // {
1563 // // there are at least two number nodes, so we have to evaluate
1564 // // the numbers
1565 // double value = 0.0;
1566 // std::set<const CEvaluationNode*>::const_iterator it = additionNumberNodes.begin(), endit = additionNumberNodes.end();
1567 //
1568 // while (it != endit)
1569 // {
1570 // value += (*it)->getValue();
1571 // ++it;
1572 // }
1573 //
1574 // it = subtractionNumberNodes.begin();
1575 // endit = subtractionNumberNodes.end();
1576 //
1577 // while (it != endit)
1578 // {
1579 // value -= (*it)->getValue();
1580 // ++it;
1581 // }
1582 //
1583 // std::vector<CEvaluationNode*> newAdditions, newSubtractions;
1584 //
1585 // if (fabs(value) >= ZERO)
1586 // {
1587 // std::ostringstream os;
1588 // os.precision(18);
1589 //
1590 // if (value < 0.0)
1591 // {
1592 // os << -1.0 * value;
1593 // CEvaluationNodeNumber* pEvaluated = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1594 // newSubtractions.push_back(pEvaluated);
1595 // }
1596 // else
1597 // {
1598 // os << value;
1599 // CEvaluationNodeNumber* pEvaluated = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1600 // newAdditions.push_back(pEvaluated);
1601 // }
1602 // }
1603 //
1604 // // now we have to copy all nonnumber nodes
1605 // std::vector<CEvaluationNode*>::const_iterator it2 = additions.begin(), endit2 = additions.end();
1606 //
1607 // while (it2 != endit2)
1608 // {
1609 // // if the node is not in additionNumberNodes, we copy
1610 // // it
1611 // it = additionNumberNodes.find(*it2);
1612 //
1613 // if (it == additionNumberNodes.end())
1614 // {
1615 // newAdditions.push_back(*it2);
1616 // }
1617 // else
1618 // {
1619 // // delete the original node that was created by splitSum
1620 // delete *it2;
1621 // }
1622 //
1623 // ++it2;
1624 // }
1625 //
1626 // it2 = subtractions.begin();
1627 // endit2 = subtractions.end();
1628 //
1629 // while (it2 != endit2)
1630 // {
1631 // // if the node is not in subtractionNumberNodes, we copy
1632 // // it
1633 // it = subtractionNumberNodes.find(*it2);
1634 //
1635 // if (it == subtractionNumberNodes.end())
1636 // {
1637 // newSubtractions.push_back(*it2);
1638 // }
1639 // else
1640 // {
1641 // // delete the original node that was created by splitSum
1642 // delete *it2;
1643 // }
1644 //
1645 // ++it2;
1646 // }
1647 //
1648 // // now we create a new result node from the newAdditions
1649 // // and newSubtractions
1650 // if (newAdditions.empty())
1651 // {
1652 // if (newSubtractions.empty())
1653 // {
1654 // pTmpOrig = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "0.0");
1655 //
1656 // if (pResult != NULL)
1657 // {
1658 // delete pResult;
1659 // }
1660 //
1661 // pResult = const_cast<CEvaluationNode*>(pTmpOrig);
1662 // }
1663 //
1664 // }
1665 // else
1666 // {
1667 // pTmpOrig = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, newAdditions);
1668 //
1669 // if (pResult != NULL)
1670 // {
1671 // delete pResult;
1672 // }
1673 //
1674 // pResult = const_cast<CEvaluationNode*>(pTmpOrig);
1675 // }
1676 //
1677 // if (!newSubtractions.empty())
1678 // {
1679 // if (newAdditions.empty())
1680 // {
1681 // if (newSubtractions.size() == 1 && CEvaluationNode::type(newSubtractions[0]->getType()) == CEvaluationNode::NUMBER)
1682 // {
1683 // std::ostringstream os;
1684 // os.precision(18);
1685 // os << -1.0 * newSubtractions[0]->getValue();
1686 // pTmpOrig = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1687 //
1688 // if (pResult != NULL)
1689 // {
1690 // delete pResult;
1691 // }
1692 //
1693 // pResult = const_cast<CEvaluationNode*>(pTmpOrig);
1694 // delete newSubtractions[0];
1695 // }
1696 // else
1697 // {
1698 // CEvaluationNode* pTmpNode2 = new CEvaluationNodeFunction(CEvaluationNodeFunction::MINUS, "-");
1699 // CEvaluationNode* pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, newSubtractions);
1700 // pTmpNode2->addChild(pTmpNode);
1701 //
1702 // if (pResult != NULL)
1703 // {
1704 // delete pResult;
1705 // }
1706 //
1707 // pResult = pTmpNode2;
1708 // }
1709 // }
1710 // else
1711 // {
1712 // CEvaluationNode* pTmpNode = new CEvaluationNodeOperator(CEvaluationNodeOperator::MINUS, "-");
1713 // pTmpNode->addChild(pResult);
1714 // pResult = pTmpNode;
1715 // pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, newSubtractions);
1716 // pResult->addChild(pTmpNode);
1717 // }
1718 // }
1719 // }
1720 // else
1721 // {
1722 // // delete all nodes in additions and subtractions
1723 // unsigned int i, iMax = additions.size();
1724 //
1725 // for (i = 0; i < iMax; ++i)
1726 // {
1727 // delete additions[i];
1728 // }
1729 //
1730 // iMax = subtractions.size();
1731 //
1732 // for (i = 0; i < iMax; ++i)
1733 // {
1734 // delete subtractions[i];
1735 // }
1736 // }
1737 // }
1738 // break;
1739 // case CEvaluationNodeOperator::INVALID:
1740 // break;
1741 // }
1742 // }
1743 //
1744 // return pResult;
1745 //}
1746 
1747 
1748 /**
1749  * This method replaces operations on two (or more) number nodes
1750  * by the resulting number node.
1751  * The returned node is either NULL, or a new node.
1752  * If the returned node is not NULL, the caller is responsible for freeing the memory
1753  * of the object.
1754  */
1756 {
1757  // if the node is unmodified, return NULL
1758  // else try to make the modifications in place instead of copying the whole
1759  // subtree
1760  CEvaluationNode* pResult = NULL;
1761  // remember if we modified anything
1762  bool modified = false;
1763  // make a copy of the node
1764  pResult = pOrig->copyBranch();
1765  assert(pResult != NULL);
1766  CEvaluationNodeDepthFirstIterator dfi(pResult);
1767  CEvaluationNode::Type type;
1768  CEvaluationNode* pTmpOrig = NULL;
1769 
1770  while (dfi.isValid())
1771  {
1772  // check if the current node is an operator
1773  type = CEvaluationNode::type(dfi->getType());
1774 
1775  if (type == CEvaluationNode::OPERATOR)
1776  {
1777  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(dfi->getChild());
1778  assert(pChild1 != NULL);
1779  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
1780  assert(pChild2 != NULL);
1782 
1783  switch (subType)
1784  {
1786 
1788  {
1789  std::ostringstream os;
1790  const CEvaluationNodeNumber* pNumberNode1 = dynamic_cast<const CEvaluationNodeNumber*>(pChild1);
1791  assert(pNumberNode1 != NULL);
1792  const CEvaluationNodeNumber* pNumberNode2 = dynamic_cast<const CEvaluationNodeNumber*>(pChild2);
1793  assert(pNumberNode1 != NULL);
1794  os << pow(pNumberNode1->getValue(), pNumberNode2->getValue());
1795  pTmpOrig = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1796 
1797  // now we need to replace dfi in it's parent by pTmpOrig and
1798  // delete dfi
1799  if (dfi->getParent() != NULL)
1800  {
1801  dfi->getParent()->addChild(pTmpOrig, *dfi);
1802  dfi->getParent()->removeChild(*dfi);
1803  delete *dfi;
1804  dfi = pTmpOrig;
1805  }
1806  else
1807  {
1808  // it must be the root node
1809  assert(*dfi == pResult);
1810  delete pResult;
1811  pResult = pTmpOrig;
1812  // we are done
1813  dfi = NULL;
1814  }
1815 
1816  modified = true;
1817  }
1818 
1819  break;
1821 
1823  {
1824  std::ostringstream os;
1825  const CEvaluationNodeNumber* pNumberNode1 = dynamic_cast<const CEvaluationNodeNumber*>(pChild1);
1826  assert(pNumberNode1 != NULL);
1827  const CEvaluationNodeNumber* pNumberNode2 = dynamic_cast<const CEvaluationNodeNumber*>(pChild2);
1828  assert(pNumberNode2 != NULL);
1829  os << ((int)pNumberNode1->getValue()) % ((int)pNumberNode2->getValue());
1830  pTmpOrig = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1831 
1832  // now we need to replace dfi in it's parent by pTmpOrig and
1833  // delete dfi
1834  if (dfi->getParent() != NULL)
1835  {
1836  dfi->getParent()->addChild(pTmpOrig, *dfi);
1837  dfi->getParent()->removeChild(*dfi);
1838  delete *dfi;
1839  dfi = pTmpOrig;
1840  }
1841  else
1842  {
1843  // it must be the root node
1844  assert(*dfi == pResult);
1845  delete pResult;
1846  pResult = pTmpOrig;
1847  // we are done
1848  dfi = NULL;
1849 
1850  }
1851 
1852  modified = true;
1853  }
1854 
1855  break;
1858  {
1859  pTmpOrig = dynamic_cast<CEvaluationNode*>(dfi->getParent());
1860 
1861  // if there is no parent or if the parent is not a multiplication or division, we try to evaluate numbers
1863  {
1864 
1865  std::vector<const CEvaluationNode*> multiplications, divisions;
1866  // multiplications and divisions contain the original nodes,
1867  // splitProduct doesn't copy nodes
1868  CNormalTranslation::splitProduct(*dfi, multiplications, divisions, false);
1869  std::set<CEvaluationNode*> multiplicationNumberNodes;
1870  unsigned int i, iMax = multiplications.size();
1871  CEvaluationNode* pNode = NULL;
1872 
1873  for (i = 0; i < iMax; ++i)
1874  {
1875  pNode = const_cast<CEvaluationNode*>(multiplications[i]);
1876 
1878  {
1879  multiplicationNumberNodes.insert(pNode);
1880  }
1881  }
1882 
1883  std::set<CEvaluationNode*> divisionNumberNodes;
1884  iMax = divisions.size();
1885 
1886  for (i = 0; i < iMax; ++i)
1887  {
1888  pNode = const_cast<CEvaluationNode*>(divisions[i]);
1889 
1891  {
1892  divisionNumberNodes.insert(pNode);
1893  }
1894  }
1895 
1896  if ((multiplicationNumberNodes.size() + divisionNumberNodes.size()) > 1)
1897  {
1898  // there are at least two number nodes, so we have to evaluate
1899  // the numbers
1900  double value = 1.0;
1901  std::set<CEvaluationNode*>::iterator it = multiplicationNumberNodes.begin(), endit = multiplicationNumberNodes.end();
1902 
1903  while (it != endit)
1904  {
1905  value *= (*it)->getValue();
1906  ++it;
1907  }
1908 
1909  it = divisionNumberNodes.begin();
1910  endit = divisionNumberNodes.end();
1911 
1912  while (it != endit)
1913  {
1914  value /= (*it)->getValue();
1915  ++it;
1916  }
1917 
1918  std::vector<CEvaluationNode*> newMultiplications, newDivisions;
1919 
1920  if (fabs((value - 1.0)) >= ZERO)
1921  {
1922  std::ostringstream os;
1923  os.precision(18);
1924 
1925  if (fabs(value) < 1.0)
1926  {
1927  os << 1.0 / value;
1928  CEvaluationNodeNumber* pEvaluated = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1929  newDivisions.push_back(pEvaluated);
1930  }
1931  else
1932  {
1933  os << value;
1934  CEvaluationNodeNumber* pEvaluated = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
1935  newMultiplications.push_back(pEvaluated);
1936  }
1937  }
1938 
1939  std::vector<const CEvaluationNode*>::iterator it2 = multiplications.begin(), endit2 = multiplications.end();
1940 
1941  while (it2 != endit2)
1942  {
1943  // if the node is not in multiplicationNumberNodes, we add
1944  // it
1945  it = multiplicationNumberNodes.find(const_cast<CEvaluationNode*>(*it2));
1946 
1947  if (it == multiplicationNumberNodes.end())
1948  {
1949 
1950  CEvaluationNode* pTmpNode = const_cast<CEvaluationNode*>(*it2);
1951 
1952  // to reuse the nodes, we have to remove them from their original parent
1953  if (pTmpNode->getParent() != NULL)
1954  {
1955  pTmpNode->getParent()->removeChild(pTmpNode);
1956  }
1957 
1958  newMultiplications.push_back(pTmpNode);
1959  }
1960  else
1961  {
1962  // delete the old number node
1963  delete *it2;
1964  }
1965 
1966  ++it2;
1967  }
1968 
1969  it2 = divisions.begin();
1970  endit2 = divisions.end();
1971 
1972  while (it2 != endit2)
1973  {
1974  // if the node is not in multiplicationNumberNodes, we add
1975  // it
1976  it = divisionNumberNodes.find(const_cast<CEvaluationNode*>(*it2));
1977 
1978  if (it == divisionNumberNodes.end())
1979  {
1980  CEvaluationNode* pTmpNode = const_cast<CEvaluationNode*>(*it2);
1981 
1982  // to reuse the nodes, we have to remove them from their original parent
1983  if (pTmpNode->getParent() != NULL)
1984  {
1985  pTmpNode->getParent()->removeChild(pTmpNode);
1986  }
1987 
1988  newDivisions.push_back(const_cast<CEvaluationNode*>(pTmpNode));
1989  }
1990  else
1991  {
1992  // delete the old number node
1993  delete *it2;
1994  }
1995 
1996  ++it2;
1997  }
1998 
1999  // now we create a new result node from the newMultiplications
2000  // and newDivisions
2001  if (newMultiplications.empty())
2002  {
2004  }
2005  else
2006  {
2007  pTmpOrig = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, newMultiplications);
2008  }
2009 
2010  if (!newDivisions.empty())
2011  {
2013  pTmpNode->addChild(pTmpOrig);
2014  pTmpOrig = pTmpNode;
2015  pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, newDivisions);
2016  pTmpOrig->addChild(pTmpNode);
2017  }
2018 
2019  // now we need to replace dfi in it's parent by pTmpOrig and
2020  // delete dfi
2021  if (dfi->getParent() != NULL)
2022  {
2023  dfi->getParent()->addChild(pTmpOrig, *dfi);
2024  dfi->getParent()->removeChild(*dfi);
2025  delete *dfi;
2026  dfi = pTmpOrig;
2027  }
2028  else
2029  {
2030  // it must be the root node
2031  assert(*dfi == pResult);
2032  delete pResult;
2033  pResult = pTmpOrig;
2034  // we are done
2035  dfi = NULL;
2036  }
2037 
2038  modified = true;
2039 
2040  }
2041  }
2042  }
2043  break;
2046  {
2047  pTmpOrig = dynamic_cast<CEvaluationNode*>(dfi->getParent());
2048 
2049  // if there is no parent or if the parent is not a multiplication or division, we try to evaluate numbers
2051  {
2052  std::vector<CEvaluationNode*> additions, subtractions;
2053  // splitSum copies the nodes that are returned
2054  CNormalTranslation::splitSum(*dfi, additions, subtractions, false);
2055  CNormalTranslation::swapNegativeNumbers(additions, subtractions);
2056  std::set<CEvaluationNode*> additionNumberNodes;
2057  unsigned int i, iMax = additions.size();
2058  CEvaluationNode* pNode = NULL;
2059 
2060  for (i = 0; i < iMax; ++i)
2061  {
2062  pNode = const_cast<CEvaluationNode*>(additions[i]);
2063 
2065  {
2066  additionNumberNodes.insert(pNode);
2067  }
2068  }
2069 
2070  std::set<CEvaluationNode*> subtractionNumberNodes;
2071  iMax = subtractions.size();
2072 
2073  for (i = 0; i < iMax; ++i)
2074  {
2075  pNode = const_cast<CEvaluationNode*>(subtractions[i]);
2076 
2078  {
2079  subtractionNumberNodes.insert(pNode);
2080  }
2081  }
2082 
2083  if ((additionNumberNodes.size() + subtractionNumberNodes.size()) > 1)
2084  {
2085  // there are at least two number nodes, so we have to evaluate
2086  // the numbers
2087  double value = 0.0;
2088  std::set<CEvaluationNode*>::const_iterator it = additionNumberNodes.begin(), endit = additionNumberNodes.end();
2089 
2090  while (it != endit)
2091  {
2092  value += (*it)->getValue();
2093  ++it;
2094  }
2095 
2096  it = subtractionNumberNodes.begin();
2097  endit = subtractionNumberNodes.end();
2098 
2099  while (it != endit)
2100  {
2101  value -= (*it)->getValue();
2102  ++it;
2103  }
2104 
2105  std::vector<CEvaluationNode*> newAdditions, newSubtractions;
2106 
2107  if (fabs(value) >= ZERO)
2108  {
2109  std::ostringstream os;
2110  os.precision(18);
2111 
2112  if (value < 0.0)
2113  {
2114  os << -1.0 * value;
2115  CEvaluationNodeNumber* pEvaluated = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
2116  newSubtractions.push_back(pEvaluated);
2117  }
2118  else
2119  {
2120  os << value;
2121  CEvaluationNodeNumber* pEvaluated = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
2122  newAdditions.push_back(pEvaluated);
2123  }
2124  }
2125 
2126  // now we have to copy all nonnumber nodes
2127  std::vector<CEvaluationNode*>::const_iterator it2 = additions.begin(), endit2 = additions.end();
2128 
2129  while (it2 != endit2)
2130  {
2131  // if the node is not in additionNumberNodes, we copy
2132  // it
2133  it = additionNumberNodes.find(*it2);
2134 
2135  if (it == additionNumberNodes.end())
2136  {
2137  newAdditions.push_back(*it2);
2138  }
2139  else
2140  {
2141  // delete the original node that was created by splitSum
2142  delete *it2;
2143  }
2144 
2145  ++it2;
2146  }
2147 
2148  it2 = subtractions.begin();
2149  endit2 = subtractions.end();
2150 
2151  while (it2 != endit2)
2152  {
2153  // if the node is not in subtractionNumberNodes, we copy
2154  // it
2155  it = subtractionNumberNodes.find(*it2);
2156 
2157  if (it == subtractionNumberNodes.end())
2158  {
2159  newSubtractions.push_back(*it2);
2160  }
2161  else
2162  {
2163  // delete the original node that was created by splitSum
2164  delete *it2;
2165  }
2166 
2167  ++it2;
2168  }
2169 
2170  // now we create a new result node from the newAdditions
2171  // and newSubtractions
2172  if (newAdditions.empty())
2173  {
2174  if (newSubtractions.empty())
2175  {
2177  }
2178 
2179  }
2180  else
2181  {
2182  pTmpOrig = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, newAdditions);
2183  }
2184 
2185  if (!newSubtractions.empty())
2186  {
2187  if (newAdditions.empty())
2188  {
2189  if (newSubtractions.size() == 1 && CEvaluationNode::type(newSubtractions[0]->getType()) == CEvaluationNode::NUMBER)
2190  {
2191  std::ostringstream os;
2192  os.precision(18);
2193  os << -1.0 * newSubtractions[0]->getValue();
2194  delete pTmpOrig;
2195  pTmpOrig = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
2196  delete newSubtractions[0];
2197  }
2198  else
2199  {
2201  CEvaluationNode* pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, newSubtractions);
2202  pTmpNode2->addChild(pTmpNode);
2203 
2204  delete pTmpOrig;
2205  pTmpOrig = pTmpNode2;
2206  }
2207  }
2208  else
2209  {
2211  pTmpNode->addChild(pTmpOrig);
2212  pTmpOrig = pTmpNode;
2213  pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, newSubtractions);
2214  pTmpOrig->addChild(pTmpNode);
2215  }
2216  }
2217 
2218  // now we need to replace dfi in it's parent by pTmpOrig and
2219  // delete dfi
2220  if (dfi->getParent() != NULL)
2221  {
2222  dfi->getParent()->addChild(pTmpOrig, *dfi);
2223  dfi->getParent()->removeChild(*dfi);
2224  delete *dfi;
2225  dfi = pTmpOrig;
2226  }
2227  else
2228  {
2229  // it must be the root node
2230  assert(*dfi == pResult);
2231  delete pResult;
2232  pResult = pTmpOrig;
2233  // we are done
2234  dfi = NULL;
2235  }
2236 
2237  modified = true;
2238  }
2239  else
2240  {
2241  // delete all nodes in additions and subtractions
2242  unsigned int i, iMax = additions.size();
2243 
2244  for (i = 0; i < iMax; ++i)
2245  {
2246  delete additions[i];
2247  }
2248 
2249  iMax = subtractions.size();
2250 
2251  for (i = 0; i < iMax; ++i)
2252  {
2253  delete subtractions[i];
2254  }
2255  }
2256  }
2257  }
2258  break;
2260  break;
2261  }
2262  }
2263 
2264  // if we are not done already
2265  if (dfi.isValid())
2266  {
2267  ++dfi;
2268  }
2269 
2270  }
2271 
2272  if (modified == false)
2273  {
2274  delete pResult;
2275  pResult = NULL;
2276  }
2277 
2278  return pResult;
2279 }
2280 
2281 /**
2282  * This method removes nested power nodes, e.g. (a^b)^c -> a^(b*c)
2283  *
2284  * The caller is responsible for freeing the memory of the returned object.
2285  */
2287 {
2288  CEvaluationNode* pResult = NULL;
2289  std::vector<CEvaluationNode*> children;
2290  const CEvaluationNode* pTmpOrig = pOrig;
2291  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
2292  bool childrenChanged = false;
2293  CEvaluationNode* pNewChild = NULL;
2294 
2295  while (pChild != NULL)
2296  {
2297  pNewChild = CNormalTranslation::eliminateNestedPowers(pChild);
2298 
2299  if (pNewChild != NULL)
2300  {
2301  childrenChanged = true;
2302  }
2303 
2304  children.push_back(pNewChild);
2305  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
2306  }
2307 
2308  if (childrenChanged == true)
2309  {
2310  std::vector<CEvaluationNode*>::iterator it = children.begin(), endit = children.end();
2311  pChild = static_cast<const CEvaluationNode*>(pTmpOrig->getChild());
2312 
2313  while (it != endit)
2314  {
2315  if ((*it) == NULL)
2316  {
2317  (*it) = pChild->copyBranch();
2318  }
2319 
2320  pChild = static_cast<const CEvaluationNode*>(pChild->getSibling());
2321  ++it;
2322  }
2323 
2324  assert(pChild == NULL);
2325  pResult = pTmpOrig->copyNode(children);
2326  pTmpOrig = pResult;
2327  }
2328 
2331  {
2332  // check if the first child is also a power node
2333  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
2334  assert(pChild1 != NULL);
2335  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
2336  assert(pChild2 != NULL);
2337  assert(pChild2->getSibling() == NULL);
2338 
2341  {
2343  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pChild1->getChild());
2344  assert(pChild != NULL);
2345  pTmpNode->addChild(pChild->copyBranch());
2347  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
2348  assert(pChild != NULL);
2349  pMult->addChild(pChild->copyBranch());
2350 
2351  if (pResult == NULL)
2352  {
2353  pMult->addChild(pChild2->copyBranch());
2354  }
2355  else
2356  {
2357  assert(pResult == pTmpOrig);
2358  pResult->removeChild(const_cast<CEvaluationNode*>(pChild2));
2359  pMult->addChild(const_cast<CEvaluationNode*>(pChild2));
2360  delete pResult;
2361  }
2362 
2363  pTmpNode->addChild(pMult);
2364  pResult = pTmpNode;
2365  }
2366  }
2367 
2368  return pResult;
2369 }
2370 
2371 /**
2372  * This method splits a product into the individual elements
2373  * and places the elements in the multiplications and divisions vector passed to the method.
2374  */
2375 void CNormalTranslation::splitProduct(const CEvaluationNode* pRoot, std::vector<const CEvaluationNode*>& multiplications, std::vector<const CEvaluationNode*>& divisions, bool division)
2376 {
2378  {
2379  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pRoot->getChild());
2380  assert(pChild1 != NULL);
2381  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
2382  assert(pChild2 != NULL);
2383  assert(pChild2->getSibling() == NULL);
2384 
2386  {
2390  {
2391  CNormalTranslation::splitProduct(pChild1, multiplications, divisions, division);
2392  }
2393  else
2394  {
2395  if (division == false)
2396  {
2397  multiplications.push_back(pChild1);
2398  }
2399  else
2400  {
2401  divisions.push_back(pChild1);
2402  }
2403  }
2404 
2408  {
2409  CNormalTranslation::splitProduct(pChild2, multiplications, divisions, division);
2410  }
2411  else
2412  {
2413  if (division == false)
2414  {
2415  multiplications.push_back(pChild2);
2416  }
2417  else
2418  {
2419  divisions.push_back(pChild2);
2420  }
2421  }
2422  }
2424  {
2428  {
2429  CNormalTranslation::splitProduct(pChild1, multiplications, divisions, division);
2430  }
2431  else
2432  {
2433  if (division == false)
2434  {
2435  multiplications.push_back(pChild1);
2436  }
2437  else
2438  {
2439  divisions.push_back(pChild1);
2440  }
2441  }
2442 
2446  {
2447  CNormalTranslation::splitProduct(pChild2, multiplications, divisions, !division);
2448  }
2449  else
2450  {
2451  if (division == false)
2452  {
2453  divisions.push_back(pChild2);
2454  }
2455  else
2456  {
2457  multiplications.push_back(pChild2);
2458  }
2459  }
2460  }
2461  }
2462  else
2463  {
2464  multiplications.push_back(pRoot);
2465  }
2466 }
2467 
2468 /**
2469  * This method splits a sum into the individual elements and adds them to the given vector of additions and subtractions.
2470  * The returned nodes are part of the original node and not copies.
2471  */
2472 void CNormalTranslation::splitSum(const CEvaluationNode* pRoot, std::vector<const CEvaluationNode*>& additions, std::vector<const CEvaluationNode*>& subtractions, bool minus)
2473 {
2474  // TODO this method might save some copy/delete cycles if the test for
2475  // TODO negative number was done before making copies of children and
2476  // TODO inserting them
2477  // TODO this would also simplify the code since the test would be put
2478  // TODO into a separate function
2480  {
2481  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pRoot->getChild());
2482  assert(pChild1 != NULL);
2483  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
2484  assert(pChild2 != NULL);
2485  assert(pChild2->getSibling() == NULL);
2486 
2488  {
2492  {
2493  CNormalTranslation::splitSum(pChild1, additions, subtractions, minus);
2494  }
2495  else
2496  {
2497  if (minus == false)
2498  {
2499  additions.push_back(pChild1);
2500  }
2501  else
2502  {
2503  subtractions.push_back(pChild1);
2504  }
2505  }
2506 
2510  {
2511  CNormalTranslation::splitSum(pChild2, additions, subtractions, minus);
2512  }
2513  else
2514  {
2515  if (minus == false)
2516  {
2517  additions.push_back(pChild2);
2518  }
2519  else
2520  {
2521  subtractions.push_back(pChild2);
2522  }
2523  }
2524  }
2526  {
2530  {
2531  CNormalTranslation::splitSum(pChild1, additions, subtractions, minus);
2532  }
2533  else
2534  {
2535  if (minus == false)
2536  {
2537  additions.push_back(pChild1);
2538  }
2539  else
2540  {
2541  subtractions.push_back(pChild1);
2542  }
2543  }
2544 
2548  {
2549  CNormalTranslation::splitSum(pChild2, additions, subtractions, !minus);
2550  }
2551  else
2552  {
2553  if (minus == false)
2554  {
2555  subtractions.push_back(pChild2);
2556  }
2557  else
2558  {
2559  additions.push_back(pChild2);
2560  }
2561  }
2562  }
2563  }
2564  else
2565  {
2566  additions.push_back(pRoot);
2567  }
2568 }
2569 
2570 /**
2571  * This methods records the order of nodes in a CEvaluationNode based tree.
2572  */
2573 void CNormalTranslation::order(const CEvaluationNode* pRoot, std::list<const CEvaluationNode*>& orderList)
2574 {
2575  if (pRoot == NULL) return;
2576 
2577  orderList.push_back(pRoot);
2578  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pRoot->getChild());
2579 
2580  while (pChild != NULL)
2581  {
2582  CNormalTranslation::order(pChild, orderList);
2583  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
2584  }
2585 }
2586 
2587 /**
2588  * This method splits a sum into the individual elements
2589  * The returned nodes are copies of the original.
2590  */
2591 void CNormalTranslation::splitSum(const CEvaluationNode* pRoot, std::vector<CEvaluationNode*>& additions, std::vector<CEvaluationNode*>& subtractions, bool minus)
2592 {
2593  //std::string s=pRoot->buildInfix();
2594  std::vector<const CEvaluationNode*> tmpAdditions, tmpSubtractions;
2595  CNormalTranslation::splitSum(pRoot, tmpAdditions, tmpSubtractions, minus);
2596  std::set<const CEvaluationNode*> tmpAdditionsS, tmpSubtractionsS;
2597  tmpAdditionsS.insert(tmpAdditions.begin(), tmpAdditions.end());
2598  tmpSubtractionsS.insert(tmpSubtractions.begin(), tmpSubtractions.end());
2599  std::list<const CEvaluationNode*> orderList;
2600  CNormalTranslation::order(pRoot, orderList);
2601 
2602  // TODO the code below was part of the old splitSum method that has largely
2603  // TODO been replaced by the new method that doesn't copy the nodes and is
2604  // TODO therefore faster
2605  // TODO If this code below is removed, the expression comparison for ordered
2606  // TODO bi bi goes into an endless loop, so I know there is still a bug somewhere
2607  // TODO in another routine which has to be fixed.
2608  // TODO actually the code below should be obsolete since swapNegativeNumbers
2609  // does this now.
2610 
2611  // check for negative numbers in additions and add them to subtractions
2612  // likewise check for negative numbers in substractions and add them to
2613  // additions
2614  // do the same for multiplications with a negative number
2615  std::list<const CEvaluationNode*>::const_iterator orderIt = orderList.begin(), orderEndit = orderList.end();
2616  const CEvaluationNode* pCurrentNode = NULL;
2617  bool isMinus = false;
2618 
2619  while (orderIt != orderEndit)
2620  {
2621  pCurrentNode = NULL;
2622  isMinus = false;
2623 
2624  if (tmpAdditionsS.find(*orderIt) == tmpAdditionsS.end())
2625  {
2626  if (tmpSubtractionsS.find(*orderIt) != tmpSubtractionsS.end())
2627  {
2628  isMinus = true;
2629  pCurrentNode = *orderIt;
2630  assert(pCurrentNode != NULL);
2631  }
2632  }
2633  else
2634  {
2635  pCurrentNode = *orderIt;
2636  assert(pCurrentNode != NULL);
2637  }
2638 
2639  if (pCurrentNode != NULL)
2640  {
2641  //
2642  if (CEvaluationNode::type(pCurrentNode->getType()) == CEvaluationNode::NUMBER && pCurrentNode->getValue() < 0.0)
2643  {
2644  std::ostringstream os;
2645  os.precision(18);
2646  os << pCurrentNode->getValue() * -1.0;
2647  CEvaluationNode* pTmpNumber = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
2648 
2649  if (isMinus == true)
2650  {
2651  additions.push_back(pTmpNumber);
2652  }
2653  else
2654  {
2655  subtractions.push_back(pTmpNumber);
2656  }
2657  }
2659  {
2660  // actually there should be code that tests if both are negative
2661  // numbers
2662  if ((CEvaluationNode::type(dynamic_cast<const CEvaluationNode*>(pCurrentNode->getChild())->getType()) == CEvaluationNode::NUMBER && dynamic_cast<const CEvaluationNodeNumber*>(pCurrentNode->getChild())->getValue() < 0.0))
2663  {
2664  if (fabs(dynamic_cast<const CEvaluationNodeNumber*>(pCurrentNode->getChild())->getValue()) - 1.0 < ZERO)
2665  {
2666  CEvaluationNode* pTmpNode = dynamic_cast<const CEvaluationNode*>(pCurrentNode->getChild()->getSibling())->copyBranch();
2667  assert(pTmpNode != NULL);
2668 
2669  if (isMinus == true)
2670  {
2671  additions.push_back(pTmpNode);
2672  }
2673  else
2674  {
2675  subtractions.push_back(pTmpNode);
2676  }
2677  }
2678  else
2679  {
2681  std::ostringstream os;
2682  os.precision(18);
2683  os << static_cast<const CEvaluationNodeNumber*>(pCurrentNode->getChild())->getValue() * -1.0;
2684  pTmp->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str()));
2685  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pCurrentNode->getChild()->getSibling())->copyBranch());
2686 
2687  if (isMinus == true)
2688  {
2689  additions.push_back(pTmp);
2690  }
2691  else
2692  {
2693  subtractions.push_back(pTmp);
2694  }
2695  }
2696  }
2697  else if (CEvaluationNode::type(dynamic_cast<const CEvaluationNode*>(pCurrentNode->getChild()->getSibling())->getType()) == CEvaluationNode::NUMBER && dynamic_cast<const CEvaluationNodeNumber*>(pCurrentNode->getChild()->getSibling())->getValue() < 0.0)
2698  {
2699  if (fabs(dynamic_cast<const CEvaluationNodeNumber*>(pCurrentNode->getChild()->getSibling())->getValue()) - 1.0 < ZERO)
2700  {
2701  CEvaluationNode* pTmpNode = dynamic_cast<const CEvaluationNode*>(pCurrentNode->getChild())->copyBranch();
2702  assert(pTmpNode != NULL);
2703 
2704  if (isMinus == true)
2705  {
2706  additions.push_back(pTmpNode);
2707  }
2708  else
2709  {
2710  subtractions.push_back(pTmpNode);
2711  }
2712  }
2713  else
2714  {
2716  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pCurrentNode->getChild())->copyBranch());
2717  std::ostringstream os;
2718  os.precision(18);
2719  os << static_cast<const CEvaluationNodeNumber*>(pCurrentNode->getChild()->getSibling())->getValue() * -1.0;
2720  pTmp->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str()));
2721 
2722  if (isMinus == true)
2723  {
2724  additions.push_back(pTmp);
2725  }
2726  else
2727  {
2728  subtractions.push_back(pTmp);
2729  }
2730  }
2731  }
2732  else
2733  {
2734  if (isMinus == true)
2735  {
2736  subtractions.push_back(pCurrentNode->copyBranch());
2737  }
2738  else
2739  {
2740  additions.push_back(pCurrentNode->copyBranch());
2741  }
2742  }
2743  }
2744  else
2745  {
2746  if (isMinus == true)
2747  {
2748  subtractions.push_back(pCurrentNode->copyBranch());
2749  }
2750  else
2751  {
2752  additions.push_back(pCurrentNode->copyBranch());
2753  }
2754  }
2755  }
2756 
2757  ++orderIt;
2758  }
2759 }
2760 
2761 /**
2762  * This method expands the exponents of power nodes, e.g. A^(x+y) -> A^x * A^y
2763  *
2764  * The caller is responsible for freeing the memory of the returned object if it is not NULL.
2765  */
2767 {
2768  CEvaluationNode* pResult = NULL;
2769  std::vector<CEvaluationNode*> children;
2770  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pOrig->getChild());
2771  CEvaluationNode* pNewChild = NULL;
2772  const CEvaluationNode* pTmpOrig = pOrig;
2773  bool childrenChanged = false;
2774 
2775  while (pChild != NULL)
2776  {
2777  pNewChild = CNormalTranslation::expandPowerNodes(pChild);
2778 
2779  if (pNewChild != NULL)
2780  {
2781  childrenChanged = true;
2782  }
2783 
2784  children.push_back(pNewChild);
2785  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
2786  }
2787 
2788  if (childrenChanged == true)
2789  {
2790  pChild = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
2791  std::vector<CEvaluationNode*>::iterator it = children.begin(), endit = children.end();
2792 
2793  while (it != endit)
2794  {
2795  if ((*it) == NULL)
2796  {
2797  (*it) = pChild->copyBranch();
2798  }
2799 
2800  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
2801  ++it;
2802  }
2803 
2804  pResult = pTmpOrig->copyNode(children);
2805  pTmpOrig = pResult;
2806  }
2807 
2808 
2811  {
2812  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
2813  assert(pChild1 != NULL);
2814  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
2815  assert(pChild2 != NULL);
2816  assert(pChild2->getSibling() == NULL);
2817 
2818  std::vector<CEvaluationNode*> additions, subtractions;
2819  CNormalTranslation::splitSum(pChild2, additions, subtractions, false);
2820  CNormalTranslation::swapNegativeNumbers(additions, subtractions);
2821 
2822  // the root node is a fraction
2823  // the denominator is a product of all subtraction nodes
2824  // the numerator is a product of all addition nodes
2825  if (!additions.empty() || !subtractions.empty())
2826  {
2827  // replace all nodes in additions and subtractions by
2828  // pChild1^node so we can use the generic method to create the
2829  // multiplication chain
2830  unsigned int i, iMax = additions.size();
2831 
2832  for (i = 0; i < iMax; ++i)
2833  {
2834  CEvaluationNode* pTmpNode = NULL;
2835 
2836  if (CEvaluationNode::type(additions[i]->getType()) == CEvaluationNode::NUMBER && fabs(static_cast<const CEvaluationNodeNumber*>(additions[i])->getValue() - 1.0) < 1e-12)
2837  {
2838  delete additions[i];
2839  pTmpNode = pChild1->copyBranch();
2840  }
2841  else
2842  {
2844  pTmpNode->addChild(pChild1->copyBranch());
2845  // don't copy additions element since this has been created in
2846  // splitSum
2847  pTmpNode->addChild(additions[i]);
2848  additions[i] = pTmpNode;
2849  }
2850 
2851  additions[i] = pTmpNode;
2852  }
2853 
2854  iMax = subtractions.size();
2855 
2856  for (i = 0; i < iMax; ++i)
2857  {
2858  CEvaluationNode* pTmpNode = NULL;
2859 
2860  if (CEvaluationNode::type(subtractions[i]->getType()) == CEvaluationNode::NUMBER && fabs(static_cast<const CEvaluationNodeNumber*>(subtractions[i])->getValue() - 1.0) < 1e-12)
2861  {
2862  pTmpNode = pChild1->copyBranch();
2863  delete subtractions[i];
2864  }
2865  else
2866  {
2868  pTmpNode->addChild(pChild1->copyBranch());
2869  // don't copy subtractions element since this has been created in
2870  // splitSum
2871  pTmpNode->addChild(subtractions[i]);
2872  }
2873 
2874  subtractions[i] = pTmpNode;
2875  }
2876 
2877  // if we have only subtractions, the numerator of the resulting
2878  // exponent has to be 1
2879  CEvaluationNode* pTmpResult = NULL;
2880 
2881  if (additions.empty())
2882  {
2883  pTmpResult = CNormalTranslation::ONE_NODE.copyBranch();
2884  }
2885  else
2886  {
2887  pTmpResult = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, additions);
2888  additions.clear();
2889  }
2890 
2891  assert(pTmpResult != NULL);
2892 
2893  if (!subtractions.empty())
2894  {
2896  pTmpNode->addChild(pTmpResult);
2897  pTmpResult = pTmpNode;
2898  pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, subtractions);
2899  assert(pTmpNode != NULL);
2900  pTmpResult->addChild(pTmpNode);
2901  subtractions.clear();
2902  }
2903 
2904  if (pResult != NULL)
2905  {
2906  delete pResult;
2907  }
2908 
2909  pResult = pTmpResult;
2910  }
2911  }
2912 
2913  return pResult;
2914 }
2915 
2916 /**
2917  * The methods get a vector of multiplication elements and a vector of division
2918  * elements and tries to find elements with the same power base in those two vectors.
2919  * e.g. A^3 and A^x would have the same power base A.
2920  *
2921  * The nodes in the match are copies of the original nodes
2922  */
2923 std::vector<product_match> CNormalTranslation::matchPowerBases(const std::vector<const CEvaluationNode*>& multiplications, const std::vector<const CEvaluationNode*>& divisions)
2924 {
2925  std::map<const CEvaluationNode*, product_match> matchMap;
2926  std::map<std::string, const CEvaluationNode*> infixMap;
2927  std::map<const CEvaluationNode*, product_match>::iterator matchPos;
2928  std::map<std::string, const CEvaluationNode*>::iterator infixPos;
2929 
2930  std::vector<const CEvaluationNode*>::const_iterator vit = multiplications.begin(), vendit = multiplications.end();
2931  const CEvaluationNode* pBase = NULL;
2932  const CNormalFraction* pBase2 = NULL;
2933  std::string base2String;
2934  CEvaluationNode *pExponent = NULL, *pAddNode = NULL;
2935  unsigned int index = 0;
2936  product_match match;
2937  // we store the order in which the base strings occur
2938  // so that we can return the result in approximately the same order
2939  // this should help in eliminating loops of chains with alternating order
2940  std::list<const CEvaluationNode*> orderList;
2941 
2942  while (vit != vendit)
2943  {
2944  pBase = (*vit);
2945  pExponent = NULL;
2946 
2948  {
2949  pBase = dynamic_cast<const CEvaluationNode*>(pBase->getChild());
2950  pExponent = dynamic_cast<const CEvaluationNode*>(pBase->getSibling())->copyBranch();
2951  }
2952 
2953  // check if a base with the same infix is already in the map.
2954  // if not, add the base
2955  // if yes, add the exponent to the vector associated with the base
2956  //
2957  // we only need to create the infix through a normal base if the
2958  // object is complex
2959  if (pBase->getChild() != NULL)
2960  {
2961  pBase2 = createNormalRepresentation(pBase);
2962  base2String = pBase2->toString();
2963  delete pBase2;
2964  pBase2 = NULL;
2965  }
2966  else
2967  {
2968  base2String = pBase->buildInfix();
2969  }
2970 
2971  infixPos = infixMap.find(base2String);
2972 
2973  if (infixPos != infixMap.end())
2974  {
2975  matchPos = matchMap.find(infixPos->second);
2976  assert(matchPos != matchMap.end());
2977 
2978  if (matchPos != matchMap.end())
2979  {
2980  if (pExponent != NULL)
2981  {
2982  if (matchPos->second.pExponentNode != NULL)
2983  {
2985  pAddNode->addChild(matchPos->second.pExponentNode);
2986  pAddNode->addChild(pExponent);
2987  matchPos->second.pExponentNode = pAddNode;
2988  matchPos->second.addition_indices.insert(index);
2989  }
2990  else
2991  {
2992  matchPos->second.pExponentNode = pExponent;
2993  }
2994  }
2995  else
2996  {
2997  matchPos->second.factor += 1.0;
2998  }
2999  }
3000  }
3001  else
3002  {
3003  match.pNode = pBase->copyBranch();
3004 
3005  if (pExponent == NULL)
3006  {
3007  match.factor = 1.0;
3008  }
3009  else
3010  {
3011  match.factor = 0.0;
3012  }
3013 
3014  match.pExponentNode = pExponent;
3015  match.addition_indices.clear();
3016  match.addition_indices.insert(index);
3017  match.subtraction_indices.clear();
3018  infixMap.insert(std::pair<std::string, const CEvaluationNode*>(base2String, pBase));
3019  matchMap.insert(std::pair<const CEvaluationNode*, product_match>(pBase, match));
3020  orderList.push_back(pBase);
3021  }
3022 
3023  ++index;
3024  ++vit;
3025  }
3026 
3027  vit = divisions.begin(), vendit = divisions.end();
3028 
3029  index = 0;
3030 
3031  while (vit != vendit)
3032  {
3033  pBase = (*vit);
3034  pExponent = NULL;
3035 
3037  {
3038  pBase = dynamic_cast<const CEvaluationNode*>(pBase->getChild());
3039  pExponent = dynamic_cast<const CEvaluationNode*>(pBase->getSibling())->copyBranch();
3040  }
3041  else
3042  {
3043  pExponent = NULL;
3044  }
3045 
3046  // check if a base with the same infix is already in the map.
3047  // if not, add the base
3048  // if yes, add the exponent to the vector associated with the base
3049  if (pBase->getChild() != NULL)
3050  {
3051  pBase2 = createNormalRepresentation(pBase);
3052  base2String = pBase2->toString();
3053  delete pBase2;
3054  pBase2 = NULL;
3055  }
3056  else
3057  {
3058  base2String = pBase->buildInfix();
3059  }
3060 
3061  infixPos = infixMap.find(base2String);
3062 
3063  if (infixPos != infixMap.end())
3064  {
3065  matchPos = matchMap.find(infixPos->second);
3066  assert(matchPos != matchMap.end());
3067 
3068  if (matchPos != matchMap.end())
3069  {
3070  if (pExponent != NULL)
3071  {
3072  if (matchPos->second.pExponentNode != NULL)
3073  {
3075  pAddNode->addChild(matchPos->second.pExponentNode);
3076  pAddNode->addChild(pExponent);
3077  matchPos->second.pExponentNode = pAddNode;
3078  matchPos->second.subtraction_indices.insert(index);
3079  }
3080  else
3081  {
3082  // we have to add -1 * pExponent
3084  pAddNode->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "-1.0"));
3085  pAddNode->addChild(pExponent);
3086  matchPos->second.pExponentNode = pAddNode;
3087  }
3088  }
3089  else
3090  {
3091  // subtract one from the factor
3092  matchPos->second.factor -= 1.0;
3093  }
3094  }
3095  }
3096  else
3097  {
3098  match.pNode = pBase->copyBranch();
3099 
3100  if (pExponent == NULL)
3101  {
3102  match.factor = -1.0;
3103  match.pExponentNode = NULL;
3104  }
3105  else
3106  {
3107  // we have to add -1 * pExponent
3108  match.factor = 0.0;
3110  pAddNode->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "-1.0"));
3111  pAddNode->addChild(pExponent);
3112  match.pExponentNode = pAddNode;
3113  }
3114 
3115  match.addition_indices.clear();
3116  match.subtraction_indices.clear();
3117  match.subtraction_indices.insert(index);
3118  infixMap.insert(std::pair<std::string, const CEvaluationNode*>(base2String, pBase));
3119  matchMap.insert(std::pair<const CEvaluationNode*, product_match>(pBase, match));
3120  orderList.push_back(pBase);
3121  }
3122 
3123  ++index;
3124  ++vit;
3125  }
3126 
3127  // create the result vector
3128  std::vector<product_match> result;
3129  CEvaluationNode* pTmpNode = NULL;
3130  std::ostringstream os;
3131 
3132  std::list<const CEvaluationNode*>::const_iterator orderIt = orderList.begin(), orderEndit = orderList.end();
3133 
3134  while (orderIt != orderEndit)
3135  {
3136  matchPos = matchMap.find(*orderIt);
3137  assert(matchPos != matchMap.end());
3138 
3139  if (matchPos != matchMap.end())
3140  {
3141 
3142  // call newEvaluateNumbers on pExponentNode of each match
3143  if (matchPos->second.pExponentNode != NULL)
3144  {
3145  if (CEvaluationNode::type(matchPos->second.pExponentNode->getType()) == CEvaluationNode::NUMBER)
3146  {
3147  // add the numerical value to factor
3148  matchPos->second.factor += matchPos->second.pExponentNode->getValue();
3149  // and delete the exponent node
3150  delete matchPos->second.pExponentNode;
3151  matchPos->second.pExponentNode = NULL;
3152  }
3153  else
3154  {
3155  pTmpNode = CNormalTranslation::newEvaluateNumbers(matchPos->second.pExponentNode);
3156 
3157  if (pTmpNode != NULL)
3158  {
3160  {
3161  // add the numerical value to factor
3162  matchPos->second.factor += pTmpNode->getValue();
3163  // and delete the exponent node
3164  delete matchPos->second.pExponentNode;
3165  matchPos->second.pExponentNode = NULL;
3166  }
3167  else
3168  {
3169  // replace the exponent node
3170  delete matchPos->second.pExponentNode;
3171  matchPos->second.pExponentNode = pTmpNode;
3172  }
3173  }
3174  else
3175  {
3176  // add the factor to the exponent node
3177  // and set the factor to 0.0
3178  if (matchPos->second.factor != 0.0)
3179  {
3180  os.str("");
3181  os.precision(18);
3182  os << matchPos->second.factor;
3183  pExponent = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
3185  pAddNode->addChild(pExponent);
3186  pAddNode->addChild(matchPos->second.pExponentNode);
3187  matchPos->second.pExponentNode = pAddNode;
3188  matchPos->second.factor = 0.0;
3189  }
3190 
3191  }
3192  }
3193  }
3194 
3195  result.push_back(matchPos->second);
3196  }
3197 
3198  ++orderIt;
3199  }
3200 
3201  return result;
3202 }
3203 
3204 
3205 
3206 /**
3207  * The methods get a vector of addition elements and a vector of subtractions
3208  * elements and tries to find equal elements in those two vectors.
3209  */
3210 std::vector<summ_match> CNormalTranslation::matchSummands(const std::vector<const CEvaluationNode*>& additions, const std::vector<const CEvaluationNode*>& subtractions)
3211 {
3212  // the individual elements could be multiplication chains and there could
3213  // be a common factor somewhere in the chain
3214  // Since I only want to get rid of numbers, it might be enough to
3215  // consider only those multiplication chains that contain a number node and
3216  // something else, everything else is ambiguous anyway and depends on
3217  // the order of the nodes in the chain
3218  std::map<const CEvaluationNode*, summ_match> matchMap;
3219  std::map<const CEvaluationNode*, summ_match>::iterator matchPos;
3220  std::map<std::string, const CEvaluationNode*> infixMap;
3221  std::map<std::string, const CEvaluationNode*>::iterator infixPos;
3222 
3223  summ_match match;
3224  std::vector<const CEvaluationNode*>::const_iterator vit = additions.begin(), vendit = additions.end();
3225  const CEvaluationNode *pNode = NULL, *pChild1 = NULL, *pChild2 = NULL;
3226  double factor = 0.0;
3227  CNormalFraction* pBase2 = NULL;
3228  std::string base2String;
3229  unsigned int index = 0;
3230  // we store the order in which the base string occur so that we can
3231  // return the result in approxiumately the same order, the will help in
3232  // reducing the problem of loops with changing element order
3233  std::list<const CEvaluationNode*> orderList;
3234 
3235  while (vit != vendit)
3236  {
3237  pNode = (*vit);
3238  factor = 1.0;
3239 
3241  {
3242  pChild1 = dynamic_cast<const CEvaluationNode*>(pNode->getChild());
3243  assert(pChild1 != NULL);
3244  pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
3245  assert(pChild2 != NULL);
3246  assert(pChild2->getSibling() == NULL);
3247 
3248  if (CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER)
3249  {
3250  pNode = pChild2;
3251  factor = pChild1->getValue();
3252  }
3253  else if (CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER)
3254  {
3255  pNode = pChild1;
3256  factor = pChild2->getValue();
3257  }
3258  }
3259 
3260  // check if a node with the same infix is already in the map.
3261  // if not, add the base
3262  // if yes, add the exponent to the vector associated with the base
3263  if (pNode->getChild() != NULL)
3264  {
3265  pBase2 = createNormalRepresentation(pNode);
3266  base2String = pBase2->toString();
3267  delete pBase2;
3268  pBase2 = NULL;
3269  }
3270  else
3271  {
3272  base2String = pNode->buildInfix();
3273  }
3274 
3275  infixPos = infixMap.find(base2String);
3276 
3277  if (infixPos != infixMap.end())
3278  {
3279  matchPos = matchMap.find(infixPos->second);
3280  assert(matchPos != matchMap.end());
3281 
3282  if (matchPos != matchMap.end())
3283  {
3284  matchPos->second.factor += factor;
3285  matchPos->second.addition_indices.insert(index);
3286  }
3287  }
3288  else
3289  {
3290  match.pNode = pNode->copyBranch();
3291  match.factor = factor;
3292  match.addition_indices.clear();
3293  match.addition_indices.insert(index);
3294  match.subtraction_indices.clear();
3295  infixMap.insert(std::pair<std::string, const CEvaluationNode*>(base2String, pNode));
3296  matchMap.insert(std::pair<const CEvaluationNode*, summ_match>(pNode, match));
3297  orderList.push_back(pNode);
3298  }
3299 
3300  ++index;
3301  ++vit;
3302  }
3303 
3304  index = 0;
3305 
3306  vit = subtractions.begin(), vendit = subtractions.end();
3307 
3308  while (vit != vendit)
3309  {
3310  pNode = (*vit);
3311  factor = -1.0;
3312 
3314  {
3315  pChild1 = dynamic_cast<const CEvaluationNode*>(pNode->getChild());
3316  assert(pChild1 != NULL);
3317  pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
3318  assert(pChild2 != NULL);
3319  assert(pChild2->getSibling() == NULL);
3320 
3321  if (CEvaluationNode::type(pChild1->getType()) == CEvaluationNode::NUMBER)
3322  {
3323  pNode = pChild2;
3324  factor = pChild1->getValue();
3325  }
3326  else if (CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER)
3327  {
3328  pNode = pChild1;
3329  factor = pChild2->getValue();
3330  }
3331  }
3332 
3333  // check if a node with the same infix is already in the map.
3334  // if not, add the node
3335  // if yes, add the 1 to the vector associated with the base
3336  if (pNode->getChild() != NULL)
3337  {
3338  pBase2 = createNormalRepresentation(pNode);
3339  base2String = pBase2->toString();
3340  delete pBase2;
3341  pBase2 = NULL;
3342  }
3343  else
3344  {
3345  base2String = pNode->buildInfix();
3346  }
3347 
3348  infixPos = infixMap.find(base2String);
3349 
3350  if (infixPos != infixMap.end())
3351  {
3352  matchPos = matchMap.find(infixPos->second);
3353  assert(matchPos != matchMap.end());
3354 
3355  if (matchPos != matchMap.end())
3356  {
3357  matchPos->second.factor -= factor;
3358  matchPos->second.subtraction_indices.insert(index);
3359  }
3360  }
3361  else
3362  {
3363  match.pNode = pNode->copyBranch();
3364  match.factor = factor;
3365  match.addition_indices.clear();
3366  match.subtraction_indices.clear();
3367  match.subtraction_indices.insert(index);
3368  infixMap.insert(std::pair<std::string, const CEvaluationNode*>(base2String, pNode));
3369  matchMap.insert(std::pair<const CEvaluationNode*, summ_match>(pNode, match));
3370  orderList.push_back(pNode);
3371  }
3372 
3373  ++index;
3374  ++vit;
3375  }
3376 
3377  // now combine the two maps
3378  std::vector<summ_match> result;
3379 
3380  std::list<const CEvaluationNode*>::const_iterator orderIt = orderList.begin(), orderEndit = orderList.end();
3381 
3382  while (orderIt != orderEndit)
3383  {
3384  matchPos = matchMap.find(*orderIt);
3385  assert(matchPos != matchMap.end());
3386 
3387  if (matchPos != matchMap.end())
3388  {
3389  result.push_back(matchPos->second);
3390  }
3391 
3392  ++orderIt;
3393  }
3394 
3395  return result;
3396 }
3397 
3398 
3399 /**
3400  * The methods get a vector of multiplication elements and a vector of division
3401  * elements and tries to find elements with the same power base in those two vectors.
3402 
3403 std::vector<std::pair<CEvaluationNode*, CEvaluationNode*> > CNormalTranslation::matchPowerBases(const std::vector<const CEvaluationNode*>& multiplications, const std::vector<const CEvaluationNode*>& divisions)
3404 {
3405  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > > matchMap;
3406  std::vector<const CEvaluationNode*>::const_iterator vit = multiplications.begin(), vendit = multiplications.end();
3407 
3408  while (vit != vendit)
3409  {
3410  const CEvaluationNode* pBase = (*vit);
3411  CEvaluationNode* pExponent = NULL;
3412 
3413  if (CEvaluationNode::type(pBase->getType()) == CEvaluationNode::OPERATOR && ((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pBase->getType())) == CEvaluationNodeOperator::POWER)
3414  {
3415  pBase = dynamic_cast<const CEvaluationNode*>(pBase->getChild());
3416  pExponent = dynamic_cast<const CEvaluationNode*>(pBase->getSibling())->copyBranch();
3417  }
3418  else
3419  {
3420  pExponent = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "1.0");
3421  }
3422 
3423  // check if a base with the same infix is already in the map.
3424  // if not, add the base
3425  // if yes, add the exponent to the vector associated with the base
3426  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > >::iterator mapIt = matchMap.begin(), mapEndit = matchMap.end();
3427  CNormalFraction* pBase2 = createNormalRepresentation(pBase);
3428  std::string base2String = pBase2->toString();
3429  delete pBase2;
3430 
3431  while (mapIt != mapEndit)
3432  {
3433  if (mapIt->first.second == base2String)
3434  {
3435  mapIt->second.push_back(pExponent);
3436  break;
3437  }
3438 
3439  ++mapIt;
3440  }
3441 
3442  if (mapIt == mapEndit)
3443  {
3444  std::vector<CEvaluationNode*> v;
3445  v.push_back(pExponent);
3446  matchMap.push_back(std::make_pair(std::pair<const CEvaluationNode*, std::string>(pBase, base2String), v));
3447  }
3448 
3449  ++vit;
3450  }
3451 
3452  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > > matchMap2;
3453  vit = divisions.begin(), vendit = divisions.end();
3454 
3455  while (vit != vendit)
3456  {
3457  const CEvaluationNode* pBase = (*vit);
3458  CEvaluationNode* pExponent = NULL;
3459 
3460  if (CEvaluationNode::type(pBase->getType()) == CEvaluationNode::OPERATOR && ((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pBase->getType())) == CEvaluationNodeOperator::POWER)
3461  {
3462  pBase = dynamic_cast<const CEvaluationNode*>(pBase->getChild());
3463  pExponent = dynamic_cast<const CEvaluationNode*>(pBase->getSibling())->copyBranch();
3464  }
3465  else
3466  {
3467  pExponent = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "1.0");
3468  }
3469 
3470  // check if a base with the same infix is already in the map.
3471  // if not, add the base
3472  // if yes, add the exponent to the vector associated with the base
3473  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > >::iterator mapIt = matchMap2.begin(), mapEndit = matchMap2.end();
3474  CNormalFraction* pBase2 = createNormalRepresentation(pBase);
3475  std::string base2String = pBase2->toString();
3476  delete pBase2;
3477 
3478  while (mapIt != mapEndit)
3479  {
3480  if (mapIt->first.second == base2String)
3481  {
3482  mapIt->second.push_back(pExponent);
3483  break;
3484  }
3485 
3486  ++mapIt;
3487  }
3488 
3489  if (mapIt == mapEndit)
3490  {
3491  std::vector<CEvaluationNode*> v;
3492  v.push_back(pExponent);
3493  matchMap2.push_back(std::make_pair(std::pair<const CEvaluationNode*, std::string>(pBase, base2String), v));
3494  }
3495 
3496  ++vit;
3497  }
3498 
3499  // now combine the two maps
3500  std::vector<std::pair<CEvaluationNode*, std::pair<CEvaluationNode*, std::string> > > result;
3501  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > >::iterator mapIt = matchMap.begin(), mapEndit = matchMap.end();
3502 
3503  while (mapIt != mapEndit)
3504  {
3505  CEvaluationNode* pNode = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, mapIt->second);
3506  assert(pNode != NULL);
3507  result.push_back(std::make_pair(pNode, std::pair<CEvaluationNode*, std::string>(mapIt->first.first->copyBranch(), mapIt->first.second)));
3508  ++mapIt;
3509  }
3510 
3511  mapIt = matchMap2.begin(), mapEndit = matchMap2.end();
3512 
3513  while (mapIt != mapEndit)
3514  {
3515  std::vector<CEvaluationNode*> constVect;
3516  constVect.insert(constVect.begin(), mapIt->second.begin(), mapIt->second.end());
3517  CEvaluationNode* pNode = CNormalTranslation::createOperatorChain(CEvaluationNodeOperator::PLUS, "+", constVect);
3518  // now check if we already have a base with the same infix in the
3519  // results
3520  unsigned int i, iMax = result.size();
3521 
3522  for (i = 0; i < iMax; ++i)
3523  {
3524  if (result[i].second.second == mapIt->first.second)
3525  {
3526  CEvaluationNode* pTmpNode = new CEvaluationNodeOperator(CEvaluationNodeOperator::MINUS, "-");
3527  pTmpNode->addChild(result[i].first);
3528  pTmpNode->addChild(pNode);
3529  result[i] = std::make_pair(pTmpNode, result[i].second);
3530  break;
3531  }
3532  }
3533 
3534  if (i == iMax)
3535  {
3536  if (CEvaluationNode::type(pNode->getType()) == CEvaluationNode::NUMBER)
3537  {
3538  std::ostringstream os;
3539  os.precision(18);
3540  os << static_cast<CEvaluationNodeNumber*>(pNode)->getValue() * -1.0;
3541  CEvaluationNode* pTmpNumber = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
3542  delete pNode;
3543  result.push_back(std::make_pair(pTmpNumber, std::pair<CEvaluationNode*, std::string>(mapIt->first.first->copyBranch(), mapIt->first.second)));
3544  }
3545  else
3546  {
3547  CEvaluationNode* pTmpNode = new CEvaluationNodeOperator(CEvaluationNodeOperator::MULTIPLY, "*");
3548  pTmpNode->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "-1.0"));
3549  pTmpNode->addChild(pNode);
3550  result.push_back(std::make_pair(pTmpNode, std::pair<CEvaluationNode*, std::string>(mapIt->first.first->copyBranch(), mapIt->first.second)));
3551  }
3552  }
3553 
3554  // delete the obsolete nodes
3555  iMax = mapIt->second.size();
3556 
3557  for (i = 0; i < iMax; ++i)
3558  {
3559  delete mapIt->second[i];
3560  }
3561 
3562  ++mapIt;
3563  }
3564 
3565  // copy the result vector into the return data structure
3566  std::vector<std::pair<CEvaluationNode*, CEvaluationNode*> > tmp;
3567  unsigned int i, iMax = result.size();
3568  // since we know how many elements will end up in tmp, we can already reserve
3569  // the space
3570  tmp.reserve(iMax);
3571 
3572  for (i = 0; i < iMax; ++i)
3573  {
3574  tmp.push_back(std::pair<CEvaluationNode*, CEvaluationNode*>(result[i].first, result[i].second.first));
3575  }
3576 
3577  return tmp;
3578 }
3579 */
3580 
3581 
3582 
3583 /**
3584  * The methods get a vector of addition elements and a vector of subtractions
3585  * elements and tries to find equal elements in those two vectors.
3586  */
3587 std::vector<std::pair<CEvaluationNode*, CEvaluationNode*> > CNormalTranslation::matchSummands(const std::vector<CEvaluationNode*>& additions, const std::vector<CEvaluationNode*>& subtractions)
3588 {
3589  // the individual elements could be multiplication chains and there could
3590  // be a common factor somewhere in the chain
3591  // Since I only want to get rid of numbers, it might be enough to
3592  // consider only those multiplication chains the contain a number node and
3593  // something else, everything else is ambiguous anyway and depends on
3594  // the order of the nodes in the chain
3595  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > > matchMap;
3596 
3597  std::vector<CEvaluationNode*>::const_iterator vit = additions.begin(), vendit = additions.end();
3598 
3599  while (vit != vendit)
3600  {
3601  const CEvaluationNode* pNode = (*vit);
3602  CEvaluationNode* pFactor = NULL;
3603 
3605  {
3606  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pNode->getChild());
3607  assert(pChild1 != NULL);
3608  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
3609  assert(pChild2 != NULL);
3610  assert(pChild2->getSibling() == NULL);
3611 
3613  {
3614  pNode = pChild2;
3615  pFactor = pChild1->copyBranch();
3616  }
3617  else if (CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER)
3618  {
3619  pNode = pChild1;
3620  pFactor = pChild2->copyBranch();
3621  }
3622  else
3623  {
3625  }
3626  }
3627  else
3628  {
3630  }
3631 
3632  // check if a node with the same infix is already in the map.
3633  // if not, add the base
3634  // if yes, add the exponent to the vector associated with the base
3635  std::string base2String;
3636 
3637  if (pNode->getChild() != NULL)
3638  {
3640  base2String = pBase2->toString();
3641  delete pBase2;
3642  pBase2 = NULL;
3643  }
3644  else
3645  {
3646  base2String = pNode->buildInfix();
3647  }
3648 
3649  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > >::iterator mapIt = matchMap.begin(), mapEndit = matchMap.end();
3650 
3651  while (mapIt != mapEndit)
3652  {
3653  if (mapIt->first.second == base2String)
3654  {
3655  mapIt->second.push_back(pFactor);
3656  break;
3657  }
3658 
3659  ++mapIt;
3660  }
3661 
3662 
3663  if (mapIt == mapEndit)
3664  {
3665  std::vector<CEvaluationNode*> v;
3666  v.push_back(pFactor);
3667  matchMap.push_back(std::make_pair(std::pair<const CEvaluationNode*, std::string>(pNode, base2String), v));
3668  }
3669 
3670  ++vit;
3671  }
3672 
3673  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > > matchMap2;
3674  vit = subtractions.begin(), vendit = subtractions.end();
3675 
3676  while (vit != vendit)
3677  {
3678  const CEvaluationNode* pNode = (*vit);
3679  CEvaluationNode* pFactor = NULL;
3680 
3682  {
3683  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pNode->getChild());
3684  assert(pChild1 != NULL);
3685  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
3686  assert(pChild2 != NULL);
3687  assert(pChild2->getSibling() == NULL);
3688 
3690  {
3691  pNode = pChild2;
3692  pFactor = pChild1->copyBranch();
3693  }
3694  else if (CEvaluationNode::type(pChild2->getType()) == CEvaluationNode::NUMBER)
3695  {
3696  pNode = pChild1;
3697  pFactor = pChild2->copyBranch();
3698  }
3699  else
3700  {
3702  }
3703  }
3704  else
3705  {
3707  }
3708 
3709  // check if a node with the same infix is already in the map.
3710  // if not, add the node
3711  // if yes, add the 1 to the vector associated with the base
3712  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > >::iterator mapIt = matchMap2.begin(), mapEndit = matchMap2.end();
3713  std::string base2String;
3714 
3715  if (pNode->getChild() != NULL)
3716  {
3718  base2String = pBase2->toString();
3719  delete pBase2;
3720  }
3721  else
3722  {
3723  base2String = pNode->buildInfix();
3724  }
3725 
3726  while (mapIt != mapEndit)
3727  {
3728  if (mapIt->first.second == base2String)
3729  {
3730  mapIt->second.push_back(pFactor);
3731  break;
3732  }
3733 
3734  ++mapIt;
3735  }
3736 
3737 
3738  if (mapIt == mapEndit)
3739  {
3740  std::vector<CEvaluationNode*> v;
3741  v.push_back(pFactor);
3742  matchMap2.push_back(std::make_pair(std::pair<const CEvaluationNode*, std::string>(pNode, base2String), v));
3743  }
3744 
3745  ++vit;
3746  }
3747 
3748  // now combine the two maps
3749  std::vector<std::pair<CEvaluationNode*, std::pair<CEvaluationNode*, std::string> > > result;
3750  std::vector<std::pair<std::pair<const CEvaluationNode*, std::string>, std::vector<CEvaluationNode*> > >::iterator mapIt = matchMap.begin(), mapEndit = matchMap.end();
3751 
3752  while (mapIt != mapEndit)
3753  {
3754  CEvaluationNode* pNode = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, mapIt->second);
3755  assert(pNode != NULL);
3756  result.push_back(std::make_pair(pNode, std::pair<CEvaluationNode*, std::string>(mapIt->first.first->copyBranch(), mapIt->first.second)));
3757  ++mapIt;
3758  }
3759 
3760  mapIt = matchMap2.begin(), mapEndit = matchMap2.end();
3761 
3762  while (mapIt != mapEndit)
3763  {
3764  std::vector<CEvaluationNode*> constVect;
3765  constVect.insert(constVect.begin(), mapIt->second.begin(), mapIt->second.end());
3767  // now check if we already have a base with the same infix in the
3768  // results
3769  unsigned int i, iMax = result.size();
3770 
3771  for (i = 0; i < iMax; ++i)
3772  {
3773  if (result[i].second.second == mapIt->first.second)
3774  {
3776  pTmpNode->addChild(result[i].first);
3777  pTmpNode->addChild(pNode);
3778  result[i] = std::make_pair(pTmpNode, result[i].second);
3779  break;
3780  }
3781  }
3782 
3783  if (i == iMax)
3784  {
3785  CEvaluationNode* pTmpNode = NULL;
3786 
3788  {
3789  std::ostringstream os;
3790  os.precision(18);
3791  os << dynamic_cast<const CEvaluationNodeNumber*>(pNode)->getValue() * -1.0;
3792  pTmpNode = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
3793  delete pNode;
3794  }
3795  else
3796  {
3799  pTmpNode->addChild(pNode);
3800  }
3801 
3802  result.push_back(std::make_pair(pTmpNode, std::pair<CEvaluationNode*, std::string>(mapIt->first.first->copyBranch(), mapIt->first.second)));
3803  }
3804 
3805  // delete the obsolete nodes
3806  iMax = mapIt->second.size();
3807 
3808  for (i = 0; i < iMax; ++i)
3809  {
3810  delete mapIt->second[i];
3811  }
3812 
3813  ++mapIt;
3814  }
3815 
3816  std::vector<std::pair<CEvaluationNode*, CEvaluationNode*> > tmp;
3817  // copy the result vector into the expected return data type
3818  unsigned int i, iMax = result.size();
3819  // since we know how many item will end up in the vector we can already
3820  // reserve the space
3821  tmp.reserve(iMax);
3822 
3823  for (i = 0; i < iMax; ++i)
3824  {
3825  tmp.push_back(std::pair<CEvaluationNode*, CEvaluationNode*>(result[i].first, result[i].second.first));
3826  }
3827 
3828  return tmp;
3829 }
3830 
3831 
3832 /**
3833  * This method expands products. (A+B)*(C+D) -> (A*C)+(A*D)+(B*C)+(B*D)
3834  */
3836 {
3837  CEvaluationNode* pResult = NULL;
3838 
3839  // we have to create operation chains and do the multiplication
3840  // on the numerator and the denominator chain if the node is a multiplication
3841  // or a division
3843  {
3844  std::vector<const CEvaluationNode*> multiplications, divisions;
3845  CNormalTranslation::splitProduct(pOrig, multiplications, divisions, false);
3846  unsigned int i, iMax = multiplications.size();
3847  CEvaluationNode* pTmpResult;
3848 
3849  for (i = 0; i < iMax; ++i)
3850  {
3851  if (pResult == NULL)
3852  {
3853  pResult = CNormalTranslation::expandProducts(multiplications[i]);
3854  }
3855  else
3856  {
3857  CEvaluationNode* pTmpNode = CNormalTranslation::expandProducts(multiplications[i]);
3858  pTmpResult = CNormalTranslation::multiply(pResult, pTmpNode);
3859  delete pResult;
3860  delete pTmpNode;
3861  pResult = pTmpResult;
3862  }
3863  }
3864 
3865  if (!divisions.empty())
3866  {
3867  CEvaluationNode* pDenominator = NULL;
3868  iMax = divisions.size();
3869 
3870  for (i = 0; i < iMax; ++i)
3871  {
3872  if (pDenominator == NULL)
3873  {
3874  pDenominator = CNormalTranslation::expandProducts(divisions[i]);
3875  }
3876  else
3877  {
3878  CEvaluationNode* pTmpNode = CNormalTranslation::expandProducts(divisions[i]);
3879  pTmpResult = CNormalTranslation::multiply(pDenominator, pTmpNode);
3880  delete pDenominator;
3881  delete pTmpNode;
3882  pDenominator = pTmpResult;
3883  }
3884 
3885  //delete divisions[i];
3886  }
3887 
3889  pTmpResult->addChild(pResult);
3890  pTmpResult->addChild(pDenominator);
3891  pResult = pTmpResult;
3892  }
3893  }
3894  else
3895  {
3896  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pOrig->getChild());
3897  std::vector<CEvaluationNode*> children;
3898 
3899  while (pChild != NULL)
3900  {
3901  children.push_back(CNormalTranslation::expandProducts(pChild));
3902  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
3903  }
3904 
3907  {
3908  assert(children.size() == 2);
3909  pResult = CNormalTranslation::multiply(children[0], children[1]);
3910  // delete the children
3911  delete children[0];
3912  delete children[1];
3913  }
3914 
3915  if (pResult == NULL)
3916  {
3917  pResult = pOrig->copyNode(children);
3918  }
3919  }
3920 
3921  return pResult;
3922 }
3923 
3924 
3925 /**
3926  * Multiplies the two given nodes and returns the result.
3927  */
3929 {
3930  CEvaluationNode* pResult = NULL;
3931  std::vector<const CEvaluationNode*> additions1, subtractions1;
3932  CNormalTranslation::splitSum(pNode1, additions1, subtractions1, false);
3933  std::vector<const CEvaluationNode*> additions2, subtractions2;
3934  CNormalTranslation::splitSum(pNode2, additions2, subtractions2, false);
3935  // multiply every element in additions1 with every element in additions2
3936  // and subtractions2 the results for the multiplication with the elements
3937  // of subtractions2 must be multiplied by -1
3938  // multiply every element in subtraction1 with every element in additions2
3939  // and subtractions2 the results for the multiplication with the elements
3940  // of additions2 must be multiplied by -1
3941  std::vector<CEvaluationNode*> tmp;
3942  unsigned int i, iMax = additions1.size();
3943 
3944  for (i = 0; i < iMax; ++i)
3945  {
3946  unsigned int j, jMax = additions2.size();
3947 
3948  for (j = 0; j < jMax; ++j)
3949  {
3951  pMult->addChild(additions1[i]->copyBranch());
3952  pMult->addChild(additions2[j]->copyBranch());
3953  tmp.push_back(pMult);
3954  }
3955  }
3956 
3957  iMax = subtractions1.size();
3958 
3959  for (i = 0; i < iMax; ++i)
3960  {
3961  unsigned int j, jMax = subtractions2.size();
3962 
3963  for (j = 0; j < jMax; ++j)
3964  {
3966  pMult->addChild(subtractions1[i]->copyBranch());
3967  pMult->addChild(subtractions2[j]->copyBranch());
3968  tmp.push_back(pMult);
3969  }
3970  }
3971 
3972  if (!tmp.empty())
3973  {
3974  pResult = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, tmp);
3975  assert(pResult != NULL);
3976  tmp.clear();
3977  }
3978 
3979  iMax = additions1.size();
3980 
3981  for (i = 0; i < iMax; ++i)
3982  {
3983  unsigned int j, jMax = subtractions2.size();
3984 
3985  for (j = 0; j < jMax; ++j)
3986  {
3988  pMult->addChild(additions1[i]->copyBranch());
3989  pMult->addChild(subtractions2[j]->copyBranch());
3990  tmp.push_back(pMult);
3991  }
3992  }
3993 
3994  iMax = subtractions1.size();
3995 
3996  for (i = 0; i < iMax; ++i)
3997  {
3998  unsigned int j, jMax = additions2.size();
3999 
4000  for (j = 0; j < jMax; ++j)
4001  {
4003  pMult->addChild(subtractions1[i]->copyBranch());
4004  pMult->addChild(additions2[j]->copyBranch());
4005  tmp.push_back(pMult);
4006  }
4007  }
4008 
4009  if (!tmp.empty())
4010  {
4011  if (pResult != NULL)
4012  {
4014  pTmpNode->addChild(pResult);
4015  pResult = pTmpNode;
4016  pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, tmp);
4017  assert(pTmpNode != NULL);
4018  pResult->addChild(pTmpNode);
4019  }
4020  else
4021  {
4022  if (tmp.size() == 1 && CEvaluationNode::type(tmp[0]->getType()) == CEvaluationNode::NUMBER)
4023  {
4024  std::ostringstream os;
4025  os.precision(18);
4026  os << tmp[0]->getValue() * -1.0;
4027  pResult = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str());
4028  delete tmp[0];
4029  }
4030  else
4031  {
4034  pResult = pTmpNode;
4035  pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, tmp);
4036  assert(pTmpNode != NULL);
4037  pResult->addChild(pTmpNode);
4038  }
4039  }
4040  }
4041 
4042  return pResult;
4043 }
4044 
4045 /**
4046  * New non-recursive cancel method.
4047  * This method does all the canceling on a given node and its children.
4048  * If no canceling was done, NULL is returned.
4049  */
4051 {
4052  //
4053  // try to find multiplication chains where something is divided by itself
4054  // or multiplied by -1 times itself
4055  // also consider powers (it's the bases that have to match)
4056  //
4057  // try to find addition changes where there is a subtraction of two
4058  // identical nodes or an addition of one node and the same node times -1
4059  bool modified = false;
4060  // make a copy of the node
4061  CEvaluationNode* pResult = pOrig->copyBranch();
4062  assert(pResult != NULL);
4063  CEvaluationNodeDepthFirstIterator dfi(pResult);
4064  CEvaluationNode::Type type;
4065  CEvaluationNode* pTmpOrig = NULL;
4066  std::ostringstream os;
4067 
4068  while (dfi.isValid())
4069  {
4070  type = CEvaluationNode::type(dfi->getType());
4071 
4072  if (type == CEvaluationNode::OPERATOR)
4073  {
4074  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(dfi->getChild());
4075  assert(pChild1 != NULL);
4076  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
4077  assert(pChild2 != NULL);
4079 
4080  switch (subType)
4081  {
4084  {
4085  pTmpOrig = dynamic_cast<CEvaluationNode*>(dfi->getParent());
4086 
4087  // if there is no parent or if the parent is not a multiplication or division, we try to evaluate numbers
4089  {
4090  // do the canceling
4091  std::vector<const CEvaluationNode*> multiplications, divisions;
4092  CNormalTranslation::splitProduct(*dfi, multiplications, divisions, false);
4093  // collect all nodes in multiplications and divisions
4094 
4095  // find identical nodes in multiplications and divisions
4096  // The first entry in the pair is the collected power exponent
4097  // the second entry is the original power base
4098  // make sure the collected factor is again simplified
4099  std::vector<product_match> collected = CNormalTranslation::matchPowerBases(multiplications, divisions);
4100 
4101  // decide if matches were found
4102  // if we are working on a copy, we can go and delete those elements, that are no longer needed (e.g. all but the first entry for each match element)
4103  // remember to delete the entries in negAdditions and negSubtractions
4104  if (collected.size() != (multiplications.size() + divisions.size()))
4105  {
4106  std::vector<CEvaluationNode*> numeratorChain;
4107  std::vector<CEvaluationNode*> denominatorChain;
4108  unsigned int iMax = collected.size();
4109 
4110  for (unsigned int i = 0; i < iMax; ++i)
4111  {
4112  product_match& match = collected[i];
4113 
4114  // the matches we get back either have the factor set if it is a pure number,
4115  // or they have the pExponentNode set if it can't be represented as a pure number
4116  // if simplified node is a 0.0, we ignore this node
4117  if (match.pExponentNode == NULL)
4118  {
4119  if (fabs(match.factor) < ZERO)
4120  {
4121  delete match.pNode;
4122  match.pNode = NULL;
4123  }
4124  else if (match.factor > 0.0)
4125  {
4126  if (fabs(match.factor - 1.0) < ZERO)
4127  {
4128  numeratorChain.push_back(match.pNode);
4129  }
4130  else
4131  {
4132  os.str("");
4133  os.precision(18);
4134  os << match.factor;
4136  pPower->addChild(match.pNode);
4137  pPower->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str()));
4138  numeratorChain.push_back(pPower);
4139  }
4140  }
4141  else
4142  {
4143  if (fabs(match.factor + 1.0) < ZERO)
4144  {
4145  denominatorChain.push_back(match.pNode);
4146  }
4147  else
4148  {
4150  pPower->addChild(match.pNode);
4151  os.str("");
4152  os.precision(18);
4153  os << fabs(match.factor);
4154  pPower->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str()));
4155  denominatorChain.push_back(pPower);
4156  }
4157  }
4158  }
4159  else
4160  {
4161  // since the pExponentNode is not NULL, we can ignore the factor attribute
4162  // because it has already been added to the pExponentNode
4163  //
4164  // since the exponent can't be represented as a number, we probably don't now if the
4165  // exponent should be added to divisions or multiplications, so we just add all of them
4166  // to the numerator
4168  pPower->addChild(match.pNode);
4169  pPower->addChild(match.pExponentNode);
4170  numeratorChain.push_back(pPower);
4171  }
4172  }
4173 
4174  // if there are only divisions, we have an empty numerator chain
4175  if (numeratorChain.empty())
4176  {
4177  pTmpOrig = CNormalTranslation::ONE_NODE.copyBranch();
4178  }
4179  else
4180  {
4181  pTmpOrig = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, numeratorChain);
4182  }
4183 
4184  assert(pTmpOrig != NULL);
4185 
4186  if (!denominatorChain.empty())
4187  {
4189  pTmpNode->addChild(pTmpOrig);
4190  pTmpOrig = pTmpNode;
4191  pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, denominatorChain);
4192  assert(pTmpNode != NULL);
4193  pTmpOrig->addChild(pTmpNode);
4194  }
4195 
4196  assert(pTmpOrig != NULL);
4197 
4198  // now we need to replace dfi in it's parent by pTmpOrig and
4199  // delete dfi
4200  if (dfi->getParent() != NULL)
4201  {
4202  dfi->getParent()->addChild(pTmpOrig, *dfi);
4203  dfi->getParent()->removeChild(*dfi);
4204  delete *dfi;
4205  dfi = pTmpOrig;
4206  }
4207  else
4208  {
4209  // it must be the root node
4210  assert(*dfi == pResult);
4211  delete pResult;
4212  pResult = pTmpOrig;
4213  // we are done
4214  dfi = NULL;
4215  }
4216 
4217  modified = true;
4218  }
4219  else
4220  {
4221  // clean up
4222  std::vector<product_match>::iterator it2 = collected.begin(), endit2 = collected.end();
4223 
4224  while (it2 != endit2)
4225  {
4226  if ((*it2).pNode != NULL)
4227  {
4228  delete(*it2).pNode;
4229 
4230  if ((*it2).pExponentNode != NULL)
4231  {
4232  delete(*it2).pExponentNode;
4233  }
4234  }
4235 
4236  ++it2;
4237  }
4238  }
4239  }
4240  }
4241  break;
4244  {
4245  pTmpOrig = dynamic_cast<CEvaluationNode*>(dfi->getParent());
4246 
4247  // if there is no parent or if the parent is not an addition or subtraction, we try to evaluate numbers
4249  {
4250  // do the canceling
4251  // we are in a sum
4252  std::vector<const CEvaluationNode*> additions, subtractions;
4253  CNormalTranslation::splitSum(*dfi, additions, subtractions, false);
4254  std::vector<CEvaluationNode*> negAdditions, negSubtractions;
4255  CNormalTranslation::findNegativeNumbers(additions, negAdditions);
4256  CNormalTranslation::findNegativeNumbers(subtractions, negSubtractions);
4257  additions.insert(additions.end(), negSubtractions.begin(), negSubtractions.end());
4258  subtractions.insert(subtractions.end(), negAdditions.begin(), negAdditions.end());
4259 
4260  // find identical nodes in additions and subtractions
4261  // The first entry in the pair is the collected factor
4262  // the second entry is the original branch
4263  // make sure the collected factor is again simplified
4264  std::vector<summ_match> collected = CNormalTranslation::matchSummands(additions, subtractions);
4265  // cleanup the generated objects negXXX vector
4266  std::vector<CEvaluationNode*>::iterator it = negAdditions.begin(), endit = negAdditions.end();
4267 
4268  while (it != endit)
4269  {
4270  delete *it;
4271  ++it;
4272  }
4273 
4274  it = negSubtractions.begin(), endit = negSubtractions.end();
4275 
4276  while (it != endit)
4277  {
4278  delete *it;
4279  ++it;
4280  }
4281 
4282  // decide if matches were found
4283  // if we are working on a copy, we can go and delete those elements, that are no longer needed (e.g. all but the first entry for each match element)
4284  if (collected.size() != (additions.size() + subtractions.size()))
4285  {
4286  std::vector<CEvaluationNode*> chain;
4287  unsigned int iMax = collected.size();
4288 
4289 
4290  // now we have to create the result chain
4291  // all elements with a negative factor are subtracted and all indices with a
4292  // positive factor are added
4293  // all nodes with a 0.0 factor are dropped
4294  for (unsigned int i = 0; i < iMax; ++i)
4295  {
4296  summ_match& match = collected[i];
4297 
4298  // if simplified node is 0.0, we ignore this node
4299  if (fabs(match.factor) < ZERO)
4300  {
4301  delete match.pNode;
4302  }
4303  else if (fabs(match.factor - 1.0) < ZERO)
4304  {
4305  chain.push_back(match.pNode);
4306  }
4307  else
4308  {
4310  os.str("");
4311  os.precision(18);
4312  os << match.factor;
4313  pMult->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str()));
4314  assert(pMult != NULL);
4315  assert(match.pNode != NULL);
4316  pMult->addChild(match.pNode);
4317  chain.push_back(pMult);
4318  }
4319  }
4320 
4321  if (!chain.empty())
4322  {
4323  // we replace the current node with the result created here
4324  pTmpOrig = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, chain);
4325  }
4326  else
4327  {
4328  // we replace the current node with the result created here
4329  // the result is 0.0
4331  }
4332 
4333  assert(pTmpOrig != NULL);
4334 
4335  // now we need to replace dfi in it's parent by pTmpOrig and
4336  // delete dfi
4337  if (dfi->getParent() != NULL)
4338  {
4339  dfi->getParent()->addChild(pTmpOrig, *dfi);
4340  dfi->getParent()->removeChild(*dfi);
4341  delete *dfi;
4342  dfi = pTmpOrig;
4343  }
4344  else
4345  {
4346  // it must be the root node
4347  assert(*dfi == pResult);
4348  delete pResult;
4349  pResult = pTmpOrig;
4350  // we are done
4351  dfi = NULL;
4352  }
4353 
4354  modified = true;
4355  }
4356  else
4357  {
4358  // delete the nodes in collected
4359  std::vector<summ_match>::iterator it2 = collected.begin(), endit2 = collected.end();
4360 
4361  while (it2 != endit2)
4362  {
4363  if ((*it2).pNode != NULL)
4364  {
4365  delete(*it2).pNode;
4366  }
4367 
4368  ++it2;
4369  }
4370  }
4371 
4372  // the entries in these two vectors can be cleared
4373  additions.clear();
4374  subtractions.clear();
4375  }
4376  }
4377  break;
4378  default:
4379  break;
4380  }
4381  }
4382 
4383  if (dfi.isValid())
4384  {
4385  ++dfi;
4386  }
4387  }
4388 
4389  if (modified == false)
4390  {
4391  delete pResult;
4392  pResult = NULL;
4393  }
4394 
4395  return pResult;
4396 }
4397 
4398 
4399 /**
4400  * This method does all the canceling on a given node and its children.
4401  * If no canceling was done, NULL is returned.
4402  *
4403  * Obsolete recursive version
4404  */
4405 //CEvaluationNode* CNormalTranslation::cancel(const CEvaluationNode* pOrig)
4406 //{
4407 // //std::cout << "Canceling: " << pOrig->buildInfix() << std::endl;
4408 // // TODO I think this method has much potential for improvement
4409 // // TODO since the comparison code seems to spend about 85% of the time
4410 // // TODO here, this is where I should start making optimizations
4411 // //
4412 // // try to find multiplication chains where something is divided by itself
4413 // // or multiplied by -1 times itself
4414 // // also consider powers (it's the bases that have to match)
4415 // //
4416 // // try to find addition changes where there is a subtraction of two
4417 // // identical nodes or an addition of one node and the same node times -1
4418 // std::vector<CEvaluationNode*> children;
4419 // CEvaluationNode* pResult = NULL;
4420 // const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pOrig->getChild());
4421 // CEvaluationNode* pNewChild = NULL;
4422 // const CEvaluationNode* pTmpOrig = pOrig;
4423 // bool childrenChanged = false;
4424 //
4425 // while (pChild != NULL)
4426 // {
4427 // pNewChild = CNormalTranslation::cancel(pChild);
4428 //
4429 // if (pNewChild != NULL)
4430 // {
4431 // childrenChanged = true;
4432 // }
4433 //
4434 // children.push_back(pNewChild);
4435 // pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
4436 // }
4437 //
4438 // // if one of the children has changed, we have to clone the remaining children as well
4439 // // this is some overhead, but it might save lots of copies
4440 // if (childrenChanged == true)
4441 // {
4442 // pChild = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
4443 // assert(pChild != NULL);
4444 // std::vector<CEvaluationNode*>::iterator it = children.begin(), endit = children.end();
4445 //
4446 // while (it != endit)
4447 // {
4448 // if ((*it) == NULL)
4449 // {
4450 // (*it) = pChild->copyBranch();
4451 // }
4452 //
4453 // pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
4454 // ++it;
4455 // }
4456 //
4457 // assert(pChild == NULL);
4458 // }
4459 //
4460 // if (CEvaluationNode::type(pTmpOrig->getType()) == CEvaluationNode::OPERATOR)
4461 // {
4462 // std::ostringstream os;
4463 // const CEvaluationNode* pParent = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getParent());
4464 //
4465 // if (((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pTmpOrig->getType())) == CEvaluationNodeOperator::PLUS ||
4466 // ((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pTmpOrig->getType())) == CEvaluationNodeOperator::MINUS)
4467 // {
4468 // // check if the parent is a plus or a minus, if so, the cancelation is done there
4469 // if (pParent != NULL)
4470 // {
4471 // CEvaluationNode::Type t = pParent->getType();
4472 //
4473 // if (CEvaluationNode::type(t) == CEvaluationNode::OPERATOR && ((((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(t)) == CEvaluationNodeOperator::PLUS ||
4474 // ((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(t)) == CEvaluationNodeOperator::MINUS)))
4475 // {
4476 // // OK, we are done
4477 // if (childrenChanged)
4478 // {
4479 // pResult = pTmpOrig->copyNode(children);
4480 // }
4481 //
4482 // return pResult;
4483 // }
4484 // }
4485 //
4486 // // if the children of the node have changed, we have to work with the changed version
4487 // if (childrenChanged == true)
4488 // {
4489 // pResult = pTmpOrig->copyNode(children);
4490 // pTmpOrig = pResult;
4491 // }
4492 //
4493 // // we are in a sum
4494 // std::vector<const CEvaluationNode*> additions, subtractions;
4495 // CNormalTranslation::splitSum(pTmpOrig, additions, subtractions, false);
4496 // std::vector<CEvaluationNode*> negAdditions, negSubtractions;
4497 // CNormalTranslation::findNegativeNumbers(additions, negAdditions);
4498 // CNormalTranslation::findNegativeNumbers(subtractions, negSubtractions);
4499 // additions.insert(additions.end(), negSubtractions.begin(), negSubtractions.end());
4500 // subtractions.insert(subtractions.end(), negAdditions.begin(), negAdditions.end());
4501 //
4502 // // find identical nodes in additions and subtractions
4503 // // The first entry in the pair is the collected factor
4504 // // the second entry is the original branch
4505 // // make sure the collected factor is again simplified
4506 // std::vector<summ_match> collected = CNormalTranslation::matchSummands(additions, subtractions);
4507 //
4508 // // decide if matches were found
4509 // // if we are working on a copy, we can go and delete those elements, that are no longer needed (e.g. all but the first entry for each match element)
4510 // // remember to delete the entries in negAdditions and negSubtractions
4511 //
4512 // if (collected.size() != (additions.size() + subtractions.size()))
4513 // {
4514 // std::vector<CEvaluationNode*> chain;
4515 // unsigned int iMax = collected.size();
4516 //
4517 // // this is not correct yet. Has to be updated for the new data structures
4518 // // if we have created a copy of pTmpOrig because if changed children, we can delete that copy
4519 // // we can delete all the elements in the negXXX vectors
4520 // if (pResult != NULL)
4521 // {
4522 // delete pResult;
4523 // pResult = NULL;
4524 // }
4525 //
4526 // std::vector<CEvaluationNode*>::iterator it = negAdditions.begin(), endit = negAdditions.end();
4527 //
4528 // while (it != endit)
4529 // {
4530 // delete *it;
4531 // ++it;
4532 // }
4533 //
4534 // negAdditions.clear();
4535 // it = negSubtractions.begin();
4536 // endit = negSubtractions.end();
4537 //
4538 // while (it != endit)
4539 // {
4540 // delete *it;
4541 // ++it;
4542 // }
4543 //
4544 // negSubtractions.clear();
4545 // additions.clear();
4546 // subtractions.clear();
4547 //
4548 // // now we have to create the result chain
4549 // // all elements with a negative factor are subtracted and all indices with a
4550 // // positive factor are added
4551 // // all nodes with a 0.0 factor are dropped
4552 // for (unsigned int i = 0; i < iMax; ++i)
4553 // {
4554 // summ_match& match = collected[i];
4555 //
4556 // // if simplified node is 0.0, we ignore this node
4557 // if (fabs(match.factor) < ZERO)
4558 // {
4559 // delete match.pNode;
4560 // }
4561 // else if (fabs(match.factor - 1.0) < ZERO)
4562 // {
4563 // chain.push_back(match.pNode);
4564 // }
4565 // else
4566 // {
4567 // CEvaluationNode* pMult = new CEvaluationNodeOperator(CEvaluationNodeOperator::MULTIPLY, "*");
4568 // os.str("");
4569 // os.precision(18);
4570 // os << match.factor;
4571 // pMult->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str()));
4572 // assert(pMult != NULL);
4573 // assert(match.pNode != NULL);
4574 // pMult->addChild(match.pNode);
4575 // chain.push_back(pMult);
4576 // }
4577 // }
4578 //
4579 // if (!chain.empty())
4580 // {
4581 // pResult = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, chain);
4582 // }
4583 // else
4584 // {
4585 // // the result is 0.0
4586 // pResult = new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, "0.0");
4587 // }
4588 //
4589 // assert(pResult != NULL);
4590 // }
4591 // else
4592 // {
4593 // // cleanup the generated objects negXXX vector
4594 // std::vector<CEvaluationNode*>::iterator it = negAdditions.begin(), endit = negAdditions.end();
4595 //
4596 // while (it != endit)
4597 // {
4598 // delete *it;
4599 // ++it;
4600 // }
4601 //
4602 // it = negSubtractions.begin(), endit = negSubtractions.end();
4603 //
4604 // while (it != endit)
4605 // {
4606 // delete *it;
4607 // ++it;
4608 // }
4609 //
4610 // std::vector<summ_match>::iterator it2 = collected.begin(), endit2 = collected.end();
4611 //
4612 // while (it2 != endit2)
4613 // {
4614 // if ((*it2).pNode != NULL)
4615 // {
4616 // delete(*it2).pNode;
4617 // }
4618 //
4619 // ++it2;
4620 // }
4621 //
4622 // // pResult is already set above
4623 // }
4624 // }
4625 // else if (((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pTmpOrig->getType())) == CEvaluationNodeOperator::MULTIPLY ||
4626 // ((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pTmpOrig->getType())) == CEvaluationNodeOperator::DIVIDE)
4627 // {
4628 // // we are in a product
4629 // // check if the parent is a plus or a minus, if so, the cancelation is done there
4630 // if (pParent != NULL)
4631 // {
4632 // CEvaluationNode::Type t = pParent->getType();
4633 //
4634 // if (CEvaluationNode::type(t) == CEvaluationNode::OPERATOR && ((((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(t)) == CEvaluationNodeOperator::MULTIPLY ||
4635 // ((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(t)) == CEvaluationNodeOperator::DIVIDE)))
4636 // {
4637 // // OK, we are done
4638 // if (childrenChanged)
4639 // {
4640 // pResult = pTmpOrig->copyNode(children);
4641 // }
4642 //
4643 // return pResult;
4644 // }
4645 // }
4646 //
4647 // // if the children of the node have changed, we have to work with the changed version
4648 // if (childrenChanged == true)
4649 // {
4650 // pResult = pTmpOrig->copyNode(children);
4651 // pTmpOrig = pResult;
4652 // }
4653 //
4654 // std::vector<const CEvaluationNode*> multiplications, divisions;
4655 // CNormalTranslation::splitProduct(pTmpOrig, multiplications, divisions, false);
4656 // // collect all nodes in multiplications and divisions
4657 //
4658 // // find identical nodes in multiplications and divisions
4659 // // The first entry in the pair is the collected power exponent
4660 // // the second entry is the original power base
4661 // // make sure the collected factor is again simplified
4662 // std::vector<product_match> collected = CNormalTranslation::matchPowerBases(multiplications, divisions);
4663 //
4664 // // decide if matches were found
4665 // // if we are working on a copy, we can go and delete those elements, that are no longer needed (e.g. all but the first entry for each match element)
4666 // // remember to delete the entries in negAdditions and negSubtractions
4667 // if (collected.size() != (multiplications.size() + divisions.size()))
4668 // {
4669 // if (pResult != NULL)
4670 // {
4671 // delete pResult;
4672 // pResult = NULL;
4673 // }
4674 //
4675 // multiplications.clear();
4676 // divisions.clear();
4677 // std::vector<CEvaluationNode*> numeratorChain;
4678 // std::vector<CEvaluationNode*> denominatorChain;
4679 // unsigned int iMax = collected.size();
4680 //
4681 // for (unsigned int i = 0; i < iMax; ++i)
4682 // {
4683 // product_match& match = collected[i];
4684 //
4685 // // the matches we get back either have the factor set if it is a pure number,
4686 // // ot they have the pExponentNode set if it can't be represented as a pure number
4687 // // if simplified node is a 0.0, we ignore this node
4688 // if (match.pExponentNode == NULL)
4689 // {
4690 // if (fabs(match.factor) < ZERO)
4691 // {
4692 // delete match.pNode;
4693 // match.pNode = NULL;
4694 // }
4695 // else if (match.factor > 0.0)
4696 // {
4697 // if (fabs(match.factor - 1.0) < ZERO)
4698 // {
4699 // numeratorChain.push_back(match.pNode);
4700 // }
4701 // else
4702 // {
4703 // os.str("");
4704 // os.precision(18);
4705 // os << match.factor;
4706 // CEvaluationNode* pPower = new CEvaluationNodeOperator(CEvaluationNodeOperator::POWER, "^");
4707 // pPower->addChild(match.pNode);
4708 // pPower->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str()));
4709 // numeratorChain.push_back(pPower);
4710 // }
4711 // }
4712 // else
4713 // {
4714 // if (fabs(match.factor + 1.0) < ZERO)
4715 // {
4716 // denominatorChain.push_back(match.pNode);
4717 // }
4718 // else
4719 // {
4720 // CEvaluationNode* pPower = new CEvaluationNodeOperator(CEvaluationNodeOperator::POWER, "^");
4721 // pPower->addChild(match.pNode);
4722 // os.str("");
4723 // os.precision(18);
4724 // os << fabs(match.factor);
4725 // pPower->addChild(new CEvaluationNodeNumber(CEvaluationNodeNumber::DOUBLE, os.str().c_str()));
4726 // denominatorChain.push_back(pPower);
4727 // }
4728 // }
4729 // }
4730 // else
4731 // {
4732 // // since the pExponentNode is not NULL, we can ignore the factor attribute
4733 // // because it has already been added to the pExponentNode
4734 // //
4735 // // since the exponent can't be represented as a number, we probably don't now if the
4736 // // exponent should be added to divisions or multiplications, so we just add all of them
4737 // // to the numerator
4738 // CEvaluationNode* pPower = new CEvaluationNodeOperator(CEvaluationNodeOperator::POWER, "^");
4739 // pPower->addChild(match.pNode);
4740 // pPower->addChild(match.pExponentNode);
4741 // numeratorChain.push_back(pPower);
4742 // }
4743 // }
4744 //
4745 // // if there are only divisions, we have an empty numerator chain
4746 // if (numeratorChain.empty())
4747 // {
4748 // pResult = CNormalTranslation::ONE_NODE.copyBranch();
4749 // }
4750 // else
4751 // {
4752 // pResult = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, numeratorChain);
4753 // assert(pResult != NULL);
4754 // }
4755 //
4756 // if (!denominatorChain.empty())
4757 // {
4758 // CEvaluationNode* pTmpNode = new CEvaluationNodeOperator(CEvaluationNodeOperator::DIVIDE, "/");
4759 // pTmpNode->addChild(pResult);
4760 // pResult = pTmpNode;
4761 // pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, denominatorChain);
4762 // assert(pTmpNode != NULL);
4763 // pResult->addChild(pTmpNode);
4764 // }
4765 // }
4766 // else
4767 // {
4768 // std::vector<product_match>::iterator it2 = collected.begin(), endit2 = collected.end();
4769 //
4770 // while (it2 != endit2)
4771 // {
4772 // if ((*it2).pNode != NULL)
4773 // {
4774 // delete(*it2).pNode;
4775 //
4776 // if ((*it2).pExponentNode != NULL)
4777 // {
4778 // delete(*it2).pExponentNode;
4779 // }
4780 // }
4781 //
4782 // ++it2;
4783 // }
4784 //
4785 // // pResult is already set above
4786 // }
4787 // }
4788 // }
4789 //
4790 // if (pResult == NULL && childrenChanged == true)
4791 // {
4792 // pResult = pTmpOrig->copyNode(children);
4793 // }
4794 //
4795 //// if(pResult != NULL)
4796 //// {
4797 //// std::cout << "Canceled: " << pResult->buildInfix() << std::endl;
4798 //// }
4799 //// else
4800 //// {
4801 //// std::cout << "Nothing Canceled." << std::endl;
4802 //// }
4803 // return pResult;
4804 //}
4805 
4806 
4807 
4808 
4809 
4810 
4811 /**
4812  * This method does all the canceling on a given node and its children.
4813  CEvaluationNode* CNormalTranslation::cancel(const CEvaluationNode* pOrig)
4814  {
4815  // TODO I think this method has much potential for improvement
4816  // TODO since the comparison code seems to spend about 85% of the time
4817  // TODO here, this is where I should start making optimizations
4818  //
4819  // try to find multiplication chains where something is divided by itself
4820  // or multiplied by -1 times itself
4821  // also consider powers (it's the bases that have to match)
4822  //
4823  // try to find addition changes where there is a subtraction of two
4824  // identical nodes or an addition of one node and the same node times -1
4825  CEvaluationNode* pResult = NULL;
4826  std::vector<CEvaluationNode*> children;
4827  //std::cout << "Canceling: " << pOrig->buildInfix() << std::endl;
4828 
4829  if (CEvaluationNode::type(pOrig->getType()) == CEvaluationNode::OPERATOR)
4830  {
4831  if (((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pOrig->getType())) == CEvaluationNodeOperator::PLUS ||
4832  ((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pOrig->getType())) == CEvaluationNodeOperator::MINUS)
4833  {
4834  // we are in a sum
4835  std::vector<CEvaluationNode*> additions, subtractions;
4836  CNormalTranslation::splitSum(pOrig, additions, subtractions, false);
4837  CNormalTranslation::swapNegativeNumbers(additions, subtractions);
4838  // collect all nodes in additions and subtractions
4839  unsigned int i, iMax = additions.size();
4840 
4841  for (i = 0; i < iMax; ++i)
4842  {
4843  CEvaluationNode* pChild = CNormalTranslation::cancel(additions[i]);
4844  delete additions[i];
4845  additions[i] = pChild;
4846  }
4847 
4848  iMax = subtractions.size();
4849 
4850  for (i = 0; i < iMax; ++i)
4851  {
4852  CEvaluationNode* pChild = CNormalTranslation::cancel(subtractions[i]);
4853  delete subtractions[i];
4854  subtractions[i] = pChild;
4855  }
4856 
4857  // find identical nodes in additions and subtractions
4858  // The first entry in the pair is the collected factor
4859  // the second entry is the original branch
4860  // make sure the collected factor is again simplified
4861  std::vector<std::pair<CEvaluationNode*, CEvaluationNode*> > collected = CNormalTranslation::matchSummands(additions, subtractions);
4862  iMax = additions.size();
4863 
4864  for (i = 0; i < iMax; ++i)
4865  {
4866  delete additions[i];
4867  }
4868 
4869  additions.clear();
4870  iMax = subtractions.size();
4871 
4872  for (i = 0; i < iMax; ++i)
4873  {
4874  delete subtractions[i];
4875  }
4876 
4877  subtractions.clear();
4878  std::vector<CEvaluationNode*> chain;
4879  iMax = collected.size();
4880 
4881  for (i = 0; i < iMax; ++i)
4882  {
4883  std::pair<CEvaluationNode*, CEvaluationNode*> pair = collected[i];
4884 
4885  //CEvaluationNode* pTmpNode = CNormalTranslation::eliminate(pair.first);
4886  //delete pair.first;
4887  // if simplified node is 0.0, we ignore this node
4888  if (CEvaluationNode::type(pair.first->getType()) == CEvaluationNode::NUMBER &&
4889  fabs(dynamic_cast<CEvaluationNodeNumber*>(pair.first)->getValue()) < ZERO)
4890  {
4891  delete pair.first;
4892  delete pair.second;
4893  }
4894  else if (CEvaluationNode::type(pair.first->getType()) == CEvaluationNode::NUMBER &&
4895  fabs(dynamic_cast<CEvaluationNodeNumber*>(pair.first)->getValue() - 1.0) < ZERO)
4896  {
4897  delete pair.first;
4898  chain.push_back(pair.second);
4899  }
4900  else
4901  {
4902  CEvaluationNode* pMult = new CEvaluationNodeOperator(CEvaluationNodeOperator::MULTIPLY, "*");
4903  pMult->addChild(pair.first);
4904  pMult->addChild(pair.second);
4905  chain.push_back(pMult);
4906  }
4907  }
4908 
4909  pResult = CNormalTranslation::createChain(&CNormalTranslation::PLUS_NODE, &CNormalTranslation::ZERO_NODE, chain);
4910  assert(pResult != NULL);
4911  }
4912  else if (((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pOrig->getType())) == CEvaluationNodeOperator::MULTIPLY ||
4913  ((CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pOrig->getType())) == CEvaluationNodeOperator::DIVIDE)
4914  {
4915  // we are in a product
4916  std::vector<const CEvaluationNode*> multiplications, divisions;
4917  CNormalTranslation::splitProduct(pOrig, multiplications, divisions, false);
4918  // collect all nodes in multiplications and divisions
4919  unsigned int i, iMax = multiplications.size();
4920 
4921  for (i = 0; i < iMax; ++i)
4922  {
4923  multiplications[i] = CNormalTranslation::cancel(multiplications[i]);
4924  }
4925 
4926  iMax = divisions.size();
4927 
4928  for (i = 0; i < iMax; ++i)
4929  {
4930  divisions[i] = CNormalTranslation::cancel(divisions[i]);
4931  }
4932 
4933  // find identical nodes in multiplications and divisions
4934  // The first entry in the pair is the collected power exponent
4935  // the second entry is the original power base
4936  // make sure the collected factor is again simplified
4937  std::vector<std::pair<CEvaluationNode*, CEvaluationNode*> > collected = CNormalTranslation::matchPowerBases(multiplications, divisions);
4938  iMax = multiplications.size();
4939 
4940  for (i = 0; i < iMax; ++i)
4941  {
4942  delete multiplications[i];
4943  }
4944 
4945  multiplications.clear();
4946  iMax = divisions.size();
4947 
4948  for (i = 0; i < iMax; ++i)
4949  {
4950  delete divisions[i];
4951  }
4952 
4953  divisions.clear();
4954  std::vector<CEvaluationNode*> numeratorChain;
4955  std::vector<CEvaluationNode*> denominatorChain;
4956  iMax = collected.size();
4957 
4958  for (i = 0; i < iMax; ++i)
4959  {
4960  std::pair<CEvaluationNode*, CEvaluationNode*> pair = collected[i];
4961 
4962  //CEvaluationNode* pTmpNode = CNormalTranslation::eliminate(pair.first);
4963  //delete pair.first;
4964  // if simplified node is a 0.0, we ignore this node
4965  if (CEvaluationNode::type(pair.first->getType()) == CEvaluationNode::NUMBER)
4966  {
4967  if (fabs(dynamic_cast<CEvaluationNodeNumber*>(pair.first)->getValue()) < ZERO)
4968  {
4969  delete pair.first;
4970  delete pair.second;
4971  }
4972  else if (dynamic_cast<CEvaluationNodeNumber*>(pair.first)->getValue() > 0.0)
4973  {
4974  if (fabs(dynamic_cast<CEvaluationNodeNumber*>(pair.first)->getValue() - 1.0) < ZERO)
4975  {
4976  delete pair.first;
4977  numeratorChain.push_back(pair.second);
4978  }
4979  else
4980  {
4981  CEvaluationNode* pPower = new CEvaluationNodeOperator(CEvaluationNodeOperator::POWER, "^");
4982  pPower->addChild(pair.second);
4983  pPower->addChild(pair.first);
4984  numeratorChain.push_back(pPower);
4985  }
4986  }
4987  else
4988  {
4989  if (fabs(dynamic_cast<CEvaluationNodeNumber*>(pair.first)->getValue() + 1.0) < ZERO)
4990  {
4991  delete pair.first;
4992  denominatorChain.push_back(pair.second);
4993  }
4994  else
4995  {
4996  CEvaluationNode* pPower = new CEvaluationNodeOperator(CEvaluationNodeOperator::POWER, "^");
4997  pPower->addChild(pair.second);
4998  std::ostringstream os;
4999  os.precision(18);
5000  os << fabs(dynamic_cast<const CEvaluationNodeNumber*>(pair.first)->getValue());
5001  pPower->addChild(new CEvaluationNodeNumber((CEvaluationNodeNumber::SubType)CEvaluationNode::subType(pair.first->getType()), os.str().c_str()));
5002  delete pair.first;
5003  denominatorChain.push_back(pPower);
5004  }
5005  }
5006  }
5007  else
5008  {
5009  CEvaluationNode* pPower = new CEvaluationNodeOperator(CEvaluationNodeOperator::POWER, "^");
5010 
5011  // check if the node is -1.0 * SOMETHING
5012  if (CEvaluationNode::type(pair.first->getType()) == CEvaluationNode::OPERATOR && (CEvaluationNodeOperator::SubType)CEvaluationNode::subType(pair.first->getType()) == CEvaluationNodeOperator::MULTIPLY
5013  && CEvaluationNode::type(dynamic_cast<const CEvaluationNode*>(pair.first->getChild())->getType()) == CEvaluationNode::NUMBER)
5014  {
5015  if (fabs(static_cast<const CEvaluationNodeNumber*>(pair.first->getChild())->getValue() + 1.0) < ZERO)
5016  {
5017  pPower->addChild(pair.second);
5018  pPower->addChild(dynamic_cast<const CEvaluationNode*>(pair.first->getChild()->getSibling())->copyBranch());
5019  delete pair.first;
5020  denominatorChain.push_back(pPower);
5021  }
5022  else if (fabs(static_cast<const CEvaluationNodeNumber*>(pair.first->getChild())->getValue()) < ZERO)
5023  {
5024  // delete the power node and add
5025  delete pPower;
5026  delete pair.first;
5027  numeratorChain.push_back(pair.second);
5028  }
5029  else if (static_cast<const CEvaluationNodeNumber*>(pair.first->getChild())->getValue() < 0.0)
5030  {
5031  pPower->addChild(pair.second);
5032  pPower->addChild(pair.first);
5033  denominatorChain.push_back(pPower);
5034  }
5035  else
5036  {
5037  pPower->addChild(pair.second);
5038  pPower->addChild(pair.first);
5039  numeratorChain.push_back(pPower);
5040  }
5041  }
5042  else
5043  {
5044  pPower->addChild(pair.second);
5045  pPower->addChild(pair.first);
5046  numeratorChain.push_back(pPower);
5047  }
5048  }
5049  }
5050 
5051  // if there are only divisions, we have an empty numerator chain
5052  if (numeratorChain.empty())
5053  {
5054  pResult = CNormalTranslation::ONE_NODE.copyBranch();
5055  }
5056  else
5057  {
5058  pResult = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, numeratorChain);
5059  assert(pResult != NULL);
5060  }
5061 
5062  if (!denominatorChain.empty())
5063  {
5064  CEvaluationNode* pTmpNode = new CEvaluationNodeOperator(CEvaluationNodeOperator::DIVIDE, "/");
5065  pTmpNode->addChild(pResult);
5066  pResult = pTmpNode;
5067  pTmpNode = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, denominatorChain);
5068  assert(pTmpNode != NULL);
5069  pResult->addChild(pTmpNode);
5070  }
5071  }
5072  else
5073  {
5074  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pOrig->getChild());
5075 
5076  while (pChild != NULL)
5077  {
5078  children.push_back(CNormalTranslation::cancel(pChild));
5079  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
5080  }
5081 
5082  assert(children.size() == 2);
5083  }
5084  }
5085  else
5086  {
5087  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pOrig->getChild());
5088 
5089  while (pChild != NULL)
5090  {
5091  children.push_back(CNormalTranslation::cancel(pChild));
5092  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
5093  }
5094  }
5095 
5096  if (pResult == NULL)
5097  {
5098  pResult = pOrig->copyNode(children);
5099  }
5100 
5101 // if(pOrig->buildInfix() == pResult->buildInfix())
5102 // {
5103 // std::cout << "Nothing Canceled." << std::endl;
5104 // }
5105 // else
5106 // {
5107 // std::cout << "Canceled: " << pResult->buildInfix() << std::endl;
5108 // }
5109  return pResult;
5110  }
5111  */
5112 
5113 
5114 
5115 /**
5116  * This method eliminates directly nested fractions.
5117  * A/B/C -> A/(B*C)
5118  *
5119  * The caller is responsible for deleting the returned object.
5120  */
5122 {
5123  if (pOrig == NULL) return NULL;
5124 
5125  CEvaluationNode* pResult = NULL;
5126  std::vector<CEvaluationNode*> children;
5127  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pOrig->getChild());
5128  CEvaluationNode* pNewChild = NULL;
5129  const CEvaluationNode* pTmpOrig = pOrig;
5130  bool childrenChanged = false;
5131 
5132  while (pChild != NULL)
5133  {
5135 
5136  if (pNewChild != NULL)
5137  {
5138  childrenChanged = true;
5139  }
5140 
5141  children.push_back(pNewChild);
5142  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
5143  }
5144 
5145  if (childrenChanged == true)
5146  {
5147  std::vector<CEvaluationNode*>::iterator it = children.begin(), endit = children.end();
5148  pChild = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
5149 
5150  while (it != endit)
5151  {
5152  if ((*it) == NULL)
5153  {
5154  (*it) = pChild->copyBranch();
5155  }
5156 
5157  pChild = static_cast<const CEvaluationNode*>(pChild->getSibling());
5158  ++it;
5159  }
5160 
5161  assert(pChild == NULL);
5162  // make a copy of the original with the new children
5163  pResult = pTmpOrig->copyNode(children);
5164  pTmpOrig = pResult;
5165  }
5166 
5167 
5169  {
5170  // check if one of the children (or both) are a division
5171  const CEvaluationNode* pChild1 = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
5172  assert(pChild1 != NULL);
5173  const CEvaluationNode* pChild2 = dynamic_cast<const CEvaluationNode*>(pChild1->getSibling());
5174  assert(pChild2 != NULL);
5175  assert(pChild2->getSibling() == NULL);
5176 
5178  {
5180  {
5181  // both children are division
5184  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pChild1->getChild())->copyBranch());
5185  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pChild2->getChild()->getSibling())->copyBranch());
5186  pTmpResult->addChild(pTmp);
5188  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pChild1->getChild()->getSibling())->copyBranch());
5189  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pChild2->getChild())->copyBranch());
5190  pTmpResult->addChild(pTmp);
5191 
5192  if (pResult != NULL)
5193  {
5194  delete pResult;
5195  }
5196 
5197  pResult = pTmpResult;
5198  }
5199  else
5200  {
5201  // only the first child is a division
5203  pTmpResult->addChild(dynamic_cast<const CEvaluationNode*>(pChild1->getChild())->copyBranch());
5205  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pChild1->getChild()->getSibling())->copyBranch());
5206 
5207  if (pResult == NULL)
5208  {
5209  pTmp->addChild(pChild2->copyBranch());
5210  }
5211  else
5212  {
5213  assert(pResult == pTmpOrig);
5214  pResult->removeChild(const_cast<CEvaluationNode*>(pChild2));
5215  pTmp->addChild(const_cast<CEvaluationNode*>(pChild2));
5216  delete pResult;
5217  }
5218 
5219  pTmpResult->addChild(pTmp);
5220  pResult = pTmpResult;
5221  }
5222  }
5224  {
5225  // only the second child is a division
5228 
5229  if (pResult != NULL)
5230  {
5231  assert(pTmpOrig == pResult);
5232  pResult->removeChild(const_cast<CEvaluationNode*>(pChild1));
5233  pTmp->addChild(const_cast<CEvaluationNode*>(pChild1));
5234  }
5235  else
5236  {
5237  pTmp->addChild(pChild1->copyBranch());
5238  }
5239 
5240  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pChild2->getChild()->getSibling())->copyBranch());
5241  pTmpResult->addChild(pTmp);
5242  pTmpResult->addChild(dynamic_cast<const CEvaluationNode*>(pChild2->getChild())->copyBranch());
5243 
5244  if (pResult != NULL)
5245  {
5246  delete pResult;
5247  }
5248 
5249  pResult = pTmpResult;
5250  }
5251  }
5252 
5253  return pResult;
5254 }
5255 
5256 
5257 /**
5258  * This method replaces a power of a fraction by the fraction of two power nodes.
5259  * (A/B)^x -> A^x / B^x
5260  *
5261  * The caller is responsible for deleting the returned object.
5262  */
5264 {
5265  if (pOrig == NULL) return NULL;
5266 
5267  CEvaluationNode* pResult = NULL;
5268 
5269  std::vector<CEvaluationNode*> children;
5270  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pOrig->getChild());
5271  CEvaluationNode* pNewChild = NULL;
5272  const CEvaluationNode* pTmpOrig = pOrig;
5273  bool childrenChanged = false;
5274 
5275  while (pChild != NULL)
5276  {
5278 
5279  if (pNewChild != NULL)
5280  {
5281  childrenChanged = true;
5282  }
5283 
5284  children.push_back(pNewChild);
5285  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
5286  }
5287 
5288  if (childrenChanged == true)
5289  {
5290  pChild = dynamic_cast<const CEvaluationNode*>(pTmpOrig->getChild());
5291  std::vector<CEvaluationNode*>::iterator it = children.begin(), endit = children.end();
5292 
5293  while (it != endit)
5294  {
5295  if ((*it) == NULL)
5296  {
5297  (*it) = pChild->copyBranch();
5298  }
5299 
5300  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
5301  ++it;
5302  }
5303 
5304  assert(pChild == NULL);
5305  pResult = pTmpOrig->copyNode(children);
5306  pTmpOrig = pResult;
5307  }
5308 
5310  {
5311  const CEvaluationNode* pChild1 = static_cast<const CEvaluationNode*>(pTmpOrig->getChild());
5312  assert(pChild1 != NULL);
5313  const CEvaluationNode* pChild2 = static_cast<const CEvaluationNode*>(pChild1->getSibling());
5314  assert(pChild2 != NULL);
5315  assert(pChild2->getSibling() == NULL);
5316 
5318  {
5319  // the first child is a division
5320 
5323  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pChild1->getChild())->copyBranch());
5324  pTmp->addChild(pChild2->copyBranch());
5325  pTmpResult->addChild(pTmp);
5327  pTmp->addChild(dynamic_cast<const CEvaluationNode*>(pChild1->getChild()->getSibling())->copyBranch());
5328 
5329  if (pResult == NULL)
5330  {
5331  pTmp->addChild(pChild2->copyBranch());
5332  }
5333  else
5334  {
5335  // since pResult is a new object, we can safely modify it
5336  pResult->removeChild(const_cast<CEvaluationNode*>(pChild2));
5337  pTmp->addChild(const_cast<CEvaluationNode*>(pChild2));
5338  delete pResult;
5339  }
5340 
5341  pTmpResult->addChild(pTmp);
5342  pResult = pTmpResult;
5343  }
5344  }
5345 
5346  return pResult;
5347 }
5348 
5349 
5350 /**
5351  * This methods converts a product of fractions into a fraction of products.
5352  * (A/C) * (B/D) -> (A*B)/(C*D)
5353  *
5354  * The caller is responsible for deleting the returned object.
5355  */
5357 {
5358  CEvaluationNode* pResult = NULL;
5359  std::vector<CEvaluationNode*> children;
5360  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pOrig->getChild());
5361 
5362  while (pChild != NULL)
5363  {
5364  children.push_back(CNormalTranslation::product2fraction(pChild));
5365  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
5366  }
5367 
5369  {
5370  CEvaluationNode* pNumerator1 = NULL;
5371  CEvaluationNode* pNumerator2 = NULL;
5372  CEvaluationNode* pDenominator1 = NULL;
5373  CEvaluationNode* pDenominator2 = NULL;
5374  assert(children.size() == 2);
5375 
5377  {
5378  pNumerator1 = dynamic_cast<CEvaluationNode*>(children[0]->getChild());
5379  pDenominator1 = dynamic_cast<CEvaluationNode*>(children[0]->getChild()->getSibling());
5380  }
5381  else
5382  {
5383  pNumerator1 = children[0];
5384  }
5385 
5387  {
5388  pNumerator2 = dynamic_cast<CEvaluationNode*>(children[1]->getChild());
5389  pDenominator2 = dynamic_cast<CEvaluationNode*>(children[1]->getChild()->getSibling());
5390  }
5391  else
5392  {
5393  pNumerator2 = children[1];
5394  }
5395 
5396  if (pDenominator1 || pDenominator2)
5397  {
5400  pTmpNode->addChild(pNumerator1->copyBranch());
5401  pTmpNode->addChild(pNumerator2->copyBranch());
5402  pResult->addChild(pTmpNode);
5403 
5404  if (pDenominator1 && pDenominator2)
5405  {
5407  pTmpNode->addChild(pDenominator1->copyBranch());
5408  pTmpNode->addChild(pDenominator2->copyBranch());
5409  pResult->addChild(pTmpNode);
5410  }
5411  else if (pDenominator1)
5412  {
5413  pResult->addChild(pDenominator1->copyBranch());
5414  }
5415  else
5416  {
5417  pResult->addChild(pDenominator2->copyBranch());
5418  }
5419 
5420  delete children[0];
5421  delete children[1];
5422  }
5423  else
5424  {
5425  pResult = pOrig->copyNode(children);
5426  }
5427  }
5428  else
5429  {
5430  pResult = pOrig->copyNode(children);
5431  }
5432 
5433  return pResult;
5434 }
5435 
5436 /**
5437  * Given a root node, this method traverses the tree and expands produtcs in
5438  * power bases to multiplications of power items.
5439  *
5440  * (A*B)^x -> A^x * B^x
5441  *
5442  * It is the responsibility of the caller to delete the returned node if it is not NULL.
5443  */
5445 {
5446  CEvaluationNode* pResult = NULL;
5447  std::vector<CEvaluationNode*> children;
5448 
5449  const CEvaluationNode* pChild = dynamic_cast<const CEvaluationNode*>(pRoot->getChild());
5450  CEvaluationNode* pNewChild = NULL;
5451  bool childrenChanged = false;
5452 
5453  while (pChild != NULL)
5454  {
5455  pNewChild = CNormalTranslation::expandPowerBases(pChild);
5456 
5457  if (pNewChild != NULL)
5458  {
5459  childrenChanged = true;
5460  }
5461 
5462  children.push_back(pNewChild);
5463  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
5464  }
5465 
5466  if (childrenChanged == true)
5467  {
5468  std::vector<CEvaluationNode*>::iterator it = children.begin(), endit = children.end();
5469  pChild = dynamic_cast<const CEvaluationNode*>(pRoot->getChild());
5470 
5471  while (it != endit)
5472  {
5473  if ((*it) == NULL)
5474  {
5475  (*it) = pChild->copyBranch();
5476  }
5477 
5478  pChild = dynamic_cast<const CEvaluationNode*>(pChild->getSibling());
5479  ++it;
5480  }
5481 
5482  assert(pChild == NULL);
5483  }
5484 
5485  pResult = pRoot->copyNode(children);
5486  pRoot = pResult;
5487 
5488 
5489  CEvaluationNode::Type type = pRoot->getType();
5490 
5492  {
5493  const CEvaluationNode* pBase = dynamic_cast<const CEvaluationNode*>(pRoot->getChild());
5494  assert(pBase != NULL);
5495  const CEvaluationNode* pExp = dynamic_cast<const CEvaluationNode*>(pBase->getSibling());
5496  assert(pExp != NULL);
5497  type = pBase->getType();
5498 
5500  {
5501  std::vector<const CEvaluationNode*> multiplications, divisions;
5502  std::vector<CEvaluationNode*> numeratorNodes, denominatorNodes;
5503  CNormalTranslation::splitProduct(pBase, multiplications, divisions, false);
5504 
5505  std::vector<const CEvaluationNode*>::const_iterator it = multiplications.begin(), endit = multiplications.end();
5506  CEvaluationNode* pPower = NULL;
5507 
5508  while (it != endit)
5509  {
5511 
5512  if (pResult == NULL)
5513  {
5514  pPower->addChild((*it)->copyBranch());
5515  }
5516  else
5517  {
5518  // since pResult is a new node and not the original,
5519  // we can safely modify it instead of copying a whole branch
5520  if ((*it)->getParent() != NULL)
5521  {
5522  const_cast<CEvaluationNode*>((*it))->getParent()->removeChild(const_cast<CEvaluationNode*>(*it));
5523  }
5524 
5525  pPower->addChild(const_cast<CEvaluationNode*>(*it));
5526  }
5527 
5528  pPower->addChild(pExp->copyBranch());
5529  numeratorNodes.push_back(pPower);
5530  ++it;
5531  }
5532 
5533  CEvaluationNode* pTmp = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, numeratorNodes);
5534  assert(pTmp != NULL);
5535 
5536  if (!divisions.empty())
5537  {
5538  it = divisions.begin(), endit = divisions.end();
5539 
5540  while (it != endit)
5541  {
5543 
5544  if (pResult == NULL)
5545  {
5546  pPower->addChild((*it)->copyBranch());
5547  }
5548  else
5549  {
5550  // since pResult is a new node and not the original,
5551  // we can safely modify it instead of copying a whole branch
5552  if ((*it)->getParent() != NULL)
5553  {
5554  const_cast<CEvaluationNode*>((*it))->getParent()->removeChild(const_cast<CEvaluationNode*>(*it));
5555  }
5556 
5557  pPower->addChild(const_cast<CEvaluationNode*>(*it));
5558  }
5559 
5560  pPower->addChild(pExp->copyBranch());
5561  denominatorNodes.push_back(pPower);
5562  ++it;
5563  }
5564 
5566  pTmpResult->addChild(pTmp);
5567  pTmp = CNormalTranslation::createChain(&CNormalTranslation::TIMES_NODE, &CNormalTranslation::ONE_NODE, denominatorNodes);
5568  assert(pTmp != NULL);
5569  pTmpResult->addChild(pTmp);
5570  pTmp = pTmpResult;
5571  }
5572 
5573  if (pResult != NULL)
5574  {
5575  delete pResult;
5576  }
5577 
5578  pResult = pTmp;
5579  }
5581  {
5582  std::vector<CEvaluationNode*> additions, subtractions;
5583  CNormalTranslation::splitSum(pBase, additions, subtractions, false);
5584  CNormalTranslation::swapNegativeNumbers(additions, subtractions);
5585  std::pair<CEvaluationNode*, CEvaluationNode*> resultPair = CNormalTranslation::factorize(additions, subtractions);
5586  unsigned int i, iMax = additions.size();
5587 
5588  for (i = 0; i < iMax; ++i)
5589  {
5590  delete additions[i];
5591  }
5592 
5593  additions.clear();
5594  iMax = subtractions.size();
5595 
5596  for (i = 0; i < iMax; ++i)
5597  {
5598  delete subtractions[i];
5599  }
5600 
5601  subtractions.clear();
5602 
5603  if (resultPair.first != NULL)
5604  {
5607  pTmpNode->addChild(resultPair.first);
5608  pTmpNode->addChild(pExp->copyBranch());
5609  pTmp->addChild(pTmpNode);
5611  pTmpNode->addChild(resultPair.second);
5612  pTmpNode->addChild(pExp->copyBranch());
5613  pTmp->addChild(pTmpNode);
5614 
5615  if (pResult != NULL)
5616  {
5617  delete pResult;
5618  }
5619 
5620  pResult = pTmp;
5621  }
5622  }
5623  }
5624 
5625  return pResult;
5626 }
5627 
5628 /**
5629  * This method takes two vectors and checks if the elements in the two vectors
5630  * can be split into multiplications and divisions and if there a common factors in all resulting subgroups.
5631  */
5632 std::pair<CEvaluationNode*, CEvaluationNode*> CNormalTranslation::factorize(const std::vector<CEvaluationNode*>& additions, const std::vector<CEvaluationNode*>& subtractions)
5633 {
5634  std::vector<const CEvaluationNode*> commonMultiplications;
5635  std::vector<const CEvaluationNode*> commonDivisions;
5636  // additions must have at least one entry
5637  assert(additions.size() > 0);
5638  // get all multipllications and divisions from the first entry in additions
5639  std::vector<const CEvaluationNode*> multiplications, divisions;
5640  unsigned int i, iMax = additions.size();
5641  unsigned int iiMax = iMax + subtractions.size();
5642  std::vector<std::vector<const CEvaluationNode*> > multiplicationVectors, divisionVectors;
5643 
5644  for (i = 0; i < iiMax; ++i)
5645  {
5646  const CEvaluationNode* pTmpNode = (i < iMax) ? additions[i] : subtractions[i - iMax];
5647  CEvaluationNode::Type type = pTmpNode->getType();
5648 
5650  {
5652 
5654  {
5655  CNormalTranslation::splitProduct(pTmpNode, multiplications, divisions, false);
5656  }
5657  else
5658  {
5659  multiplications.push_back(pTmpNode);
5660  }
5661  }
5662  else
5663  {
5664  multiplications.push_back(pTmpNode);
5665  }
5666 
5667  multiplicationVectors.push_back(multiplications);
5668  divisionVectors.push_back(divisions);
5669  multiplications.clear();
5670  divisions.clear();
5671  }
5672 
5673  // now we first search for common multiplications
5674  multiplications = multiplicationVectors[0];
5675  std::vector<const CEvaluationNode*>::const_iterator it = multiplications.begin(), endit = multiplications.end();
5676 
5677  while (it != endit)
5678  {
5679  bool everywhere = true;
5680  std::vector<std::vector<const CEvaluationNode*> >::iterator innerIt = multiplicationVectors.begin(), innerEndit = multiplicationVectors.end();
5681  // we can leave out the first one since the item comes from there anyway,
5682  // so we know it is in that vector
5683  std::string infix = (*it)->buildInfix();
5684  ++innerIt;
5685 
5686  while (innerIt != innerEndit)
5687  {
5688  bool found = false;
5689  std::vector<const CEvaluationNode*>::iterator innerIt2 = (*innerIt).begin(), innerEndit2 = (*innerIt).end();
5690 
5691  while (innerIt2 != innerEndit2)
5692  {
5693  if ((*innerIt2)->buildInfix() == infix)
5694  {
5695  found = true;
5696  break;
5697  }
5698 
5699  ++innerIt2;
5700  }
5701 
5702  if (!found)
5703  {
5704  everywhere = false;
5705  break;
5706  }
5707 
5708  ++innerIt;
5709  }
5710 
5711  // if the item was found as a factor in all other additions and
5712  // subtractions, we know it is a common factor, we add it to the
5713  // commonFactors and update the additions and subtractions
5714  if (everywhere)
5715  {
5716  commonMultiplications.push_back(*it);
5717  std::vector<std::vector<const CEvaluationNode*> >::iterator innerIt = multiplicationVectors.begin();
5718  std::vector<std::vector<const CEvaluationNode*> >::iterator innerEndit = multiplicationVectors.end();
5719 
5720  while (innerIt != innerEndit)
5721  {
5722  std::vector<const CEvaluationNode*>::iterator innerIt2 = (*innerIt).begin();
5723  std::vector<const CEvaluationNode*>::iterator innerEndit2 = (*innerIt).end();
5724 
5725  while (innerIt2 != innerEndit2)
5726  {
5727  if ((*innerIt2)->buildInfix() == infix)
5728  {
5729  innerIt->erase(innerIt2);
5730  break;
5731  }
5732 
5733  ++innerIt2;
5734  }
5735 
5736  ++innerIt;
5737  }
5738  }
5739 
5740  ++it;
5741  }
5742 
5743  // now we search for common divisions
5744  divisions = divisionVectors[0];
5745 
5746  if (!divisions.empty())
5747  {
5748  it = divisions.begin(), endit = divisions.end();
5749 
5750  while (it != endit)
5751  {
5752  bool everywhere = true;
5753  std::vector<std::vector<const CEvaluationNode*> >::iterator innerIt = divisionVectors.begin(), innerEndit = divisionVectors.end();
5754  // we can leav out the first one since the item comes from there anyway,
5755  // so we know it is in that vector
5756  std::string infix = (*it)->buildInfix();
5757  ++innerIt;
5758 
5759  while (innerIt != innerEndit)
5760  {
5761  bool found = false;
5762  std::vector<const CEvaluationNode*>::iterator innerIt2 = (*innerIt).begin(), innerEndit2 = (*innerIt).end();
5763 
5764  while (innerIt2 != innerEndit2)
5765  {
5766  if ((*innerIt2)->buildInfix() == infix)
5767  {
5768  found = true;
5769  break;
5770  }
5771 
5772  ++innerIt2;
5773  }
5774 
5775  if (!found)
5776  {
5777  everywhere = false;
5778  break;
5779  }
5780 
5781  ++innerIt;
5782  }
5783 
5784  // if the item was found as a factor in all other additions and
5785  // subtractions, we know it is a common factor, we add it to the
5786  // commonFactors and update the additions and subtractions
5787  if (everywhere)
5788  {
5789  commonDivisions.push_back(*it);
5790  innerIt = divisionVectors.begin();
5791  innerEndit = divisionVectors.end();
5792 
5793  while (innerIt != innerEndit)
5794  {
5795  std::vector<const CEvaluationNode*>::iterator innerIt2 = (*innerIt).begin();
5796  std::vector<const CEvaluationNode*>::iterator innerEndit2 = (*innerIt).end();
5797 
5798  while (innerIt2 != innerEndit2)
5799  {
5800  if ((*innerIt2)->buildInfix() == infix)
5801  {
5802  innerIt->erase(innerIt2);
5803  break;
5804  }
5805 
5806  ++innerIt2;
5807  }
5808 
5809  ++innerIt;
5810  }
5811  }
5812 
5813  ++it;
5814  }
5815  }
5816 
5817  // create the two resulting nodes
5818  // first we have to create new additions and subtraction vectors which we
5819  // then combine into a subtraction
5820  // then we combine all commonMultiplications and commonDivisions into a
5821  // division
5822  // those two nodes are then returned in a pair
5823  CEvaluationNode* pFirstNode = NULL;
5824  CEvaluationNode* pSecondNode = NULL;
5825 
5826  if (!(commonMultiplications.empty() && commonDivisions.empty()))
5827  {
5828  unsigned int i, iMax = additions.size();
5829  unsigned int iiMax = iMax + subtractions.size();
5830  std::vector<CEvaluationNode*> newAddition