#region License Information /* HeuristicLab * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections.Generic; namespace HeuristicLab.Problems.DataAnalysis.Symbolic { public static class SymbolicExpressionHashExtensions { public sealed class HashNode : IComparable>, IEquatable> where T : class { public T Data; public int Arity; public int Size; public bool IsCommutative; public bool Enabled; public ulong HashValue; // the initial (fixed) hash value for this individual node/data public ulong CalculatedHashValue; // the calculated hash value (taking into account the children hash values) public Action[], int> Simplify; public IComparer Comparer; public bool IsLeaf => Arity == 0; public HashNode(IComparer comparer) { Comparer = comparer; } private HashNode() { } public int CompareTo(HashNode other) { var res = Comparer.Compare(Data, other.Data); return res == 0 ? CalculatedHashValue.CompareTo(other.CalculatedHashValue) : res; } public override string ToString() { return $"{Data} {Arity} {Size} {CalculatedHashValue} {Enabled}"; } public bool Equals(HashNode other) { return CalculatedHashValue.Equals(other.CalculatedHashValue); } public override bool Equals(object obj) { var other = obj as HashNode; if (other != null) return Equals(other); return base.Equals(obj); } public override int GetHashCode() { return (int)CalculatedHashValue; } public static bool operator ==(HashNode a, HashNode b) { return a.Equals(b); } public static bool operator !=(HashNode a, HashNode b) { return !a.Equals(b); } } public static ulong ComputeHash(this HashNode[] nodes, int i, Func hashFunction) where T : class { var node = nodes[i]; const int size = sizeof(ulong); var hashes = new ulong[node.Arity + 1]; var bytes = new byte[(node.Arity + 1) * size]; for (int j = i - 1, k = 0; k < node.Arity; ++k, j -= 1 + nodes[j].Size) { hashes[k] = nodes[j].CalculatedHashValue; } hashes[node.Arity] = node.HashValue; Buffer.BlockCopy(hashes, 0, bytes, 0, bytes.Length); return hashFunction(bytes); } // set the enabled state for the whole subtree rooted at this node public static void SetEnabled(this HashNode[] nodes, int i, bool enabled) where T : class { nodes[i].Enabled = enabled; for (int j = i - nodes[i].Size; j < i; ++j) nodes[j].Enabled = enabled; } public static HashNode[] Simplify(this HashNode[] nodes, Func hashFunction) where T : class { var reduced = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction); for (int i = 0; i < reduced.Length; ++i) { var node = reduced[i]; if (node.IsLeaf) { continue; } node.Simplify?.Invoke(reduced, i); } // detect if anything was simplified var count = 0; foreach (var node in reduced) { if (!node.Enabled) { ++count; } } if (count == 0) { return reduced; } var simplified = new HashNode[reduced.Length - count]; int j = 0; foreach (var node in reduced) { if (node.Enabled) { simplified[j++] = node; } } return simplified.UpdateNodeSizes().Reduce().Sort(hashFunction); } public static HashNode[] Sort(this HashNode[] nodes, Func hashFunction) where T : class { int sort(int a, int b) => nodes[a].CompareTo(nodes[b]); for (int i = 0; i < nodes.Length; ++i) { var node = nodes[i]; if (node.IsLeaf) { continue; } if (node.IsCommutative) { // only sort when the argument order does not matter var arity = node.Arity; var size = node.Size; if (arity == size) { // all child nodes are terminals Array.Sort(nodes, i - size, size); } else { // i have some non-terminal children var sorted = new HashNode[size]; var indices = new int[node.Arity]; for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) { indices[k] = j; } Array.Sort(indices, sort); int idx = 0; foreach (var j in indices) { var child = nodes[j]; if (!child.IsLeaf) { // must copy complete subtree Array.Copy(nodes, j - child.Size, sorted, idx, child.Size); idx += child.Size; } sorted[idx++] = nodes[j]; } Array.Copy(sorted, 0, nodes, i - size, size); } } node.CalculatedHashValue = nodes.ComputeHash(i, hashFunction); } return nodes; } /// /// Get a function node's child indicest /// /// The data type encapsulated by a hash node /// An array of hash nodes with up-to-date node sizes /// The index in the array of hash nodes of the node whose children we want to iterate /// An array containing child indices public static int[] IterateChildren(this HashNode[] nodes, int i) where T : class { var node = nodes[i]; var arity = node.Arity; var children = new int[arity]; var idx = i - 1; for (int j = 0; j < arity; ++j) { children[j] = idx; idx -= 1 + nodes[idx].Size; } return children; } public static HashNode[] UpdateNodeSizes(this HashNode[] nodes) where T : class { for (int i = 0; i < nodes.Length; ++i) { var node = nodes[i]; if (node.IsLeaf) { node.Size = 0; continue; } node.Size = node.Arity; for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) { node.Size += nodes[j].Size; } } return nodes; } private static HashNode[] Reduce(this HashNode[] nodes) where T : class { int count = 0; for (int i = 0; i < nodes.Length; ++i) { var node = nodes[i]; if (node.IsLeaf || !node.IsCommutative) { continue; } var arity = node.Arity; for (int j = i - 1, k = 0; k < arity; j -= 1 + nodes[j].Size, ++k) { if (node.HashValue == nodes[j].HashValue) { nodes[j].Enabled = false; node.Arity += nodes[j].Arity - 1; ++count; } } } if (count == 0) return nodes; var reduced = new HashNode[nodes.Length - count]; var idx = 0; foreach (var node in nodes) { if (node.Enabled) { reduced[idx++] = node; } } return reduced.UpdateNodeSizes(); } } }