1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Linq;
|
---|
4 |
|
---|
5 | namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
|
---|
6 | using System.Diagnostics;
|
---|
7 |
|
---|
8 | using Interpreter;
|
---|
9 |
|
---|
10 | public class PushProgram : StatefulExpression<Expression[]> {
|
---|
11 | public static readonly PushProgram Empty = new PushProgram();
|
---|
12 |
|
---|
13 | private const string Prefix = "(";
|
---|
14 | private const string PrefixReduced = "[";
|
---|
15 | private const string Postfix = ")";
|
---|
16 | private const string PostfixReduced = "]";
|
---|
17 | private const string Delimiter = " ";
|
---|
18 |
|
---|
19 | public readonly bool IsEmpty;
|
---|
20 |
|
---|
21 | public PushProgram(params Expression[] state) : base(state) {
|
---|
22 | IsEmpty = state.Length == 0;
|
---|
23 | }
|
---|
24 |
|
---|
25 | public PushProgram(IEnumerable<Expression> state) : this(state.ToArray()) {
|
---|
26 | // TODO: lazy evaluation of ToArray()
|
---|
27 | }
|
---|
28 |
|
---|
29 | private string stringRepresentation;
|
---|
30 | public override string StringRepresentation
|
---|
31 | {
|
---|
32 | get
|
---|
33 | {
|
---|
34 | if (string.IsNullOrEmpty(stringRepresentation))
|
---|
35 | stringRepresentation = BuildString();
|
---|
36 | return stringRepresentation;
|
---|
37 | }
|
---|
38 | }
|
---|
39 |
|
---|
40 | private int depth = -1;
|
---|
41 | public int Depth
|
---|
42 | {
|
---|
43 | get
|
---|
44 | {
|
---|
45 | if (depth == -1) depth = CalcDepth();
|
---|
46 | return depth;
|
---|
47 | }
|
---|
48 | }
|
---|
49 |
|
---|
50 | private int[] treeIndex;
|
---|
51 | private int[] TreeIndex
|
---|
52 | {
|
---|
53 | get
|
---|
54 | {
|
---|
55 | return treeIndex ?? (treeIndex = BuildTreeIndex());
|
---|
56 | }
|
---|
57 | }
|
---|
58 |
|
---|
59 | private int hashCode;
|
---|
60 | private int HashCode
|
---|
61 | {
|
---|
62 | get
|
---|
63 | {
|
---|
64 | if (hashCode == default(int)) hashCode = HashExpressions();
|
---|
65 | return hashCode;
|
---|
66 | }
|
---|
67 | }
|
---|
68 |
|
---|
69 | //public PushProgram Copy() {
|
---|
70 | // // as the empty list is a static stateless expression, no copy required
|
---|
71 | // return ReferenceEquals(this, Empty) || this.State.IsEmpty
|
---|
72 | // ? Empty
|
---|
73 | // : new PushProgram(this.State.Copy());
|
---|
74 | //}
|
---|
75 |
|
---|
76 | public override bool Eval(IPushInterpreter interpreter) {
|
---|
77 | interpreter.ExecStack.Push(this.State);
|
---|
78 | return true;
|
---|
79 | }
|
---|
80 |
|
---|
81 | public override int GetHashCode() {
|
---|
82 | return HashCode;
|
---|
83 | }
|
---|
84 |
|
---|
85 | public override string ToString() {
|
---|
86 | return this.StringRepresentation;
|
---|
87 | }
|
---|
88 |
|
---|
89 | /// <summary>
|
---|
90 | /// Returns the amount of elements in the whole tree
|
---|
91 | /// </summary>
|
---|
92 | /// <returns></returns>
|
---|
93 | public int TotalCount
|
---|
94 | {
|
---|
95 | get
|
---|
96 | {
|
---|
97 | return this.IsEmpty
|
---|
98 | ? 1
|
---|
99 | // + 1 because "this" is also counted
|
---|
100 | : TreeIndex[0] + 1;
|
---|
101 | }
|
---|
102 | }
|
---|
103 |
|
---|
104 | public IEnumerable<Expression> DepthFirst() {
|
---|
105 | foreach (var expr in this.State) {
|
---|
106 | if (expr.CanExpand) {
|
---|
107 | var expandExpr = (PushProgram)expr;
|
---|
108 |
|
---|
109 | foreach (var sub in expandExpr.DepthFirst())
|
---|
110 | yield return sub;
|
---|
111 | } else yield return expr;
|
---|
112 | }
|
---|
113 | }
|
---|
114 |
|
---|
115 | public PushProgram Copy() {
|
---|
116 | return IsEmpty ? this : new PushProgram(State) {
|
---|
117 | stringRepresentation = this.stringRepresentation,
|
---|
118 | hashCode = this.hashCode,
|
---|
119 | depth = this.depth,
|
---|
120 | treeIndex = this.treeIndex
|
---|
121 | };
|
---|
122 | }
|
---|
123 |
|
---|
124 | public Expression[] CopyExpressions()
|
---|
125 | {
|
---|
126 | if (IsEmpty) return Empty.State;
|
---|
127 |
|
---|
128 | var copy = new Expression[State.Length];
|
---|
129 | State.CopyTo(copy, 0);
|
---|
130 |
|
---|
131 | return copy;
|
---|
132 | }
|
---|
133 |
|
---|
134 | private int CalcDepth() {
|
---|
135 | var maxDepth = 1;
|
---|
136 | for (var i = 0; i < State.Length; i++) {
|
---|
137 | var expression = State[i];
|
---|
138 | if (!expression.CanExpand) continue;
|
---|
139 | var expandExpression = (PushProgram)expression;
|
---|
140 |
|
---|
141 | if (expandExpression.Depth > maxDepth)
|
---|
142 | maxDepth = expandExpression.Depth;
|
---|
143 | }
|
---|
144 |
|
---|
145 | return maxDepth + 1;
|
---|
146 | }
|
---|
147 |
|
---|
148 | private string BuildString() {
|
---|
149 | // prevent too big string
|
---|
150 | return this.TotalCount > 50
|
---|
151 | ? PrefixReduced + this.State.Length + PostfixReduced
|
---|
152 | : Prefix + string.Join(Delimiter, this.State.Where(e => !string.IsNullOrWhiteSpace(e.StringRepresentation))) + Postfix;
|
---|
153 | }
|
---|
154 |
|
---|
155 | private int[] BuildTreeIndex() {
|
---|
156 | var local_treeIndex = new int[State.Length];
|
---|
157 |
|
---|
158 | var next = 1;
|
---|
159 |
|
---|
160 | for (var i = State.Length - 1; i >= 0; i--) {
|
---|
161 | var subExpression = State[i];
|
---|
162 |
|
---|
163 | local_treeIndex[i] = next;
|
---|
164 |
|
---|
165 | if (subExpression.CanExpand) {
|
---|
166 | next += ((PushProgram)subExpression).TotalCount;
|
---|
167 | } else {
|
---|
168 | next++;
|
---|
169 | }
|
---|
170 | }
|
---|
171 |
|
---|
172 | return local_treeIndex;
|
---|
173 | }
|
---|
174 |
|
---|
175 | private int HashExpressions() {
|
---|
176 | var hash = 19 * 31 + this.GetType().FullName.GetHashCode();
|
---|
177 |
|
---|
178 | for (var i = 0; i < State.Length; i++) {
|
---|
179 | hash = hash * 31 + State[i].GetHashCode();
|
---|
180 | }
|
---|
181 |
|
---|
182 | return hash;
|
---|
183 | }
|
---|
184 |
|
---|
185 | private static void CheckIfNested(int level, PushProgram target, PushProgram current,
|
---|
186 | IList<PushProgram> visited) {
|
---|
187 | if (visited.Any(x => ReferenceEquals(x, current)))
|
---|
188 | Debugger.Break();
|
---|
189 |
|
---|
190 | visited.Add(current);
|
---|
191 | if (level <= 0) {
|
---|
192 | // hirarchy depth > level
|
---|
193 | Debugger.Break();
|
---|
194 | return;
|
---|
195 | }
|
---|
196 |
|
---|
197 | for (var i = 0; i < current.State.Length; i++) {
|
---|
198 | if (current.State[i].CanExpand)
|
---|
199 | continue;
|
---|
200 |
|
---|
201 | var subExpression = current.State[i] as PushProgram;
|
---|
202 |
|
---|
203 | if (ReferenceEquals(target, subExpression)) {
|
---|
204 | // Endless recursion dedected
|
---|
205 | Debugger.Break();
|
---|
206 | }
|
---|
207 |
|
---|
208 | CheckIfNested(level - 1, target, subExpression, visited);
|
---|
209 | }
|
---|
210 |
|
---|
211 | visited.RemoveAt(visited.Count - 1);
|
---|
212 | }
|
---|
213 |
|
---|
214 | /// <summary>
|
---|
215 | /// Returns the element with the given index whereby the tree is indexed in depth first manner
|
---|
216 | /// </summary>
|
---|
217 | /// <param name="index">The index of the required element</param>
|
---|
218 | /// <returns>The required element</returns>
|
---|
219 | public Expression GetFromTree(int index) {
|
---|
220 | return GetFromTree(index, (root, parent, child, childIndex, parentIndex) => child);
|
---|
221 | }
|
---|
222 |
|
---|
223 | /// <returns>The required element</returns>
|
---|
224 | public T GetFromTree<T>(int index,
|
---|
225 | Func<PushProgram, PushProgram, Expression, int, int, T> resolver) {
|
---|
226 | return GetFromTree(index, 0, null, resolver);
|
---|
227 | }
|
---|
228 |
|
---|
229 | private T GetFromTree<T>(int index, int parentIndex, PushProgram parent,
|
---|
230 | Func<PushProgram, PushProgram, Expression, int, int, T> resolver) {
|
---|
231 | if (index == 0) return resolver(parent, parent, this, 0, parentIndex);
|
---|
232 |
|
---|
233 | var min = State.Length - 1;
|
---|
234 | var max = 0;
|
---|
235 | var mid = (min + max) / 2;
|
---|
236 |
|
---|
237 | while ((max <= min) && (TreeIndex[mid] != index)) {
|
---|
238 | if (TreeIndex[mid] > index) max = mid + 1;
|
---|
239 | else min = mid - 1;
|
---|
240 |
|
---|
241 | mid = (min + max) / 2;
|
---|
242 | }
|
---|
243 |
|
---|
244 | return TreeIndex[mid] == index
|
---|
245 | ? resolver(parent, this, State[mid], mid, parentIndex)
|
---|
246 | : (State[mid + 1] as PushProgram).GetFromTree(index - TreeIndex[mid + 1], mid + 1,
|
---|
247 | this, resolver);
|
---|
248 | }
|
---|
249 | }
|
---|
250 | }
|
---|