diff options
6 files changed, 159 insertions, 54 deletions
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java index 56c5fefd..a36e2bdb 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java | |||
@@ -1,5 +1,7 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | 1 | package org.eclipse.viatra.solver.data.map; |
2 | 2 | ||
3 | import org.eclipse.viatra.solver.data.map.internal.Node; | ||
4 | |||
3 | /** | 5 | /** |
4 | * A class representing an equivalence relation for a type {@code KEY} with a continuous hash function. | 6 | * A class representing an equivalence relation for a type {@code KEY} with a continuous hash function. |
5 | * @author Oszkar Semerath | 7 | * @author Oszkar Semerath |
@@ -7,11 +9,18 @@ package org.eclipse.viatra.solver.data.map; | |||
7 | * @param <KEY> Target java type. | 9 | * @param <KEY> Target java type. |
8 | */ | 10 | */ |
9 | public interface ContinousHashProvider<KEY> { | 11 | public interface ContinousHashProvider<KEY> { |
12 | public static final int effectiveBits = Node.effectiveBits; | ||
13 | public static final int effectiveBitMask = (1<<(effectiveBits))-1; | ||
14 | /** | ||
15 | * Maximal practical depth for differentiating keys. If two keys have the same hash code until that depth, the algorithm can stop. | ||
16 | */ | ||
17 | public static final int maxPracticalDepth = 500; | ||
10 | /** | 18 | /** |
11 | * Provides a hash code for a object {@code key} with a given {@code index}. It has the following contracts: | 19 | * Provides a hash code for a object {@code key} with a given {@code index}. It has the following contracts: |
12 | * <ul> | 20 | * <ul> |
13 | * <li>If {@link #equals}{@code (key1,key2)}, then {@code getHash(key1, index) == getHash(key2, index)} for all values of {@code index}.</li> | 21 | * <li>If {@link #equals}{@code (key1,key2)}, then {@code getHash(key1, index) == getHash(key2, index)} for all values of {@code index}.</li> |
14 | * <li>If {@code getHash(key1,index) == getHash(key2, index)} for all values of {@code index}, then {@link #equals}{@code (key1, key2)}</li> | 22 | * <li>If {@code getHash(key1,index) == getHash(key2, index)} for all values of {@code index}, then {@link #equals}{@code (key1, key2)}</li> |
23 | * <li>In current implementation, we use only the least significant {@link #effectiveBits} | ||
15 | * </ul> | 24 | * </ul> |
16 | * Check {@link #equals} for further details. | 25 | * Check {@link #equals} for further details. |
17 | * @param key The target data object. | 26 | * @param key The target data object. |
@@ -32,4 +41,24 @@ public interface ContinousHashProvider<KEY> { | |||
32 | // * @return whether {@code key1} and {@code key2} are equivalent with respect to an equivalence relation represented by the given . | 41 | // * @return whether {@code key1} and {@code key2} are equivalent with respect to an equivalence relation represented by the given . |
33 | // */ | 42 | // */ |
34 | // public boolean equals(KEY key1, KEY key2); | 43 | // public boolean equals(KEY key1, KEY key2); |
44 | |||
45 | public default int getEffectiveHash(KEY key, int index) { | ||
46 | return getHash(key, index) & effectiveBitMask; | ||
47 | } | ||
48 | public default int compare(KEY key1, KEY key2) { | ||
49 | if(key1.equals(key2)) { | ||
50 | return 0; | ||
51 | } else { | ||
52 | for(int i=0; i<ContinousHashProvider.maxPracticalDepth; i++) { | ||
53 | int hash1 = getEffectiveHash(key1, i); | ||
54 | int hash2 = getEffectiveHash(key2, i); | ||
55 | int result = Integer.compare(hash1, hash2); | ||
56 | if(result != 0) { | ||
57 | return result; | ||
58 | } | ||
59 | } | ||
60 | throw new IllegalArgumentException( | ||
61 | "Two different keys ("+key1+" and "+key2+") have the same hashcode over the practical depth limitation ("+ContinousHashProvider.maxPracticalDepth+")!"); | ||
62 | } | ||
63 | } | ||
35 | } | 64 | } |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java index d9adc117..09607d4a 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMapStoreImpl.java | |||
@@ -1,5 +1,7 @@ | |||
1 | package org.eclipse.viatra.solver.data.map; | 1 | package org.eclipse.viatra.solver.data.map; |
2 | 2 | ||
3 | import java.util.ArrayList; | ||
4 | import java.util.Collections; | ||
3 | import java.util.HashMap; | 5 | import java.util.HashMap; |
4 | import java.util.Map; | 6 | import java.util.Map; |
5 | import java.util.Set; | 7 | import java.util.Set; |
@@ -37,7 +39,7 @@ public class VersionedMapStoreImpl<KEY,VALUE> implements VersionedMapStore<KEY, | |||
37 | } | 39 | } |
38 | } | 40 | } |
39 | 41 | ||
40 | public VersionedMapStoreImpl(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue) { | 42 | public VersionedMapStoreImpl(ContinousHashProvider<KEY> hashProvider, VALUE defaultValue) { |
41 | this(hashProvider,defaultValue,new VersionedMapStoreConfiguration()); | 43 | this(hashProvider,defaultValue,new VersionedMapStoreConfiguration()); |
42 | } | 44 | } |
43 | 45 | ||
@@ -52,15 +54,18 @@ public class VersionedMapStoreImpl<KEY,VALUE> implements VersionedMapStore<KEY, | |||
52 | @Override | 54 | @Override |
53 | public VersionedMap<KEY,VALUE> createMap(long state) { | 55 | public VersionedMap<KEY,VALUE> createMap(long state) { |
54 | ImmutableNode<KEY, VALUE> data = revert(state); | 56 | ImmutableNode<KEY, VALUE> data = revert(state); |
55 | if(data != null) { | 57 | return new VersionedMapImpl<KEY,VALUE>(this,hashProvider,defaultValue,data); |
56 | return new VersionedMapImpl<KEY,VALUE>(this,hashProvider,defaultValue,data); | ||
57 | } else { | ||
58 | throw new IllegalArgumentException("Store does not contain state " + state + "!"); | ||
59 | } | ||
60 | } | 58 | } |
61 | 59 | ||
62 | synchronized public ImmutableNode<KEY,VALUE> revert(long state) { | 60 | synchronized public ImmutableNode<KEY,VALUE> revert(long state) { |
63 | return states.get(state); | 61 | if(states.containsKey(state)) { |
62 | return states.get(state); | ||
63 | } else { | ||
64 | ArrayList<Long> existingKeys = new ArrayList<Long>(states.keySet()); | ||
65 | Collections.sort(existingKeys); | ||
66 | throw new IllegalArgumentException( | ||
67 | "Store does not contain state "+state+"! Avaliable states: "+existingKeys.toArray().toString()); | ||
68 | } | ||
64 | } | 69 | } |
65 | synchronized public long commit(Node<KEY,VALUE> data, VersionedMapImpl<KEY, VALUE> mapToUpdateRoot) { | 70 | synchronized public long commit(Node<KEY,VALUE> data, VersionedMapImpl<KEY, VALUE> mapToUpdateRoot) { |
66 | ImmutableNode<KEY,VALUE> immutable; | 71 | ImmutableNode<KEY,VALUE> immutable; |
@@ -100,6 +105,6 @@ public class VersionedMapStoreImpl<KEY,VALUE> implements VersionedMapStore<KEY, | |||
100 | VersionedMap<KEY, VALUE> map2 = createMap(toState); | 105 | VersionedMap<KEY, VALUE> map2 = createMap(toState); |
101 | Cursor<KEY, VALUE> cursor1 = map1.getCursor(); | 106 | Cursor<KEY, VALUE> cursor1 = map1.getCursor(); |
102 | Cursor<KEY, VALUE> cursor2 = map2.getCursor(); | 107 | Cursor<KEY, VALUE> cursor2 = map2.getCursor(); |
103 | return new MapDiffCursor<KEY, VALUE>(this.defaultValue,cursor1,cursor2); | 108 | return new MapDiffCursor<KEY, VALUE>(this.hashProvider,this.defaultValue,cursor1,cursor2); |
104 | } | 109 | } |
105 | } | 110 | } |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java index 5b9d5c7d..6c177611 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java | |||
@@ -30,11 +30,12 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> { | |||
30 | // Initializing tree stack | 30 | // Initializing tree stack |
31 | super(); | 31 | super(); |
32 | this.nodeStack = new ArrayDeque<>(); | 32 | this.nodeStack = new ArrayDeque<>(); |
33 | this.nodeIndexStack = new ArrayDeque<>(); | ||
33 | if(root != null) { | 34 | if(root != null) { |
34 | this.nodeStack.add(root); | 35 | this.nodeStack.add(root); |
36 | this.nodeIndexStack.push(IndexStart); | ||
35 | } | 37 | } |
36 | this.nodeIndexStack = new ArrayDeque<>(); | 38 | |
37 | this.nodeIndexStack.push(IndexStart); | ||
38 | this.dataIndex = IndexStart; | 39 | this.dataIndex = IndexStart; |
39 | 40 | ||
40 | // Initializing cache | 41 | // Initializing cache |
@@ -63,7 +64,11 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> { | |||
63 | throw new ConcurrentModificationException(); | 64 | throw new ConcurrentModificationException(); |
64 | } | 65 | } |
65 | if(!isTerminated()) { | 66 | if(!isTerminated()) { |
66 | return this.nodeStack.peek().moveToNext(this); | 67 | boolean result = this.nodeStack.peek().moveToNext(this); |
68 | if(this.nodeIndexStack.size() != this.nodeStack.size()) { | ||
69 | throw new IllegalArgumentException("Node stack is corrupted by illegal moves!"); | ||
70 | } | ||
71 | return result; | ||
67 | } | 72 | } |
68 | return false; | 73 | return false; |
69 | } | 74 | } |
@@ -85,7 +90,11 @@ public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> { | |||
85 | public static <KEY,VALUE> boolean sameSubnode(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) { | 90 | public static <KEY,VALUE> boolean sameSubnode(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) { |
86 | Node<KEY, VALUE> nodeOfCursor1 = cursor1.nodeStack.peek(); | 91 | Node<KEY, VALUE> nodeOfCursor1 = cursor1.nodeStack.peek(); |
87 | Node<KEY, VALUE> nodeOfCursor2 = cursor2.nodeStack.peek(); | 92 | Node<KEY, VALUE> nodeOfCursor2 = cursor2.nodeStack.peek(); |
88 | return nodeOfCursor1.equals(nodeOfCursor2); | 93 | if(nodeOfCursor1 != null && nodeOfCursor2 != null) { |
94 | return nodeOfCursor1.equals(nodeOfCursor2); | ||
95 | } else { | ||
96 | return false; | ||
97 | } | ||
89 | } | 98 | } |
90 | 99 | ||
91 | /** | 100 | /** |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java index 5c911bb4..8d7cda14 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java | |||
@@ -4,6 +4,7 @@ import java.util.List; | |||
4 | import java.util.stream.Collectors; | 4 | import java.util.stream.Collectors; |
5 | import java.util.stream.Stream; | 5 | import java.util.stream.Stream; |
6 | 6 | ||
7 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | ||
7 | import org.eclipse.viatra.solver.data.map.Cursor; | 8 | import org.eclipse.viatra.solver.data.map.Cursor; |
8 | import org.eclipse.viatra.solver.data.map.DiffCursor; | 9 | import org.eclipse.viatra.solver.data.map.DiffCursor; |
9 | import org.eclipse.viatra.solver.data.map.VersionedMap; | 10 | import org.eclipse.viatra.solver.data.map.VersionedMap; |
@@ -17,43 +18,52 @@ public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE>, Cursor< | |||
17 | /** | 18 | /** |
18 | * Default value representing missing elements. | 19 | * Default value representing missing elements. |
19 | */ | 20 | */ |
20 | VALUE defaultValue; | 21 | private VALUE defaultValue; |
21 | MapCursor<KEY,VALUE> cursor1; | 22 | private MapCursor<KEY,VALUE> cursor1; |
22 | MapCursor<KEY,VALUE> cursor2; | 23 | private MapCursor<KEY,VALUE> cursor2; |
24 | private ContinousHashProvider<? super KEY> hashProvider; | ||
23 | 25 | ||
24 | // Values | 26 | // Values |
25 | KEY key; | 27 | private KEY key; |
26 | VALUE value1; | 28 | private VALUE fromValue; |
27 | VALUE value2; | 29 | private VALUE toValue; |
28 | 30 | ||
29 | // State | 31 | // State |
30 | /** | 32 | /** |
31 | * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position. | 33 | * Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position. |
32 | */ | 34 | */ |
33 | int cursorRelation; | 35 | private int cursorRelation; |
36 | /** | ||
37 | * Denotes a state when two cursors are in the same position, but they contain different keys. | ||
38 | * Possible values: | ||
39 | * <ul> | ||
40 | * <li>0: not stuck</li> | ||
41 | * <li>1: hashClash, next it should return the key of cursor 1.</li> | ||
42 | * <li>2: hashClash, next it should return the key of cursor 2.</li> | ||
43 | * </ul> | ||
44 | */ | ||
45 | private int hashClash=0; | ||
34 | 46 | ||
35 | public MapDiffCursor(VALUE defaultValue, Cursor<KEY, VALUE> cursor1, Cursor<KEY, VALUE> cursor2) { | 47 | public MapDiffCursor(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, Cursor<KEY, VALUE> cursor1, Cursor<KEY, VALUE> cursor2) { |
36 | super(); | 48 | super(); |
49 | this.hashProvider = hashProvider; | ||
37 | this.defaultValue = defaultValue; | 50 | this.defaultValue = defaultValue; |
38 | this.cursor1 = (MapCursor<KEY, VALUE>) cursor1; | 51 | this.cursor1 = (MapCursor<KEY, VALUE>) cursor1; |
39 | this.cursor2 = (MapCursor<KEY, VALUE>) cursor2; | 52 | this.cursor2 = (MapCursor<KEY, VALUE>) cursor2; |
40 | |||
41 | this.updateState(); | ||
42 | this.moveToConsistentState(); | ||
43 | } | 53 | } |
44 | 54 | ||
45 | public KEY getKey() { | 55 | public KEY getKey() { |
46 | return key; | 56 | return key; |
47 | } | 57 | } |
48 | public VALUE getValue1() { | 58 | public VALUE getFromValue() { |
49 | return value1; | 59 | return fromValue; |
50 | } | 60 | } |
51 | public VALUE getValue2() { | 61 | public VALUE getToValue() { |
52 | return value2; | 62 | return toValue; |
53 | } | 63 | } |
54 | @Override | 64 | @Override |
55 | public VALUE getValue() { | 65 | public VALUE getValue() { |
56 | return this.value2; | 66 | return getToValue(); |
57 | } | 67 | } |
58 | public boolean isTerminated() { | 68 | public boolean isTerminated() { |
59 | return cursor1.isTerminated() && cursor2.isTerminated(); | 69 | return cursor1.isTerminated() && cursor2.isTerminated(); |
@@ -71,33 +81,72 @@ public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE>, Cursor< | |||
71 | } | 81 | } |
72 | 82 | ||
73 | protected void updateState() { | 83 | protected void updateState() { |
74 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); | 84 | if(!isTerminated()) { |
75 | if(cursorRelation > 0 || cursor2.isTerminated()) { | 85 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); |
76 | this.key = cursor1.getKey(); | 86 | if(cursorRelation > 0 || cursor2.isTerminated()) { |
77 | this.value1 = cursor1.getValue(); | 87 | this.key = cursor1.getKey(); |
78 | this.value2 = defaultValue; | 88 | this.fromValue = cursor1.getValue(); |
79 | } else if(cursorRelation < 0|| cursor1.isTerminated()){ | 89 | this.toValue = defaultValue; |
80 | this.key = cursor2.getKey(); | 90 | } else if(cursorRelation < 0 || cursor1.isTerminated()){ |
81 | this.value1 = defaultValue; | 91 | this.key = cursor2.getKey(); |
82 | this.value2 = cursor1.getValue(); | 92 | this.fromValue = defaultValue; |
83 | } else { | 93 | this.toValue = cursor1.getValue(); |
84 | // cursor1 = cursor2 | 94 | } else { |
85 | if(!cursor1.getKey().equals(cursor2.getKey())) { | 95 | // cursor1 = cursor2 |
86 | throw new IllegalStateException( | 96 | if(cursor1.getKey().equals(cursor2.getKey())) { |
87 | "Cursor comarison tells that they are in the same state, but keys are different. " + cursor1.getKey() + " - " + cursor2.getKey()); | 97 | this.key = cursor1.getKey(); |
98 | this.fromValue = cursor1.getValue(); | ||
99 | this.toValue = defaultValue; | ||
100 | } else { | ||
101 | resolveHashClash1(); | ||
102 | } | ||
88 | } | 103 | } |
89 | this.key = cursor1.getKey(); | ||
90 | this.value1 = cursor1.getValue(); | ||
91 | this.value2 = defaultValue; | ||
92 | } | 104 | } |
93 | } | 105 | } |
106 | protected void resolveHashClash1() { | ||
107 | int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); | ||
108 | if(compareResult<0) { | ||
109 | this.hashClash = 2; | ||
110 | this.cursorRelation = 0; | ||
111 | this.key = cursor1.key; | ||
112 | this.fromValue = cursor1.value; | ||
113 | this.toValue = defaultValue; | ||
114 | } else if(compareResult>0) { | ||
115 | this.hashClash = 1; | ||
116 | this.cursorRelation = 0; | ||
117 | this.key = cursor2.key; | ||
118 | this.fromValue = defaultValue; | ||
119 | this.toValue = cursor2.value; | ||
120 | } else { | ||
121 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | ||
122 | } | ||
123 | } | ||
124 | protected boolean isInHashClash() { | ||
125 | return this.hashClash != 0; | ||
126 | } | ||
127 | protected void resolveHashClash2() { | ||
128 | if(hashClash == 1) { | ||
129 | this.hashClash = 0; | ||
130 | this.cursorRelation = 0; | ||
131 | this.key = cursor1.key; | ||
132 | this.fromValue = cursor1.value; | ||
133 | this.toValue = defaultValue; | ||
134 | } else if(hashClash == 2) { | ||
135 | this.hashClash = 0; | ||
136 | this.cursorRelation = 0; | ||
137 | this.key = cursor2.key; | ||
138 | this.fromValue = defaultValue; | ||
139 | this.toValue = cursor2.value; | ||
140 | } else throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | ||
141 | } | ||
142 | |||
94 | 143 | ||
95 | protected boolean differentValues() { | 144 | protected boolean sameValues() { |
96 | return this.value1 != this.value2; | 145 | return this.fromValue == this.toValue; |
97 | } | 146 | } |
98 | protected boolean moveOne() { | 147 | protected boolean moveOne() { |
99 | if(isTerminated()) { | 148 | if(isTerminated()) { |
100 | throw new IllegalStateException("DiffCursor tries to move when terminated!"); | 149 | return false; |
101 | } | 150 | } |
102 | if(this.cursorRelation > 0 || cursor2.isTerminated()) { | 151 | if(this.cursorRelation > 0 || cursor2.isTerminated()) { |
103 | return cursor1.move(); | 152 | return cursor1.move(); |
@@ -129,10 +178,11 @@ public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE>, Cursor< | |||
129 | lastResult = skipNode(); | 178 | lastResult = skipNode(); |
130 | changed = true; | 179 | changed = true; |
131 | } | 180 | } |
132 | if(differentValues()) { | 181 | if(sameValues()) { |
133 | lastResult = moveOne(); | 182 | lastResult = moveOne(); |
134 | changed = true; | 183 | changed = true; |
135 | } | 184 | } |
185 | updateState(); | ||
136 | } while(changed && !isTerminated()); | 186 | } while(changed && !isTerminated()); |
137 | return lastResult; | 187 | return lastResult; |
138 | } else { | 188 | } else { |
@@ -142,11 +192,17 @@ public class MapDiffCursor<KEY,VALUE> implements DiffCursor<KEY, VALUE>, Cursor< | |||
142 | 192 | ||
143 | public boolean move() { | 193 | public boolean move() { |
144 | if(!isTerminated()) { | 194 | if(!isTerminated()) { |
145 | if(moveOne()) { | 195 | if(isInHashClash()) { |
146 | return moveToConsistentState(); | 196 | this.resolveHashClash2(); |
197 | return true; | ||
147 | } else { | 198 | } else { |
148 | return false; | 199 | if(moveOne()) { |
200 | return moveToConsistentState(); | ||
201 | } else { | ||
202 | return false; | ||
203 | } | ||
149 | } | 204 | } |
205 | |||
150 | } else return false; | 206 | } else return false; |
151 | } | 207 | } |
152 | } | 208 | } |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java index c3a50201..1d659779 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java | |||
@@ -9,6 +9,7 @@ public abstract class Node<KEY,VALUE>{ | |||
9 | protected static final int factor = 1<<branchingFactorBit; | 9 | protected static final int factor = 1<<branchingFactorBit; |
10 | protected static final int numberOfFactors = Integer.SIZE / branchingFactorBit; | 10 | protected static final int numberOfFactors = Integer.SIZE / branchingFactorBit; |
11 | protected static final int factorMask = factor-1; | 11 | protected static final int factorMask = factor-1; |
12 | public static final int effectiveBits = branchingFactorBit * numberOfFactors; | ||
12 | 13 | ||
13 | /** | 14 | /** |
14 | * Calculates the index for the continuous hash. | 15 | * Calculates the index for the continuous hash. |
@@ -37,6 +38,7 @@ public abstract class Node<KEY,VALUE>{ | |||
37 | if(shiftDepth<0 && 5<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth); | 38 | if(shiftDepth<0 && 5<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth); |
38 | return (hash >>> shiftDepth*branchingFactorBit) & factorMask; | 39 | return (hash >>> shiftDepth*branchingFactorBit) & factorMask; |
39 | } | 40 | } |
41 | |||
40 | /** | 42 | /** |
41 | * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1. | 43 | * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1. |
42 | * @param key The key. | 44 | * @param key The key. |
@@ -45,8 +47,12 @@ public abstract class Node<KEY,VALUE>{ | |||
45 | * @return The new hash code. | 47 | * @return The new hash code. |
46 | */ | 48 | */ |
47 | protected int newHash(final ContinousHashProvider<? super KEY> hashProvider, KEY key, int hash, int depth) { | 49 | protected int newHash(final ContinousHashProvider<? super KEY> hashProvider, KEY key, int hash, int depth) { |
50 | final int hashDepth = hashDepth(depth); | ||
51 | if(hashDepth>=ContinousHashProvider.maxPracticalDepth) { | ||
52 | throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.maxPracticalDepth+")!"); | ||
53 | } | ||
48 | return depth%numberOfFactors == 0? | 54 | return depth%numberOfFactors == 0? |
49 | hashProvider.getHash(key, hashDepth(depth)) : | 55 | hashProvider.getHash(key, hashDepth) : |
50 | hash; | 56 | hash; |
51 | } | 57 | } |
52 | 58 | ||
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java index fcee6f46..715a9d74 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java | |||
@@ -108,7 +108,7 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{ | |||
108 | Cursor<KEY, VALUE> fromCursor = this.getCursor(); | 108 | Cursor<KEY, VALUE> fromCursor = this.getCursor(); |
109 | VersionedMap<KEY, VALUE> toMap = this.store.createMap(toVersion); | 109 | VersionedMap<KEY, VALUE> toMap = this.store.createMap(toVersion); |
110 | Cursor<KEY, VALUE> toCursor = toMap.getCursor(); | 110 | Cursor<KEY, VALUE> toCursor = toMap.getCursor(); |
111 | return new MapDiffCursor<KEY, VALUE>(defaultValue, fromCursor, toCursor); | 111 | return new MapDiffCursor<KEY, VALUE>(this.hashProvider,this.defaultValue, fromCursor, toCursor); |
112 | 112 | ||
113 | } | 113 | } |
114 | 114 | ||