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

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Algorithms.PushGP.Expressions;
using HeuristicLab.Algorithms.PushGP.Interpreter;
using HeuristicLab.Core;
using HeuristicLab.Random;

namespace HeuristicLab.Algorithms.PushGP.Generators
{
    /// <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 class CodeGenerator
    {
        private static IRandom random = new FastRandom();
        private readonly IInterpreter interpreter;

        public CodeGenerator(IInterpreter interpreter)
        {
            this.interpreter = interpreter;
        }

        /// <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 Expression RandomProgram(int maxPoints)
        {
            return ExecExpandExpression.TryCreate(interpreter.CodeGenerator.RandomCode(maxPoints).ToArray(), interpreter.Configuration);
        }

        public IEnumerable<Expression> RandomCode(int maxPoints)
        {
            var actualPoints = random.Next(1, Math.Max(1, maxPoints));

            return RandomCodeWithSize(actualPoints);
        }

        private IEnumerable<Expression> RandomCodeWithSize(int points)
        {
            if (points == 1)
            {
                var index = random.Next(0, ExpressionTable.Count + this.interpreter.CustomExpressions.Count - 2);
                return new[] { this.CreateExpression(index) };
            }
            else
            {
                var sizesThisLevel = Decompose(points - 1, points - 1);
                return sizesThisLevel.SelectMany(size => RandomCodeWithSize(size)).Shuffle(random);
            }
        }

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

        private Expression CreateExpression(int index)
        {
            return (index >= 0 && index < ExpressionTable.Count)
                ? ExpressionTable.GetExpression(index)
                : new NameDefineXExecExpression(this.interpreter.CustomExpressions.ElementAt(index - (ExpressionTable.Count - 1)).Key);
        }
    }
}