[14727] | 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 |
|
---|
[14730] | 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 |
|
---|
[14727] | 53 | public PushProgram(Expression[] expressions) {
|
---|
| 54 | this.Expressions = expressions;
|
---|
| 55 | this.IsEmpty = expressions.Length == 0;
|
---|
| 56 | }
|
---|
| 57 |
|
---|
| 58 |
|
---|
| 59 | public override int GetHashCode() {
|
---|
[14730] | 60 | return HashCode;
|
---|
[14727] | 61 | }
|
---|
| 62 |
|
---|
| 63 | public override string ToString() {
|
---|
[14730] | 64 | return this.StringRepresentation;
|
---|
[14727] | 65 | }
|
---|
| 66 |
|
---|
| 67 | /// <summary>
|
---|
| 68 | /// Returns the amount of elements in the whole tree
|
---|
| 69 | /// </summary>
|
---|
| 70 | /// <returns></returns>
|
---|
[14730] | 71 | public int TotalCount {
|
---|
| 72 | get {
|
---|
[14727] | 73 | return this.IsEmpty
|
---|
| 74 | ? 1
|
---|
[14730] | 75 | // + 1 because "this" is also counted
|
---|
| 76 | : TreeIndex[0] + 1;
|
---|
[14727] | 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() {
|
---|
[14730] | 133 | var local_treeIndex = new int[this.Expressions.Count];
|
---|
[14727] | 134 |
|
---|
| 135 | var next = 1;
|
---|
| 136 |
|
---|
| 137 | for (var i = this.Expressions.Count - 1; i >= 0; i--) {
|
---|
| 138 | var subExpression = this.Expressions[i];
|
---|
| 139 |
|
---|
[14730] | 140 | local_treeIndex[i] = next;
|
---|
[14727] | 141 |
|
---|
| 142 | if (subExpression.CanExpand) {
|
---|
| 143 | next += ((ExecExpandExpression)subExpression).State.TotalCount;
|
---|
| 144 | } else {
|
---|
| 145 | next++;
|
---|
| 146 | }
|
---|
| 147 | }
|
---|
| 148 |
|
---|
[14730] | 149 | return local_treeIndex;
|
---|
[14727] | 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 | }
|
---|