aboutsummaryrefslogtreecommitdiffstats
path: root/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
diff options
context:
space:
mode:
Diffstat (limited to 'store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java')
-rw-r--r--store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java69
1 files changed, 0 insertions, 69 deletions
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
deleted file mode 100644
index dd64f901..00000000
--- a/store/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java
+++ /dev/null
@@ -1,69 +0,0 @@
1package org.eclipse.viatra.solver.data.map;
2
3import org.eclipse.viatra.solver.data.map.internal.Node;
4
5/**
6 * A class representing an equivalence relation for a type {@code K} with a
7 * continuous hash function.
8 *
9 * @author Oszkar Semerath
10 *
11 * @param <K> Target java type.
12 */
13public interface ContinousHashProvider<K> {
14 public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS;
15 public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1;
16
17 /**
18 * Maximal practical depth for differentiating keys. If two keys have the same
19 * hash code until that depth, the algorithm can stop.
20 */
21 public static final int MAX_PRACTICAL_DEPTH = 500;
22
23 /**
24 * Provides a hash code for a object {@code key} with a given {@code index}. It
25 * has the following contracts:
26 * <ul>
27 * <li>If {@link #equals}{@code (key1,key2)}, then
28 * {@code getHash(key1, index) == getHash(key2, index)} for all values of
29 * {@code index}.</li>
30 * <li>If {@code getHash(key1,index) == getHash(key2, index)} for all values of
31 * {@code index}, then {@link #equals}{@code (key1, key2)}</li>
32 * <li>In current implementation, we use only the least significant
33 * {@link #EFFECTIVE_BITS}
34 * </ul>
35 * Check {@link #equals} for further details.
36 *
37 * @param key The target data object.
38 * @param index The depth of the the hash code. Needs to be non-negative.
39 * @return A hash code.
40 */
41 public int getHash(K key, int index);
42
43 public default int getEffectiveHash(K key, int index) {
44 return getHash(key, index) & EFFECTIVE_BIT_MASK;
45 }
46
47 public default int compare(K key1, K key2) {
48 if (key1.equals(key2)) {
49 return 0;
50 } else {
51 for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) {
52 int hash1 = getEffectiveHash(key1, i);
53 int hash2 = getEffectiveHash(key2, i);
54 for(int j = 0; j<Integer.SIZE/Node.BRANCHING_FACTOR_BITS; j++) {
55 final int factorMask = (1<<Node.BRANCHING_FACTOR_BITS)-1;
56 int hashFragment1 = (hash1>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
57 int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
58 var result = Integer.compare(hashFragment1, hashFragment2);
59 if (result != 0) {
60 return result;
61 }
62 }
63 }
64 throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2
65 + ") have the same hashcode over the practical depth limitation ("
66 + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
67 }
68 }
69}