Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs @ 4189

Last change on this file since 4189 was 4106, checked in by gkronber, 14 years ago

Fixed bugs in SubtreeCrossover, ArgumentCreater and ArgumentDuplicater and updated unit tests for symbolic expression tree operators. #1103

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