Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 17090 was 17090, checked in by abeham, 5 years ago

#2950: merged revisions 16218, 16252, 16255, 16258, 16259, 16260, 16261, 16263, 16267, 16270, 16271, 16272, 16273, 16284, 16290, 16291, 16302, 16305, 16382, 16478 to stable

File size: 8.0 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 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      private HashNode() { }
49
50      public int CompareTo(HashNode<T> other) {
51        var res = Comparer.Compare(Data, other.Data);
52        return res == 0 ? CalculatedHashValue.CompareTo(other.CalculatedHashValue) : res;
53      }
54
55      public override string ToString() {
56        return $"{Data} {Arity} {Size} {CalculatedHashValue} {Enabled}";
57      }
58
59      public bool Equals(HashNode<T> other) {
60        return CalculatedHashValue.Equals(other.CalculatedHashValue);
61      }
62
63      public override bool Equals(object obj) {
64        var other = obj as HashNode<T>;
65        if (other != null)
66          return Equals(other);
67        return base.Equals(obj);
68      }
69
70      public override int GetHashCode() {
71        return (int)CalculatedHashValue;
72      }
73
74      public static bool operator ==(HashNode<T> a, HashNode<T> b) {
75        return a.Equals(b);
76      }
77
78      public static bool operator !=(HashNode<T> a, HashNode<T> b) {
79        return !a.Equals(b);
80      }
81    }
82
83    public static ulong ComputeHash<T>(this HashNode<T>[] nodes, int i, Func<byte[], ulong> hashFunction) where T : class {
84      var node = nodes[i];
85      const int size = sizeof(ulong);
86      var hashes = new ulong[node.Arity + 1];
87      var bytes = new byte[(node.Arity + 1) * size];
88
89      for (int j = i - 1, k = 0; k < node.Arity; ++k, j -= 1 + nodes[j].Size) {
90        hashes[k] = nodes[j].CalculatedHashValue;
91      }
92      hashes[node.Arity] = node.HashValue;
93      Buffer.BlockCopy(hashes, 0, bytes, 0, bytes.Length);
94      return hashFunction(bytes);
95    }
96
97    // set the enabled state for the whole subtree rooted at this node
98    public static void SetEnabled<T>(this HashNode<T>[] nodes, int i, bool enabled) where T : class {
99      nodes[i].Enabled = enabled;
100      for (int j = i - nodes[i].Size; j < i; ++j)
101        nodes[j].Enabled = enabled;
102    }
103
104    public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
105      var reduced = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
106
107      for (int i = 0; i < reduced.Length; ++i) {
108        var node = reduced[i];
109        if (node.IsLeaf) {
110          continue;
111        }
112        node.Simplify?.Invoke(ref reduced, i);
113      }
114      // detect if anything was simplified
115      var count = 0;
116      foreach (var node in reduced) {
117        if (!node.Enabled) { ++count; }
118      }
119      if (count == 0) {
120        return reduced;
121      }
122
123      var simplified = new HashNode<T>[reduced.Length - count];
124      int j = 0;
125      foreach (var node in reduced) {
126        if (node.Enabled) {
127          simplified[j++] = node;
128        }
129      }
130      return simplified.UpdateNodeSizes().Reduce().Sort(hashFunction);
131    }
132
133    public static HashNode<T>[] Sort<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
134      int sort(int a, int b) => nodes[a].CompareTo(nodes[b]);
135
136      for (int i = 0; i < nodes.Length; ++i) {
137        var node = nodes[i];
138
139        if (node.IsLeaf) {
140          continue;
141        }
142
143        if (node.IsCommutative) { // only sort when the argument order does not matter
144          var arity = node.Arity;
145          var size = node.Size;
146
147          if (arity == size) { // all child nodes are terminals
148            Array.Sort(nodes, i - size, size);
149          } else { // i have some non-terminal children
150            var sorted = new HashNode<T>[size];
151            var indices = new int[node.Arity];
152            for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
153              indices[k] = j;
154            }
155            Array.Sort(indices, sort);
156
157            int idx = 0;
158            foreach (var j in indices) {
159              var child = nodes[j];
160              if (!child.IsLeaf) { // must copy complete subtree
161                Array.Copy(nodes, j - child.Size, sorted, idx, child.Size);
162                idx += child.Size;
163              }
164              sorted[idx++] = nodes[j];
165            }
166            Array.Copy(sorted, 0, nodes, i - size, size);
167          }
168        }
169        node.CalculatedHashValue = nodes.ComputeHash(i, hashFunction);
170      }
171      return nodes;
172    }
173
174    /// <summary>
175    /// Get a function node's child indicest
176    /// </summary>
177    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
178    /// <param name="nodes">An array of hash nodes with up-to-date node sizes</param>
179    /// <param name="i">The index in the array of hash nodes of the node whose children we want to iterate</param>
180    /// <returns>An array containing child indices</returns>
181    public static int[] IterateChildren<T>(this HashNode<T>[] nodes, int i) where T : class {
182      var node = nodes[i];
183      var arity = node.Arity;
184      var children = new int[arity];
185      var idx = i - 1;
186      for (int j = 0; j < arity; ++j) {
187        children[j] = idx;
188        idx -= 1 + nodes[idx].Size;
189      }
190      return children;
191    }
192
193    public static HashNode<T>[] UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
194      for (int i = 0; i < nodes.Length; ++i) {
195        var node = nodes[i];
196        if (node.IsLeaf) {
197          node.Size = 0;
198          continue;
199        }
200        node.Size = node.Arity;
201
202        for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
203          node.Size += nodes[j].Size;
204        }
205      }
206      return nodes;
207    }
208
209    private static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
210      int count = 0;
211      for (int i = 0; i < nodes.Length; ++i) {
212        var node = nodes[i];
213        if (node.IsLeaf || !node.IsCommutative) {
214          continue;
215        }
216
217        var arity = node.Arity;
218        for (int j = i - 1, k = 0; k < arity; j -= 1 + nodes[j].Size, ++k) {
219          if (node.HashValue == nodes[j].HashValue) {
220            nodes[j].Enabled = false;
221            node.Arity += nodes[j].Arity - 1;
222            ++count;
223          }
224        }
225      }
226      if (count == 0)
227        return nodes;
228
229      var reduced = new HashNode<T>[nodes.Length - count];
230      var idx = 0;
231      foreach (var node in nodes) {
232        if (node.Enabled) { reduced[idx++] = node; }
233      }
234      return reduced.UpdateNodeSizes();
235    }
236  }
237}
Note: See TracBrowser for help on using the repository browser.