source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Simplifier/Simplifier.cs @ 14834

namespace HeuristicLab.Problems.ProgramSynthesis.Push.Simplifier {
  using System;

  using Expressions;

  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Tree;

  public static class Simplifier {
    private static readonly TreeNode<Expression> NoopNode =
      new TreeNode<Expression>(ExpressionTable.GetStatelessExpression<CodeNoopExpression>());

    public static PushProgram Simplify(PushProgram program, Func<PushProgram, double> evaluator) {
      var bestResult = evaluator(program);
      var tree = program.ToTree();
      var optimizedTree = RemoveUnnecessaryExpressions(tree, tree, ref bestResult, evaluator);

      return optimizedTree.ToPushProgram(e => !ReferenceEquals(e, NoopNode.Value));
    }

    private static TreeNode<Expression> RemoveUnnecessaryExpressions(Tree<Expression> program, TreeNode<Expression> node, ref double bestResult, Func<PushProgram, double> evaluator) {
      for (var i = 0; i < node.Children.Count; i++) {
        var child = node.Children[i];
        node.ReplaceNode(i, NoopNode);

        var currentProgram = program.ToPushProgram();
        var currentResult = evaluator(currentProgram);

        if (currentResult <= bestResult) {
          bestResult = currentResult;
        } else if (child.Value.IsProgram) {
          node.ReplaceNode(i, child);
          var subProgram = RemoveUnnecessaryExpressions(program, child, ref bestResult, evaluator);
          node.ReplaceNode(i, subProgram);
        } else {
          node.ReplaceNode(i, child);
        }
      }

      return node;
    }
  }
}