Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2665 Merged ExecExpandExpression and PushProgram due to performance reasons, Tested managed object pooling

File size: 6.7 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 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}
Note: See TracBrowser for help on using the repository browser.