Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 10703 was 9456, checked in by swagner, 12 years ago

Updated copyright year and added some missing license headers (#1889)

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