1 | using System.Collections.Generic;
|
---|
2 |
|
---|
3 | namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
|
---|
4 | using System;
|
---|
5 | using System.Diagnostics;
|
---|
6 | using System.Linq;
|
---|
7 |
|
---|
8 | public class PushProgram {
|
---|
9 |
|
---|
10 | private const string Prefix = "(";
|
---|
11 | private const string PrefixReduced = "[";
|
---|
12 | private const string Postfix = ")";
|
---|
13 | private const string PostfixReduced = "]";
|
---|
14 | private const string Delimiter = " ";
|
---|
15 |
|
---|
16 | public readonly IReadOnlyList<Expression> Expressions;
|
---|
17 | public readonly bool IsEmpty;
|
---|
18 |
|
---|
19 | private readonly Lazy<int> depth;
|
---|
20 | private readonly Lazy<int[]> treeIndex;
|
---|
21 | private readonly Lazy<int> hashCode;
|
---|
22 | private readonly Lazy<string> stringRepresentation;
|
---|
23 |
|
---|
24 | public PushProgram(Expression[] expressions) {
|
---|
25 | this.Expressions = expressions;
|
---|
26 | this.IsEmpty = expressions.Length == 0;
|
---|
27 |
|
---|
28 | this.depth = new Lazy<int>(this.CalcDepth, true);
|
---|
29 | this.treeIndex = new Lazy<int[]>(this.BuildTreeIndex, true);
|
---|
30 | this.hashCode = new Lazy<int>(this.HashExpressions, true);
|
---|
31 | this.stringRepresentation = new Lazy<string>(this.BuildString, true);
|
---|
32 | }
|
---|
33 |
|
---|
34 | public int Depth { get { return depth.Value; } }
|
---|
35 | public int[] TreeIndex { get { return treeIndex.Value; } }
|
---|
36 |
|
---|
37 | public override int GetHashCode() {
|
---|
38 | return this.hashCode.Value;
|
---|
39 | }
|
---|
40 |
|
---|
41 | public override string ToString() {
|
---|
42 | return this.stringRepresentation.Value;
|
---|
43 | }
|
---|
44 |
|
---|
45 | /// <summary>
|
---|
46 | /// Returns the amount of elements in the whole tree
|
---|
47 | /// </summary>
|
---|
48 | /// <returns></returns>
|
---|
49 | public int TotalCount
|
---|
50 | {
|
---|
51 | get
|
---|
52 | {
|
---|
53 | return this.IsEmpty
|
---|
54 | ? 1
|
---|
55 | // + 1 because "this" is also counted
|
---|
56 | : this.treeIndex.Value[0] + 1;
|
---|
57 | }
|
---|
58 | }
|
---|
59 |
|
---|
60 | public IEnumerable<Expression> DepthFirst() {
|
---|
61 | foreach (var expr in this.Expressions) {
|
---|
62 | if (expr.CanExpand) {
|
---|
63 | var expandExpr = (ExecExpandExpression)expr;
|
---|
64 |
|
---|
65 | foreach (var sub in expandExpr.State.DepthFirst())
|
---|
66 | yield return sub;
|
---|
67 | } else yield return expr;
|
---|
68 | }
|
---|
69 | }
|
---|
70 |
|
---|
71 | public PushProgram Copy() {
|
---|
72 | var copy = this.CopyExpressions();
|
---|
73 |
|
---|
74 | return new PushProgram(copy);
|
---|
75 | }
|
---|
76 |
|
---|
77 | public Expression[] CopyExpressions() {
|
---|
78 | var copy = new Expression[this.Expressions.Count];
|
---|
79 | Array.Copy((Expression[])this.Expressions, copy, this.Expressions.Count);
|
---|
80 |
|
---|
81 | return copy;
|
---|
82 | }
|
---|
83 |
|
---|
84 | private int CalcDepth() {
|
---|
85 | //var subExpressions = Expressions.Where(e => e.CanExpand);
|
---|
86 | //var depth = subExpressions.Any()
|
---|
87 | // ? subExpressions.Select(e => e as ExecExpandExpression).Max(e => e.State.Depth) + 1
|
---|
88 | // : 1;
|
---|
89 |
|
---|
90 | ////return depth;
|
---|
91 |
|
---|
92 | var maxDepth = 1;
|
---|
93 | for (var i = 0; i < Expressions.Count; i++) {
|
---|
94 | var expression = Expressions[i];
|
---|
95 | if (!expression.CanExpand) continue;
|
---|
96 | var expandExpression = (ExecExpandExpression)expression;
|
---|
97 |
|
---|
98 | if (expandExpression.State.Depth > maxDepth)
|
---|
99 | maxDepth = expandExpression.State.Depth;
|
---|
100 | }
|
---|
101 |
|
---|
102 | return maxDepth + 1;
|
---|
103 | }
|
---|
104 |
|
---|
105 | private string BuildString() {
|
---|
106 | // prevent too big string
|
---|
107 | return this.TotalCount > 50
|
---|
108 | ? PrefixReduced + this.Expressions.Count + PostfixReduced
|
---|
109 | : Prefix + string.Join(Delimiter, this.Expressions.Where(e => !string.IsNullOrWhiteSpace(e.StringRepresentation))) + Postfix;
|
---|
110 | }
|
---|
111 |
|
---|
112 | private int[] BuildTreeIndex() {
|
---|
113 | var TreeIndex = new int[this.Expressions.Count];
|
---|
114 |
|
---|
115 | var next = 1;
|
---|
116 |
|
---|
117 | for (var i = this.Expressions.Count - 1; i >= 0; i--) {
|
---|
118 | var subExpression = this.Expressions[i];
|
---|
119 |
|
---|
120 | TreeIndex[i] = next;
|
---|
121 |
|
---|
122 | if (subExpression.CanExpand) {
|
---|
123 | next += ((ExecExpandExpression)subExpression).State.TotalCount;
|
---|
124 | } else {
|
---|
125 | next++;
|
---|
126 | }
|
---|
127 | }
|
---|
128 |
|
---|
129 | return TreeIndex;
|
---|
130 | }
|
---|
131 |
|
---|
132 | private int HashExpressions() {
|
---|
133 | var hash = 19 * 31 + this.GetType().FullName.GetHashCode();
|
---|
134 |
|
---|
135 | for (var i = 0; i < this.Expressions.Count; i++) {
|
---|
136 | hash = hash * 31 + this.Expressions[i].GetHashCode();
|
---|
137 | }
|
---|
138 |
|
---|
139 | return hash;
|
---|
140 | }
|
---|
141 |
|
---|
142 | private static void CheckIfNested(int level, ExecExpandExpression target, ExecExpandExpression current,
|
---|
143 | IList<ExecExpandExpression> visited) {
|
---|
144 | if (visited.Any(x => ReferenceEquals(x, current)))
|
---|
145 | Debugger.Break();
|
---|
146 |
|
---|
147 | visited.Add(current);
|
---|
148 | if (level <= 0) {
|
---|
149 | // hirarchy depth > level
|
---|
150 | Debugger.Break();
|
---|
151 | return;
|
---|
152 | }
|
---|
153 |
|
---|
154 | for (var i = 0; i < current.State.Expressions.Count; i++) {
|
---|
155 | if (current.State.Expressions[i].CanExpand)
|
---|
156 | continue;
|
---|
157 |
|
---|
158 | var subExpression = current.State.Expressions[i] as ExecExpandExpression;
|
---|
159 |
|
---|
160 | if (ReferenceEquals(target, subExpression)) {
|
---|
161 | // Endless recursion dedected
|
---|
162 | Debugger.Break();
|
---|
163 | }
|
---|
164 |
|
---|
165 | CheckIfNested(level - 1, target, subExpression, visited);
|
---|
166 | }
|
---|
167 |
|
---|
168 | visited.RemoveAt(visited.Count - 1);
|
---|
169 | }
|
---|
170 | }
|
---|
171 | }
|
---|