source: stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs @ 17099

Last change on this file since 17099 was 17099, checked in by mkommend, 2 months ago

#2950: Merged 16979, 16980, 16983 into stable.

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