Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeNode.cs @ 7799

Last change on this file since 7799 was 7799, checked in by bburlacu, 11 years ago

#1772: Sanitized IGenealogyGraph interface, implemented new graph arc semantics (an arc signifies an interaction between the two nodes that it connects and has a data object containing specific information about the interaction).

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