COPASI API  4.16.103
CNormalTranslation.h
Go to the documentation of this file.
1 // Begin CVS Header
2 // $Source: /Volumes/Home/Users/shoops/cvs/copasi_dev/copasi/compareExpressions/CNormalTranslation.h,v $
3 // $Revision: 1.25 $
4 // $Name: $
5 // $Author: gauges $
6 // $Date: 2011/03/09 14:59:46 $
7 // End CVS Header
8 
9 // Copyright (C) 2011 - 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 #ifndef COPASI_CNormalTranslation_H__
24 #define COPASI_CNormalTranslation_H__
25 
26 class CNormalFraction;
27 class CEvaluationTree;
28 
29 #include <exception>
30 #include <list>
31 
34 
35 class recursion_limit_exception : public std::exception
36 {
37 public:
39  {
42  };
43 
44  /**
45  * constructor
46  */
48 
49 protected:
51 };
52 
53 
54 struct summ_match
55 {
56 
58  factor(0.0)
59  , pNode(NULL)
60  {
61  }
62 
63  double factor;
65  std::set<unsigned int> addition_indices;
66  std::set<unsigned int> subtraction_indices;
67 };
68 
69 struct product_match : public summ_match
70 {
71 
73  summ_match()
74  , pExponentNode(NULL)
75  {
76  }
77 
79 };
80 
81 /**
82  * The class for simplification and translation of trees into CNormal
83  */
85 {
86 public:
87  static bool has_duplicate_nodes(const CEvaluationNode* pNode);
88 
89 
90  /**
91  * Simplify an evaluation tree given by the root node by creating a new simplified tree from the original one.
92  * The tree itself is actually not created!
93  * @return NodeClass*, pointer to root node of the newly created tree.
94  */
95  static CEvaluationNode* simplifyTree(const CEvaluationNode* node);
96 
97  /**
98  * Creating a simplified tree by calling simplifyTree repeatedly until it cannot be simplified further.
99  * The tree itself is actually not created!
100  * @return NodeClass*, pointer to root node of the newly created tree.
101  */
103 
104  /**
105  * Translate and simplify a tree given by the root node into CNormal structure
106  * @return CNormalFraction*
107  */
108  static CNormalFraction* normAndSimplify(const CEvaluationNode* root0);
109 
110  /**
111  * Translate and simplify a tree by calling normAndSimplify repeatedly until it cannot be simplified further
112  * The second parameter is a depth value that is used to track the
113  * recursion. If a given limit (currently 20) is reached, the algorithm throws an exception.
114  * @return CNormalFraction*
115  */
116  static CNormalFraction* normAndSimplifyReptdly(const CEvaluationTree* tree0, unsigned int depth = 0);
117 
118  /**
119  * Translate and simplify a tree by calling normAndSimplify repeatedly until it cannot be simplified further
120  * @return CNormalFraction*
121  */
122  static CNormalFraction* normAndSimplifyReptdly(const CEvaluationNode* tree0, unsigned int depth = 0);
123 
124  /**
125  * More general version of createOperatorChain.
126  * This method can also be used to combine logical item chains.
127  * Once I know this works, I will replace createOperatorChain with this
128  * method.
129  */
130  static CEvaluationNode* createChain(const CEvaluationNode* pLink, const CEvaluationNode* pNeutralElement, const std::vector<const CEvaluationNode*>& elements);
131 
132  /**
133  * More general version of createOperatorChain.
134  * This version does not copy the nodes in the given vector, but uses them
135  * directly.
136  * This method can also be used to combine logical item chains.
137  * method.
138  */
139  static CEvaluationNode* createChain(const CEvaluationNode* pLink, const CEvaluationNode* pNeutralElement, const std::vector<CEvaluationNode*>& elements);
140 
141  /**
142  * Given a vector of nodes, this method creates a multiplication chain of
143  * all the nodes. The chain contains copies of the nodes passed in.
144  */
145  static CEvaluationNode* createOperatorChain(CEvaluationNodeOperator::SubType type, const char* data, const std::vector<CEvaluationNode*>& nodes);
146 
147  /**
148  * Given a vector of nodes, this method creates a multiplication chain of
149  * all the nodes. The chain contains copies of the nodes passed in.
150  */
151  static CEvaluationNode* createOperatorChain(CEvaluationNodeOperator::SubType type, const char* data, const std::vector<const CEvaluationNode*>& nodes);
152 
153  /**
154  * Given a root node, this method traverses the tree and expands products in
155  * power bases to multiplications of power items.
156  * It is the responsibility of the caller to delete the returned node.
157  */
158  static CEvaluationNode* expandPowerBases(const CEvaluationNode* pRoot);
159 
160  /**
161  * Given a root node, this method traverses the tree and expands sums in
162  * power exponents to multiplications of power items.
163  * It is the responsibility of the caller to delete the returned node.
164  */
166 
167  /**
168  * Given a node, the method check if the node is a PLUS node, if so, it
169  * calls itself recursively on the children.
170  * This way all summands of a summation chain are gathered.
171  * All items in the vector are children of pRoot.
172  */
173  static void findSummands(const CEvaluationNode* pRoot, std::vector<const CEvaluationNode*>& summands);
174 
175  /**
176  * This method expands products. (A+B)*(C+D) -> (A*C)+(A*D)+(B*C)+(B*D)
177  * This method should be replaced by the one below pretty soon.
178  */
179  static CEvaluationNode* expandProducts(const CEvaluationNode* pOrig);
180 
181  /**
182  * This method expands products. (A+B)*(C+D) -> (A*C)+(A*D)+(B*C)+(B*D)
183  */
184  //static CEvaluationNode* expandProducts(CEvaluationNode* pOrig);
185 
186  /**
187  * This method splits a product into the individual elements
188  */
189  static void splitProduct(const CEvaluationNode* pRoot, std::vector<const CEvaluationNode*>& multiplications, std::vector<const CEvaluationNode*>& divisions, bool division);
190 
191  /**
192  * This method splits a sum into the individual elements.
193  * The returned nodes are copies of the original.
194  */
195  static void splitSum(const CEvaluationNode* pRoot, std::vector<CEvaluationNode*>& additions, std::vector<CEvaluationNode*>& substractions, bool minus);
196 
197  /**
198  * This method splits a sum into the individual elements.
199  * The returned nodes are part of the original node and not copies.
200  */
201  static void splitSum(const CEvaluationNode* pRoot, std::vector<const CEvaluationNode*>& additions, std::vector<const CEvaluationNode*>& substractions, bool minus);
202 
203  /**
204  * This method evaluates operators acting on two numbers
205  */
206  // obsolete recursive version
207  //static CEvaluationNode* evaluateNumbers(const CEvaluationNode* pOrig);
208 
209  /**
210  * This method evaluates operators acting on two numbers
211  */
212  static CEvaluationNode* newEvaluateNumbers(const CEvaluationNode* pOrig);
213 
214  /**
215  * Neutral element for an addition chain.
216  */
218 
219  /**
220  * Neutral element for a multiplication chain.
221  */
223 
224  /**
225  * Neutral element for an or chain.
226  */
228 
229  /**
230  * Neutral element for an and chain.
231  */
233 
234  /**
235  * Number node that represents 0.0
236  */
238 
239  /**
240  * Number node that represents 1.0
241  */
242  static const CEvaluationNode ONE_NODE;
243 
244  /**
245  * Operator node that represents the PLUS operation.
246  */
248 
249  /**
250  * Operator node that represents the TIMES operation.
251  */
253 
254 protected:
255  /**
256  * This routine moves all negative numbers from vector v1 to v2
257  * and changes the number to a positive number.
258  */
259  static void swapNegativeNumbers(std::vector<CEvaluationNode*>& v1, std::vector<CEvaluationNode*>& v2);
260 
261  /**
262  * This routine finds all negative numbers in vector v1
263  * and adds a copy with a positive number to v2
264  */
265  static void findNegativeNumbers(std::vector<const CEvaluationNode*>& v1, std::vector<CEvaluationNode*>& v2);
266 
267  /**
268  * This routine is responsible for recursively simplifying a given
269  * CEvaluationNode based tree.
270  */
271  static CEvaluationNode* simplify(const CEvaluationNode* pOrig);
272 
273  /**
274  * This routine is responsible for all elementary eliminations, e.g. addition
275  * of 0.
276  * These steps can not lead to new simplifications in the children of the node
277  * being simplified, so it is not necessary to run this on the children again.
278  */
280 
281  /**
282  * This method makes elementary eliminations on function nodes
283  */
284  static CEvaluationNode* elementaryEliminationFunction(const CEvaluationNode* pFunctionNode);
285 
286  /**
287  * This method makes the elementary elimination on a power node.
288  */
290 
291  /**
292  * This method makes the elementary elimination on a modulus node.
293  */
294  static CEvaluationNode* elementaryEliminationModulus(const CEvaluationNode* pModulusNode);
295 
296  /**
297  * This method makes the elementary elimination on a multiply node.
298  */
299  static CEvaluationNode* elementaryEliminationMultiply(const CEvaluationNode* pMultiplyNode);
300 
301  /**
302  * This method makes the elementary elimination on a divide node.
303  */
304  static CEvaluationNode* elementaryEliminationDivide(const CEvaluationNode* pDivideNode);
305 
306  /**
307  * This method makes the elementary elimination on a plus node.
308  */
310 
311  /**
312  * This method makes the elementary elimination on a minus node.
313  */
315 
316  /**
317  * This method removes nested power nodes, e.g. (a^b)^c -> a^(b*c)
318  */
320 
321  /**
322  * This method expands the exponents of power nodes, e.g. A^(x+y) -> A^x * A^y
323  */
324  static CEvaluationNode* expandPowerNodes(const CEvaluationNode* pOrig);
325 
326  /**
327  * The methods get a vector of multiplication elements and a vector of division
328  * elements and tries to find elements with the same power base in those two vectors.
329  */
330  //static std::vector<std::pair<CEvaluationNode*, CEvaluationNode*> > matchPowerBases(const std::vector<const CEvaluationNode*>& multiplications, const std::vector<const CEvaluationNode*>& divisions);
331  static std::vector<product_match> matchPowerBases(const std::vector<const CEvaluationNode*>& multiplications, const std::vector<const CEvaluationNode*>& divisions);
332 
333  /**
334  * The methods get a vector of addition elements and a vector of subtractions
335  * elements and tries to find equal elements in those two vectors.
336  */
337  static std::vector<std::pair<CEvaluationNode*, CEvaluationNode*> > matchSummands(const std::vector<CEvaluationNode*>& additions, const std::vector<CEvaluationNode*>& subtractions);
338  static std::vector<summ_match> matchSummands(const std::vector<const CEvaluationNode*>& additions, const std::vector<const CEvaluationNode*>& subtractions);
339 
340  /**
341  * This methods records the order of nodes in a CEvaluationNode based tree.
342  */
343  static void order(const CEvaluationNode* pRoot, std::list<const CEvaluationNode*>& orderList);
344 
345  /**
346  * Multiplies the two given nodes and returns the result.
347  */
348  static CEvaluationNode* multiply(const CEvaluationNode* pNode1, const CEvaluationNode* pNode2);
349 
350  /**
351  * This method does all the canceling on a given node and its children.
352  */
353  // obsolete recursive version
354  //static CEvaluationNode* cancel(const CEvaluationNode* pOrig);
355 
356  /**
357  * New non-recursive cancel method.
358  * This method does all the canceling on a given node and its children.
359  * If no canceling was done, NULL is returned.
360  */
361  static CEvaluationNode* newCancel(const CEvaluationNode* pOrig);
362 
363  /**
364  * This method elminates subexpressions from an expression
365  */
366  static CEvaluationNode* eliminate(const CEvaluationNode* pOrig);
367 
368  static const double ZERO;
369  static const unsigned int RECURSION_LIMIT;
370  /**
371  * This method eliminates directly nested fractions. ((a/b)/(c/d)) -> (a*d)/(b*c)
372  */
374 
375  /**
376  * This method gets rid of fractions within a power construct.
377  * (a/b)^3 -> a^3 / b^3
378  */
380 
381  /**
382  * This methods converts a product of fractions into a fraction of products.
383  */
384  static CEvaluationNode* product2fraction(const CEvaluationNode* pOrig);
385 
386  /**
387  * This method takes two vectors. One with a list of nodes that are added
388  * and one with nodes that are subtracted.
389  * It tries to find common factors and divisors in those nodes and returns
390  * two result nodes. The first is the multiplication of all common factors and
391  * divisors, the other is the sum of the remaining additions and subtractions after
392  * removing the common factors and divisors.
393  * e.g. (A*B*D+A*C*D) -> returns (A*D) and (B+C)
394  */
395  static std::pair<CEvaluationNode*, CEvaluationNode*> factorize(const std::vector<CEvaluationNode*>& additions, const std::vector<CEvaluationNode*>& subtractions);
396 
397  static void printPointers(const CEvaluationNode* pNode, const char* indent = "");
398 
399 };
400 
401 
403 {
404 protected:
406 
407 public:
408 
410 
412 
413  bool isValid() const;
414 
416 
418 
420 };
421 
422 
423 #endif // COPASI_CNormalTranslation_H__
static void splitSum(const CEvaluationNode *pRoot, std::vector< CEvaluationNode * > &additions, std::vector< CEvaluationNode * > &substractions, bool minus)
static const CEvaluationNode NEUTRAL_ELEMENT_AND
static CEvaluationNode * elementaryEliminationModulus(const CEvaluationNode *pModulusNode)
static CNormalFraction * normAndSimplifyReptdly(const CEvaluationTree *tree0, unsigned int depth=0)
recursion_limit_exception(LIMIT_TYPE type)
static bool has_duplicate_nodes(const CEvaluationNode *pNode)
static std::pair< CEvaluationNode *, CEvaluationNode * > factorize(const std::vector< CEvaluationNode * > &additions, const std::vector< CEvaluationNode * > &subtractions)
static void swapNegativeNumbers(std::vector< CEvaluationNode * > &v1, std::vector< CEvaluationNode * > &v2)
static CEvaluationNode * expandPowerBases(const CEvaluationNode *pRoot)
static CEvaluationNode * eliminateNestedPowers(const CEvaluationNode *pOrig)
CEvaluationNode * pNode
static const CEvaluationNode NEUTRAL_ELEMENT_ADD
static CEvaluationNode * simplify(const CEvaluationNode *pOrig)
static CEvaluationNode * expandPowerNodes(const CEvaluationNode *pOrig)
static CEvaluationNode * simplifyTree(const CEvaluationNode *node)
static CEvaluationNode * elementaryEliminationDivide(const CEvaluationNode *pDivideNode)
static std::vector< product_match > matchPowerBases(const std::vector< const CEvaluationNode * > &multiplications, const std::vector< const CEvaluationNode * > &divisions)
std::set< unsigned int > subtraction_indices
static void findNegativeNumbers(std::vector< const CEvaluationNode * > &v1, std::vector< CEvaluationNode * > &v2)
static const CEvaluationNode NEUTRAL_ELEMENT_MULTIPLY
static const CEvaluationNode NEUTRAL_ELEMENT_OR
static CEvaluationNode * elementaryEliminationPlus(const CEvaluationNode *pPlusNode)
static CEvaluationNode * createOperatorChain(CEvaluationNodeOperator::SubType type, const char *data, const std::vector< CEvaluationNode * > &nodes)
std::set< unsigned int > addition_indices
static void printPointers(const CEvaluationNode *pNode, const char *indent="")
static const CEvaluationNode ONE_NODE
static CNormalFraction * normAndSimplify(const CEvaluationNode *root0)
static const unsigned int RECURSION_LIMIT
static const CEvaluationNode ZERO_NODE
static CEvaluationNode * elementaryEliminationPower(const CEvaluationNode *pPowerNode)
static void splitProduct(const CEvaluationNode *pRoot, std::vector< const CEvaluationNode * > &multiplications, std::vector< const CEvaluationNode * > &divisions, bool division)
static CEvaluationNode * newEvaluateNumbers(const CEvaluationNode *pOrig)
static CEvaluationNode * product2fraction(const CEvaluationNode *pOrig)
static CEvaluationNode * elementaryEliminationMinus(const CEvaluationNode *pMinusNode)
static std::vector< std::pair< CEvaluationNode *, CEvaluationNode * > > matchSummands(const std::vector< CEvaluationNode * > &additions, const std::vector< CEvaluationNode * > &subtractions)
static CEvaluationNode * eliminate(const CEvaluationNode *pOrig)
static CEvaluationNode * multiply(const CEvaluationNode *pNode1, const CEvaluationNode *pNode2)
static CEvaluationNode * simplifyTreeReptdly(const CEvaluationNode *root0)
static CEvaluationNode * elementaryElimination(CEvaluationNode *pOrig)
static void order(const CEvaluationNode *pRoot, std::list< const CEvaluationNode * > &orderList)
static CEvaluationNode * expandProducts(const CEvaluationNode *pOrig)
static CEvaluationNode * eliminatePowersOfFractions(const CEvaluationNode *pOrig)
CEvaluationNodeDepthFirstIterator & operator=(CEvaluationNode *pNode)
static const CEvaluationNode TIMES_NODE
CEvaluationNodeDepthFirstIterator & operator++()
static CEvaluationNode * elementaryEliminationFunction(const CEvaluationNode *pFunctionNode)
CEvaluationNodeDepthFirstIterator(CEvaluationNode *pRoot)
static CEvaluationNode * createChain(const CEvaluationNode *pLink, const CEvaluationNode *pNeutralElement, const std::vector< const CEvaluationNode * > &elements)
static const CEvaluationNode PLUS_NODE
static CEvaluationNode * newCancel(const CEvaluationNode *pOrig)
CEvaluationNode * pExponentNode
static CEvaluationNode * eliminateDirectlyNestedFractions(const CEvaluationNode *pOrig)
static const double ZERO
static void findSummands(const CEvaluationNode *pRoot, std::vector< const CEvaluationNode * > &summands)
static CEvaluationNode * expandPowerExponents(const CEvaluationNode *pRoot)
static CEvaluationNode * elementaryEliminationMultiply(const CEvaluationNode *pMultiplyNode)