1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022019 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 


22  using System;


23  using System.Linq;


24 


25  namespace HeuristicLab.Problems.DataAnalysis.Symbolic {


26  public static class SymbolicExpressionHashExtensions {


27  /// <summary>


28  /// Holds data that is necessary to handle tree nodes in hashing / simplification.


29  /// </summary>


30  /// <typeparam name="T">The tree node type</typeparam>


31  public sealed class HashNode<T> : IComparable<HashNode<T>>, IEquatable<HashNode<T>> where T : class {


32  public T Data;


33  public int Arity;


34  public int Size;


35  public bool IsCommutative;


36 


37  public bool Enabled;


38  public ulong HashValue; // the initial (fixed) hash value for this individual node/data


39  public ulong CalculatedHashValue; // the calculated hash value (taking into account the children hash values)


40 


41  public delegate void SimplifyAction(ref HashNode<T>[] nodes, int i);


42  public SimplifyAction Simplify;


43 


44  public bool IsLeaf => Arity == 0;


45 


46  public int CompareTo(HashNode<T> other) {


47  var res = HashValue.CompareTo(other.HashValue);


48  return res == 0 ? CalculatedHashValue.CompareTo(other.CalculatedHashValue) : res;


49  }


50 


51  public override string ToString() {


52  return $"{Data} {Arity} {Size} {CalculatedHashValue} {Enabled}";


53  }


54 


55  public bool Equals(HashNode<T> other) {


56  return CalculatedHashValue.Equals(other.CalculatedHashValue);


57  }


58 


59  public override bool Equals(object obj) {


60  var other = obj as HashNode<T>;


61  if (other != null)


62  return Equals(other);


63  return base.Equals(obj);


64  }


65 


66  public override int GetHashCode() {


67  return (int)CalculatedHashValue;


68  }


69 


70  public static bool operator ==(HashNode<T> a, HashNode<T> b) {


71  return a.Equals(b);


72  }


73 


74  public static bool operator !=(HashNode<T> a, HashNode<T> b) {


75  return !a.Equals(b);


76  }


77  }


78 


79  public static ulong ComputeHash<T>(this HashNode<T>[] nodes, int i, Func<byte[], ulong> hashFunction) where T : class {


80  var node = nodes[i];


81  const int size = sizeof(ulong);


82  var hashes = new ulong[node.Arity + 1];


83  var bytes = new byte[(node.Arity + 1) * size];


84 


85  for (int j = i  1, k = 0; k < node.Arity; ++k, j = 1 + nodes[j].Size) {


86  hashes[k] = nodes[j].CalculatedHashValue;


87  }


88  hashes[node.Arity] = node.HashValue;


89  Buffer.BlockCopy(hashes, 0, bytes, 0, bytes.Length);


90  return hashFunction(bytes);


91  }


92 


93  // set the enabled state for the whole subtree rooted at this node


94  public static void SetEnabled<T>(this HashNode<T>[] nodes, int i, bool enabled) where T : class {


95  nodes[i].Enabled = enabled;


96  for (int j = i  nodes[i].Size; j < i; ++j)


97  nodes[j].Enabled = enabled;


98  }


99 


100  public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {


101  bool simplified = false;


102  nodes = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);


103  do {


104  if (simplified) {


105  simplified = false;


106  nodes = nodes.Where(x => x.Enabled).ToArray().UpdateNodeSizes().Reduce().Sort(hashFunction);


107  }


108 


109  for (int i = 0; i < nodes.Length; ++i) {


110  var node = nodes[i];


111  if (node.IsLeaf) {


112  continue;


113  }


114  node.Simplify?.Invoke(ref nodes, i);


115  for (int j = i  node.Size; j <= i; ++j) {


116  // detect if anything was simplified


117  if (!nodes[j].Enabled) {


118  simplified = true;


119  break;


120  }


121  }


122  }


123  } while (simplified);


124  return nodes.UpdateNodeSizes().Sort(hashFunction);


125  }


126 


127  public static HashNode<T>[] Sort<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {


128  int sort(int a, int b) => nodes[a].CompareTo(nodes[b]);


129 


130  for (int i = 0; i < nodes.Length; ++i) {


131  var node = nodes[i];


132 


133  if (node.IsLeaf) {


134  continue;


135  }


136 


137  if (node.IsCommutative) { // only sort when the argument order does not matter


138  var arity = node.Arity;


139  var size = node.Size;


140 


141  if (arity == size) { // all child nodes are terminals


142  Array.Sort(nodes, i  size, size);


143  } else { // i have some nonterminal children


144  var sorted = new HashNode<T>[size];


145  var indices = new int[node.Arity];


146  for (int j = i  1, k = 0; k < node.Arity; j = 1 + nodes[j].Size, ++k) {


147  indices[k] = j;


148  }


149  Array.Sort(indices, sort);


150 


151  int idx = 0;


152  foreach (var j in indices) {


153  var child = nodes[j];


154  if (!child.IsLeaf) { // must copy complete subtree


155  Array.Copy(nodes, j  child.Size, sorted, idx, child.Size);


156  idx += child.Size;


157  }


158  sorted[idx++] = nodes[j];


159  }


160  Array.Copy(sorted, 0, nodes, i  size, size);


161  }


162  }


163  node.CalculatedHashValue = nodes.ComputeHash(i, hashFunction);


164  }


165  return nodes;


166  }


167 


168  /// <summary>


169  /// Get a function node's child indices


170  /// </summary>


171  /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>


172  /// <param name="nodes">An array of hash nodes with uptodate node sizes (see UpdateNodeSizes)</param>


173  /// <param name="i">The index in the array of hash nodes of the node whose children we want to iterate</param>


174  /// <returns>An array containing child indices</returns>


175  public static int[] IterateChildren<T>(this HashNode<T>[] nodes, int i) where T : class {


176  var node = nodes[i];


177  var arity = node.Arity;


178  var children = new int[arity];


179  var idx = i  1;


180  for (int j = 0; j < arity; ++j) {


181  children[j] = idx;


182  idx = 1 + nodes[idx].Size;


183  }


184  return children;


185  }


186 


187  /// <summary>


188  /// Determines size of each branch and sets the results for each node.


189  /// </summary>


190  /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>


191  /// <param name="nodes">An array of hash nodes in postfix order.</param>


192  /// <returns>The array with updated node sizes. The array is not copied.</returns>


193  public static HashNode<T>[] UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {


194  for (int i = 0; i < nodes.Length; ++i) {


195  var node = nodes[i];


196  if (node.IsLeaf) {


197  node.Size = 0;


198  continue;


199  }


200  node.Size = node.Arity;


201  // visit all children and sum up their size (assumes postfix order).


202  for (int j = i  1, k = 0; k < node.Arity; j = 1 + nodes[j].Size, ++k) {


203  node.Size += nodes[j].Size;


204  }


205  }


206  return nodes;


207  }


208 


209  // disables duplicate branches and removes the disabled nodes


210  public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {


211  int count = 0;


212  for (int i = 0; i < nodes.Length; ++i) {


213  var node = nodes[i];


214  if (node.IsLeaf  !node.IsCommutative) {


215  continue;


216  }


217 


218  var arity = node.Arity;


219  for (int j = i  1, k = 0; k < arity; j = 1 + nodes[j].Size, ++k) {


220  if (node.HashValue == nodes[j].HashValue) {


221  nodes[j].Enabled = false;


222  node.Arity += nodes[j].Arity  1;


223  ++count;


224  }


225  }


226  }


227  if (count == 0)


228  return nodes;


229 


230  var reduced = new HashNode<T>[nodes.Length  count];


231  var idx = 0;


232  foreach (var node in nodes) {


233  if (node.Enabled) { reduced[idx++] = node; }


234  }


235  return reduced.UpdateNodeSizes();


236  }


237  }


238  }

