[3223] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[14185] | 3 | * Copyright (C) 2002-2016 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 |
|
---|
| 22 | using System;
|
---|
[4068] | 23 | using System.Collections.Generic;
|
---|
[4722] | 24 | using HeuristicLab.Common;
|
---|
[3223] | 25 | using HeuristicLab.Core;
|
---|
| 26 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 27 |
|
---|
| 28 | namespace 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)
|
---|
[14221] | 46 | [Storable]
|
---|
[5510] | 47 | private ISymbolicExpressionTreeNode parent;
|
---|
| 48 | public ISymbolicExpressionTreeNode Parent {
|
---|
[3484] | 49 | get { return parent; }
|
---|
| 50 | set { parent = value; }
|
---|
| 51 | }
|
---|
[3223] | 52 |
|
---|
[4722] | 53 | [StorableConstructor]
|
---|
| 54 | protected SymbolicExpressionTreeNode(bool deserializing) { }
|
---|
| 55 | protected SymbolicExpressionTreeNode(SymbolicExpressionTreeNode original, Cloner cloner)
|
---|
[7836] | 56 | : base(original, cloner) {
|
---|
[4722] | 57 | symbol = original.symbol; // symbols are reused
|
---|
[7654] | 58 | length = original.length;
|
---|
| 59 | depth = original.depth;
|
---|
[6684] | 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 | }
|
---|
[4722] | 67 | }
|
---|
| 68 | }
|
---|
| 69 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 70 | return new SymbolicExpressionTreeNode(this, cloner);
|
---|
| 71 | }
|
---|
| 72 |
|
---|
| 73 | internal SymbolicExpressionTreeNode()
|
---|
| 74 | : base() {
|
---|
[3486] | 75 | // don't allocate subtrees list here!
|
---|
| 76 | // because we don't want to allocate it in terminal nodes
|
---|
| 77 | }
|
---|
[3484] | 78 |
|
---|
[5510] | 79 | public SymbolicExpressionTreeNode(ISymbol symbol)
|
---|
[4722] | 80 | : base() {
|
---|
[5733] | 81 | subtrees = new List<ISymbolicExpressionTreeNode>(3);
|
---|
[3223] | 82 | this.symbol = symbol;
|
---|
| 83 | }
|
---|
| 84 |
|
---|
| 85 |
|
---|
[3486] | 86 | [StorableHook(HookType.AfterDeserialization)]
|
---|
[4722] | 87 | private void AfterDeserialization() {
|
---|
[5733] | 88 | if (subtrees != null) {
|
---|
| 89 | foreach (var subtree in subtrees)
|
---|
[14223] | 90 | if (subtree.Parent == null)
|
---|
[14221] | 91 | subtree.Parent = this;
|
---|
[3486] | 92 | }
|
---|
| 93 | }
|
---|
| 94 |
|
---|
[3244] | 95 | public virtual bool HasLocalParameters {
|
---|
[3223] | 96 | get { return false; }
|
---|
| 97 | }
|
---|
| 98 |
|
---|
[5733] | 99 | public virtual IEnumerable<ISymbolicExpressionTreeNode> Subtrees {
|
---|
| 100 | get { return subtrees; }
|
---|
[3223] | 101 | }
|
---|
| 102 |
|
---|
[5499] | 103 | public virtual ISymbolicExpressionTreeGrammar Grammar {
|
---|
[3369] | 104 | get { return parent.Grammar; }
|
---|
| 105 | }
|
---|
| 106 |
|
---|
[5549] | 107 | public int GetLength() {
|
---|
| 108 | if (length > 0) return length;
|
---|
[3988] | 109 | else {
|
---|
[13579] | 110 | ushort l = 1;
|
---|
[5733] | 111 | if (subtrees != null) {
|
---|
| 112 | for (int i = 0; i < subtrees.Count; i++) {
|
---|
[13579] | 113 | checked { l += (ushort)subtrees[i].GetLength(); }
|
---|
[4524] | 114 | }
|
---|
[4106] | 115 | }
|
---|
[13579] | 116 | length = l;
|
---|
[5549] | 117 | return length;
|
---|
[3988] | 118 | }
|
---|
[3223] | 119 | }
|
---|
| 120 |
|
---|
[5549] | 121 | public int GetDepth() {
|
---|
| 122 | if (depth > 0) return depth;
|
---|
[3988] | 123 | else {
|
---|
[13579] | 124 | ushort d = 0;
|
---|
[5733] | 125 | if (subtrees != null) {
|
---|
[13579] | 126 | for (int i = 0; i < subtrees.Count; i++) d = Math.Max(d, (ushort)subtrees[i].GetDepth());
|
---|
[4106] | 127 | }
|
---|
[13579] | 128 | d++;
|
---|
| 129 | depth = d;
|
---|
[5549] | 130 | return depth;
|
---|
[3988] | 131 | }
|
---|
[3223] | 132 | }
|
---|
[3294] | 133 |
|
---|
[7506] | 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 |
|
---|
[3338] | 149 | public virtual void ResetLocalParameters(IRandom random) { }
|
---|
| 150 | public virtual void ShakeLocalParameters(IRandom random, double shakingFactor) { }
|
---|
| 151 |
|
---|
[6803] | 152 | public int SubtreeCount {
|
---|
[5686] | 153 | get {
|
---|
[5733] | 154 | if (subtrees == null) return 0;
|
---|
| 155 | return subtrees.Count;
|
---|
[5686] | 156 | }
|
---|
| 157 | }
|
---|
| 158 |
|
---|
[5733] | 159 | public virtual ISymbolicExpressionTreeNode GetSubtree(int index) {
|
---|
| 160 | return subtrees[index];
|
---|
[5510] | 161 | }
|
---|
[5733] | 162 | public virtual int IndexOfSubtree(ISymbolicExpressionTreeNode tree) {
|
---|
| 163 | return subtrees.IndexOf(tree);
|
---|
[5510] | 164 | }
|
---|
[5733] | 165 | public virtual void AddSubtree(ISymbolicExpressionTreeNode tree) {
|
---|
| 166 | subtrees.Add(tree);
|
---|
[3369] | 167 | tree.Parent = this;
|
---|
[3988] | 168 | ResetCachedValues();
|
---|
[3294] | 169 | }
|
---|
[5733] | 170 | public virtual void InsertSubtree(int index, ISymbolicExpressionTreeNode tree) {
|
---|
| 171 | subtrees.Insert(index, tree);
|
---|
[3369] | 172 | tree.Parent = this;
|
---|
[3988] | 173 | ResetCachedValues();
|
---|
[3294] | 174 | }
|
---|
[5733] | 175 | public virtual void RemoveSubtree(int index) {
|
---|
| 176 | subtrees[index].Parent = null;
|
---|
| 177 | subtrees.RemoveAt(index);
|
---|
[3988] | 178 | ResetCachedValues();
|
---|
[3294] | 179 | }
|
---|
| 180 |
|
---|
[7795] | 181 | public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
|
---|
[12509] | 182 | var list = new List<ISymbolicExpressionTreeNode>(GetLength()) { this };
|
---|
[7795] | 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 |
|
---|
[5510] | 192 | public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix() {
|
---|
| 193 | List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
|
---|
[3997] | 194 | ForEachNodePrefix((n) => list.Add(n));
|
---|
| 195 | return list;
|
---|
[3294] | 196 | }
|
---|
| 197 |
|
---|
[5510] | 198 | public void ForEachNodePrefix(Action<ISymbolicExpressionTreeNode> a) {
|
---|
[3988] | 199 | a(this);
|
---|
[12509] | 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);
|
---|
[4106] | 204 | }
|
---|
[3988] | 205 | }
|
---|
| 206 | }
|
---|
| 207 |
|
---|
[5510] | 208 | public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix() {
|
---|
| 209 | List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
|
---|
[3997] | 210 | ForEachNodePostfix((n) => list.Add(n));
|
---|
| 211 | return list;
|
---|
[3294] | 212 | }
|
---|
[3988] | 213 |
|
---|
[5510] | 214 | public void ForEachNodePostfix(Action<ISymbolicExpressionTreeNode> a) {
|
---|
[12509] | 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);
|
---|
[4106] | 219 | }
|
---|
[3988] | 220 | }
|
---|
| 221 | a(this);
|
---|
| 222 | }
|
---|
| 223 |
|
---|
[3442] | 224 | public override string ToString() {
|
---|
[6375] | 225 | if (Symbol != null) return Symbol.Name;
|
---|
| 226 | return "SymbolicExpressionTreeNode";
|
---|
[3442] | 227 | }
|
---|
[3988] | 228 |
|
---|
| 229 | private void ResetCachedValues() {
|
---|
[5549] | 230 | length = 0; depth = 0;
|
---|
[5510] | 231 | SymbolicExpressionTreeNode parentNode = parent as SymbolicExpressionTreeNode;
|
---|
| 232 | if (parentNode != null) parentNode.ResetCachedValues();
|
---|
[3988] | 233 | }
|
---|
[3223] | 234 | }
|
---|
| 235 | }
|
---|