source: branches/PushGP/HeuristicLab.Algorithms.PushGP/HeuristicLab.Algorithms.PushGP/Expressions/ExecExpressions.cs @ 14602

using System.Threading;

namespace HeuristicLab.Algorithms.PushGP.Expressions {
  using System;
  using System.Collections.Generic;
  using System.Diagnostics;
  using System.Linq;
  using System.Text;
  using Interpreter;

  public class ExecExpandExpression : WrapperExpression<Expression[]> {
    private const string Prefix = "( ";
    private const string PrefixReduced = "[";
    private const string Postfix = ")";
    private const string PostfixReduced = "]";
    private const string Delimiter = " ";

    public static readonly ExecExpandExpression Empty = new ExecExpandExpression();

    private readonly Lazy<string> _stringValue;
    private readonly int[] _treeIndex;
    public readonly int Depth;

    private readonly int _hashCode;

    public ExecExpandExpression(params Expression[] state) : base(state) {
      IsEmpty = State.Length == 0;

      Depth = CalcDepth();
      _treeIndex = BuildTreeIndex();
      _hashCode = HashExpressions();

      _stringValue = new Lazy<string>(BuildString, LazyThreadSafetyMode.ExecutionAndPublication);
    }

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

#if DEBUG

    private static void CheckIfNested(int level, ExecExpandExpression target, ExecExpandExpression current,
        IList<ExecExpandExpression> visited) {
      if (visited.Any(x => ReferenceEquals(x, current)))
        Debugger.Break();

      visited.Add(current);
      if (level <= 0) {
        // hirarchy depth > level
        Debugger.Break();
        return;
      }

      for (var i = 0; i < current.State.Length; i++) {
        if (current.State[i].GetType() != typeof(ExecExpandExpression))
          continue;

        var subExpression = current.State[i] as ExecExpandExpression;

        if (ReferenceEquals(target, subExpression)) {
          // Endless recursion dedected
          Debugger.Break();
        }

        CheckIfNested(level - 1, target, subExpression, visited);
      }

      visited.RemoveAt(visited.Count - 1);
    }

#endif

    public IReadOnlyList<Expression> Expressions
    {
      get { return State; }
    }

    public bool IsEmpty { get; private set; }

    /// <summary>
    /// Returns the amount of elements in the whole tree
    /// </summary>
    /// <returns></returns>
    public int TotalCount
    {
      get
      {
        return IsEmpty
            ? 1
            // + 1 because this is also counted
            : _treeIndex[0] + 1;
      }
    }

    public override string ToString() {
      return _stringValue.Value;
    }

    private int HashExpressions() {
      var hash = 19 * 31 + this.GetType().GetHashCode();

      for (var i = 0; i < this.State.Length; i++) {
        hash = hash * 31 + this.State[i].GetHashCode();
      }

      return hash;
    }

    protected override int CalcHashCode() {
      return _hashCode;
    }

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

    public Expression[] CopyExpressions() {
      var copy = new Expression[State.Length];
      Array.Copy(State, copy, State.Length);

      return copy;
    }

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

    private int CalcDepth() {
      var subExpressions = State.Where(e => e.GetType() == typeof(ExecExpandExpression));
      var depth = subExpressions.Any()
          ? subExpressions.Select(e => e as ExecExpandExpression).Max(e => e.Depth) + 1
          : 1;

      return depth;
    }

    private string BuildString() {
      // prevent stack overflow
      if (this.TotalCount > 50)
        return PrefixReduced + this.State.Length + PostfixReduced;

      var sb = new StringBuilder();

      sb.Append(Prefix);
      for (var i = this.State.Length - 1; i >= 0; i--) sb.Append(this.State[i] + Delimiter);
      sb.Append(Postfix);
      return sb.ToString();
    }

    private int[] BuildTreeIndex() {
      var treeIndex = new int[State.Length];

      var next = 1;

      for (var i = State.Length - 1; i >= 0; i--) {
        var subExpression = State[i];

        treeIndex[i] = next;

        if (subExpression.GetType() == typeof(ExecExpandExpression)) {
          next += (subExpression as ExecExpandExpression).TotalCount;
        } else {
          next++;
        }
      }

      return treeIndex;
    }

    /// <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.Length - 1;
      var max = 0;
      var mid = (min + max) / 2;

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

        mid = (min + max) / 2;
      }

      return _treeIndex[mid] == index
          ? resolver(parent, this, State[mid], mid, parentIndex)
          : (State[mid + 1] as ExecExpandExpression).GetFromTree(index - _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>
  public class ExecIfExpression : StatelessExpression {
    public ExecIfExpression() : base("EXEC.IF") {
    }

    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>
  public class ExecYExpression : StatelessExpression {
    public ExecYExpression() : base("EXEC.Y") {
    }

    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);
    }
  }

  /// <summary>
  ///     Removes the second item on the EXEC stack.
  /// </summary>
  public class ExecKExpression : StatelessExpression {
    public ExecKExpression() : base("EXEC.K") {
    }

    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>
  public class ExecSExpression : StatelessExpression {
    public ExecSExpression() : base("EXEC.S") {
    }

    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);
    }
  }
}