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

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

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

  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;

  using Interpreter;

  public interface IMutablePushProgram {
    void SetAtIndex(int index, Expression expression);
  }

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

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

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

    [Storable]
    private IReadOnlyList<Expression> expressions;

    public PushProgram() : this(EmptyExpressions) { }

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

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

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

    private string stringRepresentation;
    public override string StringRepresentation
    {
      get
      {
        if (stringRepresentation == null) stringRepresentation = BuildString();
        return stringRepresentation;
      }
    }


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

    private int[] treeIndex;
    private int[] TreeIndex
    {
      get
      {
        if (treeIndex == null) treeIndex = BuildTreeIndex();
        return treeIndex;
      }
    }

    private int? hashCode;
    public override int GetHashCode() {
      if (hashCode == null) hashCode = HashExpressions();
      return hashCode.Value;
    }

    void IMutablePushProgram.SetAtIndex(int index, Expression expression) {

    }

    public override bool Equals(object obj) {
      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;
    }

    /// <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 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 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 = 1;
      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 BuildString() {
      // prevent too big string
      return TotalCount > StringRepresentationCountBeforeAggregate
        ? PrefixReduced + Count + PostfixReduced
        : Prefix + string.Join(Delimiter, expressions) + Postfix;
    }

    private int[] BuildTreeIndex() {
      var local_treeIndex = new int[Count];

      var next = 1;

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

        local_treeIndex[i] = next;

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

      return local_treeIndex;
    }

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

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

      return hash;
    }

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