1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2011 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.Collections;
|
---|
26 | using HeuristicLab.Common;
|
---|
27 | using HeuristicLab.Core;
|
---|
28 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
29 |
|
---|
30 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
|
---|
31 | /// <summary>
|
---|
32 | /// The default symbolic expression grammar stores symbols and syntactic constraints for symbols.
|
---|
33 | /// Symbols are treated as equvivalent if they have the same name.
|
---|
34 | /// Syntactic constraints limit the number of allowed sub trees for a node with a symbol and which symbols are allowed
|
---|
35 | /// in the sub-trees of a symbol (can be specified for each sub-tree index separately).
|
---|
36 | /// </summary>
|
---|
37 | [StorableClass]
|
---|
38 | public abstract class SymbolicExpressionGrammarBase : NamedItem, ISymbolicExpressionGrammarBase {
|
---|
39 |
|
---|
40 | #region properties for separation between implementation and persistence
|
---|
41 | [Storable(Name = "Symbols")]
|
---|
42 | private IEnumerable<ISymbol> StorableSymbols {
|
---|
43 | get { return symbols.Values.ToArray(); }
|
---|
44 | set { symbols = value.ToDictionary(sym => sym.Name); }
|
---|
45 | }
|
---|
46 |
|
---|
47 | [Storable(Name = "SymbolSubtreeCount")]
|
---|
48 | private IEnumerable<KeyValuePair<ISymbol, Tuple<int, int>>> StorableSymbolSubtreeCount {
|
---|
49 | get { return symbolSubtreeCount.Select(x => new KeyValuePair<ISymbol, Tuple<int, int>>(GetSymbol(x.Key), x.Value)).ToArray(); }
|
---|
50 | set { symbolSubtreeCount = value.ToDictionary(x => x.Key.Name, x => x.Value); }
|
---|
51 | }
|
---|
52 |
|
---|
53 | [Storable(Name = "AllowedChildSymbols")]
|
---|
54 | private IEnumerable<KeyValuePair<ISymbol, IEnumerable<ISymbol>>> StorableAllowedChildSymbols {
|
---|
55 | get { return allowedChildSymbols.Select(x => new KeyValuePair<ISymbol, IEnumerable<ISymbol>>(GetSymbol(x.Key), x.Value.Select(y => GetSymbol(y)).ToArray())).ToArray(); }
|
---|
56 | set { allowedChildSymbols = value.ToDictionary(x => x.Key.Name, x => x.Value.Select(y => y.Name).ToList()); }
|
---|
57 | }
|
---|
58 |
|
---|
59 | [Storable(Name = "AllowedChildSymbolsPerIndex")]
|
---|
60 | private IEnumerable<KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>> StorableAllowedChildSymbolsPerIndex {
|
---|
61 | 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(); }
|
---|
62 | set { allowedChildSymbolsPerIndex = value.ToDictionary(x => Tuple.Create(x.Key.Item1.Name, x.Key.Item2), x => x.Value.Select(y => y.Name).ToList()); }
|
---|
63 | }
|
---|
64 | #endregion
|
---|
65 |
|
---|
66 | protected bool suppressEvents;
|
---|
67 | protected Dictionary<string, ISymbol> symbols;
|
---|
68 | protected Dictionary<string, Tuple<int, int>> symbolSubtreeCount;
|
---|
69 | protected Dictionary<string, List<string>> allowedChildSymbols;
|
---|
70 | protected Dictionary<Tuple<string, int>, List<string>> allowedChildSymbolsPerIndex;
|
---|
71 |
|
---|
72 | public override bool CanChangeName {
|
---|
73 | get { return false; }
|
---|
74 | }
|
---|
75 | public override bool CanChangeDescription {
|
---|
76 | get { return false; }
|
---|
77 | }
|
---|
78 |
|
---|
79 | [StorableConstructor]
|
---|
80 | protected SymbolicExpressionGrammarBase(bool deserializing)
|
---|
81 | : base(deserializing) {
|
---|
82 | cachedMinExpressionLength = new Dictionary<string, int>();
|
---|
83 | cachedMaxExpressionLength = new Dictionary<string, int>();
|
---|
84 | cachedMinExpressionDepth = new Dictionary<string, int>();
|
---|
85 |
|
---|
86 | suppressEvents = false;
|
---|
87 | }
|
---|
88 | [StorableHook(HookType.AfterDeserialization)]
|
---|
89 | private void AfterDeserialization() {
|
---|
90 | foreach (ISymbol symbol in symbols.Values)
|
---|
91 | RegisterSymbolEvents(symbol);
|
---|
92 | }
|
---|
93 |
|
---|
94 | protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
|
---|
95 | : base(original, cloner) {
|
---|
96 | cachedMinExpressionLength = new Dictionary<string, int>();
|
---|
97 | cachedMaxExpressionLength = new Dictionary<string, int>();
|
---|
98 | cachedMinExpressionDepth = new Dictionary<string, int>();
|
---|
99 |
|
---|
100 | symbols = original.symbols.ToDictionary(x => x.Key, y => (ISymbol)cloner.Clone(y.Value));
|
---|
101 | symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>(original.symbolSubtreeCount);
|
---|
102 |
|
---|
103 | allowedChildSymbols = new Dictionary<string, List<string>>();
|
---|
104 | foreach (var element in original.allowedChildSymbols)
|
---|
105 | allowedChildSymbols.Add(element.Key, new List<string>(element.Value));
|
---|
106 |
|
---|
107 | allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
|
---|
108 | foreach (var element in original.allowedChildSymbolsPerIndex)
|
---|
109 | allowedChildSymbolsPerIndex.Add(element.Key, new List<string>(element.Value));
|
---|
110 |
|
---|
111 | foreach (ISymbol symbol in symbols.Values)
|
---|
112 | RegisterSymbolEvents(symbol);
|
---|
113 |
|
---|
114 | suppressEvents = false;
|
---|
115 | }
|
---|
116 |
|
---|
117 | protected SymbolicExpressionGrammarBase(string name, string description)
|
---|
118 | : base(name, description) {
|
---|
119 | cachedMinExpressionLength = new Dictionary<string, int>();
|
---|
120 | cachedMaxExpressionLength = new Dictionary<string, int>();
|
---|
121 | cachedMinExpressionDepth = new Dictionary<string, int>();
|
---|
122 |
|
---|
123 | symbols = new Dictionary<string, ISymbol>();
|
---|
124 | symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
|
---|
125 | allowedChildSymbols = new Dictionary<string, List<string>>();
|
---|
126 | allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
|
---|
127 |
|
---|
128 | suppressEvents = false;
|
---|
129 | }
|
---|
130 |
|
---|
131 | #region protected grammar manipulation methods
|
---|
132 | protected void AddSymbol(ISymbol symbol) {
|
---|
133 | AddSymbolToDictionaries(symbol);
|
---|
134 | var groupSymbol = symbol as GroupSymbol;
|
---|
135 | if (groupSymbol != null) {
|
---|
136 | foreach (ISymbol s in groupSymbol.Flatten())
|
---|
137 | AddSymbolToDictionaries(s);
|
---|
138 | }
|
---|
139 |
|
---|
140 | ClearCaches();
|
---|
141 | OnChanged();
|
---|
142 | }
|
---|
143 | private void AddSymbolToDictionaries(ISymbol symbol) {
|
---|
144 | symbols.Add(symbol.Name, symbol);
|
---|
145 | symbolSubtreeCount.Add(symbol.Name, Tuple.Create(0, 0));
|
---|
146 | RegisterSymbolEvents(symbol);
|
---|
147 | }
|
---|
148 |
|
---|
149 | protected void RemoveSymbol(ISymbol symbol) {
|
---|
150 | RemoveSymbolFromDictionaries(symbol);
|
---|
151 | var groupSymbol = symbol as GroupSymbol;
|
---|
152 | if (groupSymbol != null) {
|
---|
153 | foreach (ISymbol s in groupSymbol.Flatten())
|
---|
154 | RemoveSymbolFromDictionaries(s);
|
---|
155 | }
|
---|
156 |
|
---|
157 | foreach (GroupSymbol group in symbols.Values.OfType<GroupSymbol>())
|
---|
158 | group.SymbolsCollection.Remove(symbol);
|
---|
159 |
|
---|
160 | ClearCaches();
|
---|
161 | OnChanged();
|
---|
162 | }
|
---|
163 | private void RemoveSymbolFromDictionaries(ISymbol symbol) {
|
---|
164 | symbols.Remove(symbol.Name);
|
---|
165 | allowedChildSymbols.Remove(symbol.Name);
|
---|
166 | for (int i = 0; i < GetMaximumSubtreeCount(symbol); i++)
|
---|
167 | allowedChildSymbolsPerIndex.Remove(Tuple.Create(symbol.Name, i));
|
---|
168 | symbolSubtreeCount.Remove(symbol.Name);
|
---|
169 |
|
---|
170 | foreach (var parent in Symbols) {
|
---|
171 | List<string> allowedChilds;
|
---|
172 | if (allowedChildSymbols.TryGetValue(parent.Name, out allowedChilds))
|
---|
173 | allowedChilds.Remove(symbol.Name);
|
---|
174 |
|
---|
175 | for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
|
---|
176 | if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, i), out allowedChilds))
|
---|
177 | allowedChilds.Remove(symbol.Name);
|
---|
178 | }
|
---|
179 | }
|
---|
180 | DeregisterSymbolEvents(symbol);
|
---|
181 | }
|
---|
182 |
|
---|
183 | public virtual ISymbol GetSymbol(string symbolName) {
|
---|
184 | ISymbol symbol;
|
---|
185 | if (symbols.TryGetValue(symbolName, out symbol)) return symbol;
|
---|
186 | return null;
|
---|
187 | }
|
---|
188 |
|
---|
189 | protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child) {
|
---|
190 | List<ISymbol> parents;
|
---|
191 | List<ISymbol> childs;
|
---|
192 | bool changed = false;
|
---|
193 |
|
---|
194 | var parentGroup = parent as GroupSymbol;
|
---|
195 | if (parentGroup != null) parents = parentGroup.Flatten().Where(p => !(p is GroupSymbol)).ToList();
|
---|
196 | else parents = new List<ISymbol>() { parent };
|
---|
197 | var childGroup = child as GroupSymbol;
|
---|
198 | if (childGroup != null) childs = childGroup.Flatten().Where(c => !(c is GroupSymbol)).ToList();
|
---|
199 | else childs = new List<ISymbol>() { child };
|
---|
200 |
|
---|
201 | foreach (ISymbol p in parents) {
|
---|
202 | foreach (ISymbol c in childs) {
|
---|
203 | changed |= AddAllowedChildSymbolToDictionaries(p, c);
|
---|
204 | }
|
---|
205 | }
|
---|
206 |
|
---|
207 | if (changed) {
|
---|
208 | ClearCaches();
|
---|
209 | OnChanged();
|
---|
210 | }
|
---|
211 | }
|
---|
212 |
|
---|
213 | private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child) {
|
---|
214 | List<string> childSymbols;
|
---|
215 | if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
|
---|
216 | childSymbols = new List<string>();
|
---|
217 | allowedChildSymbols.Add(parent.Name, childSymbols);
|
---|
218 | }
|
---|
219 | if (childSymbols.Contains(child.Name)) return false;
|
---|
220 |
|
---|
221 | suppressEvents = true;
|
---|
222 | for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++)
|
---|
223 | RemoveAllowedChildSymbol(parent, child, argumentIndex);
|
---|
224 | suppressEvents = false;
|
---|
225 |
|
---|
226 | childSymbols.Add(child.Name);
|
---|
227 | return true;
|
---|
228 | }
|
---|
229 |
|
---|
230 | protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
|
---|
231 | List<ISymbol> parents;
|
---|
232 | List<ISymbol> childs;
|
---|
233 | bool changed = false;
|
---|
234 |
|
---|
235 | var parentGroup = parent as GroupSymbol;
|
---|
236 | if (parentGroup != null) parents = parentGroup.Flatten().Where(p => !(p is GroupSymbol)).ToList();
|
---|
237 | else parents = new List<ISymbol>() { parent };
|
---|
238 | var childGroup = child as GroupSymbol;
|
---|
239 | if (childGroup != null) childs = childGroup.Flatten().Where(c => !(c is GroupSymbol)).ToList();
|
---|
240 | else childs = new List<ISymbol>() { child };
|
---|
241 |
|
---|
242 | foreach (ISymbol p in parents) {
|
---|
243 | foreach (ISymbol c in childs) {
|
---|
244 | changed |= AddAllowedChildSymbolToDictionaries(p, c, argumentIndex);
|
---|
245 | }
|
---|
246 | }
|
---|
247 |
|
---|
248 | if (changed) {
|
---|
249 | ClearCaches();
|
---|
250 | OnChanged();
|
---|
251 | }
|
---|
252 | }
|
---|
253 |
|
---|
254 |
|
---|
255 | private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child, int argumentIndex) {
|
---|
256 | List<string> childSymbols;
|
---|
257 | if (allowedChildSymbols.TryGetValue(parent.Name, out childSymbols))
|
---|
258 | if (childSymbols.Contains(child.Name)) return false;
|
---|
259 |
|
---|
260 | var key = Tuple.Create(parent.Name, argumentIndex);
|
---|
261 | if (!allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
|
---|
262 | childSymbols = new List<string>();
|
---|
263 | allowedChildSymbolsPerIndex.Add(key, childSymbols);
|
---|
264 | }
|
---|
265 | if (childSymbols.Contains(child.Name)) return false;
|
---|
266 |
|
---|
267 | childSymbols.Add(child.Name);
|
---|
268 | return true;
|
---|
269 | }
|
---|
270 |
|
---|
271 | protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child) {
|
---|
272 | bool changed = false;
|
---|
273 | List<string> childSymbols;
|
---|
274 | if (allowedChildSymbols.TryGetValue(child.Name, out childSymbols)) {
|
---|
275 | changed |= childSymbols.Remove(child.Name);
|
---|
276 | }
|
---|
277 |
|
---|
278 | for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++) {
|
---|
279 | var key = Tuple.Create(parent.Name, argumentIndex);
|
---|
280 | if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
|
---|
281 | changed |= childSymbols.Remove(child.Name);
|
---|
282 | }
|
---|
283 |
|
---|
284 | if (changed) {
|
---|
285 | ClearCaches();
|
---|
286 | OnChanged();
|
---|
287 | }
|
---|
288 | }
|
---|
289 |
|
---|
290 | protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
|
---|
291 | bool changed = false;
|
---|
292 |
|
---|
293 | suppressEvents = true;
|
---|
294 | List<string> childSymbols;
|
---|
295 | if (allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
|
---|
296 | if (childSymbols.Remove(child.Name)) {
|
---|
297 | for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
|
---|
298 | if (i != argumentIndex) AddAllowedChildSymbol(parent, child, i);
|
---|
299 | }
|
---|
300 | changed = true;
|
---|
301 | }
|
---|
302 | }
|
---|
303 | suppressEvents = false;
|
---|
304 |
|
---|
305 | var key = Tuple.Create(parent.Name, argumentIndex);
|
---|
306 | if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
|
---|
307 | changed |= childSymbols.Remove(child.Name);
|
---|
308 |
|
---|
309 | if (changed) {
|
---|
310 | ClearCaches();
|
---|
311 | OnChanged();
|
---|
312 | }
|
---|
313 | }
|
---|
314 |
|
---|
315 | protected void SetSubtreeCount(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
|
---|
316 | var groupSymbol = symbol as GroupSymbol;
|
---|
317 | if (groupSymbol != null)
|
---|
318 | foreach (ISymbol s in groupSymbol.Flatten().Where(s => !(s is GroupSymbol)))
|
---|
319 | SetSubTreeCountInDictionaries(s, minimumSubtreeCount, maximumSubtreeCount);
|
---|
320 | else
|
---|
321 | SetSubTreeCountInDictionaries(symbol, minimumSubtreeCount, maximumSubtreeCount);
|
---|
322 |
|
---|
323 | ClearCaches();
|
---|
324 | OnChanged();
|
---|
325 | }
|
---|
326 |
|
---|
327 | private void SetSubTreeCountInDictionaries(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
|
---|
328 | for (int i = GetMaximumSubtreeCount(symbol) - 1; i >= maximumSubtreeCount; i--) {
|
---|
329 | var key = Tuple.Create(symbol.Name, i);
|
---|
330 | allowedChildSymbolsPerIndex.Remove(key);
|
---|
331 | }
|
---|
332 |
|
---|
333 | symbolSubtreeCount[symbol.Name] = Tuple.Create(minimumSubtreeCount, maximumSubtreeCount);
|
---|
334 | }
|
---|
335 | #endregion
|
---|
336 |
|
---|
337 | public virtual IEnumerable<ISymbol> Symbols {
|
---|
338 | get { return symbols.Values; }
|
---|
339 | }
|
---|
340 | public virtual IEnumerable<ISymbol> AllowedSymbols {
|
---|
341 | get { return Symbols.Where(s => s.Enabled); }
|
---|
342 | }
|
---|
343 | public virtual bool ContainsSymbol(ISymbol symbol) {
|
---|
344 | return symbols.ContainsKey(symbol.Name);
|
---|
345 | }
|
---|
346 |
|
---|
347 | public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
|
---|
348 | if (!child.Enabled) return false;
|
---|
349 |
|
---|
350 | List<string> temp;
|
---|
351 | if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
|
---|
352 | return temp.Contains(child.Name);
|
---|
353 | return false;
|
---|
354 | }
|
---|
355 |
|
---|
356 | public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
|
---|
357 | if (!child.Enabled) return false;
|
---|
358 |
|
---|
359 | List<string> temp;
|
---|
360 | if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
|
---|
361 | if (temp.Contains(child.Name)) return true;
|
---|
362 |
|
---|
363 | var key = Tuple.Create(parent.Name, argumentIndex);
|
---|
364 | if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
|
---|
365 | return temp.Contains(child.Name);
|
---|
366 | return false;
|
---|
367 | }
|
---|
368 |
|
---|
369 | public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
|
---|
370 | List<string> childs;
|
---|
371 | if (allowedChildSymbols.TryGetValue(parent.Name, out childs))
|
---|
372 | return childs.Select(s => GetSymbol(s)).Where(s => s.Enabled);
|
---|
373 | return Enumerable.Empty<ISymbol>();
|
---|
374 | }
|
---|
375 |
|
---|
376 | public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
|
---|
377 | var result = Enumerable.Empty<string>();
|
---|
378 |
|
---|
379 | List<string> temp;
|
---|
380 | if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
|
---|
381 | result = result.Union(temp);
|
---|
382 | var key = Tuple.Create(parent.Name, argumentIndex);
|
---|
383 | if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
|
---|
384 | result = result.Union(temp);
|
---|
385 |
|
---|
386 | return result.Select(x => GetSymbol(x)).Where(s => s.Enabled);
|
---|
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 | private void ClearCaches() {
|
---|
397 | cachedMinExpressionLength.Clear();
|
---|
398 | cachedMaxExpressionLength.Clear();
|
---|
399 | cachedMinExpressionDepth.Clear();
|
---|
400 | }
|
---|
401 |
|
---|
402 | private Dictionary<string, int> cachedMinExpressionLength;
|
---|
403 | public int GetMinimumExpressionLength(ISymbol symbol) {
|
---|
404 | int temp;
|
---|
405 | if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
|
---|
406 | cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
|
---|
407 | long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
|
---|
408 | let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
|
---|
409 | select GetMinimumExpressionLength(s)).DefaultIfEmpty(0).Min()
|
---|
410 | select minForSlot).DefaultIfEmpty(0).Sum();
|
---|
411 |
|
---|
412 | cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
|
---|
413 | return cachedMinExpressionLength[symbol.Name];
|
---|
414 | }
|
---|
415 | return temp;
|
---|
416 | }
|
---|
417 |
|
---|
418 | private Dictionary<string, int> cachedMaxExpressionLength;
|
---|
419 | public int GetMaximumExpressionLength(ISymbol symbol) {
|
---|
420 | int temp;
|
---|
421 | if (!cachedMaxExpressionLength.TryGetValue(symbol.Name, out temp)) {
|
---|
422 | cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
|
---|
423 | long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
|
---|
424 | let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
|
---|
425 | select GetMaximumExpressionLength(s)).DefaultIfEmpty(0).Max()
|
---|
426 | select maxForSlot).DefaultIfEmpty(0).Sum();
|
---|
427 | cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
|
---|
428 | return cachedMaxExpressionLength[symbol.Name];
|
---|
429 | }
|
---|
430 | return temp;
|
---|
431 | }
|
---|
432 |
|
---|
433 | private Dictionary<string, int> cachedMinExpressionDepth;
|
---|
434 | public int GetMinimumExpressionDepth(ISymbol symbol) {
|
---|
435 | int temp;
|
---|
436 | if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
|
---|
437 | cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
|
---|
438 | long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
|
---|
439 | let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
|
---|
440 | select GetMinimumExpressionDepth(s)).DefaultIfEmpty(0).Min()
|
---|
441 | select minForSlot).DefaultIfEmpty(0).Max();
|
---|
442 | cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
|
---|
443 | return cachedMinExpressionDepth[symbol.Name];
|
---|
444 | }
|
---|
445 | return temp;
|
---|
446 | }
|
---|
447 |
|
---|
448 |
|
---|
449 | #region events
|
---|
450 | private void RegisterSymbolEvents(ISymbol symbol) {
|
---|
451 | symbol.NameChanging += new EventHandler<CancelEventArgs<string>>(Symbol_NameChanging);
|
---|
452 | symbol.NameChanged += new EventHandler(Symbol_NameChanged);
|
---|
453 | symbol.Changed += new EventHandler(Symbol_Changed);
|
---|
454 | var groupSymbol = symbol as GroupSymbol;
|
---|
455 | if (groupSymbol != null) RegisterGroupSymbolEvents(groupSymbol);
|
---|
456 | }
|
---|
457 | private void DeregisterSymbolEvents(ISymbol symbol) {
|
---|
458 | symbol.NameChanging -= new EventHandler<CancelEventArgs<string>>(Symbol_NameChanging);
|
---|
459 | symbol.NameChanged -= new EventHandler(Symbol_NameChanged);
|
---|
460 | symbol.Changed -= new EventHandler(Symbol_Changed);
|
---|
461 | var groupSymbol = symbol as GroupSymbol;
|
---|
462 | if (groupSymbol != null) DeregisterGroupSymbolEvents(groupSymbol);
|
---|
463 | }
|
---|
464 |
|
---|
465 | private void RegisterGroupSymbolEvents(GroupSymbol groupSymbol) {
|
---|
466 | groupSymbol.SymbolsCollection.ItemsAdded += new Collections.CollectionItemsChangedEventHandler<ISymbol>(GroupSymbol_ItemsAdded);
|
---|
467 | groupSymbol.SymbolsCollection.ItemsRemoved += new Collections.CollectionItemsChangedEventHandler<ISymbol>(GroupSymbol_ItemsRemoved);
|
---|
468 | groupSymbol.SymbolsCollection.CollectionReset += new Collections.CollectionItemsChangedEventHandler<ISymbol>(GroupSymbol_CollectionReset);
|
---|
469 | }
|
---|
470 | private void DeregisterGroupSymbolEvents(GroupSymbol groupSymbol) {
|
---|
471 | groupSymbol.SymbolsCollection.ItemsAdded -= new Collections.CollectionItemsChangedEventHandler<ISymbol>(GroupSymbol_ItemsAdded);
|
---|
472 | groupSymbol.SymbolsCollection.ItemsRemoved -= new Collections.CollectionItemsChangedEventHandler<ISymbol>(GroupSymbol_ItemsRemoved);
|
---|
473 | groupSymbol.SymbolsCollection.CollectionReset -= new Collections.CollectionItemsChangedEventHandler<ISymbol>(GroupSymbol_CollectionReset);
|
---|
474 | }
|
---|
475 |
|
---|
476 | private void Symbol_NameChanging(object sender, CancelEventArgs<string> e) {
|
---|
477 | if (symbols.ContainsKey(e.Value)) e.Cancel = true;
|
---|
478 | }
|
---|
479 | private void Symbol_NameChanged(object sender, EventArgs e) {
|
---|
480 | ISymbol symbol = (ISymbol)sender;
|
---|
481 | string oldName = symbols.Where(x => x.Value == symbol).First().Key;
|
---|
482 | string newName = symbol.Name;
|
---|
483 |
|
---|
484 | symbols.Remove(oldName);
|
---|
485 | symbols.Add(newName, symbol);
|
---|
486 |
|
---|
487 | var subtreeCount = symbolSubtreeCount[oldName];
|
---|
488 | symbolSubtreeCount.Remove(oldName);
|
---|
489 | symbolSubtreeCount.Add(newName, subtreeCount);
|
---|
490 |
|
---|
491 | List<string> allowedChilds;
|
---|
492 | if (allowedChildSymbols.TryGetValue(oldName, out allowedChilds)) {
|
---|
493 | allowedChildSymbols.Remove(oldName);
|
---|
494 | allowedChildSymbols.Add(newName, allowedChilds);
|
---|
495 | }
|
---|
496 |
|
---|
497 | for (int i = 0; i < GetMaximumSubtreeCount(symbol); i++) {
|
---|
498 | if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(oldName, i), out allowedChilds)) {
|
---|
499 | allowedChildSymbolsPerIndex.Remove(Tuple.Create(oldName, i));
|
---|
500 | allowedChildSymbolsPerIndex.Add(Tuple.Create(newName, i), allowedChilds);
|
---|
501 | }
|
---|
502 | }
|
---|
503 |
|
---|
504 | foreach (var parent in Symbols) {
|
---|
505 | if (allowedChildSymbols.TryGetValue(parent.Name, out allowedChilds))
|
---|
506 | if (allowedChilds.Remove(oldName))
|
---|
507 | allowedChilds.Add(newName);
|
---|
508 |
|
---|
509 | for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
|
---|
510 | if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, i), out allowedChilds))
|
---|
511 | if (allowedChilds.Remove(oldName)) allowedChilds.Add(newName);
|
---|
512 | }
|
---|
513 | }
|
---|
514 |
|
---|
515 | ClearCaches();
|
---|
516 | OnChanged();
|
---|
517 | }
|
---|
518 |
|
---|
519 | private void Symbol_Changed(object sende, EventArgs e) {
|
---|
520 | ClearCaches();
|
---|
521 | OnChanged();
|
---|
522 | }
|
---|
523 |
|
---|
524 | private void GroupSymbol_ItemsAdded(object sender, CollectionItemsChangedEventArgs<ISymbol> e) {
|
---|
525 | suppressEvents = true;
|
---|
526 | foreach (ISymbol symbol in e.Items)
|
---|
527 | if (!ContainsSymbol(symbol))
|
---|
528 | AddSymbol(symbol);
|
---|
529 | suppressEvents = false;
|
---|
530 | OnChanged();
|
---|
531 | }
|
---|
532 | private void GroupSymbol_ItemsRemoved(object sender, CollectionItemsChangedEventArgs<ISymbol> e) {
|
---|
533 | suppressEvents = true;
|
---|
534 | foreach (ISymbol symbol in e.Items)
|
---|
535 | if (ContainsSymbol(symbol))
|
---|
536 | RemoveSymbol(symbol);
|
---|
537 | suppressEvents = false;
|
---|
538 | OnChanged();
|
---|
539 | }
|
---|
540 | private void GroupSymbol_CollectionReset(object sender, CollectionItemsChangedEventArgs<ISymbol> e) {
|
---|
541 | suppressEvents = true;
|
---|
542 | foreach (ISymbol symbol in e.Items)
|
---|
543 | if (!ContainsSymbol(symbol))
|
---|
544 | AddSymbol(symbol);
|
---|
545 | foreach (ISymbol symbol in e.OldItems)
|
---|
546 | if (ContainsSymbol(symbol))
|
---|
547 | RemoveSymbol(symbol);
|
---|
548 | suppressEvents = false;
|
---|
549 | OnChanged();
|
---|
550 | }
|
---|
551 |
|
---|
552 | public event EventHandler Changed;
|
---|
553 | protected virtual void OnChanged() {
|
---|
554 | if (suppressEvents) return;
|
---|
555 | var handler = Changed;
|
---|
556 | if (handler != null) Changed(this, EventArgs.Empty);
|
---|
557 | }
|
---|
558 | #endregion
|
---|
559 | }
|
---|
560 | }
|
---|