Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14875 was 14875, checked in by pkimmesw, 7 years ago

#2665 BenchmarkSuite, all examples, partially tested, VectorExpressions added

File size: 9.9 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
6  using System.Diagnostics;
7
8  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
9
10  using Interpreter;
11
12  public interface IMutablePushProgram {
13    void SetAtIndex(int index, Expression expression);
14  }
15
16  [Serializable]
17  public sealed class PushProgram : Expression, IPooledObject, IMutablePushProgram {
18#if DEBUG
19    private const int StringRepresentationCountBeforeAggregate = 50;
20#else
21    private const int StringRepresentationCountBeforeAggregate = 10;
22#endif
23
24    private static readonly Expression[] EmptyExpressions = new Expression[0];
25    public static readonly PushProgram Empty = new PushProgram();
26
27    private const string Prefix = "(";
28    private const string PrefixReduced = "[";
29    private const string Postfix = ")";
30    private const string PostfixReduced = "]";
31    private const string Delimiter = " ";
32
33    private IReadOnlyList<Expression> expressions;
34
35    public PushProgram() : this(EmptyExpressions) {
36    }
37
38    public PushProgram(IReadOnlyList<Expression> expressions) {
39      this.expressions = expressions;
40    }
41
42    public bool IsEmpty { get { return Count == 0; } }
43    public int Count { get { return expressions.Count; } }
44
45    public IReadOnlyList<Expression> Expressions { get { return this.expressions; } }
46
47    public static PushProgram Create(IManagedPool<PushProgram> pool, IReadOnlyList<Expression> expressions) {
48      var program = pool.Get();
49      program.expressions = expressions;
50      return program;
51    }
52
53    void IPooledObject.Reset() {
54      expressions = null;
55      stringRepresentation = null;
56      depth = null;
57      treeIndex = null;
58      hashCode = null;
59    }
60
61    public static PushProgram Merge(IManagedPool<PushProgram> pool, IManagedPool<PooledList<Expression>> expressionListPool,
62      PushProgram first, Expression second) {
63      var program = pool.Get();
64      var list = expressionListPool.Get();
65
66      list.AddRange(first.Expressions);
67      list.Add(second);
68
69      program.expressions = list;
70
71      return program;
72    }
73
74    public static PushProgram Merge(IManagedPool<PushProgram> pool, IManagedPool<PooledList<Expression>> expressionListPool,
75      Expression first, PushProgram second) {
76      var program = pool.Get();
77      var list = expressionListPool.Get();
78
79      list.Add(first);
80      list.AddRange(second.Expressions);
81
82      program.expressions = list;
83
84      return program;
85    }
86
87    public static PushProgram Merge(IManagedPool<PushProgram> pool, IManagedPool<PooledList<Expression>> expressionListPool,
88      PushProgram first, PushProgram second) {
89      var program = pool.Get();
90      var list = expressionListPool.Get();
91
92      list.AddRange(first.Expressions);
93      list.AddRange(second.Expressions);
94
95      program.expressions = list;
96
97      return program;
98    }
99
100    public int IndexOf(Expression expression) {
101      var max = expressions.Count - 1;
102      for (var i = max; i >= 0; i--) {
103        if (expression.Equals(expressions[i])) return max - i;
104      }
105
106      return -1;
107    }
108
109    private string stringRepresentation;
110    public override string StringRepresentation
111    {
112      get
113      {
114        if (stringRepresentation == null) stringRepresentation = BuildString();
115        return stringRepresentation;
116      }
117    }
118
119
120    private int? depth;
121    public int Depth
122    {
123      get
124      {
125        if (depth == null) depth = CalcDepth();
126        return depth.Value;
127      }
128    }
129
130    private int[] treeIndex;
131    private int[] TreeIndex
132    {
133      get
134      {
135        if (treeIndex == null) treeIndex = BuildTreeIndex();
136        return treeIndex;
137      }
138    }
139
140    private int? hashCode;
141    public override int GetHashCode() {
142      if (hashCode == null) hashCode = HashExpressions();
143      return hashCode.Value;
144    }
145
146    void IMutablePushProgram.SetAtIndex(int index, Expression expression) {
147
148    }
149
150    public override bool Equals(object obj) {
151      if (ReferenceEquals(this, obj))
152        return true;
153
154      if (this.GetType() != obj.GetType())
155        return false;
156
157      var other = (PushProgram)obj;
158
159      return ReferenceEquals(expressions, other.expressions) ||
160             GetHashCode() == other.GetHashCode();
161    }
162
163    public bool Equals(PushProgram other) {
164      return ReferenceEquals(this, other) ||
165             ReferenceEquals(expressions, other.expressions) ||
166             GetHashCode() == other.GetHashCode();
167    }
168
169    public override bool Eval(IInternalPushInterpreter interpreter) {
170      interpreter.ExecStack.Push(this.expressions);
171      return true;
172    }
173
174    public override string ToString() {
175      return StringRepresentation;
176    }
177
178    /// <summary>
179    /// Returns the amount of elements in the whole tree
180    /// </summary>
181    /// <returns></returns>
182    public int TotalCount
183    {
184      get
185      {
186        return this.IsEmpty
187            ? 1
188            // + 1 because "this" is also counted
189            : TreeIndex[0] + 1;
190      }
191    }
192
193    public IEnumerable<Expression> DepthLast() {
194      foreach (var expr in this.expressions) {
195        if (expr.IsProgram)
196          foreach (var sub in ((PushProgram)expr).DepthLast())
197            yield return sub;
198        else yield return expr;
199      }
200    }
201
202    public PushProgram Copy() {
203      if (IsEmpty) return this;
204
205      return new PushProgram(expressions) {
206        stringRepresentation = stringRepresentation,
207        hashCode = hashCode,
208        depth = depth,
209        treeIndex = treeIndex
210      };
211    }
212
213    public PushProgram Copy(IManagedPool<PushProgram> pool) {
214      if (IsEmpty) return this;
215
216      var program = pool.Get(reset: false);
217
218      program.expressions = expressions;
219      program.stringRepresentation = stringRepresentation;
220      program.hashCode = hashCode;
221      program.depth = depth;
222      program.treeIndex = treeIndex;
223
224      return program;
225    }
226
227    public IList<Expression> CopyExpressions() {
228      return new List<Expression>(this.expressions);
229    }
230
231    public IList<Expression> CopyExpressions(IManagedPool<PooledList<Expression>> expressionListPool) {
232      if (IsEmpty) return EmptyExpressions;
233
234      var copy = expressionListPool.Get();
235      copy.AddRange(this.expressions);
236
237      return copy;
238    }
239
240    private int CalcDepth() {
241      var maxDepth = 1;
242      for (var i = 0; i < Count; i++) {
243        var expression = this.expressions[i];
244        if (!expression.IsProgram) continue;
245        var expandExpression = (PushProgram)expression;
246
247        if (expandExpression.Depth > maxDepth)
248          maxDepth = expandExpression.Depth;
249      }
250
251      return maxDepth + 1;
252    }
253
254    private string BuildString() {
255      // prevent too big string
256      return TotalCount > StringRepresentationCountBeforeAggregate
257        ? PrefixReduced + Count + PostfixReduced
258        : Prefix + string.Join(Delimiter, expressions) + Postfix;
259    }
260
261    private int[] BuildTreeIndex() {
262      var local_treeIndex = new int[Count];
263
264      var next = 1;
265
266      for (var i = Count - 1; i >= 0; i--) {
267        var subExpression = this.expressions[i];
268
269        local_treeIndex[i] = next;
270
271        if (subExpression.IsProgram) {
272          next += ((PushProgram)subExpression).TotalCount;
273        } else {
274          next++;
275        }
276      }
277
278      return local_treeIndex;
279    }
280
281    private int HashExpressions() {
282      var hash = 19 * 31 + typeof(PushProgram).GetHashCode();
283
284      for (var i = 0; i < Count; i++) {
285        hash = hash * 31 + this.expressions[i].GetHashCode();
286      }
287
288      return hash;
289    }
290
291    private static void CheckIfNested(int level, PushProgram target, PushProgram current,
292        IList<PushProgram> visited) {
293      if (visited.Any(x => ReferenceEquals(x, current)))
294        Debugger.Break();
295
296      visited.Add(current);
297      if (level <= 0) {
298        // hierarchy depth > level
299        Debugger.Break();
300        return;
301      }
302
303      for (var i = 0; i < current.Count; i++) {
304        if (current.expressions[i].IsProgram)
305          continue;
306
307        var subExpression = current.expressions[i] as PushProgram;
308
309        if (ReferenceEquals(target, subExpression)) {
310          // Endless recursion dedected
311          Debugger.Break();
312        }
313
314        CheckIfNested(level - 1, target, subExpression, visited);
315      }
316
317      visited.RemoveAt(visited.Count - 1);
318    }
319
320    /// <summary>
321    ///     Returns the element with the given index whereby the tree is indexed in depth first manner
322    /// </summary>
323    /// <param name="index">The index of the required element</param>
324    /// <returns>The required element</returns>
325    public Expression GetFromTree(int index) {
326      return GetFromTree(index, (root, parent, child, childIndex, parentIndex) => child);
327    }
328
329    /// <returns>The required element</returns>
330    public T GetFromTree<T>(int index,
331        Func<PushProgram, PushProgram, Expression, int, int, T> resolver) {
332      return GetFromTree(index, 0, null, resolver);
333    }
334
335    private T GetFromTree<T>(int index, int parentIndex, PushProgram parent,
336        Func<PushProgram, PushProgram, Expression, int, int, T> resolver) {
337      if (index == 0) return resolver(parent, parent, this, 0, parentIndex);
338
339      var min = Count - 1;
340      var max = 0;
341      var mid = (min + max) / 2;
342
343      while ((max <= min) && (TreeIndex[mid] != index)) {
344        if (TreeIndex[mid] > index) max = mid + 1;
345        else min = mid - 1;
346
347        mid = (min + max) / 2;
348      }
349
350      return TreeIndex[mid] == index
351          ? resolver(parent, this, this.expressions[mid], mid, parentIndex)
352          : (this.expressions[mid + 1] as PushProgram).GetFromTree(index - TreeIndex[mid + 1], mid + 1,
353              this, resolver);
354    }
355  }
356}
Note: See TracBrowser for help on using the repository browser.