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

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

  public class RandomSimplifier : ISimplifier {
    public int Trys { get; set; }

    public PushProgram Simplify(PushProgram program, IRandom random, Predicate<PushProgram> isBetter) {

      if (program.TotalCount == 1) {
        return isBetter(PushProgram.Empty) ? PushProgram.Empty : program;
      }

      var copy = program.Copy();
      var maxTries = Math.Min(Trys, program.TotalCount - 2);
      var successfulRemoves = 0;

      for (var i = 0; i < maxTries; i++) {
        var rndIndex = random.Next(1, program.TotalCount - 1 - successfulRemoves);
        var node = copy.GetFromTree(
          rndIndex,
          (super, parent, child, childIndex, parentIndex) => new {
            Super = super,
            Parent = parent,
            ChildIndex = childIndex,
            ParentIndex = parentIndex
          });

        var oldParentExpressions = node.Parent.State;
        var newParentExpressions = RemoveAt(oldParentExpressions, node.ChildIndex);
        var newParent = new PushProgram(newParentExpressions);

        var superExpressions = node.Super == null ? copy.State : node.Super.State;
        superExpressions[node.ParentIndex] = newParent;

        if (isBetter(copy)) {
          successfulRemoves++;
        } else {
          superExpressions[node.ParentIndex] = node.Parent;
        }
      }

      return copy;
    }

    private static T[] RemoveAt<T>(T[] source, int index) {
      var dest = new T[source.Length - 1];
      if (index > 0)
        Array.Copy(source, 0, dest, 0, index);

      if (index < source.Length - 1)
        Array.Copy(source, index + 1, dest, index, source.Length - index - 1);

      return dest;
    }
  }
}