source: branches/PushGP/HeuristicLab.Algorithms.PushGP/HeuristicLab.Algorithms.PushGP/Generators/CodeGenerator.cs @ 14513

namespace HeuristicLab.Algorithms.PushGP.Generators {
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Threading;

  using HeuristicLab.Algorithms.PushGP.Data.Random;
  using HeuristicLab.Algorithms.PushGP.Expressions;
  using HeuristicLab.Core;
  using HeuristicLab.Random;

  /// <summary>
  ///     The following is the standard Push random code generation algorithm, which is used for the CODE.RAND instruction.
  ///     It may also be useful for the initialization of programs in evolutionary computation systems, and it is used for
  ///     this purpose in PushGP.
  ///     It produces a uniform distribution of sizes and what seems to be a reasonable distribution of shapes, in a
  ///     reasonable amount of time.
  /// </summary>
  /// <see cref="http://faculty.hampshire.edu/lspector/push3-description.html#RandomCode" />
  public static class CodeGenerator {
    private static readonly ThreadLocal<IRandom> random = RandomFactory.GetRandom();

    /// <summary>
    ///     Generates a random program with a given max size
    /// </summary>
    /// <param name="maxPoints"></param>
    /// <returns>Returns an ExpandExpression if maxPoints smaller or equal to Configuration.MaxProgramPoints and Noop otherwise</returns>
    public static ExecExpandExpression RandomProgram(int maxPoints, IDictionary<string, Expression> customExpressions = null) {
      var code = RandomCode(maxPoints, customExpressions).ToArray();

      return new ExecExpandExpression(code);
    }

    public static IEnumerable<Expression> RandomCode(int maxPoints, IDictionary<string, Expression> customExpressions = null) {
      var actualPoints = random.Value.Next(1, Math.Max(1, maxPoints));

      return RandomCodeWithSize(actualPoints, customExpressions);
    }

    private static IEnumerable<Expression> RandomCodeWithSize(
      int points,
      IDictionary<string, Expression> customExpressions = null) {
      if (points == 1) {
        var customCount = customExpressions == null ? 0 : customExpressions.Count - 1;
        var index = random.Value.Next(0, ExpressionTable.Count + customCount - 1);
        return new[] { CreateExpression(index, customExpressions) };
      }

      var sizesThisLevel = Decompose(points - 1, points - 1);
      return sizesThisLevel.SelectMany(size => RandomCodeWithSize(size, customExpressions)).Shuffle(random.Value);
    }

    private static IEnumerable<int> Decompose(int number, int maxParts) {
      if ((number == 1) || (maxParts == 1)) return new[] { number };
      var thisPart = random.Value.Next(1, number - 1);
      return new[] { thisPart }.Concat(Decompose(number - thisPart, maxParts - 1));
    }

    private static Expression CreateExpression(int index, IDictionary<string, Expression> customExpressions = null) {
      if ((index >= 0) && (index < ExpressionTable.Count)) return ExpressionTable.GetExpression(index);

      if (customExpressions == null) throw new IndexOutOfRangeException();
      return new NameDefineXExecExpression(customExpressions.ElementAt(index - (ExpressionTable.Count - 1)).Key);
    }
  }
}