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

using System.Collections.Generic;

namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
  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 static readonly PushProgram Empty = new PushProgram(new Expression[0]);

    public readonly IReadOnlyList<Expression> Expressions;
    public bool IsEmpty { get; private set; }

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

    private string stringRepresentation;
    private string StringRepresentation
    {
      get
      {
        if (string.IsNullOrEmpty(stringRepresentation))
          stringRepresentation = BuildString();
        return stringRepresentation;
      }
    }

    private int depth = -1;
    private int Depth
    {
      get
      {
        if (depth == -1) depth = CalcDepth();
        return depth;
      }
    }

    private int[] treeIndex = null;
    public int[] TreeIndex
    {
      get
      {
        return this.treeIndex ?? (this.treeIndex = this.BuildTreeIndex());
      }
    }

    private int hashCode;
    private int HashCode
    {
      get
      {
        if (hashCode == default(int)) hashCode = HashExpressions();
        return hashCode;
      }
    }

    public override int GetHashCode() {
      return HashCode;
    }

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

    /// <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
            : TreeIndex[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() {
      return IsEmpty ? this : new PushProgram((Expression[])Expressions) {
        stringRepresentation = this.stringRepresentation,
        hashCode = this.hashCode,
        depth = this.depth,
        treeIndex = this.treeIndex
      };
    }

    public Expression[] CopyExpressions() {
      var copy = new Expression[this.Expressions.Count];
      ((Expression[])this.Expressions).CopyTo(copy, 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 local_treeIndex = new int[this.Expressions.Count];

      var next = 1;

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

        local_treeIndex[i] = next;

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

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