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

using System.Collections.Generic;

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

  public class PushProgram {

    private const string Prefix = "(";
    private const string PrefixReduced = "[";
    private const string Postfix = ")";
    private const string PostfixReduced = "]";
    private const string Delimiter = " ";

    public readonly IReadOnlyList<Expression> Expressions;
    public readonly bool IsEmpty;

    private readonly Lazy<int> depth;
    private readonly Lazy<int[]> treeIndex;
    private readonly Lazy<int> hashCode;
    private readonly Lazy<string> stringRepresentation;

    public PushProgram(Expression[] expressions) {
      this.Expressions = expressions;
      this.IsEmpty = expressions.Length == 0;

      this.depth = new Lazy<int>(this.CalcDepth, true);
      this.treeIndex = new Lazy<int[]>(this.BuildTreeIndex, true);
      this.hashCode = new Lazy<int>(this.HashExpressions, true);
      this.stringRepresentation = new Lazy<string>(this.BuildString, true);
    }

    public int Depth { get { return depth.Value; } }
    public int[] TreeIndex { get { return treeIndex.Value; } }

    public override int GetHashCode() {
      return this.hashCode.Value;
    }

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

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

    public IEnumerable<Expression> DepthFirst() {
      foreach (var expr in this.Expressions) {
        if (expr.CanExpand) {
          var expandExpr = (ExecExpandExpression)expr;

          foreach (var sub in expandExpr.State.DepthFirst())
            yield return sub;
        } else yield return expr;
      }
    }

    public PushProgram Copy() {
      var copy = this.CopyExpressions();

      return new PushProgram(copy);
    }

    public Expression[] CopyExpressions() {
      var copy = new Expression[this.Expressions.Count];
      Array.Copy((Expression[])this.Expressions, copy, this.Expressions.Count);

      return copy;
    }

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

      ////return depth;

      var maxDepth = 1;
      for (var i = 0; i < Expressions.Count; i++) {
        var expression = Expressions[i];
        if (!expression.CanExpand) continue;
        var expandExpression = (ExecExpandExpression)expression;

        if (expandExpression.State.Depth > maxDepth)
          maxDepth = expandExpression.State.Depth;
      }

      return maxDepth + 1;
    }

    private string BuildString() {
      // prevent too big string
      return this.TotalCount > 50
        ? PrefixReduced + this.Expressions.Count + PostfixReduced
        : Prefix + string.Join(Delimiter, this.Expressions.Where(e => !string.IsNullOrWhiteSpace(e.StringRepresentation))) + Postfix;
    }

    private int[] BuildTreeIndex() {
      var TreeIndex = new int[this.Expressions.Count];

      var next = 1;

      for (var i = this.Expressions.Count - 1; i >= 0; i--) {
        var subExpression = this.Expressions[i];

        TreeIndex[i] = next;

        if (subExpression.CanExpand) {
          next += ((ExecExpandExpression)subExpression).State.TotalCount;
        } else {
          next++;
        }
      }

      return TreeIndex;
    }

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

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

      return hash;
    }

    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.Expressions.Count; i++) {
        if (current.State.Expressions[i].CanExpand)
          continue;

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

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

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

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