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

Last change on this file since 14223 was 14223, checked in by bburlacu, 3 years ago

#2647: Fix logical mistake.

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