Changeset 3988


Ignore:
Timestamp:
06/30/10 15:25:00 (9 years ago)
Author:
gkronber
Message:

Added caching of tree size and height values and changed postfix and prefix iteration methods in SymbolicExpressionTreeNodes. #938

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs

    r3905 r3988  
    3939    [Storable]
    4040    private Symbol symbol;
     41
     42    // cached values to prevent unnecessary tree iterations
     43    private short size;
     44    private short height;
     45    private List<SymbolicExpressionTreeNode> prefixForm;
     46    private List<SymbolicExpressionTreeNode> postfixForm;
     47
    4148    public Symbol Symbol {
    4249      get { return symbol; }
     
    6471    protected SymbolicExpressionTreeNode(SymbolicExpressionTreeNode original) {
    6572      symbol = original.symbol;
    66       subTrees = new List<SymbolicExpressionTreeNode>();
     73      subTrees = new List<SymbolicExpressionTreeNode>(original.SubTrees.Count);
    6774      foreach (var subtree in original.SubTrees) {
    6875        AddSubTree((SymbolicExpressionTreeNode)subtree.Clone());
     
    9198
    9299    public int GetSize() {
    93       int size = 1;
    94       foreach (SymbolicExpressionTreeNode tree in SubTrees) size += tree.GetSize();
    95       return size;
     100      if (size > 0) return size;
     101      else {
     102        size = 1;
     103        for (int i = 0; i < SubTrees.Count; i++) size += (short)SubTrees[i].GetSize();
     104        return size;
     105      }
    96106    }
    97107
    98108    public int GetHeight() {
    99       int maxHeight = 0;
    100       foreach (SymbolicExpressionTreeNode tree in SubTrees) maxHeight = Math.Max(maxHeight, tree.GetHeight());
    101       return maxHeight + 1;
     109      if (height > 0) return height;
     110      else {
     111        for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (short)SubTrees[i].GetHeight());
     112        height++;
     113        return height;
     114      }
    102115    }
    103116
     
    108121      subTrees.Add(tree);
    109122      tree.Parent = this;
     123      ResetCachedValues();
    110124    }
    111125
     
    113127      subTrees.Insert(index, tree);
    114128      tree.Parent = this;
     129      ResetCachedValues();
    115130    }
    116131
     
    118133      subTrees[index].Parent = null;
    119134      subTrees.RemoveAt(index);
     135      ResetCachedValues();
    120136    }
    121137
    122138    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix() {
    123       if (SubTrees != null) {
    124         return (new SymbolicExpressionTreeNode[] { this })
    125           .Concat(SubTrees.SelectMany(tree => tree.IterateNodesPrefix()));
    126       } else {
    127         return new SymbolicExpressionTreeNode[] { this };
     139      if (prefixForm == null) {
     140        prefixForm = new List<SymbolicExpressionTreeNode>(200);
     141        ForEachNodePrefix(x => prefixForm.Add(x));
     142      }
     143      return prefixForm;
     144    }
     145
     146    private void ForEachNodePrefix(Action<SymbolicExpressionTreeNode> a) {
     147      a(this);
     148      for (int i = 0; i < SubTrees.Count; i++) {
     149        SubTrees[i].ForEachNodePrefix(a);
    128150      }
    129151    }
    130152
    131153    public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPostfix() {
    132       if (SubTrees != null) {
    133         return SubTrees.SelectMany(tree => tree.IterateNodesPrefix())
    134           .Concat(new SymbolicExpressionTreeNode[] { this });
    135       } else {
    136         return new SymbolicExpressionTreeNode[] { this };
     154      if (postfixForm == null) {
     155        postfixForm = new List<SymbolicExpressionTreeNode>(200);
     156        ForEachNodePostfix(x => postfixForm.Add(x));
    137157      }
     158      return postfixForm;
    138159    }
     160
     161    private void ForEachNodePostfix(Action<SymbolicExpressionTreeNode> a) {
     162      for (int i = 0; i < SubTrees.Count; i++) {
     163        SubTrees[i].ForEachNodePrefix(a);
     164      }
     165      a(this);
     166    }
     167
    139168    public IEnumerable<Symbol> GetAllowedSymbols(int argumentIndex) {
    140169      return Grammar.Symbols.Where(s => Grammar.IsAllowedChild(Symbol, s, argumentIndex));
     
    158187      return Symbol.Name;
    159188    }
     189
     190    private void ResetCachedValues() {
     191      size = 0; height = 0;
     192      prefixForm = null; postfixForm = null;
     193      if (parent != null) parent.ResetCachedValues();
     194    }
    160195  }
    161196}
Note: See TracChangeset for help on using the changeset viewer.