1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2019 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 HEAL.Attic;
|
---|
26 | using HeuristicLab.Common;
|
---|
27 | using HeuristicLab.Core;
|
---|
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 | [StorableType("E76C087C-4E10-488A-86D0-295A4265DA53")]
|
---|
37 | public abstract class SymbolicExpressionGrammarBase : NamedItem, ISymbolicExpressionGrammarBase {
|
---|
38 |
|
---|
39 | #region properties for separation between implementation and persistence
|
---|
40 | private IEnumerable<ISymbol> storableSymbols;
|
---|
41 | [Storable(Name = "Symbols")]
|
---|
42 | private IEnumerable<ISymbol> StorableSymbols {
|
---|
43 | get { return symbols.Values.ToArray(); }
|
---|
44 | set { storableSymbols = value; }
|
---|
45 | }
|
---|
46 |
|
---|
47 | private IEnumerable<KeyValuePair<ISymbol, Tuple<int, int>>> storableSymbolSubtreeCount;
|
---|
48 | [Storable(Name = "SymbolSubtreeCount")]
|
---|
49 | private IEnumerable<KeyValuePair<ISymbol, Tuple<int, int>>> StorableSymbolSubtreeCount {
|
---|
50 | get { return symbolSubtreeCount.Select(x => new KeyValuePair<ISymbol, Tuple<int, int>>(GetSymbol(x.Key), x.Value)).ToArray(); }
|
---|
51 | set { storableSymbolSubtreeCount = value; }
|
---|
52 | }
|
---|
53 |
|
---|
54 | private IEnumerable<KeyValuePair<ISymbol, IEnumerable<ISymbol>>> storableAllowedChildSymbols;
|
---|
55 | [Storable(Name = "AllowedChildSymbols")]
|
---|
56 | private IEnumerable<KeyValuePair<ISymbol, IEnumerable<ISymbol>>> StorableAllowedChildSymbols {
|
---|
57 | get { return allowedChildSymbols.Select(x => new KeyValuePair<ISymbol, IEnumerable<ISymbol>>(GetSymbol(x.Key), x.Value.Select(GetSymbol).ToArray())).ToArray(); }
|
---|
58 | set { storableAllowedChildSymbols = value; }
|
---|
59 | }
|
---|
60 |
|
---|
61 | private IEnumerable<KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>> storableAllowedChildSymbolsPerIndex;
|
---|
62 | [Storable(Name = "AllowedChildSymbolsPerIndex")]
|
---|
63 | private IEnumerable<KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>> StorableAllowedChildSymbolsPerIndex {
|
---|
64 | get { return allowedChildSymbolsPerIndex.Select(x => new KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>(Tuple.Create(GetSymbol(x.Key.Item1), x.Key.Item2), x.Value.Select(GetSymbol).ToArray())).ToArray(); }
|
---|
65 | set { storableAllowedChildSymbolsPerIndex = value; }
|
---|
66 | }
|
---|
67 | #endregion
|
---|
68 |
|
---|
69 | private bool suppressEvents;
|
---|
70 | protected readonly Dictionary<string, ISymbol> symbols;
|
---|
71 | protected readonly Dictionary<string, Tuple<int, int>> symbolSubtreeCount;
|
---|
72 | protected readonly Dictionary<string, List<string>> allowedChildSymbols;
|
---|
73 | protected readonly Dictionary<Tuple<string, int>, List<string>> allowedChildSymbolsPerIndex;
|
---|
74 |
|
---|
75 | public override bool CanChangeName {
|
---|
76 | get { return false; }
|
---|
77 | }
|
---|
78 | public override bool CanChangeDescription {
|
---|
79 | get { return false; }
|
---|
80 | }
|
---|
81 |
|
---|
82 | [StorableConstructor]
|
---|
83 | protected SymbolicExpressionGrammarBase(StorableConstructorFlag _) : base(_) {
|
---|
84 |
|
---|
85 | symbols = new Dictionary<string, ISymbol>();
|
---|
86 | symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
|
---|
87 | allowedChildSymbols = new Dictionary<string, List<string>>();
|
---|
88 | allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
|
---|
89 |
|
---|
90 | suppressEvents = false;
|
---|
91 | }
|
---|
92 |
|
---|
93 | [StorableHook(HookType.AfterDeserialization)]
|
---|
94 | private void AfterDeserialization() {
|
---|
95 | foreach (var s in storableSymbols) symbols.Add(s.Name, s);
|
---|
96 | foreach (var pair in storableSymbolSubtreeCount) symbolSubtreeCount.Add(pair.Key.Name, pair.Value);
|
---|
97 | foreach (var pair in storableAllowedChildSymbols) allowedChildSymbols.Add(pair.Key.Name, pair.Value.Select(y => y.Name).ToList());
|
---|
98 | foreach (var pair in storableAllowedChildSymbolsPerIndex)
|
---|
99 | allowedChildSymbolsPerIndex.Add(Tuple.Create(pair.Key.Item1.Name, pair.Key.Item2), pair.Value.Select(y => y.Name).ToList());
|
---|
100 |
|
---|
101 | storableSymbols = null;
|
---|
102 | storableSymbolSubtreeCount = null;
|
---|
103 | storableAllowedChildSymbols = null;
|
---|
104 | storableAllowedChildSymbolsPerIndex = null;
|
---|
105 | }
|
---|
106 |
|
---|
107 | protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
|
---|
108 | : base(original, cloner) {
|
---|
109 |
|
---|
110 | symbols = original.symbols.ToDictionary(x => x.Key, y => cloner.Clone(y.Value));
|
---|
111 | symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>(original.symbolSubtreeCount);
|
---|
112 |
|
---|
113 | allowedChildSymbols = new Dictionary<string, List<string>>();
|
---|
114 | foreach (var element in original.allowedChildSymbols)
|
---|
115 | allowedChildSymbols.Add(element.Key, new List<string>(element.Value));
|
---|
116 |
|
---|
117 | allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
|
---|
118 | foreach (var element in original.allowedChildSymbolsPerIndex)
|
---|
119 | allowedChildSymbolsPerIndex.Add(element.Key, new List<string>(element.Value));
|
---|
120 |
|
---|
121 | suppressEvents = false;
|
---|
122 | }
|
---|
123 |
|
---|
124 | protected SymbolicExpressionGrammarBase(string name, string description)
|
---|
125 | : base(name, description) {
|
---|
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 | public 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 | public 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 | public virtual 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 | public virtual 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 | public virtual 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 | public virtual 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 | public virtual 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 { return Symbols.Where(s => s.Enabled); }
|
---|
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 = new Dictionary<Tuple<string, string>, bool>();
|
---|
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 | // value has to be calculated and cached make sure this is done in only one thread
|
---|
326 | lock (cachedIsAllowedChildSymbol) {
|
---|
327 | // in case the value has been calculated on another thread in the meanwhile
|
---|
328 | if (cachedIsAllowedChildSymbol.TryGetValue(key, out result)) return result;
|
---|
329 |
|
---|
330 | List<string> temp;
|
---|
331 | if (allowedChildSymbols.TryGetValue(parent.Name, out temp)) {
|
---|
332 | for (int i = 0; i < temp.Count; i++) {
|
---|
333 | var symbol = GetSymbol(temp[i]);
|
---|
334 | foreach (var s in symbol.Flatten())
|
---|
335 | if (s.Name == child.Name) {
|
---|
336 | cachedIsAllowedChildSymbol.Add(key, true);
|
---|
337 | return true;
|
---|
338 | }
|
---|
339 | }
|
---|
340 | }
|
---|
341 | cachedIsAllowedChildSymbol.Add(key, false);
|
---|
342 | return false;
|
---|
343 | }
|
---|
344 | }
|
---|
345 |
|
---|
346 | private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
|
---|
347 | public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
|
---|
348 | if (!child.Enabled) return false;
|
---|
349 | if (IsAllowedChildSymbol(parent, child)) return true;
|
---|
350 | if (allowedChildSymbolsPerIndex.Count == 0) return false;
|
---|
351 |
|
---|
352 | bool result;
|
---|
353 | var key = Tuple.Create(parent.Name, child.Name, argumentIndex);
|
---|
354 | if (cachedIsAllowedChildSymbolIndex.TryGetValue(key, out result)) return result;
|
---|
355 |
|
---|
356 | // value has to be calculated and cached make sure this is done in only one thread
|
---|
357 | lock (cachedIsAllowedChildSymbolIndex) {
|
---|
358 | // in case the value has been calculated on another thread in the meanwhile
|
---|
359 | if (cachedIsAllowedChildSymbolIndex.TryGetValue(key, out result)) return result;
|
---|
360 |
|
---|
361 | List<string> temp;
|
---|
362 | if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, argumentIndex), out temp)) {
|
---|
363 | for (int i = 0; i < temp.Count; i++) {
|
---|
364 | var symbol = GetSymbol(temp[i]);
|
---|
365 | foreach (var s in symbol.Flatten())
|
---|
366 | if (s.Name == child.Name) {
|
---|
367 | cachedIsAllowedChildSymbolIndex.Add(key, true);
|
---|
368 | return true;
|
---|
369 | }
|
---|
370 | }
|
---|
371 | }
|
---|
372 | cachedIsAllowedChildSymbolIndex.Add(key, false);
|
---|
373 | return false;
|
---|
374 | }
|
---|
375 | }
|
---|
376 |
|
---|
377 | public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
|
---|
378 | foreach (ISymbol child in AllowedSymbols) {
|
---|
379 | if (IsAllowedChildSymbol(parent, child)) yield return child;
|
---|
380 | }
|
---|
381 | }
|
---|
382 |
|
---|
383 | public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
|
---|
384 | foreach (ISymbol child in AllowedSymbols) {
|
---|
385 | if (IsAllowedChildSymbol(parent, child, argumentIndex)) yield return child;
|
---|
386 | }
|
---|
387 | }
|
---|
388 |
|
---|
389 | public virtual int GetMinimumSubtreeCount(ISymbol symbol) {
|
---|
390 | return symbolSubtreeCount[symbol.Name].Item1;
|
---|
391 | }
|
---|
392 | public virtual int GetMaximumSubtreeCount(ISymbol symbol) {
|
---|
393 | return symbolSubtreeCount[symbol.Name].Item2;
|
---|
394 | }
|
---|
395 |
|
---|
396 | protected void ClearCaches() {
|
---|
397 | cachedMinExpressionLength.Clear();
|
---|
398 | cachedMaxExpressionLength.Clear();
|
---|
399 | cachedMinExpressionDepth.Clear();
|
---|
400 | cachedMaxExpressionDepth.Clear();
|
---|
401 |
|
---|
402 | cachedIsAllowedChildSymbol.Clear();
|
---|
403 | cachedIsAllowedChildSymbolIndex.Clear();
|
---|
404 | }
|
---|
405 |
|
---|
406 | private readonly Dictionary<string, int> cachedMinExpressionLength = new Dictionary<string, int>();
|
---|
407 | public int GetMinimumExpressionLength(ISymbol symbol) {
|
---|
408 | int res;
|
---|
409 | if (cachedMinExpressionLength.TryGetValue(symbol.Name, out res))
|
---|
410 | return res;
|
---|
411 |
|
---|
412 | // value has to be calculated and cached make sure this is done in only one thread
|
---|
413 | lock (cachedMinExpressionLength) {
|
---|
414 | // in case the value has been calculated on another thread in the meanwhile
|
---|
415 | if (cachedMinExpressionLength.TryGetValue(symbol.Name, out res)) return res;
|
---|
416 |
|
---|
417 | GrammarUtils.CalculateMinimumExpressionLengths(this, cachedMinExpressionLength);
|
---|
418 | return cachedMinExpressionLength[symbol.Name];
|
---|
419 | }
|
---|
420 | }
|
---|
421 |
|
---|
422 |
|
---|
423 | private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
|
---|
424 | public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
|
---|
425 | int temp;
|
---|
426 | var key = Tuple.Create(symbol.Name, maxDepth);
|
---|
427 | if (cachedMaxExpressionLength.TryGetValue(key, out temp)) return temp;
|
---|
428 | // value has to be calculated and cached make sure this is done in only one thread
|
---|
429 | lock (cachedMaxExpressionLength) {
|
---|
430 | // in case the value has been calculated on another thread in the meanwhile
|
---|
431 | if (cachedMaxExpressionLength.TryGetValue(key, out temp)) return temp;
|
---|
432 |
|
---|
433 | cachedMaxExpressionLength[key] = int.MaxValue; // prevent infinite recursion
|
---|
434 | long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
|
---|
435 | let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
|
---|
436 | where s.InitialFrequency > 0.0
|
---|
437 | where GetMinimumExpressionDepth(s) < maxDepth
|
---|
438 | select GetMaximumExpressionLength(s, maxDepth - 1)).DefaultIfEmpty(0).Max()
|
---|
439 | select maxForSlot).DefaultIfEmpty(0).Sum();
|
---|
440 | cachedMaxExpressionLength[key] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
|
---|
441 | return cachedMaxExpressionLength[key];
|
---|
442 | }
|
---|
443 | }
|
---|
444 |
|
---|
445 | private readonly Dictionary<string, int> cachedMinExpressionDepth = new Dictionary<string, int>();
|
---|
446 | public int GetMinimumExpressionDepth(ISymbol symbol) {
|
---|
447 | int res;
|
---|
448 | if (cachedMinExpressionDepth.TryGetValue(symbol.Name, out res))
|
---|
449 | return res;
|
---|
450 |
|
---|
451 | // value has to be calculated and cached make sure this is done in only one thread
|
---|
452 | lock (cachedMinExpressionDepth) {
|
---|
453 | // in case the value has been calculated on another thread in the meanwhile
|
---|
454 | if (cachedMinExpressionDepth.TryGetValue(symbol.Name, out res)) return res;
|
---|
455 |
|
---|
456 | GrammarUtils.CalculateMinimumExpressionDepth(this, cachedMinExpressionDepth);
|
---|
457 | return cachedMinExpressionDepth[symbol.Name];
|
---|
458 | }
|
---|
459 | }
|
---|
460 |
|
---|
461 | private readonly Dictionary<string, int> cachedMaxExpressionDepth = new Dictionary<string, int>();
|
---|
462 | public int GetMaximumExpressionDepth(ISymbol symbol) {
|
---|
463 | int temp;
|
---|
464 | if (cachedMaxExpressionDepth.TryGetValue(symbol.Name, out temp)) return temp;
|
---|
465 | // value has to be calculated and cached make sure this is done in only one thread
|
---|
466 | lock (cachedMaxExpressionDepth) {
|
---|
467 | // in case the value has been calculated on another thread in the meanwhile
|
---|
468 | if (cachedMaxExpressionDepth.TryGetValue(symbol.Name, out temp)) return temp;
|
---|
469 |
|
---|
470 | cachedMaxExpressionDepth[symbol.Name] = int.MaxValue;
|
---|
471 | long maxDepth = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
|
---|
472 | let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
|
---|
473 | where s.InitialFrequency > 0.0
|
---|
474 | select GetMaximumExpressionDepth(s)).DefaultIfEmpty(0).Max()
|
---|
475 | select maxForSlot).DefaultIfEmpty(0).Max();
|
---|
476 | cachedMaxExpressionDepth[symbol.Name] = (int)Math.Min(maxDepth, int.MaxValue);
|
---|
477 | return cachedMaxExpressionDepth[symbol.Name];
|
---|
478 | }
|
---|
479 | }
|
---|
480 |
|
---|
481 | public event EventHandler Changed;
|
---|
482 | protected virtual void OnChanged() {
|
---|
483 | if (suppressEvents) return;
|
---|
484 | var handler = Changed;
|
---|
485 | if (handler != null) handler(this, EventArgs.Empty);
|
---|
486 | }
|
---|
487 | }
|
---|
488 | }
|
---|