source: addons/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/PushProgram.cs

using System;
using System.Collections.Generic;
using System.Linq;

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

  using Constants;
  using Data.Pool;
  using Extensions;

  using HeuristicLab.Common;

  using Interpreter;
  using Persistence.Default.CompositeSerializers.Storable;

  [Serializable]
  [StorableClass]
  public sealed class PushProgram : Expression, IPooledObject {
#if DEBUG
    private const int STRING_REPRESENTATION_COUNT_BEFORE_AGGREGATE = 10;
#else
    private const int STRING_REPRESENTATION_COUNT_BEFORE_AGGREGATE = 1;
#endif

    private static readonly Expression[] EmptyExpressions = new Expression[0];
    public static readonly PushProgram Empty = new PushProgram();

    private const string Prefix = PushEnvironment.ProgramStartSymbolStr + " ";
    private const string Postfix = " " + PushEnvironment.ProgramEndSymbolStr;
    private const string PrefixReduced = "|";
    private const string PostfixReduced = "|";
    private const string Delimiter = " ";

    [Storable]
    private IReadOnlyList<Expression> expressions;

    public PushProgram() : this(EmptyExpressions) { }

    [StorableConstructor]
    private PushProgram(bool deserializing) : this(EmptyExpressions) { }

    public PushProgram(IReadOnlyList<Expression> expressions) {
      this.expressions = expressions;
    }

    public PushProgram(PushProgram origin, Cloner cloner) {
      stringRepresentation = origin.stringRepresentation;
      hashCode = origin.hashCode;
      depth = origin.depth;
      treeIndex = origin.treeIndex;

      var expressionsCopy = new List<Expression>(origin.expressions.Count);
      for (var i = 0; i < origin.expressions.Count; i++) {
        expressionsCopy.Add(cloner.Clone(origin.expressions[i]));
      }

      expressions = expressionsCopy;
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new PushProgram(this, cloner);
    }

    public bool IsEmpty { get { return Count == 0; } }
    public int Count { get { return expressions.Count; } }

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

    public static PushProgram Create(IManagedPool<PushProgram> pool, IReadOnlyList<Expression> expressions) {
      var program = pool.Get();
      program.expressions = expressions;
      return program;
    }

    void IPooledObject.Reset() {
      expressions = null;
      stringRepresentation = null;
      depth = null;
      treeIndex = null;
      hashCode = null;
    }

    public static PushProgram Merge(IManagedPool<PushProgram> pool, IManagedPool<PooledList<Expression>> expressionListPool,
      PushProgram first, Expression second) {
      var program = pool.Get();
      var list = expressionListPool.Get();

      list.AddRange(first.Expressions);
      list.Add(second);

      program.expressions = list;

      return program;
    }

    public static PushProgram Merge(IManagedPool<PushProgram> pool, IManagedPool<PooledList<Expression>> expressionListPool,
      Expression first, PushProgram second) {
      var program = pool.Get();
      var list = expressionListPool.Get();

      list.Add(first);
      list.AddRange(second.Expressions);

      program.expressions = list;

      return program;
    }

    public static PushProgram Merge(IManagedPool<PushProgram> pool, IManagedPool<PooledList<Expression>> expressionListPool,
      PushProgram first, PushProgram second) {
      var program = pool.Get();
      var list = expressionListPool.Get();

      list.AddRange(first.Expressions);
      list.AddRange(second.Expressions);

      program.expressions = list;

      return program;
    }

    public int IndexOf(Expression expression) {
      var max = expressions.Count - 1;
      for (var i = max; i >= 0; i--) {
        if (expression.Equals(expressions[i])) return max - i;
      }

      return -1;
    }

    [NonSerialized]
    private string stringRepresentation;
    public override string StringRepresentation
    {
      get
      {
        return stringRepresentation ?? (stringRepresentation = BuildStringRepresentation());
      }
    }


    [NonSerialized]
    private int? depth;
    public int Depth
    {
      get
      {
        if (depth == null) depth = CalcDepth();
        return depth.Value;
      }
    }

    [NonSerialized]
    private int[] treeIndex;
    private int[] TreeIndex
    {
      get
      {
        return treeIndex ?? (treeIndex = BuildTreeIndex());
      }
    }

    [NonSerialized]
    private int? hashCode;
    [SuppressMessage("ReSharper", "NonReadonlyMemberInGetHashCode")]
    public override int GetHashCode() {
      if (hashCode == null) hashCode = expressions.HashCode();
      return hashCode.Value;
    }

    public override bool Equals(object obj) {
      if (obj == null)
        return false;

      if (ReferenceEquals(this, obj))
        return true;

      if (GetType() != obj.GetType())
        return false;

      var other = (PushProgram)obj;

      return ReferenceEquals(expressions, other.expressions) ||
             GetHashCode() == other.GetHashCode();
    }

    public bool Equals(PushProgram other) {
      return ReferenceEquals(this, other) ||
             ReferenceEquals(expressions, other.expressions) ||
             GetHashCode() == other.GetHashCode();
    }

    public override bool IsNoop(IInternalPushInterpreter interpreter) {
      return IsEmpty;
    }

    public override void Eval(IInternalPushInterpreter interpreter) {
      interpreter.ExecStack.Push(expressions);
    }

    public override string ToString() {
      return StringRepresentation;
    }

    [NonSerialized]
    private int? totalCount;

    /// <summary>
    /// Returns the amount of elements in the whole tree
    /// </summary>
    /// <returns></returns>
    public int TotalCount
    {
      get
      {
        if (totalCount == null) {
          totalCount = IsEmpty
            ? 1
            // + 1 because "this" is also counted
            : TreeIndex[0] + 1;
        }

        return totalCount.Value;
      }
    }

    [NonSerialized]
    private int? totalInstructionCount;
    /// <summary>
    /// Returns the amount of none program expressions
    /// </summary>
    /// <returns></returns>
    public int TotalInstructionCount
    {
      get
      {
        if (totalInstructionCount == null) {
          totalInstructionCount = 0;

          for (var i = 0; i < Count; i++) {
            var expression = expressions[i];

            totalInstructionCount += expression.IsProgram
              ? ((PushProgram)expression).TotalInstructionCount
              : 1;
          }
        }

        return totalInstructionCount.Value;
      }
    }

    [NonSerialized]
    private int? branches;
    /// <summary>
    /// Returns the amount of branches in the whole tree. Even an empty program represents at least one branch
    /// </summary>
    /// <returns></returns>
    public int Branches
    {
      get
      {
        if (branches == null) CountBranches();
        return branches.Value;
      }
    }

    private void CountBranches() {
      branches = 1;

      for (var i = 0; i < Count; i++) {
        var expression = expressions[i];

        if (!expression.IsProgram)
          continue;

        var program = (PushProgram)expression;
        branches += program.Branches;
      }
    }

    public IEnumerable<Expression> DepthLast() {
      foreach (var expr in expressions) {
        if (expr.IsProgram)
          foreach (var sub in ((PushProgram)expr).DepthLast())
            yield return sub;
        else yield return expr;
      }
    }

    public IReadOnlyList<Expression> Flatten() {
      var result = new List<Expression>();
      Flatten(result);
      return result;
    }

    private void Flatten(List<Expression> result) {
      result.AddRange(expressions);

      for (var i = 0; i < expressions.Count; i++) {
        var expr = expressions[i];
        if (expr.IsProgram) {
          ((PushProgram)expr).Flatten(result);
        }
      }
    }

    public PushProgram Copy() {
      if (IsEmpty) return this;

      return new PushProgram(expressions) {
        stringRepresentation = stringRepresentation,
        hashCode = hashCode,
        depth = depth,
        treeIndex = treeIndex
      };
    }

    public PushProgram Copy(IManagedPool<PushProgram> pool) {
      if (IsEmpty) return this;

      var program = pool.Get(reset: false);

      program.expressions = expressions;
      program.stringRepresentation = stringRepresentation;
      program.hashCode = hashCode;
      program.depth = depth;
      program.treeIndex = treeIndex;

      return program;
    }

    public IList<Expression> CopyExpressions() {
      return new List<Expression>(expressions);
    }

    public IList<Expression> CopyExpressions(IManagedPool<PooledList<Expression>> expressionListPool) {
      if (IsEmpty) return EmptyExpressions;

      var copy = expressionListPool.Get();
      copy.AddRange(expressions);

      return copy;
    }

    private int CalcDepth() {
      var maxDepth = 0;
      for (var i = 0; i < Count; i++) {
        var expression = expressions[i];
        if (!expression.IsProgram) continue;

        var expandExpression = (PushProgram)expression;
        if (expandExpression.Depth > maxDepth)
          maxDepth = expandExpression.Depth;
      }

      return maxDepth + 1;
    }

    private string BuildStringRepresentation() {
      // prevent too big string
      return Count > STRING_REPRESENTATION_COUNT_BEFORE_AGGREGATE
        ? PrefixReduced + Count + PostfixReduced
        : Prefix + string.Join(Delimiter, expressions.Reverse()) + Postfix;
    }

    private int[] BuildTreeIndex() {
      var localTreeIndex = new int[Count];
      var next = 1;

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

        localTreeIndex[i] = next;

        if (subExpression.IsProgram) {
          next += ((PushProgram)subExpression).TotalCount;
        } else {
          next++;
        }
      }

      return localTreeIndex;
    }

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

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

      for (var i = 0; i < current.Count; i++) {
        if (current.expressions[i].IsProgram)
          continue;

        var subExpression = current.expressions[i] as PushProgram;

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

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

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

    /// <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<PushProgram, PushProgram, Expression, int, int, T> resolver) {
      return GetFromTree(index, 0, null, resolver);
    }

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

      var min = Count - 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, expressions[mid], mid, parentIndex)
          : (expressions[mid + 1] as PushProgram).GetFromTree(index - TreeIndex[mid + 1], mid + 1,
              this, resolver);
    }
  }
}