Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeNode.cs @ 14185

Last change on this file since 14185 was 14185, checked in by swagner, 6 years ago

#2526: Updated year of copyrights in license headers

File size: 7.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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 HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
27
28namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
29  [StorableClass]
30  public class SymbolicExpressionTreeNode : DeepCloneable, ISymbolicExpressionTreeNode {
31    [Storable]
32    private IList<ISymbolicExpressionTreeNode> subtrees;
33    [Storable]
34    private ISymbol symbol;
35
36    // cached values to prevent unnecessary tree iterations
37    private ushort length;
38    private ushort depth;
39
40    public ISymbol Symbol {
41      get { return symbol; }
42      protected set { symbol = value; }
43    }
44
45    // parent relation is not persisted or cloned (will be set on AddSubtree or RemoveSubtree)
46    private ISymbolicExpressionTreeNode parent;
47    public ISymbolicExpressionTreeNode Parent {
48      get { return parent; }
49      set { parent = value; }
50    }
51
52    [StorableConstructor]
53    protected SymbolicExpressionTreeNode(bool deserializing) { }
54    protected SymbolicExpressionTreeNode(SymbolicExpressionTreeNode original, Cloner cloner)
55      : base(original, cloner) {
56      symbol = original.symbol; // symbols are reused
57      length = original.length;
58      depth = original.depth;
59      if (original.subtrees != null) {
60        subtrees = new List<ISymbolicExpressionTreeNode>(original.subtrees.Count);
61        foreach (var subtree in original.subtrees) {
62          var clonedSubtree = cloner.Clone(subtree);
63          subtrees.Add(clonedSubtree);
64          clonedSubtree.Parent = this;
65        }
66      }
67    }
68    public override IDeepCloneable Clone(Cloner cloner) {
69      return new SymbolicExpressionTreeNode(this, cloner);
70    }
71
72    internal SymbolicExpressionTreeNode()
73      : base() {
74      // don't allocate subtrees list here!
75      // because we don't want to allocate it in terminal nodes
76    }
77
78    public SymbolicExpressionTreeNode(ISymbol symbol)
79      : base() {
80      subtrees = new List<ISymbolicExpressionTreeNode>(3);
81      this.symbol = symbol;
82    }
83
84
85    [StorableHook(HookType.AfterDeserialization)]
86    private void AfterDeserialization() {
87      if (subtrees != null) {
88        foreach (var subtree in subtrees)
89          subtree.Parent = this;
90      }
91    }
92
93    public virtual bool HasLocalParameters {
94      get { return false; }
95    }
96
97    public virtual IEnumerable<ISymbolicExpressionTreeNode> Subtrees {
98      get { return subtrees; }
99    }
100
101    public virtual ISymbolicExpressionTreeGrammar Grammar {
102      get { return parent.Grammar; }
103    }
104
105    public int GetLength() {
106      if (length > 0) return length;
107      else {
108        ushort l = 1;
109        if (subtrees != null) {
110          for (int i = 0; i < subtrees.Count; i++) {
111            checked { l += (ushort)subtrees[i].GetLength(); }
112          }
113        }
114        length = l;
115        return length;
116      }
117    }
118
119    public int GetDepth() {
120      if (depth > 0) return depth;
121      else {
122        ushort d = 0;
123        if (subtrees != null) {
124          for (int i = 0; i < subtrees.Count; i++) d = Math.Max(d, (ushort)subtrees[i].GetDepth());
125        }
126        d++;
127        depth = d;
128        return depth;
129      }
130    }
131
132    public int GetBranchLevel(ISymbolicExpressionTreeNode child) {
133      return GetBranchLevel(this, child);
134    }
135
136    private static int GetBranchLevel(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode point) {
137      if (root == point)
138        return 0;
139      foreach (var subtree in root.Subtrees) {
140        int branchLevel = GetBranchLevel(subtree, point);
141        if (branchLevel < int.MaxValue)
142          return 1 + branchLevel;
143      }
144      return int.MaxValue;
145    }
146
147    public virtual void ResetLocalParameters(IRandom random) { }
148    public virtual void ShakeLocalParameters(IRandom random, double shakingFactor) { }
149
150    public int SubtreeCount {
151      get {
152        if (subtrees == null) return 0;
153        return subtrees.Count;
154      }
155    }
156
157    public virtual ISymbolicExpressionTreeNode GetSubtree(int index) {
158      return subtrees[index];
159    }
160    public virtual int IndexOfSubtree(ISymbolicExpressionTreeNode tree) {
161      return subtrees.IndexOf(tree);
162    }
163    public virtual void AddSubtree(ISymbolicExpressionTreeNode tree) {
164      subtrees.Add(tree);
165      tree.Parent = this;
166      ResetCachedValues();
167    }
168    public virtual void InsertSubtree(int index, ISymbolicExpressionTreeNode tree) {
169      subtrees.Insert(index, tree);
170      tree.Parent = this;
171      ResetCachedValues();
172    }
173    public virtual void RemoveSubtree(int index) {
174      subtrees[index].Parent = null;
175      subtrees.RemoveAt(index);
176      ResetCachedValues();
177    }
178
179    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
180      var list = new List<ISymbolicExpressionTreeNode>(GetLength()) { this };
181      int i = 0;
182      while (i != list.Count) {
183        for (int j = 0; j != list[i].SubtreeCount; ++j)
184          list.Add(list[i].GetSubtree(j));
185        ++i;
186      }
187      return list;
188    }
189
190    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix() {
191      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
192      ForEachNodePrefix((n) => list.Add(n));
193      return list;
194    }
195
196    public void ForEachNodePrefix(Action<ISymbolicExpressionTreeNode> a) {
197      a(this);
198      if (subtrees != null) {
199        //avoid linq to reduce memory pressure
200        for (int i = 0; i < subtrees.Count; i++) {
201          subtrees[i].ForEachNodePrefix(a);
202        }
203      }
204    }
205
206    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix() {
207      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
208      ForEachNodePostfix((n) => list.Add(n));
209      return list;
210    }
211
212    public void ForEachNodePostfix(Action<ISymbolicExpressionTreeNode> a) {
213      if (subtrees != null) {
214        //avoid linq to reduce memory pressure
215        for (int i = 0; i < subtrees.Count; i++) {
216          subtrees[i].ForEachNodePostfix(a);
217        }
218      }
219      a(this);
220    }
221
222    public override string ToString() {
223      if (Symbol != null) return Symbol.Name;
224      return "SymbolicExpressionTreeNode";
225    }
226
227    private void ResetCachedValues() {
228      length = 0; depth = 0;
229      SymbolicExpressionTreeNode parentNode = parent as SymbolicExpressionTreeNode;
230      if (parentNode != null) parentNode.ResetCachedValues();
231    }
232  }
233}
Note: See TracBrowser for help on using the repository browser.