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

Last change on this file since 14730 was 14730, checked in by mkommend, 5 years ago

#2665: Removed memory pressure from expressions.

File size: 5.1 KB
Line 
1using System.Collections.Generic;
2
3namespace 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}
Note: See TracBrowser for help on using the repository browser.