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 Expressions; public readonly bool IsEmpty; 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 { if (treeIndex == null) treeIndex = BuildTreeIndex(); return treeIndex; } } private int hashCode; private int HashCode { get { if (hashCode == default(int)) hashCode = HashExpressions(); return hashCode; } } public PushProgram(Expression[] expressions) { this.Expressions = expressions; this.IsEmpty = expressions.Length == 0; } public override int GetHashCode() { return HashCode; } public override string ToString() { return this.StringRepresentation; } /// /// Returns the amount of elements in the whole tree /// /// public int TotalCount { get { return this.IsEmpty ? 1 // + 1 because "this" is also counted : TreeIndex[0] + 1; } } public IEnumerable 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 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 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); } } }