diff options
Diffstat (limited to 'store/src/main/java/tools/refinery/data/map/ContinousHashProvider.java')
-rw-r--r-- | store/src/main/java/tools/refinery/data/map/ContinousHashProvider.java | 69 |
1 files changed, 69 insertions, 0 deletions
diff --git a/store/src/main/java/tools/refinery/data/map/ContinousHashProvider.java b/store/src/main/java/tools/refinery/data/map/ContinousHashProvider.java new file mode 100644 index 00000000..6a54a3ff --- /dev/null +++ b/store/src/main/java/tools/refinery/data/map/ContinousHashProvider.java | |||
@@ -0,0 +1,69 @@ | |||
1 | package tools.refinery.data.map; | ||
2 | |||
3 | import tools.refinery.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 | */ | ||
13 | public 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 | } | ||