source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/ExecExpressions.cs @ 14727

namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
  using System;
  using System.Collections.Generic;
  using System.Linq;

  using HeuristicLab.Problems.ProgramSynthesis.Push.Attributes;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Stack;

  using Interpreter;

  public class ExecExpandExpression : StatefullExpression<PushProgram> {
    public static readonly ExecExpandExpression Empty = new ExecExpandExpression();

    public ExecExpandExpression(PushProgram program)
      : base(program) {
    }

    public ExecExpandExpression(params Expression[] state) : this(new PushProgram(state)) {
    }

    public ExecExpandExpression(IEnumerable<Expression> state) : this(state.ToArray()) {
      // TODO: lazy evaluation of ToArray()
    }

    public override string StringRepresentation { get { return this.State.ToString(); } }

    public ExecExpandExpression Copy() {
      // as the empty list is a static stateless expression, no copy required
      return ReferenceEquals(this, Empty) || this.State.IsEmpty
        ? Empty
        : new ExecExpandExpression(this.State.Copy());
    }

    public override void Eval(IPushGpInterpreter interpreter) {
      interpreter.ExecStack.Push(this.State.Expressions);
    }

    /// <summary>
    ///     Returns the element with the given index whereby the tree is indexed in depth first manner
    /// </summary>
    /// <param name="index">The index of the required element</param>
    /// <returns>The required element</returns>
    public Expression GetFromTree(int index) {
      return GetFromTree(index, (root, parent, child, childIndex, parentIndex) => child);
    }

    /// <returns>The required element</returns>
    public T GetFromTree<T>(int index,
        Func<ExecExpandExpression, ExecExpandExpression, Expression, int, int, T> resolver) {
      return GetFromTree(index, 0, null, resolver);
    }

    private T GetFromTree<T>(int index, int parentIndex, ExecExpandExpression parent,
        Func<ExecExpandExpression, ExecExpandExpression, Expression, int, int, T> resolver) {
      if (index == 0) return resolver(parent, parent, this, 0, parentIndex);

      var min = State.Expressions.Count - 1;
      var max = 0;
      var mid = (min + max) / 2;

      while ((max <= min) && (this.State.TreeIndex[mid] != index)) {
        if (this.State.TreeIndex[mid] > index) max = mid + 1;
        else min = mid - 1;

        mid = (min + max) / 2;
      }

      return this.State.TreeIndex[mid] == index
          ? resolver(parent, this, State.Expressions[mid], mid, parentIndex)
          : (State.Expressions[mid + 1] as ExecExpandExpression).GetFromTree(index - this.State.TreeIndex[mid + 1], mid + 1,
              this, resolver);
    }
  }

  /// <summary>
  /// If the top item of the BOOLEAN stack is TRUE then this removes the second item on the EXEC stack, leaving the first
  /// item to be executed. If it is false then it removes the first item, leaving the second to be executed. This is similar to
  /// CODE.IF except that it operates on the EXEC stack. This acts as a NOOP unless there are at least two items on the EXEC stack and
  /// one item on the BOOLEAN stack.
  /// </summary>
  [PushExpression(StackType.Exec, "EXEC.IF")]
  public class ExecIfExpression : StatelessExpression {
    public override void Eval(IPushGpInterpreter interpreter) {
      // not enough arguments on stack
      if ((interpreter.BooleanStack.Count == 0) || (interpreter.ExecStack.Count < 2)) return;

      var condition = interpreter.BooleanStack.Pop();

      if (condition) interpreter.ExecStack.RemoveAt(interpreter.ExecStack.Count - 2);
      else interpreter.ExecStack.RemoveTop();
    }
  }

  /// <summary>
  ///     Inserts beneath the top item of the EXEC stack a new item of the form
  ///     "( EXEC.Y <TopItem> )".
  /// </summary>
  [PushExpression(StackType.Exec, "EXEC.Y")]
  public class ExecYExpression : StatelessExpression {
    public override void Eval(IPushGpInterpreter interpreter) {
      // not enough arguments on stack
      if (interpreter.ExecStack.Count == 0 ||
          interpreter.Configuration.MaxPointsInProgram < 2)
        return;

      var top = interpreter.ExecStack.Top;
      var result = new ExecExpandExpression(top, new ExecYExpression());

      //interpreter.ExecStack.Insert(interpreter.ExecStack.Count - 1, result);
      interpreter.ExecStack.SetTop(result);
      interpreter.ExecStack.Add(top);
    }
  }

  /// <summary>
  ///     Removes the second item on the EXEC stack.
  /// </summary>
  [PushExpression(StackType.Exec, "EXEC.K")]
  public class ExecKExpression : StatelessExpression {
    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.ExecStack.Count < 2) return;

      var top = interpreter.ExecStack.Pop();
      interpreter.ExecStack.SetTop(top);
    }
  }

  /// <summary>
  ///     Pops 3 items from the EXEC stack, which we will call A, B, and C
  ///     (with A being the first one popped). Then pushes a list containing B and C back onto the EXEC stack, followed by
  ///     another instance of C, followed by another instance of A.
  /// </summary>
  [PushExpression(StackType.Exec, "EXEC.S")]
  public class ExecSExpression : StatelessExpression {
    public override void Eval(IPushGpInterpreter interpreter) {
      if (interpreter.ExecStack.Count < 3) return;

      var expression = interpreter.ExecStack.Pop(2);
      var a = expression[1];
      var b = expression[0];
      var c = interpreter.ExecStack.Top;

      var newTop = new ExecExpandExpression(c, b);

      interpreter.ExecStack.SetTop(newTop);
      interpreter.ExecStack.Push(c, a);
    }
  }
}