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