1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 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.Collections.Generic;


24 


25  namespace HeuristicLab.Problems.DataAnalysis.Symbolic {


26  public static class SymbolicExpressionHashExtensions {


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


28  public T Data;


29  public int Arity;


30  public int Size;


31  public bool IsCommutative;


32 


33  public bool Enabled;


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 Action<HashNode<T>[], int> Simplify;


38  public IComparer<T> Comparer;


39 


40  public bool IsLeaf => Arity == 0;


41 


42  public HashNode(IComparer<T> comparer) {


43  Comparer = comparer;


44  }


45 


46  private HashNode() { }


47 


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


49  var res = Comparer.Compare(Data, other.Data);


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


51  }


52 


53  public override string ToString() {


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


55  }


56 


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


58  return CalculatedHashValue.Equals(other.CalculatedHashValue);


59  }


60 


61  public override bool Equals(object obj) {


62  var other = obj as HashNode<T>;


63  if (other != null)


64  return Equals(other);


65  return base.Equals(obj);


66  }


67 


68  public override int GetHashCode() {


69  return (int)CalculatedHashValue;


70  }


71 


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


73  return a.Equals(b);


74  }


75 


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


77  return !a.Equals(b);


78  }


79  }


80 


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


82  var node = nodes[i];


83  const int size = sizeof(ulong);


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


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


86 


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


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


89  }


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


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


92  return hashFunction(bytes);


93  }


94 


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


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


97  nodes[i].Enabled = enabled;


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


99  nodes[j].Enabled = enabled;


100  }


101 


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


103  var reduced = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);


104 


105  for (int i = 0; i < reduced.Length; ++i) {


106  var node = reduced[i];


107  if (node.IsLeaf) {


108  continue;


109  }


110  node.Simplify?.Invoke(reduced, i);


111  }


112  // detect if anything was simplified


113  var count = 0;


114  foreach (var node in reduced) {


115  if (!node.Enabled) { ++count; }


116  }


117  if (count == 0) {


118  return reduced;


119  }


120 


121  var simplified = new HashNode<T>[reduced.Length  count];


122  int j = 0;


123  foreach (var node in reduced) {


124  if (node.Enabled) {


125  simplified[j++] = node;


126  }


127  }


128  return simplified.UpdateNodeSizes().Reduce().Sort(hashFunction);


129  }


130 


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


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


133 


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


135  var node = nodes[i];


136 


137  if (node.IsLeaf) {


138  continue;


139  }


140 


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


142  var arity = node.Arity;


143  var size = node.Size;


144 


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


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


147  } else { // i have some nonterminal children


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


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


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


151  indices[k] = j;


152  }


153  Array.Sort(indices, sort);


154 


155  int idx = 0;


156  foreach (var j in indices) {


157  var child = nodes[j];


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


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


160  idx += child.Size;


161  }


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


163  }


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


165  }


166  }


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


168  }


169  return nodes;


170  }


171 


172  /// <summary>


173  /// Get a function node's child indicest


174  /// </summary>


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


176  /// <param name="nodes">An array of hash nodes with uptodate node sizes</param>


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


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


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


180  var node = nodes[i];


181  var arity = node.Arity;


182  var children = new int[arity];


183  var idx = i  1;


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


185  children[j] = idx;


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


187  }


188  return children;


189  }


190 


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


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


193  var node = nodes[i];


194  if (node.IsLeaf) {


195  node.Size = 0;


196  continue;


197  }


198  node.Size = node.Arity;


199 


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


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


202  }


203  }


204  return nodes;


205  }


206 


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


208  int count = 0;


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


210  var node = nodes[i];


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


212  continue;


213  }


214 


215  var arity = node.Arity;


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


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


218  nodes[j].Enabled = false;


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


220  ++count;


221  }


222  }


223  }


224  if (count == 0)


225  return nodes;


226 


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


228  var idx = 0;


229  foreach (var node in nodes) {


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


231  }


232  return reduced.UpdateNodeSizes();


233  }


234  }


235  }

