source: branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs @ 16304

Last change on this file since 16304 was 16304, checked in by lkammere, 2 years ago

#2915: Merge changes in the trunk to current HEAD into the branch.

File size: 7.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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;
24
25namespace 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 non-terminal 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 up-to-date 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}
Note: See TracBrowser for help on using the repository browser.