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  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 delegate void SimplifyAction(ref HashNode<T>[] nodes, int i);


38  public SimplifyAction Simplify;


39 


40  //public IComparer<T> Comparer;


41 


42  public bool IsLeaf => Arity == 0;


43 


44  //public HashNode(IComparer<T> comparer) {


45  // Comparer = comparer;


46  //}


47 


48  //public HashNode() { }


49 


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


51  return CalculatedHashValue.CompareTo(other.CalculatedHashValue);


52  }


53 


54  public override string ToString() {


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


56  }


57 


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


59  return CalculatedHashValue.Equals(other.CalculatedHashValue);


60  }


61 


62  public override bool Equals(object obj) {


63  var other = obj as HashNode<T>;


64  if (other != null)


65  return Equals(other);


66  return base.Equals(obj);


67  }


68 


69  public override int GetHashCode() {


70  return (int)CalculatedHashValue;


71  }


72 


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


74  return a.Equals(b);


75  }


76 


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


78  return !a.Equals(b);


79  }


80  }


81 


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


83  var node = nodes[i];


84  const int size = sizeof(ulong);


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


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


87 


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


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


90  }


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


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


93  return hashFunction(bytes);


94  }


95 


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


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


98  nodes[i].Enabled = enabled;


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


100  nodes[j].Enabled = enabled;


101  }


102 


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


104  bool simplified = false;


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


106  do {


107  if (simplified) {


108  simplified = false;


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


110  }


111 


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


113  var node = nodes[i];


114  if (node.IsLeaf) {


115  continue;


116  }


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


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


119  // detect if anything was simplified


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


121  simplified = true;


122  break;


123  }


124  }


125  }


126  } while (simplified);


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


128  }


129 


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


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


132 


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


134  var node = nodes[i];


135 


136  if (node.IsLeaf) {


137  continue;


138  }


139 


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


141  var arity = node.Arity;


142  var size = node.Size;


143 


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


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


146  } else { // i have some nonterminal children


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


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


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


150  indices[k] = j;


151  }


152  Array.Sort(indices, sort);


153 


154  int idx = 0;


155  foreach (var j in indices) {


156  var child = nodes[j];


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


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


159  idx += child.Size;


160  }


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


162  }


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


164  }


165  }


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


167  }


168  return nodes;


169  }


170 


171  /// <summary>


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


173  /// </summary>


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


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


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


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


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


179  var node = nodes[i];


180  var arity = node.Arity;


181  var children = new int[arity];


182  var idx = i  1;


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


184  children[j] = idx;


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


186  }


187  return children;


188  }


189 


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


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


192  var node = nodes[i];


193  if (node.IsLeaf) {


194  node.Size = 0;


195  continue;


196  }


197  node.Size = node.Arity;


198 


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


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


201  }


202  }


203  return nodes;


204  }


205 


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


207  int count = 0;


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


209  var node = nodes[i];


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


211  continue;


212  }


213 


214  var arity = node.Arity;


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


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


217  nodes[j].Enabled = false;


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


219  ++count;


220  }


221  }


222  }


223  if (count == 0)


224  return nodes;


225 


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


227  var idx = 0;


228  foreach (var node in nodes) {


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


230  }


231  return reduced.UpdateNodeSizes();


232  }


233  }


234  }

