Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs @ 5026

Last change on this file since 5026 was 5015, checked in by mkommend, 14 years ago

Moved check for max expression depth from tree node to the manipulator and corrected `MultiSymbolicExpressionTreeArchitectureManipulator' (ticket #1315).

File size: 6.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
31  [StorableClass]
32  public class SymbolicExpressionTreeNode : DeepCloneable {
33    [Storable]
34    private IList<SymbolicExpressionTreeNode> subTrees;
35    [Storable]
36    private Symbol symbol;
37
38    // cached values to prevent unnecessary tree iterations
39    private short size;
40    private short height;
41
42    public Symbol Symbol {
43      get { return symbol; }
44      protected set { symbol = value; }
45    }
46
47    // parent relation is not persisted or cloned (will be set on AddSubtree or RemoveSubtree)
48    private SymbolicExpressionTreeNode parent;
49    internal SymbolicExpressionTreeNode Parent {
50      get { return parent; }
51      set { parent = value; }
52    }
53
54    [StorableConstructor]
55    protected SymbolicExpressionTreeNode(bool deserializing) { }
56    protected SymbolicExpressionTreeNode(SymbolicExpressionTreeNode original, Cloner cloner)
57      : base() {
58      symbol = original.symbol; // symbols are reused
59      subTrees = new List<SymbolicExpressionTreeNode>(original.SubTrees.Count);
60      foreach (var subtree in original.SubTrees) {
61        var clonedSubTree = cloner.Clone(subtree);
62        subTrees.Add(clonedSubTree);
63        clonedSubTree.Parent = this;
64      }
65    }
66    public override IDeepCloneable Clone(Cloner cloner) {
67      return new SymbolicExpressionTreeNode(this, cloner);
68    }
69
70    internal SymbolicExpressionTreeNode()
71      : base() {
72      // don't allocate subtrees list here!
73      // because we don't want to allocate it in terminal nodes
74    }
75
76    public SymbolicExpressionTreeNode(Symbol symbol)
77      : base() {
78      subTrees = new List<SymbolicExpressionTreeNode>(3);
79      this.symbol = symbol;
80    }
81
82
83    [StorableHook(HookType.AfterDeserialization)]
84    private void AfterDeserialization() {
85      foreach (var subtree in SubTrees) {
86        subtree.Parent = this;
87      }
88    }
89
90    public virtual bool HasLocalParameters {
91      get { return false; }
92    }
93
94    public virtual IList<SymbolicExpressionTreeNode> SubTrees {
95      get { return subTrees; }
96    }
97
98    public virtual ISymbolicExpressionGrammar Grammar {
99      get { return parent.Grammar; }
100    }
101
102    public int GetSize() {
103      if (size > 0) return size;
104      else {
105        size = 1;
106        if (SubTrees != null) {
107          for (int i = 0; i < SubTrees.Count; i++) {
108            checked { size += (short)SubTrees[i].GetSize(); }
109          }
110        }
111        return size;
112      }
113    }
114
115    public int GetHeight() {
116      if (height > 0) return height;
117      else {
118        if (SubTrees != null) {
119          for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (short)SubTrees[i].GetHeight());
120        }
121        height++;
122        return height;
123      }
124    }
125
126    public virtual void ResetLocalParameters(IRandom random) { }
127    public virtual void ShakeLocalParameters(IRandom random, double shakingFactor) { }
128
129    public virtual void AddSubTree(SymbolicExpressionTreeNode tree) {
130      SubTrees.Add(tree);
131      tree.Parent = this;
132      ResetCachedValues();
133    }
134
135    public virtual void InsertSubTree(int index, SymbolicExpressionTreeNode tree) {
136      SubTrees.Insert(index, tree);
137      tree.Parent = this;
138      ResetCachedValues();
139    }
140
141    public virtual void RemoveSubTree(int index) {
142      SubTrees[index].Parent = null;
143      SubTrees.RemoveAt(index);
144      ResetCachedValues();
145    }
146
147    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix() {
148      List<SymbolicExpressionTreeNode> list = new List<SymbolicExpressionTreeNode>();
149      ForEachNodePrefix((n) => list.Add(n));
150      return list;
151    }
152
153    public void ForEachNodePrefix(Action<SymbolicExpressionTreeNode> a) {
154      a(this);
155      if (SubTrees != null) {
156        for (int i = 0; i < SubTrees.Count; i++) {
157          SubTrees[i].ForEachNodePrefix(a);
158        }
159      }
160    }
161
162    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPostfix() {
163      List<SymbolicExpressionTreeNode> list = new List<SymbolicExpressionTreeNode>();
164      ForEachNodePostfix((n) => list.Add(n));
165      return list;
166    }
167
168    public void ForEachNodePostfix(Action<SymbolicExpressionTreeNode> a) {
169      if (SubTrees != null) {
170        for (int i = 0; i < SubTrees.Count; i++) {
171          SubTrees[i].ForEachNodePostfix(a);
172        }
173      }
174      a(this);
175    }
176
177    public IEnumerable<Symbol> GetAllowedSymbols(int argumentIndex) {
178      return Grammar.Symbols.Where(s => Grammar.IsAllowedChild(Symbol, s, argumentIndex));
179    }
180
181    public int GetMinSubtreeCount() {
182      return Grammar.GetMinSubtreeCount(Symbol);
183    }
184    public int GetMaxSubtreeCount() {
185      return Grammar.GetMaxSubtreeCount(Symbol);
186    }
187    public override string ToString() {
188      return Symbol.Name;
189    }
190
191    private void ResetCachedValues() {
192      size = 0; height = 0;
193      if (parent != null) parent.ResetCachedValues();
194    }
195  }
196}
Note: See TracBrowser for help on using the repository browser.