source: branches/3040_VectorBasedGP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/VectorTreeSimplifier.cs @ 17626

Last change on this file since 17626 was 17626, checked in by pfleck, 7 weeks ago

#3040 Unified simplification rules for vector aggregation functions.

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