1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
4 | *
|
---|
5 | * This file is part of HeuristicLab.
|
---|
6 | *
|
---|
7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
8 | * it under the terms of the GNU General Public License as published by
|
---|
9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
10 | * (at your option) any later version.
|
---|
11 | *
|
---|
12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
15 | * GNU General Public License for more details.
|
---|
16 | *
|
---|
17 | * You should have received a copy of the GNU General Public License
|
---|
18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
19 | */
|
---|
20 | #endregion
|
---|
21 |
|
---|
22 | using System;
|
---|
23 | using System.Collections.Generic;
|
---|
24 | using System.Linq;
|
---|
25 | using HeuristicLab.Common;
|
---|
26 | using HeuristicLab.Core;
|
---|
27 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
28 |
|
---|
29 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
|
---|
30 | /// <summary>
|
---|
31 | /// The default symbolic expression grammar stores symbols and syntactic constraints for symbols.
|
---|
32 | /// Symbols are treated as equvivalent if they have the same name.
|
---|
33 | /// Syntactic constraints limit the number of allowed sub trees for a node with a symbol and which symbols are allowed
|
---|
34 | /// in the sub-trees of a symbol (can be specified for each sub-tree index separately).
|
---|
35 | /// </summary>
|
---|
36 | [StorableClass]
|
---|
37 | public abstract class SymbolicExpressionGrammarBase : NamedItem, ISymbolicExpressionGrammarBase {
|
---|
38 |
|
---|
39 | #region properties for separation between implementation and persistence
|
---|
40 | [Storable(Name = "Symbols")]
|
---|
41 | private IEnumerable<ISymbol> StorableSymbols {
|
---|
42 | get { return symbols.Values.ToArray(); }
|
---|
43 | set { symbols = value.ToDictionary(sym => sym.Name); }
|
---|
44 | }
|
---|
45 |
|
---|
46 | [Storable(Name = "SymbolSubtreeCount")]
|
---|
47 | private IEnumerable<KeyValuePair<ISymbol, Tuple<int, int>>> StorableSymbolSubtreeCount {
|
---|
48 | get { return symbolSubtreeCount.Select(x => new KeyValuePair<ISymbol, Tuple<int, int>>(GetSymbol(x.Key), x.Value)).ToArray(); }
|
---|
49 | set { symbolSubtreeCount = value.ToDictionary(x => x.Key.Name, x => x.Value); }
|
---|
50 | }
|
---|
51 |
|
---|
52 | [Storable(Name = "AllowedChildSymbols")]
|
---|
53 | private IEnumerable<KeyValuePair<ISymbol, IEnumerable<ISymbol>>> StorableAllowedChildSymbols {
|
---|
54 | get { return allowedChildSymbols.Select(x => new KeyValuePair<ISymbol, IEnumerable<ISymbol>>(GetSymbol(x.Key), x.Value.Select(GetSymbol).ToArray())).ToArray(); }
|
---|
55 | set { allowedChildSymbols = value.ToDictionary(x => x.Key.Name, x => x.Value.Select(y => y.Name).ToList()); }
|
---|
56 | }
|
---|
57 |
|
---|
58 | [Storable(Name = "AllowedChildSymbolsPerIndex")]
|
---|
59 | private IEnumerable<KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>> StorableAllowedChildSymbolsPerIndex {
|
---|
60 | get { return allowedChildSymbolsPerIndex.Select(x => new KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>(Tuple.Create<ISymbol, int>(GetSymbol(x.Key.Item1), x.Key.Item2), x.Value.Select(y => GetSymbol(y)).ToArray())).ToArray(); }
|
---|
61 | set { allowedChildSymbolsPerIndex = value.ToDictionary(x => Tuple.Create(x.Key.Item1.Name, x.Key.Item2), x => x.Value.Select(y => y.Name).ToList()); }
|
---|
62 | }
|
---|
63 | #endregion
|
---|
64 |
|
---|
65 | private bool suppressEvents;
|
---|
66 | protected Dictionary<string, ISymbol> symbols;
|
---|
67 | protected Dictionary<string, Tuple<int, int>> symbolSubtreeCount;
|
---|
68 | protected Dictionary<string, List<string>> allowedChildSymbols;
|
---|
69 | protected Dictionary<Tuple<string, int>, List<string>> allowedChildSymbolsPerIndex;
|
---|
70 |
|
---|
71 | public override bool CanChangeName {
|
---|
72 | get { return false; }
|
---|
73 | }
|
---|
74 | public override bool CanChangeDescription {
|
---|
75 | get { return false; }
|
---|
76 | }
|
---|
77 |
|
---|
78 | [StorableConstructor]
|
---|
79 | protected SymbolicExpressionGrammarBase(bool deserializing)
|
---|
80 | : base(deserializing) {
|
---|
81 | cachedMinExpressionLength = new Dictionary<string, int>();
|
---|
82 | cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
|
---|
83 | cachedMinExpressionDepth = new Dictionary<string, int>();
|
---|
84 | cachedMaxExpressionDepth = new Dictionary<string, int>();
|
---|
85 |
|
---|
86 | cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
|
---|
87 | cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
|
---|
88 |
|
---|
89 | suppressEvents = false;
|
---|
90 | }
|
---|
91 |
|
---|
92 | protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
|
---|
93 | : base(original, cloner) {
|
---|
94 | cachedMinExpressionLength = new Dictionary<string, int>();
|
---|
95 | cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
|
---|
96 | cachedMinExpressionDepth = new Dictionary<string, int>();
|
---|
97 | cachedMaxExpressionDepth = new Dictionary<string, int>();
|
---|
98 |
|
---|
99 | cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
|
---|
100 | cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
|
---|
101 |
|
---|
102 | symbols = original.symbols.ToDictionary(x => x.Key, y => cloner.Clone(y.Value));
|
---|
103 | symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>(original.symbolSubtreeCount);
|
---|
104 |
|
---|
105 | allowedChildSymbols = new Dictionary<string, List<string>>();
|
---|
106 | foreach (var element in original.allowedChildSymbols)
|
---|
107 | allowedChildSymbols.Add(element.Key, new List<string>(element.Value));
|
---|
108 |
|
---|
109 | allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
|
---|
110 | foreach (var element in original.allowedChildSymbolsPerIndex)
|
---|
111 | allowedChildSymbolsPerIndex.Add(element.Key, new List<string>(element.Value));
|
---|
112 |
|
---|
113 | suppressEvents = false;
|
---|
114 | }
|
---|
115 |
|
---|
116 | protected SymbolicExpressionGrammarBase(string name, string description)
|
---|
117 | : base(name, description) {
|
---|
118 | cachedMinExpressionLength = new Dictionary<string, int>();
|
---|
119 | cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
|
---|
120 | cachedMinExpressionDepth = new Dictionary<string, int>();
|
---|
121 | cachedMaxExpressionDepth = new Dictionary<string, int>();
|
---|
122 |
|
---|
123 | cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
|
---|
124 | cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
|
---|
125 |
|
---|
126 | symbols = new Dictionary<string, ISymbol>();
|
---|
127 | symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
|
---|
128 | allowedChildSymbols = new Dictionary<string, List<string>>();
|
---|
129 | allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
|
---|
130 |
|
---|
131 | suppressEvents = false;
|
---|
132 | }
|
---|
133 |
|
---|
134 | #region protected grammar manipulation methods
|
---|
135 | protected virtual void AddSymbol(ISymbol symbol) {
|
---|
136 | if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
|
---|
137 | foreach (var s in symbol.Flatten()) {
|
---|
138 | symbols.Add(s.Name, s);
|
---|
139 | int maxSubTreeCount = Math.Min(s.MinimumArity + 1, s.MaximumArity);
|
---|
140 | symbolSubtreeCount.Add(s.Name, Tuple.Create(s.MinimumArity, maxSubTreeCount));
|
---|
141 | }
|
---|
142 | ClearCaches();
|
---|
143 | }
|
---|
144 |
|
---|
145 | protected virtual void RemoveSymbol(ISymbol symbol) {
|
---|
146 | foreach (var s in symbol.Flatten()) {
|
---|
147 | symbols.Remove(s.Name);
|
---|
148 | allowedChildSymbols.Remove(s.Name);
|
---|
149 | for (int i = 0; i < GetMaximumSubtreeCount(s); i++)
|
---|
150 | allowedChildSymbolsPerIndex.Remove(Tuple.Create(s.Name, i));
|
---|
151 | symbolSubtreeCount.Remove(s.Name);
|
---|
152 |
|
---|
153 | foreach (var parent in Symbols) {
|
---|
154 | List<string> allowedChilds;
|
---|
155 | if (allowedChildSymbols.TryGetValue(parent.Name, out allowedChilds))
|
---|
156 | allowedChilds.Remove(s.Name);
|
---|
157 |
|
---|
158 | for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
|
---|
159 | if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, i), out allowedChilds))
|
---|
160 | allowedChilds.Remove(s.Name);
|
---|
161 | }
|
---|
162 | }
|
---|
163 | suppressEvents = true;
|
---|
164 | foreach (var groupSymbol in Symbols.OfType<GroupSymbol>())
|
---|
165 | groupSymbol.SymbolsCollection.Remove(symbol);
|
---|
166 | suppressEvents = false;
|
---|
167 | }
|
---|
168 | ClearCaches();
|
---|
169 | }
|
---|
170 |
|
---|
171 | public virtual ISymbol GetSymbol(string symbolName) {
|
---|
172 | ISymbol symbol;
|
---|
173 | if (symbols.TryGetValue(symbolName, out symbol)) return symbol;
|
---|
174 | return null;
|
---|
175 | }
|
---|
176 |
|
---|
177 | protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child) {
|
---|
178 | bool changed = false;
|
---|
179 |
|
---|
180 | foreach (ISymbol p in parent.Flatten().Where(p => !(p is GroupSymbol)))
|
---|
181 | changed |= AddAllowedChildSymbolToDictionaries(p, child);
|
---|
182 |
|
---|
183 | if (changed) {
|
---|
184 | ClearCaches();
|
---|
185 | OnChanged();
|
---|
186 | }
|
---|
187 | }
|
---|
188 |
|
---|
189 | private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child) {
|
---|
190 | List<string> childSymbols;
|
---|
191 | if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
|
---|
192 | childSymbols = new List<string>();
|
---|
193 | allowedChildSymbols.Add(parent.Name, childSymbols);
|
---|
194 | }
|
---|
195 | if (childSymbols.Contains(child.Name)) return false;
|
---|
196 |
|
---|
197 | suppressEvents = true;
|
---|
198 | for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++)
|
---|
199 | RemoveAllowedChildSymbol(parent, child, argumentIndex);
|
---|
200 | suppressEvents = false;
|
---|
201 |
|
---|
202 | childSymbols.Add(child.Name);
|
---|
203 | return true;
|
---|
204 | }
|
---|
205 |
|
---|
206 | protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
|
---|
207 | bool changed = false;
|
---|
208 |
|
---|
209 | foreach (ISymbol p in parent.Flatten().Where(p => !(p is GroupSymbol)))
|
---|
210 | changed |= AddAllowedChildSymbolToDictionaries(p, child, argumentIndex);
|
---|
211 |
|
---|
212 | if (changed) {
|
---|
213 | ClearCaches();
|
---|
214 | OnChanged();
|
---|
215 | }
|
---|
216 | }
|
---|
217 |
|
---|
218 |
|
---|
219 | private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child, int argumentIndex) {
|
---|
220 | List<string> childSymbols;
|
---|
221 | if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
|
---|
222 | childSymbols = new List<string>();
|
---|
223 | allowedChildSymbols.Add(parent.Name, childSymbols);
|
---|
224 | }
|
---|
225 | if (childSymbols.Contains(child.Name)) return false;
|
---|
226 |
|
---|
227 |
|
---|
228 | var key = Tuple.Create(parent.Name, argumentIndex);
|
---|
229 | if (!allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
|
---|
230 | childSymbols = new List<string>();
|
---|
231 | allowedChildSymbolsPerIndex.Add(key, childSymbols);
|
---|
232 | }
|
---|
233 |
|
---|
234 | if (childSymbols.Contains(child.Name)) return false;
|
---|
235 |
|
---|
236 | childSymbols.Add(child.Name);
|
---|
237 | return true;
|
---|
238 | }
|
---|
239 |
|
---|
240 | protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child) {
|
---|
241 | bool changed = false;
|
---|
242 | List<string> childSymbols;
|
---|
243 | if (allowedChildSymbols.TryGetValue(child.Name, out childSymbols)) {
|
---|
244 | changed |= childSymbols.Remove(child.Name);
|
---|
245 | }
|
---|
246 |
|
---|
247 | for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++) {
|
---|
248 | var key = Tuple.Create(parent.Name, argumentIndex);
|
---|
249 | if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
|
---|
250 | changed |= childSymbols.Remove(child.Name);
|
---|
251 | }
|
---|
252 |
|
---|
253 | if (changed) {
|
---|
254 | ClearCaches();
|
---|
255 | OnChanged();
|
---|
256 | }
|
---|
257 | }
|
---|
258 |
|
---|
259 | protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
|
---|
260 | bool changed = false;
|
---|
261 |
|
---|
262 | suppressEvents = true;
|
---|
263 | List<string> childSymbols;
|
---|
264 | if (allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
|
---|
265 | if (childSymbols.Remove(child.Name)) {
|
---|
266 | for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
|
---|
267 | if (i != argumentIndex) AddAllowedChildSymbol(parent, child, i);
|
---|
268 | }
|
---|
269 | changed = true;
|
---|
270 | }
|
---|
271 | }
|
---|
272 | suppressEvents = false;
|
---|
273 |
|
---|
274 | var key = Tuple.Create(parent.Name, argumentIndex);
|
---|
275 | if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
|
---|
276 | changed |= childSymbols.Remove(child.Name);
|
---|
277 |
|
---|
278 | if (changed) {
|
---|
279 | ClearCaches();
|
---|
280 | OnChanged();
|
---|
281 | }
|
---|
282 | }
|
---|
283 |
|
---|
284 | protected void SetSubtreeCount(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
|
---|
285 | var symbols = symbol.Flatten().Where(s => !(s is GroupSymbol));
|
---|
286 | if (symbols.Any(s => s.MinimumArity > minimumSubtreeCount)) throw new ArgumentException("Invalid minimum subtree count " + minimumSubtreeCount + " for " + symbol);
|
---|
287 | if (symbols.Any(s => s.MaximumArity < maximumSubtreeCount)) throw new ArgumentException("Invalid maximum subtree count " + maximumSubtreeCount + " for " + symbol);
|
---|
288 |
|
---|
289 | foreach (ISymbol s in symbols)
|
---|
290 | SetSubTreeCountInDictionaries(s, minimumSubtreeCount, maximumSubtreeCount);
|
---|
291 |
|
---|
292 | ClearCaches();
|
---|
293 | OnChanged();
|
---|
294 | }
|
---|
295 |
|
---|
296 | private void SetSubTreeCountInDictionaries(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
|
---|
297 | for (int i = maximumSubtreeCount; i < GetMaximumSubtreeCount(symbol); i++) {
|
---|
298 | var key = Tuple.Create(symbol.Name, i);
|
---|
299 | allowedChildSymbolsPerIndex.Remove(key);
|
---|
300 | }
|
---|
301 |
|
---|
302 | symbolSubtreeCount[symbol.Name] = Tuple.Create(minimumSubtreeCount, maximumSubtreeCount);
|
---|
303 | }
|
---|
304 | #endregion
|
---|
305 |
|
---|
306 | public virtual IEnumerable<ISymbol> Symbols {
|
---|
307 | get { return symbols.Values; }
|
---|
308 | }
|
---|
309 | public virtual IEnumerable<ISymbol> AllowedSymbols {
|
---|
310 | get { foreach (var s in Symbols) if (s.Enabled) yield return s; }
|
---|
311 | }
|
---|
312 | public virtual bool ContainsSymbol(ISymbol symbol) {
|
---|
313 | return symbols.ContainsKey(symbol.Name);
|
---|
314 | }
|
---|
315 |
|
---|
316 | private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
|
---|
317 | public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
|
---|
318 | if (allowedChildSymbols.Count == 0) return false;
|
---|
319 | if (!child.Enabled) return false;
|
---|
320 |
|
---|
321 | bool result;
|
---|
322 | var key = Tuple.Create(parent.Name, child.Name);
|
---|
323 | if (cachedIsAllowedChildSymbol.TryGetValue(key, out result)) return result;
|
---|
324 |
|
---|
325 | List<string> temp;
|
---|
326 | if (allowedChildSymbols.TryGetValue(parent.Name, out temp)) {
|
---|
327 | //if (temp.Contains(child.Name)) return true;
|
---|
328 | if (temp.SelectMany(s => GetSymbol(s).Flatten()).Any(s => s.Name == child.Name)) {
|
---|
329 | cachedIsAllowedChildSymbol.Add(key, true);
|
---|
330 | return true;
|
---|
331 | }
|
---|
332 | }
|
---|
333 | cachedIsAllowedChildSymbol.Add(key, false);
|
---|
334 | return false;
|
---|
335 | }
|
---|
336 |
|
---|
337 | private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex;
|
---|
338 | public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
|
---|
339 | if (!child.Enabled) return false;
|
---|
340 | if (IsAllowedChildSymbol(parent, child)) return true;
|
---|
341 | if (allowedChildSymbolsPerIndex.Count == 0) return false;
|
---|
342 |
|
---|
343 | bool result;
|
---|
344 | var key = Tuple.Create(parent.Name, child.Name, argumentIndex);
|
---|
345 | if (cachedIsAllowedChildSymbolIndex.TryGetValue(key, out result)) return result;
|
---|
346 |
|
---|
347 | List<string> temp;
|
---|
348 | if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, argumentIndex), out temp)) {
|
---|
349 | if (temp.SelectMany(s => GetSymbol(s).Flatten()).Any(s => s.Name == child.Name)) {
|
---|
350 | cachedIsAllowedChildSymbolIndex.Add(key, true);
|
---|
351 | return true;
|
---|
352 | }
|
---|
353 | }
|
---|
354 | cachedIsAllowedChildSymbolIndex.Add(key, false);
|
---|
355 | return false;
|
---|
356 | }
|
---|
357 |
|
---|
358 | public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
|
---|
359 | foreach (ISymbol child in AllowedSymbols) {
|
---|
360 | if (IsAllowedChildSymbol(parent, child)) yield return child;
|
---|
361 | }
|
---|
362 | }
|
---|
363 |
|
---|
364 | public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
|
---|
365 | foreach (ISymbol child in AllowedSymbols) {
|
---|
366 | if (IsAllowedChildSymbol(parent, child, argumentIndex)) yield return child;
|
---|
367 | }
|
---|
368 | }
|
---|
369 |
|
---|
370 | public virtual int GetMinimumSubtreeCount(ISymbol symbol) {
|
---|
371 | return symbolSubtreeCount[symbol.Name].Item1;
|
---|
372 | }
|
---|
373 | public virtual int GetMaximumSubtreeCount(ISymbol symbol) {
|
---|
374 | return symbolSubtreeCount[symbol.Name].Item2;
|
---|
375 | }
|
---|
376 |
|
---|
377 | protected void ClearCaches() {
|
---|
378 | cachedMinExpressionLength.Clear();
|
---|
379 | cachedMaxExpressionLength.Clear();
|
---|
380 | cachedMinExpressionDepth.Clear();
|
---|
381 | cachedMaxExpressionDepth.Clear();
|
---|
382 |
|
---|
383 | cachedIsAllowedChildSymbol.Clear();
|
---|
384 | cachedIsAllowedChildSymbolIndex.Clear();
|
---|
385 | }
|
---|
386 |
|
---|
387 | private readonly Dictionary<string, int> cachedMinExpressionLength;
|
---|
388 | public int GetMinimumExpressionLength(ISymbol symbol) {
|
---|
389 | int res;
|
---|
390 | if (cachedMinExpressionLength.TryGetValue(symbol.Name, out res))
|
---|
391 | return res;
|
---|
392 |
|
---|
393 | res = GetMinimumExpressionLengthRec(symbol);
|
---|
394 | foreach (var entry in cachedMinExpressionLength.Where(e => e.Value >= int.MaxValue).ToList()) {
|
---|
395 | if (entry.Key != symbol.Name) cachedMinExpressionLength.Remove(entry.Key);
|
---|
396 | }
|
---|
397 | return res;
|
---|
398 | }
|
---|
399 |
|
---|
400 | private int GetMinimumExpressionLengthRec(ISymbol symbol) {
|
---|
401 | int temp;
|
---|
402 | if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
|
---|
403 | cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
|
---|
404 | long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
|
---|
405 | let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
|
---|
406 | where s.InitialFrequency > 0.0
|
---|
407 | select GetMinimumExpressionLengthRec(s)).DefaultIfEmpty(0).Min()
|
---|
408 | select minForSlot).DefaultIfEmpty(0).Sum();
|
---|
409 |
|
---|
410 | cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
|
---|
411 | return cachedMinExpressionLength[symbol.Name];
|
---|
412 | }
|
---|
413 | return temp;
|
---|
414 | }
|
---|
415 |
|
---|
416 | private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
|
---|
417 | public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
|
---|
418 | int temp;
|
---|
419 | var key = Tuple.Create(symbol.Name, maxDepth);
|
---|
420 | if (!cachedMaxExpressionLength.TryGetValue(key, out temp)) {
|
---|
421 | cachedMaxExpressionLength[key] = int.MaxValue; // prevent infinite recursion
|
---|
422 | long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
|
---|
423 | let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
|
---|
424 | where s.InitialFrequency > 0.0
|
---|
425 | where GetMinimumExpressionDepth(s) < maxDepth
|
---|
426 | select GetMaximumExpressionLength(s, maxDepth - 1)).DefaultIfEmpty(0).Max()
|
---|
427 | select maxForSlot).DefaultIfEmpty(0).Sum();
|
---|
428 | cachedMaxExpressionLength[key] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
|
---|
429 | return cachedMaxExpressionLength[key];
|
---|
430 | }
|
---|
431 | return temp;
|
---|
432 | }
|
---|
433 |
|
---|
434 | private readonly Dictionary<string, int> cachedMinExpressionDepth;
|
---|
435 | public int GetMinimumExpressionDepth(ISymbol symbol) {
|
---|
436 | int res;
|
---|
437 | if (cachedMinExpressionDepth.TryGetValue(symbol.Name, out res))
|
---|
438 | return res;
|
---|
439 |
|
---|
440 | res = GetMinimumExpressionDepthRec(symbol);
|
---|
441 | foreach (var entry in cachedMinExpressionDepth.Where(e => e.Value >= int.MaxValue).ToList()) {
|
---|
442 | if (entry.Key != symbol.Name) cachedMinExpressionDepth.Remove(entry.Key);
|
---|
443 | }
|
---|
444 | return res;
|
---|
445 | }
|
---|
446 | private int GetMinimumExpressionDepthRec(ISymbol symbol) {
|
---|
447 | int temp;
|
---|
448 | if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
|
---|
449 | cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
|
---|
450 | long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
|
---|
451 | let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
|
---|
452 | where s.InitialFrequency > 0.0
|
---|
453 | select GetMinimumExpressionDepthRec(s)).DefaultIfEmpty(0).Min()
|
---|
454 | select minForSlot).DefaultIfEmpty(0).Max();
|
---|
455 | cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
|
---|
456 | return cachedMinExpressionDepth[symbol.Name];
|
---|
457 | }
|
---|
458 | return temp;
|
---|
459 | }
|
---|
460 |
|
---|
461 | private readonly Dictionary<string, int> cachedMaxExpressionDepth;
|
---|
462 | public int GetMaximumExpressionDepth(ISymbol symbol) {
|
---|
463 | int temp;
|
---|
464 | if (!cachedMaxExpressionDepth.TryGetValue(symbol.Name, out temp)) {
|
---|
465 | cachedMaxExpressionDepth[symbol.Name] = int.MaxValue;
|
---|
466 | long maxDepth = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
|
---|
467 | let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
|
---|
468 | where s.InitialFrequency > 0.0
|
---|
469 | select GetMaximumExpressionDepth(s)).DefaultIfEmpty(0).Max()
|
---|
470 | select maxForSlot).DefaultIfEmpty(0).Max();
|
---|
471 | cachedMaxExpressionDepth[symbol.Name] = (int)Math.Min(maxDepth, int.MaxValue);
|
---|
472 | return cachedMaxExpressionDepth[symbol.Name];
|
---|
473 | }
|
---|
474 | return temp;
|
---|
475 | }
|
---|
476 |
|
---|
477 | public event EventHandler Changed;
|
---|
478 | protected virtual void OnChanged() {
|
---|
479 | if (suppressEvents) return;
|
---|
480 | var handler = Changed;
|
---|
481 | if (handler != null) Changed(this, EventArgs.Empty);
|
---|
482 | }
|
---|
483 | }
|
---|
484 | }
|
---|