Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/05/19 15:44:04 (5 years ago)
Author:
abeham
Message:

#2950: merged revisions 16218, 16252, 16255, 16258, 16259, 16260, 16261, 16263, 16267, 16270, 16271, 16272, 16273, 16284, 16290, 16291, 16302, 16305, 16382, 16478 to stable

Location:
stable
Files:
5 edited
1 copied

Legend:

Unmodified
Added
Removed

  • stable

  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic

  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs

    r16218 r17090  
    3232
    3333      public bool Enabled;
    34       public int HashValue;           // the initial (fixed) hash value for this individual node/data
    35       public int CalculatedHashValue; // the calculated hash value (taking into account the children hash values)
    36 
    37       public Action<HashNode<T>[], int> Simplify;
     34      public ulong HashValue;           // the initial (fixed) hash value for this individual node/data
     35      public ulong CalculatedHashValue; // the calculated hash value (taking into account the children hash values)
     36
     37      public delegate void SimplifyAction(ref HashNode<T>[] nodes, int i);
     38      public SimplifyAction Simplify;
     39
    3840      public IComparer<T> Comparer;
    3941
    40       public bool IsChild => Arity == 0;
     42      public bool IsLeaf => Arity == 0;
    4143
    4244      public HashNode(IComparer<T> comparer) {
    … …  
    6769
    6870      public override int GetHashCode() {
    69         return CalculatedHashValue;
     71        return (int)CalculatedHashValue;
    7072      }
    7173
    … …  
    7981    }
    8082
    81     public static int ComputeHash<T>(this HashNode<T>[] nodes, int i) where T : class {
     83    public static ulong ComputeHash<T>(this HashNode<T>[] nodes, int i, Func<byte[], ulong> hashFunction) where T : class {
    8284      var node = nodes[i];
    83       var hashes = new int[node.Arity + 1];
    84       int idx = 0;
    85       foreach (int c in nodes.IterateChildren(i)) {
    86         hashes[idx++] = nodes[c].CalculatedHashValue;
    87       }
    88       hashes[idx] = node.HashValue;
    89       return HashUtil.JSHash(hashes);
    90     }
    91 
    92     public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes) where T : class {
    93       var reduced = nodes.Reduce();
    94       reduced.Sort();
     85      const int size = sizeof(ulong);
     86      var hashes = new ulong[node.Arity + 1];
     87      var bytes = new byte[(node.Arity + 1) * size];
     88
     89      for (int j = i - 1, k = 0; k < node.Arity; ++k, j -= 1 + nodes[j].Size) {
     90        hashes[k] = nodes[j].CalculatedHashValue;
     91      }
     92      hashes[node.Arity] = node.HashValue;
     93      Buffer.BlockCopy(hashes, 0, bytes, 0, bytes.Length);
     94      return hashFunction(bytes);
     95    }
     96
     97    // set the enabled state for the whole subtree rooted at this node
     98    public static void SetEnabled<T>(this HashNode<T>[] nodes, int i, bool enabled) where T : class {
     99      nodes[i].Enabled = enabled;
     100      for (int j = i - nodes[i].Size; j < i; ++j)
     101        nodes[j].Enabled = enabled;
     102    }
     103
     104    public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
     105      var reduced = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
    95106
    96107      for (int i = 0; i < reduced.Length; ++i) {
    97108        var node = reduced[i];
    98         if (node.IsChild) {
    99           continue;
    100         }
    101         node.Simplify?.Invoke(reduced, i);
     109        if (node.IsLeaf) {
     110          continue;
     111        }
     112        node.Simplify?.Invoke(ref reduced, i);
    102113      }
    103114      // detect if anything was simplified
    … …  
    117128        }
    118129      }
    119       simplified.UpdateNodeSizes();
    120       simplified.Sort();
    121       return simplified;
    122     }
    123 
    124     public static void Sort<T>(this HashNode<T>[] nodes) where T : class {
     130      return simplified.UpdateNodeSizes().Reduce().Sort(hashFunction);
     131    }
     132
     133    public static HashNode<T>[] Sort<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
     134      int sort(int a, int b) => nodes[a].CompareTo(nodes[b]);
     135
    125136      for (int i = 0; i < nodes.Length; ++i) {
    126137        var node = nodes[i];
    127138
    128         if (node.IsChild) {
     139        if (node.IsLeaf) {
    129140          continue;
    130141        }
    … …  
    138149          } else { // i have some non-terminal children
    139150            var sorted = new HashNode<T>[size];
    140             var indices = nodes.IterateChildren(i);
    141             Array.Sort(indices, (a, b) => nodes[a].CompareTo(nodes[b]));
     151            var indices = new int[node.Arity];
     152            for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
     153              indices[k] = j;
     154            }
     155            Array.Sort(indices, sort);
    142156
    143157            int idx = 0;
    144158            foreach (var j in indices) {
    145159              var child = nodes[j];
    146               if (!child.IsChild) { // must copy complete subtree
     160              if (!child.IsLeaf) { // must copy complete subtree
    147161                Array.Copy(nodes, j - child.Size, sorted, idx, child.Size);
    148162                idx += child.Size;
    … …  
    153167          }
    154168        }
    155         node.CalculatedHashValue = nodes.ComputeHash(i);
    156       }
     169        node.CalculatedHashValue = nodes.ComputeHash(i, hashFunction);
     170      }
     171      return nodes;
    157172    }
    158173
    159174    /// <summary>
    160     /// Get a function node's child indices from left to right
     175    /// Get a function node's child indicest
    161176    /// </summary>
    162     /// <typeparam name="T"></typeparam>
    163     /// <param name="nodes"></param>
    164     /// <param name="i"></param>
     177    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
     178    /// <param name="nodes">An array of hash nodes with up-to-date node sizes</param>
     179    /// <param name="i">The index in the array of hash nodes of the node whose children we want to iterate</param>
    165180    /// <returns>An array containing child indices</returns>
    166181    public static int[] IterateChildren<T>(this HashNode<T>[] nodes, int i) where T : class {
    … …  
    170185      var idx = i - 1;
    171186      for (int j = 0; j < arity; ++j) {
    172         while (!nodes[idx].Enabled) { --idx; } // skip nodes possibly disabled by simplification
    173187        children[j] = idx;
    174188        idx -= 1 + nodes[idx].Size;
    … …  
    177191    }
    178192
    179     public static void UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
     193    public static HashNode<T>[] UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
    180194      for (int i = 0; i < nodes.Length; ++i) {
    181195        var node = nodes[i];
    182         if (node.IsChild) {
     196        if (node.IsLeaf) {
    183197          node.Size = 0;
    184198          continue;
    185199        }
    186200        node.Size = node.Arity;
    187         foreach (int j in nodes.IterateChildren(i)) {
     201
     202        for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
    188203          node.Size += nodes[j].Size;
    189204        }
    190205      }
    191     }
    192 
    193     /// <summary>
    194     /// Reduce nodes of the same type according to arithmetic rules
    195     /// </summary>
    196     /// <typeparam name="T"></typeparam>
    197     /// <param name="g">The given grammar (controls symbol arities)</param>
    198     /// <param name="nodes">The node array</param>
    199     /// <param name="i">Parent index</param>
    200     /// <param name="j">Child index</param>
    201     private static void Reduce<T>(this HashNode<T>[] nodes, int i, int j) where T : class {
    202       var p = nodes[i]; // parent node
    203       var c = nodes[j]; // child node
    204 
    205       if (c.IsChild)
    206         return;
    207 
    208       foreach (int k in nodes.IterateChildren(j)) {
    209         if (nodes[k].IsChild) continue;
    210         nodes.Reduce(j, k);
    211       }
    212 
    213       // handle commutative symbols (add, mul)
    214       if (p.IsCommutative && p.HashValue == c.HashValue) {
    215         c.Enabled = false;
    216         p.Arity += c.Arity - 1;
    217       }
    218     }
    219 
    220     public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
    221       nodes.UpdateNodeSizes();
    222       int i = nodes.Length - 1;
    223       foreach (int c in nodes.IterateChildren(i)) {
    224         if (nodes[c].IsChild) continue;
    225         nodes.Reduce(i, c);
    226       }
     206      return nodes;
     207    }
     208
     209    private static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
    227210      int count = 0;
    228       foreach (var node in nodes) {
    229         if (!node.Enabled) { ++count; }
     211      for (int i = 0; i < nodes.Length; ++i) {
     212        var node = nodes[i];
     213        if (node.IsLeaf || !node.IsCommutative) {
     214          continue;
     215        }
     216
     217        var arity = node.Arity;
     218        for (int j = i - 1, k = 0; k < arity; j -= 1 + nodes[j].Size, ++k) {
     219          if (node.HashValue == nodes[j].HashValue) {
     220            nodes[j].Enabled = false;
     221            node.Arity += nodes[j].Arity - 1;
     222            ++count;
     223          }
     224        }
    230225      }
    231226      if (count == 0)
    … …  
    233228
    234229      var reduced = new HashNode<T>[nodes.Length - count];
    235       i = 0;
     230      var idx = 0;
    236231      foreach (var node in nodes) {
    237         if (node.Enabled) { reduced[i++] = node; }
    238       }
    239       reduced.UpdateNodeSizes();
    240       return reduced;
     232        if (node.Enabled) { reduced[idx++] = node; }
     233      }
     234      return reduced.UpdateNodeSizes();
    241235    }
    242236  }

  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashUtil.cs

    r16218 r17090  
    2020#endregion
    2121
     22
    2223using System;
    2324using System.Security.Cryptography;
    … …  
    2829
    2930    // A simple hash function from Robert Sedgwicks Algorithms in C book.I've added some simple optimizations to the algorithm in order to speed up its hashing process.
    30     public static int RSHash(int[] input) {
     31    public static ulong RSHash(byte[] input) {
    3132      const int b = 378551;
    32       int a = 63689;
    33       int hash = 0;
     33      ulong a = 63689;
     34      ulong hash = 0;
    3435
    3536      foreach (var v in input) {
    … …  
    4142
    4243    // A bitwise hash function written by Justin Sobel
    43     public static int JSHash(int[] input) {
    44       int hash = 1315423911;
     44    public static ulong JSHash(byte[] input) {
     45      ulong hash = 1315423911;
    4546      for (int i = 0; i < input.Length; ++i)
    4647        hash ^= (hash << 5) + input[i] + (hash >> 2);
    … …  
    4950
    5051    // This hash function comes from Brian Kernighan and Dennis Ritchie's book "The C Programming Language". It is a simple hash function using a strange set of possible seeds which all constitute a pattern of 31....31...31 etc, it seems to be very similar to the DJB hash function.
    51     public static int BKDRHash(int[] input) {
    52       const int seed = 131;
    53       int hash = 0;
     52    public static ulong BKDRHash(byte[] input) {
     53      ulong seed = 131;
     54      ulong hash = 0;
    5455      foreach (var v in input) {
    5556        hash = (hash * seed) + v;
    … …  
    5960
    6061    // This is the algorithm of choice which is used in the open source SDBM project. The hash function seems to have a good over-all distribution for many different data sets. It seems to work well in situations where there is a high variance in the MSBs of the elements in a data set.
    61     public static int SDBMHash(int[] input) {
    62       int hash = 0;
     62    public static ulong SDBMHash(byte[] input) {
     63      ulong hash = 0;
    6364      foreach (var v in input) {
    6465        hash = v + (hash << 6) + (hash << 16) - hash;
    … …  
    6869
    6970    // An algorithm produced by Professor Daniel J. Bernstein and shown first to the world on the usenet newsgroup comp.lang.c. It is one of the most efficient hash functions ever published.
    70     public static int DJBHash(int[] input) {
    71       int hash = 5381;
     71    public static ulong DJBHash(byte[] input) {
     72      ulong hash = 5381;
    7273      foreach (var v in input) {
    7374        hash = (hash << 5) + hash + v;
    … …  
    7778
    7879    // An algorithm proposed by Donald E.Knuth in The Art Of Computer Programming Volume 3, under the topic of sorting and search chapter 6.4.
    79     public static int DEKHash(int[] input) {
    80       int hash = input.Length;
     80    public static ulong DEKHash(byte[] input) {
     81      ulong hash = (ulong)input.Length;
    8182      foreach (var v in input) {
    8283        hash = (hash << 5) ^ (hash >> 27) ^ v;
    … …  
    8586    }
    8687
    87     public static int CryptoHash(HashAlgorithm ha, int[] input) {
    88       return BitConverter.ToInt32(ha.ComputeHash(input.ToByteArray()), 0);
    89     }
    90 
    91     public static byte[] ToByteArray(this int[] input) {
    92       const int size = sizeof(int);
    93       var bytes = new byte[input.Length * sizeof(int)];
    94       for (int i = 0; i < input.Length; ++i) {
    95         Array.Copy(BitConverter.GetBytes(bytes[i]), 0, bytes, i * size, size);
    96       }
    97       return bytes;
     88    public static ulong CryptoHash(HashAlgorithm ha, byte[] input) {
     89      return BitConverter.ToUInt64(ha.ComputeHash(input), 0);
    9890    }
    9991  }

  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs

    r16218 r17090  
    1 using System.Collections.Generic;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2019 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;
    224using System.Linq;
    325using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    … …  
    1739
    1840    private static readonly ISymbolicExpressionTreeNodeComparer comparer = new SymbolicExpressionTreeNodeComparer();
    19 
    20     public static int ComputeHash(this ISymbolicExpressionTree tree) {
    21       return ComputeHash(tree.Root.GetSubtree(0).GetSubtree(0));
    22     }
    23 
    24     public static Dictionary<ISymbolicExpressionTreeNode, int> ComputeNodeHashes(this ISymbolicExpressionTree tree) {
    25       var root = tree.Root.GetSubtree(0).GetSubtree(0);
    26       var nodes = root.MakeNodes();
    27       nodes.UpdateNodeSizes();
    28 
    29       for (int i = 0; i < nodes.Length; ++i) {
    30         if (nodes[i].IsChild)
    31           continue;
    32         nodes[i].CalculatedHashValue = nodes.ComputeHash(i);
    33       }
    34       return nodes.ToDictionary(x => x.Data, x => x.CalculatedHashValue);
    35     }
    36 
    37     public static int ComputeHash(this ISymbolicExpressionTreeNode treeNode) {
    38       var hashNodes = treeNode.MakeNodes();
    39       var simplified = hashNodes.Simplify();
    40       return ComputeHash(simplified);
    41     }
    42 
    43     public static int ComputeHash(this HashNode<ISymbolicExpressionTreeNode>[] nodes) {
    44       int hash = 1315423911;
    45       foreach (var node in nodes)
    46         hash ^= (hash << 5) + node.CalculatedHashValue + (hash >> 2);
    47       return hash;
    48     }
    49 
    50     public static HashNode<ISymbolicExpressionTreeNode> ToHashNode(this ISymbolicExpressionTreeNode node) {
     41    private static ISymbolicExpressionTreeNode ActualRoot(this ISymbolicExpressionTree tree) => tree.Root.GetSubtree(0).GetSubtree(0);
     42
     43    #region tree hashing
     44    public static ulong[] Hash(this ISymbolicExpressionTree tree, bool simplify = false, bool strict = false) {
     45      return tree.ActualRoot().Hash(simplify, strict);
     46    }
     47
     48    public static ulong[] Hash(this ISymbolicExpressionTreeNode node, bool simplify = false, bool strict = false) {
     49      ulong hashFunction(byte[] input) => HashUtil.DJBHash(input);
     50
     51      var hashNodes = simplify ? node.MakeNodes(strict).Simplify(hashFunction) : node.MakeNodes(strict).Sort(hashFunction);
     52      var hashes = new ulong[hashNodes.Length];
     53      for (int i = 0; i < hashes.Length; ++i) {
     54        hashes[i] = hashNodes[i].CalculatedHashValue;
     55      }
     56      return hashes;
     57    }
     58
     59    public static ulong ComputeHash(this ISymbolicExpressionTree tree, bool simplify = false, bool strict = false) {
     60      return ComputeHash(tree.ActualRoot(), simplify, strict);
     61    }
     62
     63    public static ulong ComputeHash(this ISymbolicExpressionTreeNode treeNode, bool simplify = false, bool strict = false) {
     64      return treeNode.Hash(simplify, strict).Last();
     65    }
     66
     67    public static HashNode<ISymbolicExpressionTreeNode> ToHashNode(this ISymbolicExpressionTreeNode node, bool strict = false) {
    5168      var symbol = node.Symbol;
    5269      var name = symbol.Name;
    53       if (symbol is Variable) {
    54         var variableTreeNode = (VariableTreeNode)node;
    55         name = variableTreeNode.VariableName;
    56       }
    57       var hash = name.GetHashCode();
     70      if (node is ConstantTreeNode constantNode) {
     71        name = strict ? constantNode.Value.ToString() : symbol.Name;
     72      } else if (node is VariableTreeNode variableNode) {
     73        name = strict ? variableNode.Weight.ToString() + variableNode.VariableName : variableNode.VariableName;
     74      }
     75      var hash = (ulong)name.GetHashCode();
    5876      var hashNode = new HashNode<ISymbolicExpressionTreeNode>(comparer) {
    5977        Data = node,
    … …  
    7997    }
    8098
    81     public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTreeNode node) {
    82       return node.IterateNodesPostfix().Select(ToHashNode).ToArray();
    83     }
     99    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTree tree, bool strict = false) {
     100      return MakeNodes(tree.ActualRoot(), strict);
     101    }
     102
     103    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTreeNode node, bool strict = false) {
     104      return node.IterateNodesPostfix().Select(x => x.ToHashNode(strict)).ToArray().UpdateNodeSizes();
     105    }
     106    #endregion
     107
     108    #region tree similarity
     109    public static double ComputeSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool simplify = false, bool strict = false) {
     110      return ComputeSimilarity(t1.ActualRoot(), t2.ActualRoot(), simplify, strict);
     111    }
     112
     113    public static double ComputeSimilarity(ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, bool simplify = false, bool strict = false) {
     114      var lh = t1.Hash(simplify, strict);
     115      var rh = t2.Hash(simplify, strict);
     116
     117      Array.Sort(lh);
     118      Array.Sort(rh);
     119
     120      return ComputeSimilarity(lh, rh);
     121    }
     122
     123    // requires lhs and rhs to be sorted
     124    public static int IntersectCount(this ulong[] lh, ulong[] rh) {
     125      int count = 0;
     126      for (int i = 0, j = 0; i < lh.Length && j < rh.Length;) {
     127        var h1 = lh[i];
     128        var h2 = rh[j];
     129        if (h1 == h2) {
     130          ++count;
     131          ++i;
     132          ++j;
     133        } else if (h1 < h2) {
     134          ++i;
     135        } else if (h1 > h2) {
     136          ++j;
     137        }
     138      }
     139      return count;
     140    }
     141
     142    public static IEnumerable<ulong> Intersect(this ulong[] lh, ulong[] rh) {
     143      for (int i = 0, j = 0; i < lh.Length && j < rh.Length;) {
     144        var h1 = lh[i];
     145        var h2 = rh[j];
     146        if (h1 == h2) {
     147          yield return h1;
     148          ++i;
     149          ++j;
     150        } else if (h1 < h2) {
     151          ++i;
     152        } else if (h1 > h2) {
     153          ++j;
     154        }
     155      }
     156    }
     157
     158    // this will only work if lh and rh are sorted
     159    public static double ComputeSimilarity(ulong[] lh, ulong[] rh) {
     160      return 2d * IntersectCount(lh, rh) / (lh.Length + rh.Length);
     161    }
     162
     163    public static double ComputeAverageSimilarity(IList<ISymbolicExpressionTree> trees, bool simplify = false, bool strict = false) {
     164      var total = trees.Count * (trees.Count - 1) / 2;
     165      double avg = 0;
     166      var hashes = new ulong[trees.Count][];
     167      // build hash arrays
     168      for (int i = 0; i < trees.Count; ++i) {
     169        var nodes = trees[i].MakeNodes(strict);
     170        hashes[i] = (simplify ? nodes.Simplify(HashUtil.DJBHash) : nodes.Sort(HashUtil.DJBHash)).Select(x => x.CalculatedHashValue).ToArray();
     171        Array.Sort(hashes[i]);
     172      }
     173      // compute similarity matrix
     174      for (int i = 0; i < trees.Count - 1; ++i) {
     175        for (int j = i + 1; j < trees.Count; ++j) {
     176          avg += ComputeSimilarity(hashes[i], hashes[j]);
     177        }
     178      }
     179      return avg / total;
     180    }
     181
     182    public static double[,] ComputeSimilarityMatrix(IList<ISymbolicExpressionTree> trees, bool simplify = false, bool strict = false) {
     183      var sim = new double[trees.Count, trees.Count];
     184      var hashes = new ulong[trees.Count][];
     185      // build hash arrays
     186      for (int i = 0; i < trees.Count; ++i) {
     187        var nodes = trees[i].MakeNodes(strict);
     188        hashes[i] = (simplify ? nodes.Simplify(HashUtil.DJBHash) : nodes.Sort(HashUtil.DJBHash)).Select(x => x.CalculatedHashValue).ToArray();
     189        Array.Sort(hashes[i]);
     190      }
     191      // compute similarity matrix
     192      for (int i = 0; i < trees.Count - 1; ++i) {
     193        for (int j = i + 1; j < trees.Count; ++j) {
     194          sim[i, j] = sim[j, i] = ComputeSimilarity(hashes[i], hashes[j]);
     195        }
     196      }
     197      return sim;
     198    }
     199    #endregion
    84200
    85201    #region parse a nodes array back into a tree
    … …  
    98214        var node = nodes[i];
    99215
    100         if (node.IsChild) {
     216        if (node.IsLeaf) {
    101217          if (node.Data is VariableTreeNode variable) {
    102218            var variableTreeNode = (VariableTreeNode)treeNodes[i];
    103219            variableTreeNode.VariableName = variable.VariableName;
    104             variableTreeNode.Weight = 1;
     220            variableTreeNode.Weight = variable.Weight;
    105221          } else if (node.Data is ConstantTreeNode @const) {
    106222            var constantTreeNode = (ConstantTreeNode)treeNodes[i];
    … …  
    127243    #region tree simplification
    128244    // these simplification methods rely on the assumption that child nodes of the current node have already been simplified
    129     // (in other words simplification should be applied in a bottom-up fashion) 
     245    // (in other words simplification should be applied in a bottom-up fashion)
    130246    public static ISymbolicExpressionTree Simplify(ISymbolicExpressionTree tree) {
     247      ulong hashFunction(byte[] bytes) => HashUtil.JSHash(bytes);
    131248      var root = tree.Root.GetSubtree(0).GetSubtree(0);
    132249      var nodes = root.MakeNodes();
    133       var simplified = nodes.Simplify();
     250      var simplified = nodes.Simplify(hashFunction);
    134251      return simplified.ToTree();
    135252    }
    136253
    137     public static void SimplifyAddition(HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
     254    public static void SimplifyAddition(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
    138255      // simplify additions of terms by eliminating terms with the same symbol and hash
    139256      var children = nodes.IterateChildren(i);
    140257
     258      // we always assume the child nodes are sorted
    141259      var curr = children[0];
    142260      var node = nodes[i];
    … …  
    144262      foreach (var j in children.Skip(1)) {
    145263        if (nodes[j] == nodes[curr]) {
    146           for (int k = j - nodes[j].Size; k <= j; ++k) {
    147             nodes[k].Enabled = false;
    148           }
     264          nodes.SetEnabled(j, false);
    149265          node.Arity--;
    150266        } else {
    … …  
    157273    }
    158274
    159     // simplify multiplications by reducing constants and div terms 
    160     public static void SimplifyMultiplication(HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
     275    // simplify multiplications by reducing constants and div terms
     276    public static void SimplifyMultiplication(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
    161277      var node = nodes[i];
    162278      var children = nodes.IterateChildren(i);
    … …  
    174290            var d = children[k];
    175291            if (nodes[d].Data.Symbol is Constant) {
    176               ((ConstantTreeNode)child.Data).Value *= ((ConstantTreeNode)nodes[d].Data).Value;
    177292              nodes[d].Enabled = false;
    178293              node.Arity--;
    … …  
    207322    }
    208323
    209     public static void SimplifyDivision(HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
     324    public static void SimplifyDivision(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
    210325      var node = nodes[i];
    211326      var children = nodes.IterateChildren(i);
    212327
    213       if (children.All(x => nodes[x].Data.Symbol is Constant)) {
     328      var tmp = nodes;
     329
     330      if (children.All(x => tmp[x].Data.Symbol is Constant)) {
    214331        var v = ((ConstantTreeNode)nodes[children.First()].Data).Value;
    215332        if (node.Arity == 1) {
    … …  
    242359    }
    243360
    244     public static void SimplifyUnaryNode(HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
     361    public static void SimplifyUnaryNode(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
    245362      // check if the child of the unary node is a constant, then the whole node can be simplified
    246363      var parent = nodes[i];
    … …  
    257374    }
    258375
    259     public static void SimplifyBinaryNode(HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
     376    public static void SimplifyBinaryNode(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
    260377      var children = nodes.IterateChildren(i);
    261       if (children.All(x => nodes[x].Data.Symbol is Constant)) {
     378      var tmp = nodes;
     379      if (children.All(x => tmp[x].Data.Symbol is Constant)) {
    262380        foreach (var j in children) {
    263381          nodes[j].Enabled = false;
Note: See TracChangeset for help on using the changeset viewer.