source: trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeSimplifier.cs @ 17963

Last change on this file since 17963 was 17963, checked in by gkronber, 6 months ago

#3121: support integer powers in interval arithmetic (and two simplification rules)

File size: 67.0 KB
Line 
1#region License Information
2
3/* HeuristicLab
4 * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
5 *
6 * This file is part of HeuristicLab.
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#endregion
23
24using System;
25using System.Collections.Generic;
26using System.Linq;
27using HeuristicLab.Common;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29
30namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
31  /// <summary>
32  /// Simplifier for symbolic expressions
33  /// </summary>
34  public class TreeSimplifier {
35    private static readonly Addition addSymbol = new Addition();
36    private static readonly Multiplication mulSymbol = new Multiplication();
37    private static readonly Division divSymbol = new Division();
38    private static readonly Constant constSymbol = new Constant();
39    private static readonly Absolute absSymbol = new Absolute();
40    private static readonly Logarithm logSymbol = new Logarithm();
41    private static readonly Exponential expSymbol = new Exponential();
42    private static readonly Root rootSymbol = new Root();
43    private static readonly Square sqrSymbol = new Square();
44    private static readonly SquareRoot sqrtSymbol = new SquareRoot();
45    private static readonly AnalyticQuotient aqSymbol = new AnalyticQuotient();
46    private static readonly Cube cubeSymbol = new Cube();
47    private static readonly CubeRoot cubeRootSymbol = new CubeRoot();
48    private static readonly Power powSymbol = new Power();
49    private static readonly Sine sineSymbol = new Sine();
50    private static readonly Cosine cosineSymbol = new Cosine();
51    private static readonly Tangent tanSymbol = new Tangent();
52    private static readonly IfThenElse ifThenElseSymbol = new IfThenElse();
53    private static readonly And andSymbol = new And();
54    private static readonly Or orSymbol = new Or();
55    private static readonly Not notSymbol = new Not();
56    private static readonly GreaterThan gtSymbol = new GreaterThan();
57    private static readonly LessThan ltSymbol = new LessThan();
58    private static readonly Integral integralSymbol = new Integral();
59    private static readonly LaggedVariable laggedVariableSymbol = new LaggedVariable();
60    private static readonly TimeLag timeLagSymbol = new TimeLag();
61
62    [Obsolete("Use static method TreeSimplifier.Simplify instead")]
63    public TreeSimplifier() { }
64
65    public static ISymbolicExpressionTree Simplify(ISymbolicExpressionTree originalTree) {
66      var clone = (ISymbolicExpressionTreeNode)originalTree.Root.Clone();
67      // macro expand (initially no argument trees)
68      var macroExpandedTree = MacroExpand(clone, clone.GetSubtree(0), new List<ISymbolicExpressionTreeNode>());
69      ISymbolicExpressionTreeNode rootNode = (new ProgramRootSymbol()).CreateTreeNode();
70      rootNode.AddSubtree(GetSimplifiedTree(macroExpandedTree));
71
72#if DEBUG
73      // check that each node is only referenced once
74      var nodes = rootNode.IterateNodesPrefix().ToArray();
75      foreach (var n in nodes) if (nodes.Count(ni => ni == n) > 1) throw new InvalidOperationException();
76#endif
77      return new SymbolicExpressionTree(rootNode);
78    }
79
80    // the argumentTrees list contains already expanded trees used as arguments for invocations
81    private static ISymbolicExpressionTreeNode MacroExpand(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode node,
82      IList<ISymbolicExpressionTreeNode> argumentTrees) {
83      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
84      while (node.SubtreeCount > 0) node.RemoveSubtree(0);
85      if (node.Symbol is InvokeFunction) {
86        var invokeSym = node.Symbol as InvokeFunction;
87        var defunNode = FindFunctionDefinition(root, invokeSym.FunctionName);
88        var macroExpandedArguments = new List<ISymbolicExpressionTreeNode>();
89        foreach (var subtree in subtrees) {
90          macroExpandedArguments.Add(MacroExpand(root, subtree, argumentTrees));
91        }
92        return MacroExpand(root, defunNode, macroExpandedArguments);
93      } else if (node.Symbol is Argument) {
94        var argSym = node.Symbol as Argument;
95        // return the correct argument sub-tree (already macro-expanded)
96        return (SymbolicExpressionTreeNode)argumentTrees[argSym.ArgumentIndex].Clone();
97      } else {
98        // recursive application
99        foreach (var subtree in subtrees) {
100          node.AddSubtree(MacroExpand(root, subtree, argumentTrees));
101        }
102        return node;
103      }
104    }
105
106    private static ISymbolicExpressionTreeNode FindFunctionDefinition(ISymbolicExpressionTreeNode root, string functionName) {
107      foreach (var subtree in root.Subtrees.OfType<DefunTreeNode>()) {
108        if (subtree.FunctionName == functionName) return subtree.GetSubtree(0);
109      }
110
111      throw new ArgumentException("Definition of function " + functionName + " not found.");
112    }
113
114    #region symbol predicates
115
116    // arithmetic
117    private static bool IsDivision(ISymbolicExpressionTreeNode node) {
118      return node.Symbol is Division;
119    }
120
121    private static bool IsMultiplication(ISymbolicExpressionTreeNode node) {
122      return node.Symbol is Multiplication;
123    }
124
125    private static bool IsSubtraction(ISymbolicExpressionTreeNode node) {
126      return node.Symbol is Subtraction;
127    }
128
129    private static bool IsAddition(ISymbolicExpressionTreeNode node) {
130      return node.Symbol is Addition;
131    }
132
133    private static bool IsAverage(ISymbolicExpressionTreeNode node) {
134      return node.Symbol is Average;
135    }
136
137    private static bool IsAbsolute(ISymbolicExpressionTreeNode node) {
138      return node.Symbol is Absolute;
139    }
140
141    // exponential
142    private static bool IsLog(ISymbolicExpressionTreeNode node) {
143      return node.Symbol is Logarithm;
144    }
145
146    private static bool IsExp(ISymbolicExpressionTreeNode node) {
147      return node.Symbol is Exponential;
148    }
149
150    private static bool IsRoot(ISymbolicExpressionTreeNode node) {
151      return node.Symbol is Root;
152    }
153
154    private static bool IsSquare(ISymbolicExpressionTreeNode node) {
155      return node.Symbol is Square;
156    }
157
158    private static bool IsSquareRoot(ISymbolicExpressionTreeNode node) {
159      return node.Symbol is SquareRoot;
160    }
161
162    private static bool IsCube(ISymbolicExpressionTreeNode node) {
163      return node.Symbol is Cube;
164    }
165
166    private static bool IsCubeRoot(ISymbolicExpressionTreeNode node) {
167      return node.Symbol is CubeRoot;
168    }
169
170    private static bool IsPower(ISymbolicExpressionTreeNode node) {
171      return node.Symbol is Power;
172    }
173
174    // trigonometric
175    private static bool IsSine(ISymbolicExpressionTreeNode node) {
176      return node.Symbol is Sine;
177    }
178
179    private static bool IsCosine(ISymbolicExpressionTreeNode node) {
180      return node.Symbol is Cosine;
181    }
182
183    private static bool IsTangent(ISymbolicExpressionTreeNode node) {
184      return node.Symbol is Tangent;
185    }
186
187    private static bool IsAnalyticalQuotient(ISymbolicExpressionTreeNode node) {
188      return node.Symbol is AnalyticQuotient;
189    }
190
191    // boolean
192    private static bool IsIfThenElse(ISymbolicExpressionTreeNode node) {
193      return node.Symbol is IfThenElse;
194    }
195
196    private static bool IsAnd(ISymbolicExpressionTreeNode node) {
197      return node.Symbol is And;
198    }
199
200    private static bool IsOr(ISymbolicExpressionTreeNode node) {
201      return node.Symbol is Or;
202    }
203
204    private static bool IsNot(ISymbolicExpressionTreeNode node) {
205      return node.Symbol is Not;
206    }
207
208    // comparison
209    private static bool IsGreaterThan(ISymbolicExpressionTreeNode node) {
210      return node.Symbol is GreaterThan;
211    }
212
213    private static bool IsLessThan(ISymbolicExpressionTreeNode node) {
214      return node.Symbol is LessThan;
215    }
216
217    private static bool IsBoolean(ISymbolicExpressionTreeNode node) {
218      return
219        node.Symbol is GreaterThan ||
220        node.Symbol is LessThan ||
221        node.Symbol is And ||
222        node.Symbol is Or;
223    }
224
225    // terminals
226    private static bool IsVariable(ISymbolicExpressionTreeNode node) {
227      return node.Symbol is Variable;
228    }
229
230    private static bool IsVariableBase(ISymbolicExpressionTreeNode node) {
231      return node is VariableTreeNodeBase;
232    }
233
234    private static bool IsFactor(ISymbolicExpressionTreeNode node) {
235      return node is FactorVariableTreeNode;
236    }
237
238    private static bool IsBinFactor(ISymbolicExpressionTreeNode node) {
239      return node is BinaryFactorVariableTreeNode;
240    }
241
242    private static bool IsConstant(ISymbolicExpressionTreeNode node) {
243      return node.Symbol is Constant;
244    }
245
246    // dynamic
247    private static bool IsTimeLag(ISymbolicExpressionTreeNode node) {
248      return node.Symbol is TimeLag;
249    }
250
251    private static bool IsIntegral(ISymbolicExpressionTreeNode node) {
252      return node.Symbol is Integral;
253    }
254
255    #endregion
256
257    /// <summary>
258    /// Creates a new simplified tree
259    /// </summary>
260    /// <param name="original"></param>
261    /// <returns></returns>
262    public static ISymbolicExpressionTreeNode GetSimplifiedTree(ISymbolicExpressionTreeNode original) {
263      if (IsConstant(original) || IsVariableBase(original)) {
264        return (ISymbolicExpressionTreeNode)original.Clone();
265      } else if (IsAbsolute(original)) {
266        return SimplifyAbsolute(original);
267      } else if (IsAddition(original)) {
268        return SimplifyAddition(original);
269      } else if (IsSubtraction(original)) {
270        return SimplifySubtraction(original);
271      } else if (IsMultiplication(original)) {
272        return SimplifyMultiplication(original);
273      } else if (IsDivision(original)) {
274        return SimplifyDivision(original);
275      } else if (IsAverage(original)) {
276        return SimplifyAverage(original);
277      } else if (IsLog(original)) {
278        return SimplifyLog(original);
279      } else if (IsExp(original)) {
280        return SimplifyExp(original);
281      } else if (IsSquare(original)) {
282        return SimplifySquare(original);
283      } else if (IsSquareRoot(original)) {
284        return SimplifySquareRoot(original);
285      } else if (IsCube(original)) {
286        return SimplifyCube(original);
287      } else if (IsCubeRoot(original)) {
288        return SimplifyCubeRoot(original);
289      } else if (IsPower(original)) {
290        return SimplifyPower(original);
291      } else if (IsRoot(original)) {
292        return SimplifyRoot(original);
293      } else if (IsSine(original)) {
294        return SimplifySine(original);
295      } else if (IsCosine(original)) {
296        return SimplifyCosine(original);
297      } else if (IsTangent(original)) {
298        return SimplifyTangent(original);
299      } else if (IsAnalyticalQuotient(original)) {
300        return SimplifyAnalyticalQuotient(original);
301      } else if (IsIfThenElse(original)) {
302        return SimplifyIfThenElse(original);
303      } else if (IsGreaterThan(original)) {
304        return SimplifyGreaterThan(original);
305      } else if (IsLessThan(original)) {
306        return SimplifyLessThan(original);
307      } else if (IsAnd(original)) {
308        return SimplifyAnd(original);
309      } else if (IsOr(original)) {
310        return SimplifyOr(original);
311      } else if (IsNot(original)) {
312        return SimplifyNot(original);
313      } else if (IsTimeLag(original)) {
314        return SimplifyTimeLag(original);
315      } else if (IsIntegral(original)) {
316        return SimplifyIntegral(original);
317      } else {
318        return SimplifyAny(original);
319      }
320    }
321
322    #region specific simplification routines
323
324    private static ISymbolicExpressionTreeNode SimplifyAny(ISymbolicExpressionTreeNode original) {
325      // can't simplify this function but simplify all subtrees
326      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(original.Subtrees);
327      while (original.Subtrees.Count() > 0) original.RemoveSubtree(0);
328      var clone = (SymbolicExpressionTreeNode)original.Clone();
329      List<ISymbolicExpressionTreeNode> simplifiedSubtrees = new List<ISymbolicExpressionTreeNode>();
330      foreach (var subtree in subtrees) {
331        simplifiedSubtrees.Add(GetSimplifiedTree(subtree));
332        original.AddSubtree(subtree);
333      }
334      foreach (var simplifiedSubtree in simplifiedSubtrees) {
335        clone.AddSubtree(simplifiedSubtree);
336      }
337      if (simplifiedSubtrees.TrueForAll(t => IsConstant(t))) {
338        SimplifyConstantExpression(clone);
339      }
340      return clone;
341    }
342
343    private static ISymbolicExpressionTreeNode SimplifyConstantExpression(ISymbolicExpressionTreeNode original) {
344      // not yet implemented
345      return original;
346    }
347
348    private static ISymbolicExpressionTreeNode SimplifyAverage(ISymbolicExpressionTreeNode original) {
349      if (original.Subtrees.Count() == 1) {
350        return GetSimplifiedTree(original.GetSubtree(0));
351      } else {
352        // simplify expressions x0..xn
353        // make sum(x0..xn) / n
354        var sum = original.Subtrees
355          .Select(GetSimplifiedTree)
356          .Aggregate(MakeSum);
357        return MakeFraction(sum, MakeConstant(original.Subtrees.Count()));
358      }
359    }
360
361    private static ISymbolicExpressionTreeNode SimplifyDivision(ISymbolicExpressionTreeNode original) {
362      if (original.Subtrees.Count() == 1) {
363        return Invert(GetSimplifiedTree(original.GetSubtree(0)));
364      } else {
365        // simplify expressions x0..xn
366        // make multiplication (x0 * 1/(x1 * x1 * .. * xn))
367        var first = original.GetSubtree(0);
368        var second = original.GetSubtree(1);
369        var remaining = original.Subtrees.Skip(2);
370        return
371          MakeProduct(GetSimplifiedTree(first),
372            Invert(remaining.Aggregate(GetSimplifiedTree(second), (a, b) => MakeProduct(a, GetSimplifiedTree(b)))));
373      }
374    }
375
376    private static ISymbolicExpressionTreeNode SimplifyMultiplication(ISymbolicExpressionTreeNode original) {
377      if (original.Subtrees.Count() == 1) {
378        return GetSimplifiedTree(original.GetSubtree(0));
379      } else {
380        return original.Subtrees
381          .Select(GetSimplifiedTree)
382          .Aggregate(MakeProduct);
383      }
384    }
385
386    private static ISymbolicExpressionTreeNode SimplifySubtraction(ISymbolicExpressionTreeNode original) {
387      if (original.Subtrees.Count() == 1) {
388        return Negate(GetSimplifiedTree(original.GetSubtree(0)));
389      } else {
390        // simplify expressions x0..xn
391        // make addition (x0,-x1..-xn)
392        var first = original.Subtrees.First();
393        var remaining = original.Subtrees.Skip(1);
394        return remaining.Aggregate(GetSimplifiedTree(first), (a, b) => MakeSum(a, Negate(GetSimplifiedTree(b))));
395      }
396    }
397
398    private static ISymbolicExpressionTreeNode SimplifyAddition(ISymbolicExpressionTreeNode original) {
399      if (original.Subtrees.Count() == 1) {
400        return GetSimplifiedTree(original.GetSubtree(0));
401      } else {
402        // simplify expression x0..xn
403        // make addition (x0..xn)
404        return original.Subtrees
405          .Select(GetSimplifiedTree)
406          .Aggregate(MakeSum);
407      }
408    }
409
410    private static ISymbolicExpressionTreeNode SimplifyAbsolute(ISymbolicExpressionTreeNode original) {
411      return MakeAbs(GetSimplifiedTree(original.GetSubtree(0)));
412    }
413
414    private static ISymbolicExpressionTreeNode SimplifyNot(ISymbolicExpressionTreeNode original) {
415      return MakeNot(GetSimplifiedTree(original.GetSubtree(0)));
416    }
417
418    private static ISymbolicExpressionTreeNode SimplifyOr(ISymbolicExpressionTreeNode original) {
419      return original.Subtrees
420        .Select(GetSimplifiedTree)
421        .Aggregate(MakeOr);
422    }
423
424    private static ISymbolicExpressionTreeNode SimplifyAnd(ISymbolicExpressionTreeNode original) {
425      return original.Subtrees
426        .Select(GetSimplifiedTree)
427        .Aggregate(MakeAnd);
428    }
429
430    private static ISymbolicExpressionTreeNode SimplifyLessThan(ISymbolicExpressionTreeNode original) {
431      return MakeLessThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
432    }
433
434    private static ISymbolicExpressionTreeNode SimplifyGreaterThan(ISymbolicExpressionTreeNode original) {
435      return MakeGreaterThan(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
436    }
437
438    private static ISymbolicExpressionTreeNode SimplifyIfThenElse(ISymbolicExpressionTreeNode original) {
439      return MakeIfThenElse(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)),
440        GetSimplifiedTree(original.GetSubtree(2)));
441    }
442
443    private static ISymbolicExpressionTreeNode SimplifyTangent(ISymbolicExpressionTreeNode original) {
444      return MakeTangent(GetSimplifiedTree(original.GetSubtree(0)));
445    }
446
447    private static ISymbolicExpressionTreeNode SimplifyCosine(ISymbolicExpressionTreeNode original) {
448      return MakeCosine(GetSimplifiedTree(original.GetSubtree(0)));
449    }
450
451    private static ISymbolicExpressionTreeNode SimplifySine(ISymbolicExpressionTreeNode original) {
452      return MakeSine(GetSimplifiedTree(original.GetSubtree(0)));
453    }
454
455    private static ISymbolicExpressionTreeNode SimplifyExp(ISymbolicExpressionTreeNode original) {
456      return MakeExp(GetSimplifiedTree(original.GetSubtree(0)));
457    }
458
459    private static ISymbolicExpressionTreeNode SimplifySquare(ISymbolicExpressionTreeNode original) {
460      return MakeSquare(GetSimplifiedTree(original.GetSubtree(0)));
461    }
462
463    private static ISymbolicExpressionTreeNode SimplifySquareRoot(ISymbolicExpressionTreeNode original) {
464      return MakeSquareRoot(GetSimplifiedTree(original.GetSubtree(0)));
465    }
466    private static ISymbolicExpressionTreeNode SimplifyCube(ISymbolicExpressionTreeNode original) {
467      return MakeCube(GetSimplifiedTree(original.GetSubtree(0)));
468    }
469
470    private static ISymbolicExpressionTreeNode SimplifyCubeRoot(ISymbolicExpressionTreeNode original) {
471      return MakeCubeRoot(GetSimplifiedTree(original.GetSubtree(0)));
472    }
473
474    private static ISymbolicExpressionTreeNode SimplifyLog(ISymbolicExpressionTreeNode original) {
475      return MakeLog(GetSimplifiedTree(original.GetSubtree(0)));
476    }
477
478    private static ISymbolicExpressionTreeNode SimplifyRoot(ISymbolicExpressionTreeNode original) {
479      return MakeRoot(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
480    }
481
482    private static ISymbolicExpressionTreeNode SimplifyPower(ISymbolicExpressionTreeNode original) {
483      return MakePower(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
484    }
485
486    private static ISymbolicExpressionTreeNode SimplifyAnalyticalQuotient(ISymbolicExpressionTreeNode original) {
487      return MakeAnalyticalQuotient(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
488    }
489
490    private static ISymbolicExpressionTreeNode SimplifyTimeLag(ISymbolicExpressionTreeNode original) {
491      var laggedTreeNode = original as ILaggedTreeNode;
492      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
493      if (!ContainsVariableCondition(simplifiedSubtree)) {
494        return AddLagToDynamicNodes(simplifiedSubtree, laggedTreeNode.Lag);
495      } else {
496        return MakeTimeLag(simplifiedSubtree, laggedTreeNode.Lag);
497      }
498    }
499
500    private static ISymbolicExpressionTreeNode SimplifyIntegral(ISymbolicExpressionTreeNode original) {
501      var laggedTreeNode = original as ILaggedTreeNode;
502      var simplifiedSubtree = GetSimplifiedTree(original.GetSubtree(0));
503      if (IsConstant(simplifiedSubtree)) {
504        return GetSimplifiedTree(MakeProduct(simplifiedSubtree, MakeConstant(-laggedTreeNode.Lag)));
505      } else {
506        return MakeIntegral(simplifiedSubtree, laggedTreeNode.Lag);
507      }
508    }
509
510    #endregion
511
512    #region low level tree restructuring
513
514    private static ISymbolicExpressionTreeNode MakeTimeLag(ISymbolicExpressionTreeNode subtree, int lag) {
515      if (lag == 0) return subtree;
516      if (IsConstant(subtree)) return subtree;
517      var lagNode = (LaggedTreeNode)timeLagSymbol.CreateTreeNode();
518      lagNode.Lag = lag;
519      lagNode.AddSubtree(subtree);
520      return lagNode;
521    }
522
523    private static ISymbolicExpressionTreeNode MakeIntegral(ISymbolicExpressionTreeNode subtree, int lag) {
524      if (lag == 0) return subtree;
525      else if (lag == -1 || lag == 1) {
526        return MakeSum(subtree, AddLagToDynamicNodes((ISymbolicExpressionTreeNode)subtree.Clone(), lag));
527      } else {
528        var node = (LaggedTreeNode)integralSymbol.CreateTreeNode();
529        node.Lag = lag;
530        node.AddSubtree(subtree);
531        return node;
532      }
533    }
534
535    private static ISymbolicExpressionTreeNode MakeNot(ISymbolicExpressionTreeNode t) {
536      if (IsConstant(t)) {
537        var constNode = t as ConstantTreeNode;
538        if (constNode.Value > 0) return MakeConstant(-1.0);
539        else return MakeConstant(1.0);
540      } else if (IsNot(t)) {
541        return t.GetSubtree(0);
542      } else if (!IsBoolean(t)) {
543        var gtNode = gtSymbol.CreateTreeNode();
544        gtNode.AddSubtree(t);
545        gtNode.AddSubtree(MakeConstant(0.0));
546        var notNode = notSymbol.CreateTreeNode();
547        notNode.AddSubtree(gtNode);
548        return notNode;
549      } else {
550        var notNode = notSymbol.CreateTreeNode();
551        notNode.AddSubtree(t);
552        return notNode;
553      }
554    }
555
556    private static ISymbolicExpressionTreeNode MakeOr(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
557      if (IsConstant(a) && IsConstant(b)) {
558        var constA = a as ConstantTreeNode;
559        var constB = b as ConstantTreeNode;
560        if (constA.Value > 0.0 || constB.Value > 0.0) {
561          return MakeConstant(1.0);
562        } else {
563          return MakeConstant(-1.0);
564        }
565      } else if (IsConstant(a)) {
566        return MakeOr(b, a);
567      } else if (IsConstant(b)) {
568        var constT = b as ConstantTreeNode;
569        if (constT.Value > 0.0) {
570          // boolean expression is necessarily true
571          return MakeConstant(1.0);
572        } else {
573          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
574          var orNode = orSymbol.CreateTreeNode();
575          orNode.AddSubtree(a);
576          return orNode;
577        }
578      } else {
579        var orNode = orSymbol.CreateTreeNode();
580        orNode.AddSubtree(a);
581        orNode.AddSubtree(b);
582        return orNode;
583      }
584    }
585
586    private static ISymbolicExpressionTreeNode MakeAnd(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
587      if (IsConstant(a) && IsConstant(b)) {
588        var constA = a as ConstantTreeNode;
589        var constB = b as ConstantTreeNode;
590        if (constA.Value > 0.0 && constB.Value > 0.0) {
591          return MakeConstant(1.0);
592        } else {
593          return MakeConstant(-1.0);
594        }
595      } else if (IsConstant(a)) {
596        return MakeAnd(b, a);
597      } else if (IsConstant(b)) {
598        var constB = b as ConstantTreeNode;
599        if (constB.Value > 0.0) {
600          // the constant value has no effect on the result of the boolean condition so we can drop the constant term
601          var andNode = andSymbol.CreateTreeNode();
602          andNode.AddSubtree(a);
603          return andNode;
604        } else {
605          // boolean expression is necessarily false
606          return MakeConstant(-1.0);
607        }
608      } else {
609        var andNode = andSymbol.CreateTreeNode();
610        andNode.AddSubtree(a);
611        andNode.AddSubtree(b);
612        return andNode;
613      }
614    }
615
616    private static ISymbolicExpressionTreeNode MakeLessThan(ISymbolicExpressionTreeNode leftSide,
617      ISymbolicExpressionTreeNode rightSide) {
618      if (IsConstant(leftSide) && IsConstant(rightSide)) {
619        var lsConst = leftSide as ConstantTreeNode;
620        var rsConst = rightSide as ConstantTreeNode;
621        if (lsConst.Value < rsConst.Value) return MakeConstant(1.0);
622        else return MakeConstant(-1.0);
623      } else {
624        var ltNode = ltSymbol.CreateTreeNode();
625        ltNode.AddSubtree(leftSide);
626        ltNode.AddSubtree(rightSide);
627        return ltNode;
628      }
629    }
630
631    private static ISymbolicExpressionTreeNode MakeGreaterThan(ISymbolicExpressionTreeNode leftSide,
632      ISymbolicExpressionTreeNode rightSide) {
633      if (IsConstant(leftSide) && IsConstant(rightSide)) {
634        var lsConst = leftSide as ConstantTreeNode;
635        var rsConst = rightSide as ConstantTreeNode;
636        if (lsConst.Value > rsConst.Value) return MakeConstant(1.0);
637        else return MakeConstant(-1.0);
638      } else {
639        var gtNode = gtSymbol.CreateTreeNode();
640        gtNode.AddSubtree(leftSide);
641        gtNode.AddSubtree(rightSide);
642        return gtNode;
643      }
644    }
645
646    private static ISymbolicExpressionTreeNode MakeIfThenElse(ISymbolicExpressionTreeNode condition,
647      ISymbolicExpressionTreeNode trueBranch, ISymbolicExpressionTreeNode falseBranch) {
648      if (IsConstant(condition)) {
649        var constT = condition as ConstantTreeNode;
650        if (constT.Value > 0.0) return trueBranch;
651        else return falseBranch;
652      } else {
653        var ifNode = ifThenElseSymbol.CreateTreeNode();
654        if (IsBoolean(condition)) {
655          ifNode.AddSubtree(condition);
656        } else {
657          var gtNode = gtSymbol.CreateTreeNode();
658          gtNode.AddSubtree(condition);
659          gtNode.AddSubtree(MakeConstant(0.0));
660          ifNode.AddSubtree(gtNode);
661        }
662        ifNode.AddSubtree(trueBranch);
663        ifNode.AddSubtree(falseBranch);
664        return ifNode;
665      }
666    }
667
668    private static ISymbolicExpressionTreeNode MakeSine(ISymbolicExpressionTreeNode node) {
669      if (IsConstant(node)) {
670        var constT = node as ConstantTreeNode;
671        return MakeConstant(Math.Sin(constT.Value));
672      } else if (IsFactor(node)) {
673        var factor = node as FactorVariableTreeNode;
674        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Sin));
675      } else if (IsBinFactor(node)) {
676        var binFactor = node as BinaryFactorVariableTreeNode;
677        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sin(binFactor.Weight));
678      } else {
679        var sineNode = sineSymbol.CreateTreeNode();
680        sineNode.AddSubtree(node);
681        return sineNode;
682      }
683    }
684
685    private static ISymbolicExpressionTreeNode MakeTangent(ISymbolicExpressionTreeNode node) {
686      if (IsConstant(node)) {
687        var constT = node as ConstantTreeNode;
688        return MakeConstant(Math.Tan(constT.Value));
689      } else if (IsFactor(node)) {
690        var factor = node as FactorVariableTreeNode;
691        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Tan));
692      } else if (IsBinFactor(node)) {
693        var binFactor = node as BinaryFactorVariableTreeNode;
694        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Tan(binFactor.Weight));
695      } else {
696        var tanNode = tanSymbol.CreateTreeNode();
697        tanNode.AddSubtree(node);
698        return tanNode;
699      }
700    }
701
702    private static ISymbolicExpressionTreeNode MakeCosine(ISymbolicExpressionTreeNode node) {
703      if (IsConstant(node)) {
704        var constT = node as ConstantTreeNode;
705        return MakeConstant(Math.Cos(constT.Value));
706      } else if (IsFactor(node)) {
707        var factor = node as FactorVariableTreeNode;
708        return MakeFactor(factor.Symbol, factor.VariableName, factor.Weights.Select(Math.Cos));
709      } else if (IsBinFactor(node)) {
710        var binFactor = node as BinaryFactorVariableTreeNode;
711        // cos(0) = 1 see similar case for Exp(binfactor)
712        return MakeSum(MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Cos(binFactor.Weight) - 1),
713          MakeConstant(1.0));
714      } else {
715        var cosNode = cosineSymbol.CreateTreeNode();
716        cosNode.AddSubtree(node);
717        return cosNode;
718      }
719    }
720
721    private static ISymbolicExpressionTreeNode MakeExp(ISymbolicExpressionTreeNode node) {
722      if (IsConstant(node)) {
723        var constT = node as ConstantTreeNode;
724        return MakeConstant(Math.Exp(constT.Value));
725      } else if (IsFactor(node)) {
726        var factNode = node as FactorVariableTreeNode;
727        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Exp(w)));
728      } else if (IsBinFactor(node)) {
729        // exp( binfactor w val=a) = if(val=a) exp(w) else exp(0) = binfactor( (exp(w) - 1) val a) + 1
730        var binFactor = node as BinaryFactorVariableTreeNode;
731        return
732          MakeSum(MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Exp(binFactor.Weight) - 1), MakeConstant(1.0));
733      } else if (IsLog(node)) {
734        return node.GetSubtree(0);
735      } else if (IsAddition(node)) {
736        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, t));
737      } else if (IsSubtraction(node)) {
738        return node.Subtrees.Select(s => MakeExp(s)).Aggregate((s, t) => MakeProduct(s, Negate(t)));
739      } else {
740        var expNode = expSymbol.CreateTreeNode();
741        expNode.AddSubtree(node);
742        return expNode;
743      }
744    }
745    private static ISymbolicExpressionTreeNode MakeLog(ISymbolicExpressionTreeNode node) {
746      if (IsConstant(node)) {
747        var constT = node as ConstantTreeNode;
748        return MakeConstant(Math.Log(constT.Value));
749      } else if (IsFactor(node)) {
750        var factNode = node as FactorVariableTreeNode;
751        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Log(w)));
752      } else if (IsExp(node)) {
753        return node.GetSubtree(0);
754      } else if (IsSquareRoot(node)) {
755        return MakeFraction(MakeLog(node.GetSubtree(0)), MakeConstant(2.0));
756      } else {
757        var logNode = logSymbol.CreateTreeNode();
758        logNode.AddSubtree(node);
759        return logNode;
760      }
761    }
762
763    private static ISymbolicExpressionTreeNode MakeSquare(ISymbolicExpressionTreeNode node) {
764      if (IsConstant(node)) {
765        var constT = node as ConstantTreeNode;
766        return MakeConstant(constT.Value * constT.Value);
767      } else if (IsFactor(node)) {
768        var factNode = node as FactorVariableTreeNode;
769        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w * w));
770      } else if (IsBinFactor(node)) {
771        var binFactor = node as BinaryFactorVariableTreeNode;
772        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, binFactor.Weight * binFactor.Weight);
773      } else if (IsSquareRoot(node)) {
774        return node.GetSubtree(0);
775      } else if (IsMultiplication(node)) {
776        // sqr( x * y ) = sqr(x) * sqr(y)
777        var mulNode = mulSymbol.CreateTreeNode();
778        foreach (var subtree in node.Subtrees) {
779          mulNode.AddSubtree(MakeSquare(subtree));
780        }
781        return mulNode;
782      } else if (IsAbsolute(node)) {
783        return MakeSquare(node.GetSubtree(0)); // sqr(abs(x)) = sqr(x)
784      } else if (IsExp(node)) {
785        return MakeExp(MakeProduct(node.GetSubtree(0), MakeConstant(2.0))); // sqr(exp(x)) = exp(2x)
786      } else if (IsSquare(node)) {
787        return MakePower(node.GetSubtree(0), MakeConstant(4));
788      } else if (IsCube(node)) {
789        return MakePower(node.GetSubtree(0), MakeConstant(6));
790      } else {
791        var sqrNode = sqrSymbol.CreateTreeNode();
792        sqrNode.AddSubtree(node);
793        return sqrNode;
794      }
795    }
796
797    private static ISymbolicExpressionTreeNode MakeCube(ISymbolicExpressionTreeNode node) {
798      if (IsConstant(node)) {
799        var constT = node as ConstantTreeNode;
800        return MakeConstant(constT.Value * constT.Value * constT.Value);
801      } else if (IsFactor(node)) {
802        var factNode = node as FactorVariableTreeNode;
803        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w * w * w));
804      } else if (IsBinFactor(node)) {
805        var binFactor = node as BinaryFactorVariableTreeNode;
806        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, binFactor.Weight * binFactor.Weight * binFactor.Weight);
807      } else if (IsCubeRoot(node)) {
808        return node.GetSubtree(0); // NOTE: not really accurate because cuberoot(x) with negative x is evaluated to NaN and after this simplification we evaluate as x
809      } else if (IsExp(node)) {
810        return MakeExp(MakeProduct(node.GetSubtree(0), MakeConstant(3)));
811      } else if (IsSquare(node)) {
812        return MakePower(node.GetSubtree(0), MakeConstant(6));
813      } else if (IsCube(node)) {
814        return MakePower(node.GetSubtree(0), MakeConstant(9));
815      } else {
816        var cubeNode = cubeSymbol.CreateTreeNode();
817        cubeNode.AddSubtree(node);
818        return cubeNode;
819      }
820    }
821
822    private static ISymbolicExpressionTreeNode MakeAbs(ISymbolicExpressionTreeNode node) {
823      if (IsConstant(node)) {
824        var constT = node as ConstantTreeNode;
825        return MakeConstant(Math.Abs(constT.Value));
826      } else if (IsFactor(node)) {
827        var factNode = node as FactorVariableTreeNode;
828        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Abs(w)));
829      } else if (IsBinFactor(node)) {
830        var binFactor = node as BinaryFactorVariableTreeNode;
831        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Abs(binFactor.Weight));
832      } else if (IsSquare(node) || IsExp(node) || IsSquareRoot(node) || IsCubeRoot(node)) {
833        return node; // abs(sqr(x)) = sqr(x), abs(exp(x)) = exp(x) ...
834      } else if (IsMultiplication(node)) {
835        var mul = mulSymbol.CreateTreeNode();
836        foreach (var st in node.Subtrees) {
837          mul.AddSubtree(MakeAbs(st));
838        }
839        return mul;
840      } else if (IsDivision(node)) {
841        var div = divSymbol.CreateTreeNode();
842        foreach (var st in node.Subtrees) {
843          div.AddSubtree(MakeAbs(st));
844        }
845        return div;
846      } else {
847        var absNode = absSymbol.CreateTreeNode();
848        absNode.AddSubtree(node);
849        return absNode;
850      }
851    }
852
853    // constant folding only
854    private static ISymbolicExpressionTreeNode MakeAnalyticalQuotient(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
855      if (IsConstant(b)) {
856        var c = b as ConstantTreeNode;
857        return MakeFraction(a, MakeConstant(Math.Sqrt(1.0 + c.Value * c.Value)));
858      } else if (IsFactor(b)) {
859        var factNode = b as FactorVariableTreeNode;
860        return MakeFraction(a, MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Sqrt(1.0 + w * w))));
861      } else if (IsBinFactor(b)) {
862        var binFactor = b as BinaryFactorVariableTreeNode;
863        return MakeFraction(a, MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(1.0 + binFactor.Weight * binFactor.Weight)));
864      } else {
865        var aqNode = aqSymbol.CreateTreeNode();
866        aqNode.AddSubtree(a);
867        aqNode.AddSubtree(b);
868        return aqNode;
869      }
870    }
871
872    private static ISymbolicExpressionTreeNode MakeSquareRoot(ISymbolicExpressionTreeNode node) {
873      if (IsConstant(node)) {
874        var constT = node as ConstantTreeNode;
875        return MakeConstant(Math.Sqrt(constT.Value));
876      } else if (IsFactor(node)) {
877        var factNode = node as FactorVariableTreeNode;
878        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Sqrt(w)));
879      } else if (IsBinFactor(node)) {
880        var binFactor = node as BinaryFactorVariableTreeNode;
881        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(binFactor.Weight));
882      } else if (IsSquare(node)) {
883        return node.GetSubtree(0); // NOTE: not really accurate because sqrt(x) with negative x is evaluated to NaN and after this simplification we evaluate as x
884      } else {
885        var sqrtNode = sqrtSymbol.CreateTreeNode();
886        sqrtNode.AddSubtree(node);
887        return sqrtNode;
888      }
889    }
890
891    private static ISymbolicExpressionTreeNode MakeCubeRoot(ISymbolicExpressionTreeNode node) {
892      if (IsConstant(node)) {
893        var constT = node as ConstantTreeNode;
894        return MakeConstant(Math.Pow(constT.Value, 1.0 / 3.0));
895      } else if (IsFactor(node)) {
896        var factNode = node as FactorVariableTreeNode;
897        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(w, 1.0 / 3.0)));
898      } else if (IsBinFactor(node)) {
899        var binFactor = node as BinaryFactorVariableTreeNode;
900        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(Math.Pow(binFactor.Weight, 1.0 / 3.0)));
901      } else if (IsCube(node)) {
902        return node.GetSubtree(0);
903      } else {
904        var cubeRootNode = cubeRootSymbol.CreateTreeNode();
905        cubeRootNode.AddSubtree(node);
906        return cubeRootNode;
907      }
908    }
909
910    private static ISymbolicExpressionTreeNode MakeRoot(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
911      if (IsConstant(a) && IsConstant(b)) {
912        var constA = a as ConstantTreeNode;
913        var constB = b as ConstantTreeNode;
914        return MakeConstant(Math.Pow(constA.Value, 1.0 / Math.Round(constB.Value)));
915      } else if (IsFactor(a) && IsConstant(b)) {
916        var factNode = a as FactorVariableTreeNode;
917        var constNode = b as ConstantTreeNode;
918        return MakeFactor(factNode.Symbol, factNode.VariableName,
919          factNode.Weights.Select(w => Math.Pow(w, 1.0 / Math.Round(constNode.Value))));
920      } else if (IsBinFactor(a) && IsConstant(b)) {
921        var binFactor = a as BinaryFactorVariableTreeNode;
922        var constNode = b as ConstantTreeNode;
923        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, 1.0 / Math.Round(constNode.Value)));
924      } else if (IsConstant(a) && IsFactor(b)) {
925        var constNode = a as ConstantTreeNode;
926        var factNode = b as FactorVariableTreeNode;
927        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, 1.0 / Math.Round(w))));
928      } else if (IsConstant(a) && IsBinFactor(b)) {
929        var constNode = a as ConstantTreeNode;
930        var factNode = b as BinaryFactorVariableTreeNode;
931        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, 1.0 / Math.Round(factNode.Weight)));
932      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
933        var node0 = a as FactorVariableTreeNode;
934        var node1 = b as FactorVariableTreeNode;
935        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, 1.0 / Math.Round(v))));
936      } else if (IsConstant(b)) {
937        var constB = b as ConstantTreeNode;
938        var constBValue = Math.Round(constB.Value);
939        if (constBValue == 1.0) {
940          // root(a, 1) => a
941          return a;
942        } else if (constBValue == 0.0) {
943          // root(a, 0) is not defined
944          //return MakeConstant(1.0);
945          return MakeConstant(double.NaN);
946        } else if (constBValue == -1.0) {
947          // root(a, -1) => a^(-1/1) => 1/a
948          return MakeFraction(MakeConstant(1.0), a);
949        } else if (constBValue < 0) {
950          // root(a, -b) => a^(-1/b) => (1/a)^(1/b) => root(1, b) / root(a, b) => 1 / root(a, b)
951          var rootNode = rootSymbol.CreateTreeNode();
952          rootNode.AddSubtree(a);
953          rootNode.AddSubtree(MakeConstant(-1.0 * constBValue));
954          return MakeFraction(MakeConstant(1.0), rootNode);
955        } else {
956          var rootNode = rootSymbol.CreateTreeNode();
957          rootNode.AddSubtree(a);
958          rootNode.AddSubtree(MakeConstant(constBValue));
959          return rootNode;
960        }
961      } else {
962        var rootNode = rootSymbol.CreateTreeNode();
963        rootNode.AddSubtree(a);
964        rootNode.AddSubtree(b);
965        return rootNode;
966      }
967    }
968
969
970    private static ISymbolicExpressionTreeNode MakePower(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
971      if (IsConstant(a) && IsConstant(b)) {
972        var constA = a as ConstantTreeNode;
973        var constB = b as ConstantTreeNode;
974        return MakeConstant(Math.Pow(constA.Value, Math.Round(constB.Value)));
975      } else if (IsFactor(a) && IsConstant(b)) {
976        var factNode = a as FactorVariableTreeNode;
977        var constNode = b as ConstantTreeNode;
978        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(w, Math.Round(constNode.Value))));
979      } else if (IsBinFactor(a) && IsConstant(b)) {
980        var binFactor = a as BinaryFactorVariableTreeNode;
981        var constNode = b as ConstantTreeNode;
982        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Pow(binFactor.Weight, Math.Round(constNode.Value)));
983      } else if (IsConstant(a) && IsFactor(b)) {
984        var constNode = a as ConstantTreeNode;
985        var factNode = b as FactorVariableTreeNode;
986        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(constNode.Value, Math.Round(w))));
987      } else if (IsConstant(a) && IsBinFactor(b)) {
988        var constNode = a as ConstantTreeNode;
989        var factNode = b as BinaryFactorVariableTreeNode;
990        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, Math.Pow(constNode.Value, Math.Round(factNode.Weight)));
991      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
992        var node0 = a as FactorVariableTreeNode;
993        var node1 = b as FactorVariableTreeNode;
994        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => Math.Pow(u, Math.Round(v))));
995      } else if (IsConstant(b)) {
996        var constB = b as ConstantTreeNode;
997        double exponent = Math.Round(constB.Value);
998        if (exponent == 0.0) {
999          // a^0 => 1
1000          return MakeConstant(1.0);
1001        } else if (exponent == 1.0) {
1002          // a^1 => a
1003          return a;
1004        } else if (exponent == -1.0) {
1005          // a^-1 => 1/a
1006          return MakeFraction(MakeConstant(1.0), a);
1007        } else if (exponent < 0) {
1008          // a^-b => (1/a)^b => 1/(a^b)
1009          var powNode = powSymbol.CreateTreeNode();
1010          powNode.AddSubtree(a);
1011          powNode.AddSubtree(MakeConstant(-1.0 * exponent));
1012          return MakeFraction(MakeConstant(1.0), powNode);
1013        } else {
1014          var powNode = powSymbol.CreateTreeNode();
1015          powNode.AddSubtree(a);
1016          powNode.AddSubtree(MakeConstant(exponent));
1017          return powNode;
1018        }
1019      } else {
1020        var powNode = powSymbol.CreateTreeNode();
1021        powNode.AddSubtree(a);
1022        powNode.AddSubtree(b);
1023        return powNode;
1024      }
1025    }
1026
1027
1028    // MakeFraction, MakeProduct and MakeSum take two already simplified trees and create a new simplified tree
1029    private static ISymbolicExpressionTreeNode MakeFraction(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1030      if (IsConstant(a) && IsConstant(b)) {
1031        // fold constants
1032        return MakeConstant(((ConstantTreeNode)a).Value / ((ConstantTreeNode)b).Value);
1033      } else if ((IsConstant(a) && ((ConstantTreeNode)a).Value != 1.0)) {
1034        // a / x => (a * 1/a) / (x * 1/a) => 1 / (x * 1/a)
1035        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
1036      } else if (IsVariableBase(a) && IsConstant(b)) {
1037        // merge constant values into variable weights
1038        var constB = ((ConstantTreeNode)b).Value;
1039        ((VariableTreeNodeBase)a).Weight /= constB;
1040        return a;
1041      } else if (IsFactor(a) && IsConstant(b)) {
1042        var factNode = a as FactorVariableTreeNode;
1043        var constNode = b as ConstantTreeNode;
1044        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w / constNode.Value));
1045      } else if (IsBinFactor(a) && IsConstant(b)) {
1046        var factNode = a as BinaryFactorVariableTreeNode;
1047        var constNode = b as ConstantTreeNode;
1048        return MakeBinFactor(factNode.Symbol, factNode.VariableName, factNode.VariableValue, factNode.Weight / constNode.Value);
1049      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
1050        var node0 = a as FactorVariableTreeNode;
1051        var node1 = b as FactorVariableTreeNode;
1052        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u / v));
1053      } else if (IsFactor(a) && IsBinFactor(b) && ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
1054        var node0 = a as FactorVariableTreeNode;
1055        var node1 = b as BinaryFactorVariableTreeNode;
1056        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
1057        var wi = Array.IndexOf(varValues, node1.VariableValue);
1058        if (wi < 0) throw new ArgumentException();
1059        var newWeighs = new double[varValues.Length];
1060        node0.Weights.CopyTo(newWeighs, 0);
1061        for (int i = 0; i < newWeighs.Length; i++)
1062          if (wi == i) newWeighs[i] /= node1.Weight;
1063          else newWeighs[i] /= 0.0;
1064        return MakeFactor(node0.Symbol, node0.VariableName, newWeighs);
1065      } else if (IsFactor(a)) {
1066        return MakeFraction(MakeConstant(1.0), MakeProduct(b, Invert(a)));
1067      } else if (IsVariableBase(a) && IsVariableBase(b) && AreSameTypeAndVariable(a, b) && !IsBinFactor(b)) {
1068        // cancel variables (not allowed for bin factors because of division by zero)
1069        var aVar = a as VariableTreeNode;
1070        var bVar = b as VariableTreeNode;
1071        return MakeConstant(aVar.Weight / bVar.Weight);
1072      } else if (IsAddition(a) && IsConstant(b)) {
1073        return a.Subtrees
1074          .Select(x => GetSimplifiedTree(x))
1075          .Select(x => MakeFraction(x, GetSimplifiedTree(b)))
1076          .Aggregate((c, d) => MakeSum(c, d));
1077      } else if (IsMultiplication(a) && IsConstant(b)) {
1078        return MakeProduct(a, Invert(b));
1079      } else if (IsDivision(a) && IsConstant(b)) {
1080        // (a1 / a2) / c => (a1 / (a2 * c))
1081        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
1082      } else if (IsDivision(a) && IsDivision(b)) {
1083        // (a1 / a2) / (b1 / b2) =>
1084        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(1)), MakeProduct(a.GetSubtree(1), b.GetSubtree(0)));
1085      } else if (IsDivision(a)) {
1086        // (a1 / a2) / b => (a1 / (a2 * b))
1087        return MakeFraction(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
1088      } else if (IsDivision(b)) {
1089        // a / (b1 / b2) => (a * b2) / b1
1090        return MakeFraction(MakeProduct(a, b.GetSubtree(1)), b.GetSubtree(0));
1091      } else if (IsAnalyticalQuotient(a)) {
1092        return MakeAnalyticalQuotient(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
1093      } else {
1094        var div = divSymbol.CreateTreeNode();
1095        div.AddSubtree(a);
1096        div.AddSubtree(b);
1097        return div;
1098      }
1099    }
1100
1101    private static ISymbolicExpressionTreeNode MakeSum(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1102      if (IsConstant(a) && IsConstant(b)) {
1103        // fold constants
1104        ((ConstantTreeNode)a).Value += ((ConstantTreeNode)b).Value;
1105        return a;
1106      } else if (IsConstant(a)) {
1107        // c + x => x + c
1108        // b is not constant => make sure constant is on the right
1109        return MakeSum(b, a);
1110      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value == 0.0) {
1111        // x + 0 => x
1112        return a;
1113      } else if (IsFactor(a) && IsConstant(b)) {
1114        var factNode = a as FactorVariableTreeNode;
1115        var constNode = b as ConstantTreeNode;
1116        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select((w) => w + constNode.Value));
1117      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
1118        var node0 = a as FactorVariableTreeNode;
1119        var node1 = b as FactorVariableTreeNode;
1120        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u + v));
1121      } else if (IsBinFactor(a) && IsFactor(b)) {
1122        return MakeSum(b, a);
1123      } else if (IsFactor(a) && IsBinFactor(b) &&
1124        ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
1125        var node0 = a as FactorVariableTreeNode;
1126        var node1 = b as BinaryFactorVariableTreeNode;
1127        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
1128        var wi = Array.IndexOf(varValues, node1.VariableValue);
1129        if (wi < 0) throw new ArgumentException();
1130        var newWeighs = new double[varValues.Length];
1131        node0.Weights.CopyTo(newWeighs, 0);
1132        newWeighs[wi] += node1.Weight;
1133        return MakeFactor(node0.Symbol, node0.VariableName, newWeighs);
1134      } else if (IsAddition(a) && IsAddition(b)) {
1135        // merge additions
1136        var add = addSymbol.CreateTreeNode();
1137        // add all sub trees except for the last
1138        for (int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
1139        for (int i = 0; i < b.Subtrees.Count() - 1; i++) add.AddSubtree(b.GetSubtree(i));
1140        if (IsConstant(a.Subtrees.Last()) && IsConstant(b.Subtrees.Last())) {
1141          add.AddSubtree(MakeSum(a.Subtrees.Last(), b.Subtrees.Last()));
1142        } else if (IsConstant(a.Subtrees.Last())) {
1143          add.AddSubtree(b.Subtrees.Last());
1144          add.AddSubtree(a.Subtrees.Last());
1145        } else {
1146          add.AddSubtree(a.Subtrees.Last());
1147          add.AddSubtree(b.Subtrees.Last());
1148        }
1149        MergeVariablesInSum(add);
1150        if (add.Subtrees.Count() == 1) {
1151          return add.GetSubtree(0);
1152        } else {
1153          return add;
1154        }
1155      } else if (IsAddition(b)) {
1156        return MakeSum(b, a);
1157      } else if (IsAddition(a) && IsConstant(b)) {
1158        // a is an addition and b is a constant => append b to a and make sure the constants are merged
1159        var add = addSymbol.CreateTreeNode();
1160        // add all sub trees except for the last
1161        for (int i = 0; i < a.Subtrees.Count() - 1; i++) add.AddSubtree(a.GetSubtree(i));
1162        if (IsConstant(a.Subtrees.Last()))
1163          add.AddSubtree(MakeSum(a.Subtrees.Last(), b));
1164        else {
1165          add.AddSubtree(a.Subtrees.Last());
1166          add.AddSubtree(b);
1167        }
1168        return add;
1169      } else if (IsAddition(a)) {
1170        // a is already an addition => append b
1171        var add = addSymbol.CreateTreeNode();
1172        add.AddSubtree(b);
1173        foreach (var subtree in a.Subtrees) {
1174          add.AddSubtree(subtree);
1175        }
1176        MergeVariablesInSum(add);
1177        if (add.Subtrees.Count() == 1) {
1178          return add.GetSubtree(0);
1179        } else {
1180          return add;
1181        }
1182      } else {
1183        var add = addSymbol.CreateTreeNode();
1184        add.AddSubtree(a);
1185        add.AddSubtree(b);
1186        MergeVariablesInSum(add);
1187        if (add.Subtrees.Count() == 1) {
1188          return add.GetSubtree(0);
1189        } else {
1190          return add;
1191        }
1192      }
1193    }
1194
1195    // makes sure variable symbols in sums are combined
1196    private static void MergeVariablesInSum(ISymbolicExpressionTreeNode sum) {
1197      var subtrees = new List<ISymbolicExpressionTreeNode>(sum.Subtrees);
1198      while (sum.Subtrees.Any()) sum.RemoveSubtree(0);
1199      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
1200                            where node.SubtreeCount == 0
1201                            group node by GroupId(node) into g
1202                            select g;
1203      var constant = (from node in subtrees.OfType<ConstantTreeNode>()
1204                      select node.Value).DefaultIfEmpty(0.0).Sum();
1205      var unchangedSubtrees = subtrees.Where(t => t.SubtreeCount > 0 || !(t is IVariableTreeNode) && !(t is ConstantTreeNode));
1206
1207      foreach (var variableNodeGroup in groupedVarNodes) {
1208        var firstNode = variableNodeGroup.First();
1209        if (firstNode is VariableTreeNodeBase) {
1210          var representative = firstNode as VariableTreeNodeBase;
1211          var weightSum = variableNodeGroup.Cast<VariableTreeNodeBase>().Select(t => t.Weight).Sum();
1212          representative.Weight = weightSum;
1213          sum.AddSubtree(representative);
1214        } else if (firstNode is FactorVariableTreeNode) {
1215          var representative = firstNode as FactorVariableTreeNode;
1216          foreach (var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
1217            for (int j = 0; j < representative.Weights.Length; j++) {
1218              representative.Weights[j] += node.Weights[j];
1219            }
1220          }
1221          sum.AddSubtree(representative);
1222        }
1223      }
1224      foreach (var unchangedSubtree in unchangedSubtrees)
1225        sum.AddSubtree(unchangedSubtree);
1226      if (constant != 0.0) {
1227        sum.AddSubtree(MakeConstant(constant));
1228      }
1229    }
1230
1231    // nodes referencing variables can be grouped if they have
1232    private static string GroupId(IVariableTreeNode node) {
1233      var binaryFactorNode = node as BinaryFactorVariableTreeNode;
1234      var factorNode = node as FactorVariableTreeNode;
1235      var variableNode = node as VariableTreeNode;
1236      var laggedVarNode = node as LaggedVariableTreeNode;
1237      if (variableNode != null) {
1238        return "var " + variableNode.VariableName;
1239      } else if (binaryFactorNode != null) {
1240        return "binfactor " + binaryFactorNode.VariableName + " " + binaryFactorNode.VariableValue;
1241      } else if (factorNode != null) {
1242        return "factor " + factorNode.VariableName;
1243      } else if (laggedVarNode != null) {
1244        return "lagged " + laggedVarNode.VariableName + " " + laggedVarNode.Lag;
1245      } else {
1246        throw new NotSupportedException();
1247      }
1248    }
1249
1250
1251    private static ISymbolicExpressionTreeNode MakeProduct(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1252      if (IsConstant(a) && IsConstant(b)) {
1253        // fold constants
1254        return MakeConstant(((ConstantTreeNode)a).Value * ((ConstantTreeNode)b).Value);
1255      } else if (IsConstant(a)) {
1256        // a * $ => $ * a
1257        return MakeProduct(b, a);
1258      } else if (IsFactor(a) && IsFactor(b) && AreSameTypeAndVariable(a, b)) {
1259        var node0 = a as FactorVariableTreeNode;
1260        var node1 = b as FactorVariableTreeNode;
1261        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Zip(node1.Weights, (u, v) => u * v));
1262      } else if (IsBinFactor(a) && IsBinFactor(b) && AreSameTypeAndVariable(a, b)) {
1263        var node0 = a as BinaryFactorVariableTreeNode;
1264        var node1 = b as BinaryFactorVariableTreeNode;
1265        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Weight);
1266      } else if (IsFactor(a) && IsConstant(b)) {
1267        var node0 = a as FactorVariableTreeNode;
1268        var node1 = b as ConstantTreeNode;
1269        return MakeFactor(node0.Symbol, node0.VariableName, node0.Weights.Select(w => w * node1.Value));
1270      } else if (IsBinFactor(a) && IsConstant(b)) {
1271        var node0 = a as BinaryFactorVariableTreeNode;
1272        var node1 = b as ConstantTreeNode;
1273        return MakeBinFactor(node0.Symbol, node0.VariableName, node0.VariableValue, node0.Weight * node1.Value);
1274      } else if (IsBinFactor(a) && IsFactor(b)) {
1275        return MakeProduct(b, a);
1276      } else if (IsFactor(a) && IsBinFactor(b) &&
1277        ((IVariableTreeNode)a).VariableName == ((IVariableTreeNode)b).VariableName) {
1278        var node0 = a as FactorVariableTreeNode;
1279        var node1 = b as BinaryFactorVariableTreeNode;
1280        var varValues = node0.Symbol.GetVariableValues(node0.VariableName).ToArray();
1281        var wi = Array.IndexOf(varValues, node1.VariableValue);
1282        if (wi < 0) throw new ArgumentException();
1283        return MakeBinFactor(node1.Symbol, node1.VariableName, node1.VariableValue, node1.Weight * node0.Weights[wi]);
1284      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value == 1.0) {
1285        // $ * 1.0 => $
1286        return a;
1287      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value == 0.0) {
1288        return MakeConstant(0);
1289      } else if (IsConstant(b) && IsVariableBase(a)) {
1290        // multiply constants into variables weights
1291        ((VariableTreeNodeBase)a).Weight *= ((ConstantTreeNode)b).Value;
1292        return a;
1293      } else if (IsConstant(b) && IsAddition(a) ||
1294          IsFactor(b) && IsAddition(a) ||
1295          IsBinFactor(b) && IsAddition(a)) {
1296        // multiply constants into additions
1297        return a.Subtrees.Select(x => MakeProduct(GetSimplifiedTree(x), GetSimplifiedTree(b))).Aggregate((c, d) => MakeSum(c, d));
1298      } else if (IsDivision(a) && IsDivision(b)) {
1299        // (a1 / a2) * (b1 / b2) => (a1 * b1) / (a2 * b2)
1300        return MakeFraction(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)), MakeProduct(a.GetSubtree(1), b.GetSubtree(1)));
1301      } else if (IsDivision(a)) {
1302        // (a1 / a2) * b => (a1 * b) / a2
1303        return MakeFraction(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
1304      } else if (IsDivision(b)) {
1305        // a * (b1 / b2) => (b1 * a) / b2
1306        return MakeFraction(MakeProduct(b.GetSubtree(0), a), b.GetSubtree(1));
1307      } else if (IsMultiplication(a) && IsMultiplication(b)) {
1308        // merge multiplications (make sure constants are merged)
1309        var mul = mulSymbol.CreateTreeNode();
1310        for (int i = 0; i < a.Subtrees.Count(); i++) mul.AddSubtree(a.GetSubtree(i));
1311        for (int i = 0; i < b.Subtrees.Count(); i++) mul.AddSubtree(b.GetSubtree(i));
1312        MergeVariablesAndConstantsInProduct(mul);
1313        return mul;
1314      } else if (IsMultiplication(b)) {
1315        return MakeProduct(b, a);
1316      } else if (IsMultiplication(a)) {
1317        // a is already an multiplication => append b
1318        a.AddSubtree(GetSimplifiedTree(b));
1319        MergeVariablesAndConstantsInProduct(a);
1320        return a;
1321      } else if (IsAbsolute(a) && IsAbsolute(b)) {
1322        return MakeAbs(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)));
1323      } else if (IsAbsolute(a) && IsConstant(b)) {
1324        var constNode = b as ConstantTreeNode;
1325        var posF = Math.Abs(constNode.Value);
1326        if (constNode.Value > 0) {
1327          return MakeAbs(MakeProduct(a.GetSubtree(0), MakeConstant(posF)));
1328        } else {
1329          var mul = mulSymbol.CreateTreeNode();
1330          mul.AddSubtree(MakeAbs(MakeProduct(a.GetSubtree(0), MakeConstant(posF))));
1331          mul.AddSubtree(MakeConstant(-1.0));
1332          return mul;
1333        }
1334      } else if (IsAnalyticalQuotient(a)) {
1335        return MakeAnalyticalQuotient(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
1336      } else {
1337        var mul = mulSymbol.CreateTreeNode();
1338        mul.AddSubtree(a);
1339        mul.AddSubtree(b);
1340        MergeVariablesAndConstantsInProduct(mul);
1341        return mul;
1342      }
1343    }
1344
1345    #endregion
1346
1347    #region helper functions
1348
1349    private static bool ContainsVariableCondition(ISymbolicExpressionTreeNode node) {
1350      if (node.Symbol is VariableCondition) return true;
1351      foreach (var subtree in node.Subtrees)
1352        if (ContainsVariableCondition(subtree)) return true;
1353      return false;
1354    }
1355
1356    private static ISymbolicExpressionTreeNode AddLagToDynamicNodes(ISymbolicExpressionTreeNode node, int lag) {
1357      var laggedTreeNode = node as ILaggedTreeNode;
1358      var variableNode = node as VariableTreeNode;
1359      var variableConditionNode = node as VariableConditionTreeNode;
1360      if (laggedTreeNode != null)
1361        laggedTreeNode.Lag += lag;
1362      else if (variableNode != null) {
1363        var laggedVariableNode = (LaggedVariableTreeNode)laggedVariableSymbol.CreateTreeNode();
1364        laggedVariableNode.Lag = lag;
1365        laggedVariableNode.VariableName = variableNode.VariableName;
1366        return laggedVariableNode;
1367      } else if (variableConditionNode != null) {
1368        throw new NotSupportedException("Removal of time lags around variable condition symbols is not allowed.");
1369      }
1370      var subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
1371      while (node.SubtreeCount > 0) node.RemoveSubtree(0);
1372      foreach (var subtree in subtrees) {
1373        node.AddSubtree(AddLagToDynamicNodes(subtree, lag));
1374      }
1375      return node;
1376    }
1377
1378    private static bool AreSameTypeAndVariable(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
1379      return GroupId((IVariableTreeNode)a) == GroupId((IVariableTreeNode)b);
1380    }
1381
1382    // helper to combine the constant factors in products and to combine variables (powers of 2, 3...)
1383    private static void MergeVariablesAndConstantsInProduct(ISymbolicExpressionTreeNode prod) {
1384      var subtrees = new List<ISymbolicExpressionTreeNode>(prod.Subtrees);
1385      while (prod.Subtrees.Any()) prod.RemoveSubtree(0);
1386      var groupedVarNodes = from node in subtrees.OfType<IVariableTreeNode>()
1387                            where node.SubtreeCount == 0
1388                            group node by GroupId(node) into g
1389                            orderby g.Count()
1390                            select g;
1391      var constantProduct = (from node in subtrees.OfType<VariableTreeNodeBase>()
1392                             select node.Weight)
1393        .Concat(from node in subtrees.OfType<ConstantTreeNode>()
1394                select node.Value)
1395        .DefaultIfEmpty(1.0)
1396        .Aggregate((c1, c2) => c1 * c2);
1397
1398      var unchangedSubtrees = from tree in subtrees
1399                              where tree.SubtreeCount > 0 || !(tree is IVariableTreeNode) && !(tree is ConstantTreeNode)
1400                              select tree;
1401
1402      foreach (var variableNodeGroup in groupedVarNodes) {
1403        var firstNode = variableNodeGroup.First();
1404        if (firstNode is VariableTreeNodeBase) {
1405          var representative = (VariableTreeNodeBase)firstNode;
1406          representative.Weight = 1.0;
1407          if (variableNodeGroup.Count() > 1) {
1408            var poly = mulSymbol.CreateTreeNode();
1409            for (int p = 0; p < variableNodeGroup.Count(); p++) {
1410              poly.AddSubtree((ISymbolicExpressionTreeNode)representative.Clone());
1411            }
1412            prod.AddSubtree(poly);
1413          } else {
1414            prod.AddSubtree(representative);
1415          }
1416        } else if (firstNode is FactorVariableTreeNode) {
1417          var representative = (FactorVariableTreeNode)firstNode;
1418          foreach (var node in variableNodeGroup.Skip(1).Cast<FactorVariableTreeNode>()) {
1419            for (int j = 0; j < representative.Weights.Length; j++) {
1420              representative.Weights[j] *= node.Weights[j];
1421            }
1422          }
1423          for (int j = 0; j < representative.Weights.Length; j++) {
1424            representative.Weights[j] *= constantProduct;
1425          }
1426          constantProduct = 1.0;
1427          // if the product already contains a factor it is not necessary to multiply a constant below
1428          prod.AddSubtree(representative);
1429        }
1430      }
1431
1432      foreach (var unchangedSubtree in unchangedSubtrees)
1433        prod.AddSubtree(unchangedSubtree);
1434
1435      if (constantProduct != 1.0) {
1436        prod.AddSubtree(MakeConstant(constantProduct));
1437      }
1438    }
1439
1440
1441    /// <summary>
1442    /// x => x * -1
1443    /// Is only used in cases where it is not necessary to create new tree nodes. Manipulates x directly.
1444    /// </summary>
1445    /// <param name="x"></param>
1446    /// <returns>-x</returns>
1447    private static ISymbolicExpressionTreeNode Negate(ISymbolicExpressionTreeNode x) {
1448      if (IsConstant(x)) {
1449        ((ConstantTreeNode)x).Value *= -1;
1450      } else if (IsVariableBase(x)) {
1451        var variableTree = (VariableTreeNodeBase)x;
1452        variableTree.Weight *= -1.0;
1453      } else if (IsFactor(x)) {
1454        var factorNode = (FactorVariableTreeNode)x;
1455        for (int i = 0; i < factorNode.Weights.Length; i++) factorNode.Weights[i] *= -1;
1456      } else if (IsBinFactor(x)) {
1457        var factorNode = (BinaryFactorVariableTreeNode)x;
1458        factorNode.Weight *= -1;
1459      } else if (IsAddition(x)) {
1460        // (x0 + x1 + .. + xn) * -1 => (-x0 + -x1 + .. + -xn)       
1461        var subtrees = new List<ISymbolicExpressionTreeNode>(x.Subtrees);
1462        while (x.Subtrees.Any()) x.RemoveSubtree(0);
1463        foreach (var subtree in subtrees) {
1464          x.AddSubtree(Negate(subtree));
1465        }
1466      } else if (IsMultiplication(x) || IsDivision(x)) {
1467        // x0 * x1 * .. * xn * -1 => x0 * x1 * .. * -xn
1468        var lastSubTree = x.Subtrees.Last();
1469        x.RemoveSubtree(x.SubtreeCount - 1);
1470        x.AddSubtree(Negate(lastSubTree)); // last is maybe a constant, prefer to negate the constant
1471      } else {
1472        // any other function
1473        return MakeProduct(x, MakeConstant(-1));
1474      }
1475      return x;
1476    }
1477
1478    /// <summary>
1479    /// x => 1/x
1480    /// Must create new tree nodes
1481    /// </summary>
1482    /// <param name="x"></param>
1483    /// <returns></returns>
1484    private static ISymbolicExpressionTreeNode Invert(ISymbolicExpressionTreeNode x) {
1485      if (IsConstant(x)) {
1486        return MakeConstant(1.0 / ((ConstantTreeNode)x).Value);
1487      } else if (IsFactor(x)) {
1488        var factorNode = (FactorVariableTreeNode)x;
1489        return MakeFactor(factorNode.Symbol, factorNode.VariableName, factorNode.Weights.Select(w => 1.0 / w));
1490      } else if (IsDivision(x)) {
1491        return MakeFraction(x.GetSubtree(1), x.GetSubtree(0));
1492      } else {
1493        // any other function
1494        return MakeFraction(MakeConstant(1), x);
1495      }
1496    }
1497
1498    private static ISymbolicExpressionTreeNode MakeConstant(double value) {
1499      ConstantTreeNode constantTreeNode = (ConstantTreeNode)(constSymbol.CreateTreeNode());
1500      constantTreeNode.Value = value;
1501      return constantTreeNode;
1502    }
1503
1504    private static ISymbolicExpressionTreeNode MakeFactor(FactorVariable sy, string variableName, IEnumerable<double> weights) {
1505      var tree = (FactorVariableTreeNode)sy.CreateTreeNode();
1506      tree.VariableName = variableName;
1507      tree.Weights = weights.ToArray();
1508      return tree;
1509    }
1510    private static ISymbolicExpressionTreeNode MakeBinFactor(BinaryFactorVariable sy, string variableName, string variableValue, double weight) {
1511      var tree = (BinaryFactorVariableTreeNode)sy.CreateTreeNode();
1512      tree.VariableName = variableName;
1513      tree.VariableValue = variableValue;
1514      tree.Weight = weight;
1515      return tree;
1516    }
1517
1518
1519    #endregion
1520  }
1521}
Note: See TracBrowser for help on using the repository browser.