Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeNode.cs @ 12891

Last change on this file since 12891 was 12891, checked in by bburlacu, 9 years ago

#1772: Merge trunk changes. Remove dead code from the genealogy analyzer.

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