public override void CalculateImpactAndReplacementValues(ISymbolicDataAnalysisModel model, ISymbolicExpressionTreeNode node,
      IDataAnalysisProblemData problemData, IEnumerable<int> rows, out double impactValue, out double replacementValue, out double newQualityForImpactsCalculation,
      double qualityForImpactsCalculation = Double.NaN) {
      var classificationModel = (ISymbolicClassificationModel)model;
      var classificationProblemData = (IClassificationProblemData)problemData;

      if (double.IsNaN(qualityForImpactsCalculation))
        qualityForImpactsCalculation = CalculateQualityForImpacts(classificationModel, classificationProblemData, rows);

      replacementValue = CalculateReplacementValue(classificationModel, node, classificationProblemData, rows);
      var constantNode = new ConstantTreeNode(new Constant()) { Value = replacementValue };

      var cloner = new Cloner();
      var tempModel = cloner.Clone(classificationModel);
      var tempModelNode = (ISymbolicExpressionTreeNode)cloner.GetClone(node);

      var tempModelParentNode = tempModelNode.Parent;
      int i = tempModelParentNode.IndexOfSubtree(tempModelNode);
      tempModelParentNode.RemoveSubtree(i);
      tempModelParentNode.InsertSubtree(i, constantNode);

      OnlineCalculatorError errorState;
      var dataset = classificationProblemData.Dataset;
      var targetClassValues = dataset.GetDoubleValues(classificationProblemData.TargetVariable, rows);
      var estimatedClassValues = tempModel.GetEstimatedClassValues(dataset, rows);
      newQualityForImpactsCalculation = OnlineAccuracyCalculator.Calculate(targetClassValues, estimatedClassValues, out errorState);
      if (errorState != OnlineCalculatorError.None) newQualityForImpactsCalculation = 0.0;

      impactValue = qualityForImpactsCalculation - newQualityForImpactsCalculation;
    }

    public static void Create(IRandom random, ISymbolicExpressionTreeNode seedNode, int maxDepth) {
      // make sure it is possible to create a trees smaller than maxDepth
      if (seedNode.Grammar.GetMinimumExpressionDepth(seedNode.Symbol) > maxDepth)
        throw new ArgumentException("Cannot create trees of depth " + maxDepth + " or smaller because of grammar constraints.", "maxDepth");

      var arity = SampleArity(random, seedNode);
      // throw an exception if the seedNode happens to be a terminal, since in this case we cannot grow a tree
      if (arity <= 0)
        throw new ArgumentException("Cannot grow tree. Seed node shouldn't have arity zero.");

      var allowedSymbols = seedNode.Grammar.AllowedSymbols.Where(s => s.InitialFrequency > 0.0).ToList();

      for (var i = 0; i < arity; i++) {
        var possibleSymbols = allowedSymbols.Where(s => seedNode.Grammar.IsAllowedChildSymbol(seedNode.Symbol, s, i)).ToList();
        var weights = possibleSymbols.Select(s => s.InitialFrequency).ToList();

#pragma warning disable 612, 618
        var selectedSymbol = possibleSymbols.SelectRandom(weights, random);
#pragma warning restore 612, 618

        var tree = selectedSymbol.CreateTreeNode();
        if (tree.HasLocalParameters) tree.ResetLocalParameters(random);
        seedNode.AddSubtree(tree);
      }

      // Only iterate over the non-terminal nodes (those which have arity > 0)
      // Start from depth 2 since the first two levels are formed by the rootNode and the seedNode
      foreach (var subTree in seedNode.Subtrees)
        if (subTree.Grammar.GetMaximumSubtreeCount(subTree.Symbol) > 0)
          RecursiveCreate(random, subTree, 2, maxDepth);
    }

 public static void RenderNode(TextWriter writer, ISymbolicExpressionTreeNode node, string prefix) {
   string label = node.ToString();
   writer.Write(label);
   if (node.SubtreeCount > 0) {
     var padding = prefix + new string(' ', label.Length);
     for (int i = 0; i != node.SubtreeCount; ++i) {
       char connector, extender = ' ';
       if (i == 0) {
         if (node.SubtreeCount > 1) {
           connector = RenderChars.JunctionDown;
           extender = RenderChars.VerticalLine;
         } else {
           connector = RenderChars.HorizontalLine;
           extender = ' ';
         }
       } else {
         writer.Write(padding);
         if (i == node.SubtreeCount - 1) {
           connector = RenderChars.CornerRight;
           extender = ' ';
         } else {
           connector = RenderChars.JunctionRight;
           extender = RenderChars.VerticalLine;
         }
       }
       writer.Write(string.Concat(connector, RenderChars.HorizontalLine));
       var newPrefix = string.Concat(padding, extender, ' ');
       RenderNode(writer, node.GetSubtree(i), newPrefix);
     }
   } else
     writer.WriteLine();
 }

    /// <summary>
    /// Genotype-to-Phenotype mapper (iterative breath-first approach, by using a queue -> FIFO).
    /// </summary>
    /// <param name="startNode">first node of the tree with arity 1</param>
    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
    /// <param name="grammar">grammar to determine the allowed child symbols for each node</param>
    /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
    /// <param name="random">random number generator</param>
    private void MapBreathFirstIteratively(ISymbolicExpressionTreeNode startNode,
                                          IntegerVector genotype,
                                          ISymbolicExpressionGrammar grammar,
                                          int maxSubtreeCount, IRandom random) {

      Queue<Tuple<ISymbolicExpressionTreeNode, int>> queue
        = new Queue<Tuple<ISymbolicExpressionTreeNode, int>>(); // tuples of <node, arity>

      int genotypeIndex = 0;
      queue.Enqueue(new Tuple<ISymbolicExpressionTreeNode, int>(startNode, 1));

      while (queue.Count > 0) {

        Tuple<ISymbolicExpressionTreeNode, int> current = queue.Dequeue();

        // foreach subtree of the current node, create a new node and enqueue it, if it is no terminal node
        for (int i = 0; i < current.Item2; ++i) {

          if (genotypeIndex >= maxSubtreeCount) {
            // if all genomes were used, only add terminal nodes to the remaining subtrees
            current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
          } else {
            var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);
            int arity = SampleArity(random, newNode, grammar);

            current.Item1.AddSubtree(newNode);
            genotypeIndex++;
            if (arity > 0) {
              // new node has subtrees so enqueue the node 
              queue.Enqueue(new Tuple<ISymbolicExpressionTreeNode, int>(newNode, arity));
            }
          }
        }
      }
    }

    public static int CompareNodes(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
      var ta = a as SymbolicExpressionTreeTerminalNode;
      var tb = b as SymbolicExpressionTreeTerminalNode;

      if (ta == null)
        return tb == null ? String.CompareOrdinal(a.Symbol.Name, b.Symbol.Name) : -1;

      if (tb == null)
        return 1;

      // at this point we know a and b are both terminals
      var va = a as VariableTreeNode;
      var vb = b as VariableTreeNode;

      if (va != null)
        return vb == null ? -1 : CompareVariables(va, vb);

      if (vb != null)
        return 1;

      // at this point we know a and b are not variables
      var ca = a as ConstantTreeNode;
      var cb = b as ConstantTreeNode;

      if (ca != null && cb != null)
        return ca.Value.CompareTo(cb.Value);

      // for other unknown terminal types, compare strings
      return string.CompareOrdinal(a.ToString(), b.ToString());
    }

    public VariableNodeEditDialog(ISymbolicExpressionTreeNode node) {
      InitializeComponent();
      oldValueTextBox.TabStop = false; // cannot receive focus using tab key

      NewNode = (VariableTreeNode)node; // will throw an invalid cast exception if node is not of the correct type
      InitializeFields();
    }

    private string FormatRecursively(ISymbolicExpressionTreeNode node, int indentLength, ref int nodeId) {
      // save id of current node
      int currentNodeId = nodeId;
      // increment id for next node
      nodeId++;

      StringBuilder strBuilder = new StringBuilder();
      if (Indent) strBuilder.Append(' ', indentLength);

      // get label for node and map if necessary
      string nodeLabel = node.ToString();
      if (symbolNameMap.ContainsKey(nodeLabel)) {
        nodeLabel = symbolNameMap[nodeLabel];
      }

      strBuilder.Append("node" + currentNodeId + "[label=\"" + nodeLabel + "\"");
      // leaf nodes should have box shape
      if (node.SubtreeCount == 0) {
        strBuilder.AppendLine(", shape=\"box\"];");
      } else {
        strBuilder.AppendLine("];");
      }

      // internal nodes or leaf nodes?
      foreach (ISymbolicExpressionTreeNode subTree in node.Subtrees) {
        // add an edge 
        if (Indent) strBuilder.Append(' ', indentLength);
        strBuilder.AppendLine("node" + currentNodeId + " -- node" + nodeId + ";");
        // format the whole subtree
        strBuilder.Append(FormatRecursively(subTree, indentLength + 2, ref nodeId));
      }

      return strBuilder.ToString();
    }

 private void FormatRecursively(ISymbolicExpressionTreeNode node, StringBuilder strBuilder) {
   // TODO: adapt to interpreter semantics. The HL interpreter also allows Boolean operations on reals
   if (node.Subtrees.Any()) {
     if (node.Symbol is Addition) {
       FormatOperator(node, "+", strBuilder);
     } else if (node.Symbol is And) {
       FormatOperator(node, "&&", strBuilder);
     } else if (node.Symbol is Average) {
       FormatFunction(node, "Average", strBuilder);
     } else if (node.Symbol is Cosine) {
       FormatFunction(node, "Math.Cos", strBuilder);
     } else if (node.Symbol is Division) {
       FormatDivision(node, strBuilder);
     } else if (node.Symbol is Exponential) {
       FormatFunction(node, "Math.Exp", strBuilder);
     } else if (node.Symbol is GreaterThan) {
       FormatOperator(node, ">", strBuilder);
     } else if (node.Symbol is IfThenElse) {
       FormatFunction(node, "EvaluateIf", strBuilder);
     } else if (node.Symbol is LessThan) {
       FormatOperator(node, "<", strBuilder);
     } else if (node.Symbol is Logarithm) {
       FormatFunction(node, "Math.Log", strBuilder);
     } else if (node.Symbol is Multiplication) {
       FormatOperator(node, "*", strBuilder);
     } else if (node.Symbol is Not) {
       FormatOperator(node, "!", strBuilder);
     } else if (node.Symbol is Or) {
       FormatOperator(node, "||", strBuilder);
     } else if (node.Symbol is Xor) {
       FormatOperator(node, "^", strBuilder);
     } else if (node.Symbol is Sine) {
       FormatFunction(node, "Math.Sin", strBuilder);
     } else if (node.Symbol is Subtraction) {
       FormatSubtraction(node, strBuilder);
     } else if (node.Symbol is Tangent) {
       FormatFunction(node, "Math.Tan", strBuilder);
     } else if (node.Symbol is Square) {
       FormatSquare(node, strBuilder);
     } else if (node.Symbol is SquareRoot) {
       FormatFunction(node, "Math.Sqrt", strBuilder);
     } else if (node.Symbol is Power) {
       FormatFunction(node, "Math.Pow", strBuilder);
     } else if (node.Symbol is Root) {
       FormatRoot(node, strBuilder);
     } else {
       throw new NotSupportedException("Formatting of symbol: " + node.Symbol + " not supported for C# symbolic expression tree formatter.");
     }
   } else {
     if (node is VariableTreeNode) {
       var varNode = node as VariableTreeNode;
       strBuilder.AppendFormat("{0} * {1}", varNode.VariableName, varNode.Weight.ToString("g17", CultureInfo.InvariantCulture));
     } else if (node is ConstantTreeNode) {
       var constNode = node as ConstantTreeNode;
       strBuilder.Append(constNode.Value.ToString("g17", CultureInfo.InvariantCulture));
     } else {
       throw new NotSupportedException("Formatting of symbol: " + node.Symbol + " not supported for C# symbolic expression tree formatter.");
     }
   }
 }

 private string FormatRecursively(ISymbolicExpressionTreeNode node, int indentLength) {
   StringBuilder strBuilder = new StringBuilder();
   if (Indent) strBuilder.Append(' ', indentLength);
   if (node.Subtrees.Count() > 0) { // internal node
     strBuilder.Append("(");
     if (node.Symbol is Addition) {
       strBuilder.AppendLine("+");
     } else if (node.Symbol is And) {
       strBuilder.AppendLine("&&");
     } else if (node.Symbol is Average) {
       strBuilder.AppendLine("avg");
     } else if (node.Symbol is Cosine) {
       strBuilder.AppendLine("cos");
     } else if (node.Symbol is Division) {
       strBuilder.AppendLine("/");
     } else if (node.Symbol is Exponential) {
       strBuilder.AppendLine("exp");
     } else if (node.Symbol is GreaterThan) {
       strBuilder.AppendLine(">");
     } else if (node.Symbol is IfThenElse) {
       strBuilder.AppendLine("if");
     } else if (node.Symbol is LessThan) {
       strBuilder.AppendLine("<");
     } else if (node.Symbol is Logarithm) {
       strBuilder.AppendLine("ln");
     } else if (node.Symbol is Multiplication) {
       strBuilder.AppendLine("*");
     } else if (node.Symbol is Not) {
       strBuilder.AppendLine("!");
     } else if (node.Symbol is Or) {
       strBuilder.AppendLine("||");
     } else if (node.Symbol is Sine) {
       strBuilder.AppendLine("sin");
     } else if (node.Symbol is Subtraction) {
       strBuilder.AppendLine("-");
     } else if (node.Symbol is Tangent) {
       strBuilder.AppendLine("tan");
     } else {
       throw new NotSupportedException("Formatting of symbol: " + node.Symbol + " not supported for external evaluation.");
     }
     // each subtree expression on a new line
     // and closing ')' also on new line
     foreach (var subtree in node.Subtrees) {
       strBuilder.AppendLine(FormatRecursively(subtree, indentLength + 2));
     }
     if (Indent) strBuilder.Append(' ', indentLength);
     strBuilder.Append(")");
   } else {
     if (node is VariableTreeNode) {
       var varNode = node as VariableTreeNode;
       strBuilder.AppendFormat("(* {0} {1})", varNode.VariableName, varNode.Weight.ToString("g17", CultureInfo.InvariantCulture));
     } else if (node is ConstantTreeNode) {
       var constNode = node as ConstantTreeNode;
       strBuilder.Append(constNode.Value.ToString("g17", CultureInfo.InvariantCulture));
     } else {
       throw new NotSupportedException("Formatting of symbol: " + node.Symbol + " not supported for external evaluation.");
     }
   }
   return strBuilder.ToString();
 }

 private static string FormatRecursively(ISymbolicExpressionTreeNode node) {
   StringBuilder strBuilder = new StringBuilder();
   if (node.Subtrees.Count() > 0) {
     // node
     var symbol = node.Symbol as CFGSymbol;
     if (symbol != null) {
       var partsEnumerator = symbol.GetTerminalParts().GetEnumerator();
       var subtreeEnumerator = node.Subtrees.GetEnumerator();
       while (partsEnumerator.MoveNext() && subtreeEnumerator.MoveNext()) {
         strBuilder.Append(partsEnumerator.Current);
         strBuilder.Append(FormatRecursively(subtreeEnumerator.Current));
       }
       strBuilder.Append(partsEnumerator.Current);
     } else {
       // ProgramRoot or StartSymbol
       foreach (var subtree in node.Subtrees) {
         strBuilder.Append(FormatRecursively(subtree));
       }
     }
   } else {
     // leaf
     var symbol = node.Symbol as CFGSymbol;
     if (symbol != null) {
       var parts = symbol.GetTerminalParts();
       strBuilder.Append(parts.First());
     }
   }
   return strBuilder.ToString();
 }

    public static IEnumerable<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode subtree, SymbolicExpressionTreeNodeEqualityComparer comp) {
      var fragmentLength = subtree.GetLength();
      // below, we use ">=" for Match(n, subtree, comp) >= fragmentLength because in case of relaxed conditions, 
      // we can have multiple matches of the same node

      return root.IterateNodesBreadth().Where(n => n.GetLength() >= fragmentLength && Match(n, subtree, comp) == fragmentLength);
    }

 public string FormatOnlyExpression(ISymbolicExpressionTreeNode expressionNode) {
   var stringBuilder = new StringBuilder();
   stringBuilder.AppendLine("  for " + CurrentIndexVariable + " = 1:1:rows");
   stringBuilder.AppendLine("    estimated(" + CurrentIndexVariable + ") = " + FormatRecursively(expressionNode.GetSubtree(0)) + ";");
   stringBuilder.AppendLine("  end;");
   return stringBuilder.ToString();
 }

 public void SortSubtrees(ISymbolicExpressionTreeNode node) {
   if (node.SubtreeCount == 0) return;
   var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode> ?? node.Subtrees.ToList();
   if (IsSymmetric(node.Symbol)) {
     var comparer = new SymbolicExpressionTreeNodeComparer();
     subtrees.Sort(comparer);
   }
   foreach (var s in subtrees)
     SortSubtrees(s);
 }

    private void SwapVariableWithTree(VariableTreeNode variableNode, ISymbolicExpressionTreeNode treeNode) {
      var parent = variableNode.Parent;
      int index = parent.IndexOfSubtree(variableNode);
      parent.RemoveSubtree(index);

      if (!variableNode.Weight.IsAlmost(1.0))
        treeNode = CreateNodeFromWeight(treeNode, variableNode);

      parent.InsertSubtree(index, treeNode);
    }

 private static string FormatRecursively(ISymbolicExpressionTreeNode node) {
   StringBuilder strBuilder = new StringBuilder();
   if (node.Subtrees.Count() > 0) {
     // node
     foreach (var subtree in node.Subtrees) {
       strBuilder.Append(FormatRecursively(subtree));
     }
   } else {
     // leaf
     strBuilder.Append(node.ToString());
   }
   return strBuilder.ToString();
 }

 public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode other) {
   var a = node.IterateNodesPrefix().ToList();
   var b = other.IterateNodesPrefix().ToList();
   var list = new List<ISymbolicExpressionTreeNode>();
   for (int i = 0, j = 0; i < a.Count && j < b.Count; ++i, ++j) {
     var s1 = a[i].ToString();
     var s2 = b[j].ToString();
     if (s1 == s2) continue;
     list.Add(a[i]);
     // skip subtrees since the parents are already different
     i += a[i].SubtreeCount;
     j += b[j].SubtreeCount;
   }
   ISymbolicExpressionTreeNode result = list.Count > 0 ? LowestCommonAncestor(node, list) : null;
   return result;
 }

 ///<summary>
 /// Finds the longest common subsequence in quadratic time and linear space
 /// Variant of:
 /// D. S. Hirschberg. A linear space algorithm for or computing maximal common subsequences. 1975.
 /// http://dl.acm.org/citation.cfm?id=360861
 /// </summary>
 /// <returns>Number of pairs that were matched</returns>
 public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, ISymbolicExpressionTreeNodeSimilarityComparer comp) {
   if (!comp.Equals(a, b)) return 0;
   int m = a.SubtreeCount;
   int n = b.SubtreeCount;
   if (m == 0 || n == 0) return 1;
   var matrix = new int[m + 1, n + 1];
   for (int i = 1; i <= m; ++i) {
     var ai = a.GetSubtree(i - 1);
     for (int j = 1; j <= n; ++j) {
       var bj = b.GetSubtree(j - 1);
       int match = Match(ai, bj, comp);
       matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + match);
     }
   }
   return matrix[m, n] + 1;
 }

    /// <summary>
    /// Randomly returns a terminal node for the given <paramref name="parentNode"/>.
    /// (A terminal has got a minimum and maximum arity of 0.)
    /// </summary>
    /// <param name="parentNode">parent node for which a child node is returned randomly</param>
    /// <param name="grammar">grammar to determine the allowed child symbols for parentNode</param>
    /// <param name="random">random number generator</param>
    /// <returns>randomly chosen terminal node with arity 0 or null, if no terminal node exists</returns>
    protected ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode,
                                                                ISymbolicExpressionGrammar grammar,
                                                                IRandom random) {
      // only select specific symbols, which can be interpreted ...
      var possibleSymbolsList = (from s in grammar.GetAllowedChildSymbols(parentNode.Symbol)
                                 where s.InitialFrequency > 0.0
                                 where s.MaximumArity == 0
                                 where s.MinimumArity == 0
                                 select s).ToList();

      // no terminal node exists for the given parent node
      if (!possibleSymbolsList.Any()) return null;

      var newNode = possibleSymbolsList.SampleRandom(random).CreateTreeNode();
      if (newNode.HasLocalParameters) newNode.ResetLocalParameters(random);
      return newNode;
    }

    protected static double CalculateReplacementValue(ISymbolicExpressionTreeNode node, ISymbolicExpressionTree sourceTree, ISymbolicDataAnalysisExpressionTreeInterpreter interpreter,
      IDataset dataset, IEnumerable<int> rows) {
      //optimization: constant nodes return always the same value
      ConstantTreeNode constantNode = node as ConstantTreeNode;
      if (constantNode != null) return constantNode.Value;

      var rootSymbol = new ProgramRootSymbol().CreateTreeNode();
      var startSymbol = new StartSymbol().CreateTreeNode();
      rootSymbol.AddSubtree(startSymbol);
      startSymbol.AddSubtree((ISymbolicExpressionTreeNode)node.Clone());

      var tempTree = new SymbolicExpressionTree(rootSymbol);
      // clone ADFs of source tree
      for (int i = 1; i < sourceTree.Root.SubtreeCount; i++) {
        tempTree.Root.AddSubtree((ISymbolicExpressionTreeNode)sourceTree.Root.GetSubtree(i).Clone());
      }
      return interpreter.GetSymbolicExpressionTreeValues(tempTree, dataset, rows).Median();
    }

 private static IEnumerable<Instruction> Compile(ISymbolicExpressionTreeNode branch, Func<ISymbolicExpressionTreeNode, byte> opCodeMapper, IEnumerable<Func<Instruction, Instruction>> postInstructionCompiledHooks) {
   foreach (var node in branch.IterateNodesPrefix()) {
     Instruction instr = new Instruction();
     int subtreesCount = node.SubtreeCount;
     if (subtreesCount > 255) throw new ArgumentException("Number of subtrees is too big (>255)");
     instr.nArguments = (byte)subtreesCount;
     instr.opCode = opCodeMapper(node);
     if (node.Symbol is Argument) {
       var argNode = (ArgumentTreeNode)node;
       instr.data = (ushort)argNode.Symbol.ArgumentIndex;
     }
     instr.dynamicNode = node;
     foreach (var hook in postInstructionCompiledHooks) {
       instr = hook(instr);
     }
     yield return instr;
   }
 }