diff options
author | OszkarSemerath <semerath@mit.bme.hu> | 2021-08-01 21:59:06 +0200 |
---|---|---|
committer | OszkarSemerath <semerath@mit.bme.hu> | 2021-08-01 21:59:06 +0200 |
commit | bd4a77df9e4cda57806c9df2b272b40e82e9ae65 (patch) | |
tree | 921b2ac22e1712c7c2383595dc09b46212c31aea /model-data/src/main/java/org/eclipse | |
parent | Merge remote-tracking branch 'origin/web-demo' (diff) | |
download | refinery-bd4a77df9e4cda57806c9df2b272b40e82e9ae65.tar.gz refinery-bd4a77df9e4cda57806c9df2b272b40e82e9ae65.tar.zst refinery-bd4a77df9e4cda57806c9df2b272b40e82e9ae65.zip |
Hashprovide + Node update to make better equals/hashcodes services
Diffstat (limited to 'model-data/src/main/java/org/eclipse')
4 files changed, 253 insertions, 177 deletions
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java index 79ca4412..6ab45c7c 100644 --- a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java | |||
@@ -48,12 +48,17 @@ public interface ContinousHashProvider<K> { | |||
48 | if (key1.equals(key2)) { | 48 | if (key1.equals(key2)) { |
49 | return 0; | 49 | return 0; |
50 | } else { | 50 | } else { |
51 | for (var i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) { | 51 | for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) { |
52 | int hash1 = getEffectiveHash(key1, i); | 52 | int hash1 = getEffectiveHash(key1, i); |
53 | int hash2 = getEffectiveHash(key2, i); | 53 | int hash2 = getEffectiveHash(key2, i); |
54 | var result = Integer.compare(hash1, hash2); | 54 | for(int j = 0; j<Integer.SIZE/Node.branchingFactorBit; j++) { |
55 | if (result != 0) { | 55 | final int factorMask = (1<<Node.branchingFactorBit)-1; |
56 | return result; | 56 | int hashFragment1 = (hash1>>>j*Node.branchingFactorBit) & factorMask; |
57 | int hashFragment2 = (hash2>>>j*Node.branchingFactorBit) & factorMask; | ||
58 | var result = Integer.compare(hashFragment1, hashFragment2); | ||
59 | if (result != 0) { | ||
60 | return result; | ||
61 | } | ||
57 | } | 62 | } |
58 | } | 63 | } |
59 | throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2 | 64 | throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2 |
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java index 832742d0..5f293f70 100644 --- a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java | |||
@@ -174,7 +174,7 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> { | |||
174 | return this; | 174 | return this; |
175 | } else { | 175 | } else { |
176 | MutableNode<KEY, VALUE> mutable = toMutable(); | 176 | MutableNode<KEY, VALUE> mutable = toMutable(); |
177 | Node<KEY, VALUE> result = mutable.updateSubNode(selectedHashFragment, newsubNode); | 177 | Node<KEY, VALUE> result = mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue)); |
178 | return result; | 178 | return result; |
179 | } | 179 | } |
180 | } else { | 180 | } else { |
@@ -209,6 +209,11 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> { | |||
209 | return this; | 209 | return this; |
210 | } | 210 | } |
211 | 211 | ||
212 | @Override | ||
213 | protected MutableNode<KEY, VALUE> isMutable() { | ||
214 | return null; | ||
215 | } | ||
216 | |||
212 | @SuppressWarnings("unchecked") | 217 | @SuppressWarnings("unchecked") |
213 | @Override | 218 | @Override |
214 | boolean moveToNext(MapCursor<KEY, VALUE> cursor) { | 219 | boolean moveToNext(MapCursor<KEY, VALUE> cursor) { |
@@ -293,6 +298,28 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> { | |||
293 | } | 298 | } |
294 | } | 299 | } |
295 | 300 | ||
301 | @SuppressWarnings("unchecked") | ||
302 | @Override | ||
303 | public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) { | ||
304 | if(depth>0) { | ||
305 | boolean orphaned = Integer.bitCount(dataMap) == 1 && nodeMap == 0; | ||
306 | if(orphaned) { | ||
307 | throw new IllegalStateException("Orphaned node! " + dataMap + ": " + content[0]); | ||
308 | } | ||
309 | } | ||
310 | // check the place of data | ||
311 | |||
312 | // check subnodes | ||
313 | for(int i = 0; i<Integer.bitCount(nodeMap); i++) { | ||
314 | Node<KEY,VALUE> subnode = (Node<KEY, VALUE>) this.content[this.content.length-1-i]; | ||
315 | if(! (subnode instanceof ImmutableNode<?,?>)) { | ||
316 | throw new IllegalStateException("Immutable node contains mutable subnodes!"); | ||
317 | } else { | ||
318 | subnode.checkIntegrity(hashProvider, defaultValue, depth+1); | ||
319 | } | ||
320 | } | ||
321 | } | ||
322 | |||
296 | @Override | 323 | @Override |
297 | public int hashCode() { | 324 | public int hashCode() { |
298 | return this.precalculatedHash; | 325 | return this.precalculatedHash; |
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java index d32e5fc9..f28405da 100644 --- a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java | |||
@@ -5,69 +5,69 @@ import java.util.Map; | |||
5 | 5 | ||
6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | 6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; |
7 | 7 | ||
8 | public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | 8 | public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> { |
9 | int cachedHash; | 9 | int cachedHash; |
10 | protected Object[] content; | 10 | protected Object[] content; |
11 | 11 | ||
12 | protected MutableNode() { | 12 | protected MutableNode() { |
13 | this.content = new Object[2*factor]; | 13 | this.content = new Object[2 * factor]; |
14 | updateHash(); | 14 | updateHash(); |
15 | } | 15 | } |
16 | public static <KEY,VALUE> MutableNode<KEY,VALUE> initialize( | 16 | |
17 | KEY key, VALUE value, | 17 | public static <KEY, VALUE> MutableNode<KEY, VALUE> initialize(KEY key, VALUE value, |
18 | ContinousHashProvider<? super KEY> hashProvider, | 18 | ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue) { |
19 | VALUE defaultValue) | 19 | if (value == defaultValue) { |
20 | { | ||
21 | if(value == defaultValue) { | ||
22 | return null; | 20 | return null; |
23 | } else { | 21 | } else { |
24 | int hash = hashProvider.getHash(key, 0); | 22 | int hash = hashProvider.getHash(key, 0); |
25 | int fragment = hashFragment(hash, 0); | 23 | int fragment = hashFragment(hash, 0); |
26 | MutableNode<KEY, VALUE> res = new MutableNode<KEY, VALUE>(); | 24 | MutableNode<KEY, VALUE> res = new MutableNode<KEY, VALUE>(); |
27 | res.content[2*fragment] = key; | 25 | res.content[2 * fragment] = key; |
28 | res.content[2*fragment+1] = value; | 26 | res.content[2 * fragment + 1] = value; |
29 | res.updateHash(); | 27 | res.updateHash(); |
30 | return res; | 28 | return res; |
31 | } | 29 | } |
32 | } | 30 | } |
33 | 31 | ||
34 | /** | 32 | /** |
35 | * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} | 33 | * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode} |
34 | * | ||
36 | * @param node | 35 | * @param node |
37 | */ | 36 | */ |
38 | protected MutableNode(ImmutableNode<KEY,VALUE> node) { | 37 | protected MutableNode(ImmutableNode<KEY, VALUE> node) { |
39 | this.content = new Object[2*factor]; | 38 | this.content = new Object[2 * factor]; |
40 | int dataUsed=0; | 39 | int dataUsed = 0; |
41 | int nodeUsed=0; | 40 | int nodeUsed = 0; |
42 | for(int i=0; i<factor; i++) { | 41 | for (int i = 0; i < factor; i++) { |
43 | int bitposition = 1 << i; | 42 | int bitposition = 1 << i; |
44 | if((node.dataMap & bitposition) != 0) { | 43 | if ((node.dataMap & bitposition) != 0) { |
45 | content[2*i] = node.content[dataUsed*2]; | 44 | content[2 * i] = node.content[dataUsed * 2]; |
46 | content[2*i+1] = node.content[dataUsed*2+1]; | 45 | content[2 * i + 1] = node.content[dataUsed * 2 + 1]; |
47 | dataUsed++; | 46 | dataUsed++; |
48 | } else if((node.nodeMap & bitposition) != 0) { | 47 | } else if ((node.nodeMap & bitposition) != 0) { |
49 | content[2*i+1] = node.content[node.content.length-1-nodeUsed]; | 48 | content[2 * i + 1] = node.content[node.content.length - 1 - nodeUsed]; |
50 | nodeUsed++; | 49 | nodeUsed++; |
51 | } | 50 | } |
52 | } | 51 | } |
53 | this.cachedHash = node.hashCode(); | 52 | this.cachedHash = node.hashCode(); |
54 | } | 53 | } |
55 | 54 | ||
56 | @SuppressWarnings("unchecked") | 55 | @SuppressWarnings("unchecked") |
57 | @Override | 56 | @Override |
58 | public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) { | 57 | public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, |
59 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | 58 | int depth) { |
60 | KEY keyCandidate = (KEY) this.content[2*selectedHashFragment]; | 59 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
61 | if(keyCandidate != null) { | 60 | KEY keyCandidate = (KEY) this.content[2 * selectedHashFragment]; |
62 | if(keyCandidate.equals(key)) { | 61 | if (keyCandidate != null) { |
63 | return (VALUE) this.content[2*selectedHashFragment+1]; | 62 | if (keyCandidate.equals(key)) { |
63 | return (VALUE) this.content[2 * selectedHashFragment + 1]; | ||
64 | } else { | 64 | } else { |
65 | return defaultValue; | 65 | return defaultValue; |
66 | } | 66 | } |
67 | } else { | 67 | } else { |
68 | Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1]; | 68 | Node<KEY, VALUE> nodeCandidate = (Node<KEY, VALUE>) content[2 * selectedHashFragment + 1]; |
69 | if(nodeCandidate != null) { | 69 | if (nodeCandidate != null) { |
70 | int newDepth = depth+1; | 70 | int newDepth = depth + 1; |
71 | int newHash = newHash(hashProvider, key, hash, newDepth); | 71 | int newHash = newHash(hashProvider, key, hash, newDepth); |
72 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); | 72 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); |
73 | } else { | 73 | } else { |
@@ -75,32 +75,26 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
75 | } | 75 | } |
76 | } | 76 | } |
77 | } | 77 | } |
78 | 78 | ||
79 | private boolean hasContent() { | ||
80 | for(Object element : this.content) { | ||
81 | if(element != null) return true; | ||
82 | } | ||
83 | return false; | ||
84 | } | ||
85 | |||
86 | @SuppressWarnings("unchecked") | 79 | @SuppressWarnings("unchecked") |
87 | @Override | 80 | @Override |
88 | public Node<KEY,VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) { | 81 | public Node<KEY, VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, |
89 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | 82 | VALUE defaultValue, int hash, int depth) { |
90 | KEY keyCandidate = (KEY) content[2*selectedHashFragment]; | 83 | int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); |
91 | if(keyCandidate != null) { | 84 | KEY keyCandidate = (KEY) content[2 * selectedHashFragment]; |
85 | if (keyCandidate != null) { | ||
92 | // If has key | 86 | // If has key |
93 | if(keyCandidate.equals(key)) { | 87 | if (keyCandidate.equals(key)) { |
94 | // The key is equals to an existing key -> update entry | 88 | // The key is equals to an existing key -> update entry |
95 | if(value == defaultValue) { | 89 | if (value == defaultValue) { |
96 | return removeEntry(selectedHashFragment); | 90 | return removeEntry(selectedHashFragment); |
97 | } else { | 91 | } else { |
98 | return updateValue(value,selectedHashFragment); | 92 | return updateValue(value, selectedHashFragment); |
99 | } | 93 | } |
100 | } else { | 94 | } else { |
101 | // The key is not equivalent to an existing key on the same hash bin | 95 | // The key is not equivalent to an existing key on the same hash bin |
102 | // -> split entry if it is necessary | 96 | // -> split entry if it is necessary |
103 | if(value == defaultValue) { | 97 | if (value == defaultValue) { |
104 | // Value is default -> do not need to add new node | 98 | // Value is default -> do not need to add new node |
105 | return this; | 99 | return this; |
106 | } else { | 100 | } else { |
@@ -110,85 +104,130 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
110 | } | 104 | } |
111 | } else { | 105 | } else { |
112 | // If it does not have key, check for value | 106 | // If it does not have key, check for value |
113 | Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1]; | 107 | Node<KEY, VALUE> nodeCandidate = (Node<KEY, VALUE>) content[2 * selectedHashFragment + 1]; |
114 | if(nodeCandidate != null) { | 108 | if (nodeCandidate != null) { |
115 | // If it has value, it is a subnode -> upate that | 109 | // If it has value, it is a subnode -> upate that |
116 | Node<KEY, VALUE> newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, newHash(hashProvider, key, hash, depth+1), depth+1); | 110 | Node<KEY, VALUE> newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, |
117 | return updateSubNode(selectedHashFragment,newNode); | 111 | newHash(hashProvider, key, hash, depth + 1), depth + 1); |
112 | return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue)); | ||
118 | } else { | 113 | } else { |
119 | // If it does not have value, put it in the empty place | 114 | // If it does not have value, put it in the empty place |
120 | if(value == defaultValue) { | 115 | if (value == defaultValue) { |
121 | // dont need to add new key-value pair | 116 | // dont need to add new key-value pair |
122 | return this; | 117 | return this; |
123 | } else { | 118 | } else { |
124 | return addEntry(key, value, selectedHashFragment); | 119 | return addEntry(key, value, selectedHashFragment); |
125 | } | 120 | } |
126 | 121 | ||
127 | } | 122 | } |
128 | } | 123 | } |
129 | } | 124 | } |
130 | 125 | ||
131 | private Node<KEY, VALUE> addEntry(KEY key, VALUE value, int selectedHashFragment) { | 126 | private Node<KEY, VALUE> addEntry(KEY key, VALUE value, int selectedHashFragment) { |
132 | content[2*selectedHashFragment] = key; | 127 | content[2 * selectedHashFragment] = key; |
133 | content[2*selectedHashFragment+1] = value; | 128 | content[2 * selectedHashFragment + 1] = value; |
134 | updateHash(); | 129 | updateHash(); |
135 | return this; | 130 | return this; |
136 | } | 131 | } |
132 | |||
137 | /** | 133 | /** |
138 | * Updates an entry in a selected hash-fragment to a non-default value. | 134 | * Updates an entry in a selected hash-fragment to a non-default value. |
135 | * | ||
139 | * @param value | 136 | * @param value |
140 | * @param selectedHashFragment | 137 | * @param selectedHashFragment |
141 | * @return | 138 | * @return |
142 | */ | 139 | */ |
143 | Node<KEY, VALUE> updateValue(VALUE value, int selectedHashFragment) { | 140 | Node<KEY, VALUE> updateValue(VALUE value, int selectedHashFragment) { |
144 | content[2*selectedHashFragment+1] = value; | 141 | content[2 * selectedHashFragment + 1] = value; |
145 | updateHash(); | 142 | updateHash(); |
146 | return this; | 143 | return this; |
147 | } | 144 | } |
148 | 145 | ||
149 | /** | 146 | /** |
150 | * | 147 | * |
151 | * @param selectedHashFragment | 148 | * @param selectedHashFragment |
152 | * @param newNode | 149 | * @param newNode |
153 | * @return | 150 | * @return |
154 | */ | 151 | */ |
155 | Node<KEY, VALUE> updateSubNode(int selectedHashFragment, Node<KEY, VALUE> newNode) { | 152 | Node<KEY, VALUE> updateWithSubNode(int selectedHashFragment, Node<KEY, VALUE> newNode, boolean deletionHappened) { |
156 | content[2*selectedHashFragment+1] = newNode; | 153 | if (deletionHappened) { |
157 | for(int i = 0; i<this.content.length; i++) { | 154 | if (newNode == null) { |
158 | if(content[i]!=null) { | 155 | // Check whether this node become empty |
159 | updateHash(); | 156 | content[2 * selectedHashFragment + 1] = null; // i.e. the new node |
160 | return this; | 157 | if (hasContent()) { |
158 | updateHash(); | ||
159 | return this; | ||
160 | } else { | ||
161 | return null; | ||
162 | } | ||
163 | } else { | ||
164 | // check whether newNode is orphan; | ||
165 | MutableNode<KEY, VALUE> immutableNewNode = newNode.isMutable(); | ||
166 | if (immutableNewNode != null) { | ||
167 | int orphaned = immutableNewNode.isOrphaned(); | ||
168 | if (orphaned >= 0) { | ||
169 | // orphan subnode data is replaced with data | ||
170 | content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2]; | ||
171 | content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1]; | ||
172 | updateHash(); | ||
173 | return this; | ||
174 | } | ||
175 | } | ||
176 | } | ||
177 | } | ||
178 | // normal behaviour | ||
179 | content[2 * selectedHashFragment + 1] = newNode; | ||
180 | updateHash(); | ||
181 | return this; | ||
182 | |||
183 | } | ||
184 | |||
185 | private boolean hasContent() { | ||
186 | for (Object element : this.content) { | ||
187 | if (element != null) | ||
188 | return true; | ||
189 | } | ||
190 | return false; | ||
191 | } | ||
192 | |||
193 | @Override | ||
194 | protected MutableNode<KEY, VALUE> isMutable() { | ||
195 | return this; | ||
196 | } | ||
197 | |||
198 | protected int isOrphaned() { | ||
199 | int dataFound = -2; | ||
200 | for (int i = 0; i < factor; i++) { | ||
201 | if (content[i * 2] != null) { | ||
202 | if (dataFound >= 0) { | ||
203 | return -1; | ||
204 | } else { | ||
205 | dataFound = i; | ||
206 | } | ||
207 | } else if (content[i * 2 + 1] != null) { | ||
208 | return -3; | ||
161 | } | 209 | } |
162 | } | 210 | } |
163 | return null; | 211 | return dataFound; |
164 | } | 212 | } |
165 | 213 | ||
166 | @SuppressWarnings("unchecked") | 214 | @SuppressWarnings("unchecked") |
167 | private Node<KEY, VALUE> moveDownAndSplit( | 215 | private Node<KEY, VALUE> moveDownAndSplit(ContinousHashProvider<? super KEY> hashProvider, KEY newKey, |
168 | ContinousHashProvider<? super KEY> hashProvider, | 216 | VALUE newValue, KEY previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { |
169 | KEY newKey, VALUE newValue, KEY previousKey, | 217 | VALUE previousValue = (VALUE) content[2 * selectedHashFragmentOfCurrentDepth + 1]; |
170 | int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) | 218 | |
171 | { | 219 | // final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth); |
172 | VALUE previousValue = (VALUE) content[2*selectedHashFragmentOfCurrentDepth+1]; | 220 | MutableNode<KEY, VALUE> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, |
173 | 221 | hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1); | |
174 | //final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth); | 222 | |
175 | MutableNode<KEY,VALUE> newSubNode = newNodeWithTwoEntries( | 223 | content[2 * selectedHashFragmentOfCurrentDepth] = null; |
176 | hashProvider, | 224 | content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode; |
177 | previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), | ||
178 | newKey, newValue, hashOfNewKey, | ||
179 | depth+1); | ||
180 | |||
181 | content[2*selectedHashFragmentOfCurrentDepth] = null; | ||
182 | content[2*selectedHashFragmentOfCurrentDepth+1] = newSubNode; | ||
183 | updateHash(); | 225 | updateHash(); |
184 | return this; | 226 | return this; |
185 | } | 227 | } |
186 | private MutableNode<KEY,VALUE> newNodeWithTwoEntries( | 228 | |
187 | ContinousHashProvider<? super KEY> hashProvider, | 229 | private MutableNode<KEY, VALUE> newNodeWithTwoEntries(ContinousHashProvider<? super KEY> hashProvider, KEY key1, |
188 | KEY key1, VALUE value1, int oldHash1, | 230 | VALUE value1, int oldHash1, KEY key2, VALUE value2, int oldHash2, int newdepth) { |
189 | KEY key2, VALUE value2, int oldHash2, | ||
190 | int newdepth) | ||
191 | { | ||
192 | // final int depthLimit = 4000; | 231 | // final int depthLimit = 4000; |
193 | // if(newdepth>depthLimit) { | 232 | // if(newdepth>depthLimit) { |
194 | // final int newHashes = 4000/numberOfFactors; | 233 | // final int newHashes = 4000/numberOfFactors; |
@@ -199,101 +238,97 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
199 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); | 238 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); |
200 | int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); | 239 | int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); |
201 | int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); | 240 | int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); |
202 | 241 | ||
203 | MutableNode<KEY,VALUE> subNode = new MutableNode<KEY,VALUE>(); | 242 | MutableNode<KEY, VALUE> subNode = new MutableNode<KEY, VALUE>(); |
204 | if(newFragment1 != newFragment2) { | 243 | if (newFragment1 != newFragment2) { |
205 | subNode.content[newFragment1*2]=key1; | 244 | subNode.content[newFragment1 * 2] = key1; |
206 | subNode.content[newFragment1*2+1]=value1; | 245 | subNode.content[newFragment1 * 2 + 1] = value1; |
207 | 246 | ||
208 | subNode.content[newFragment2*2]=key2; | 247 | subNode.content[newFragment2 * 2] = key2; |
209 | subNode.content[newFragment2*2+1]=value2; | 248 | subNode.content[newFragment2 * 2 + 1] = value2; |
210 | } else { | 249 | } else { |
211 | MutableNode<KEY,VALUE> subSubNode = newNodeWithTwoEntries( | 250 | MutableNode<KEY, VALUE> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, |
212 | hashProvider, | 251 | value2, newHash2, newdepth + 1); |
213 | key1, value1, newHash1, | 252 | subNode.content[newFragment1 * 2 + 1] = subSubNode; |
214 | key2, value2, newHash2, | ||
215 | newdepth+1); | ||
216 | subNode.content[newFragment1*2+1] = subSubNode; | ||
217 | } | 253 | } |
218 | subNode.updateHash(); | 254 | subNode.updateHash(); |
219 | return subNode; | 255 | return subNode; |
220 | } | 256 | } |
221 | 257 | ||
222 | Node<KEY, VALUE> removeEntry(int selectedHashFragment) { | 258 | Node<KEY, VALUE> removeEntry(int selectedHashFragment) { |
223 | content[2*selectedHashFragment] = null; | 259 | content[2 * selectedHashFragment] = null; |
224 | content[2*selectedHashFragment+1] = null; | 260 | content[2 * selectedHashFragment + 1] = null; |
225 | if(hasContent()) { | 261 | if (hasContent()) { |
226 | updateHash(); | 262 | updateHash(); |
227 | return this; | 263 | return this; |
228 | } else { | 264 | } else { |
229 | return null; | 265 | return null; |
230 | } | 266 | } |
231 | } | 267 | } |
232 | 268 | ||
233 | @SuppressWarnings("unchecked") | 269 | @SuppressWarnings("unchecked") |
234 | @Override | 270 | @Override |
235 | public long getSize() { | 271 | public long getSize() { |
236 | int size = 0; | 272 | int size = 0; |
237 | for(int i=0; i<factor; i++) { | 273 | for (int i = 0; i < factor; i++) { |
238 | if(content[i*2]!=null) { | 274 | if (content[i * 2] != null) { |
239 | size++; | 275 | size++; |
240 | } else{ | 276 | } else { |
241 | Node<KEY,VALUE> nodeCandidate = (Node<KEY, VALUE>) content[i*2+1]; | 277 | Node<KEY, VALUE> nodeCandidate = (Node<KEY, VALUE>) content[i * 2 + 1]; |
242 | if(nodeCandidate!=null) { | 278 | if (nodeCandidate != null) { |
243 | size+=nodeCandidate.getSize(); | 279 | size += nodeCandidate.getSize(); |
244 | } | 280 | } |
245 | } | 281 | } |
246 | } | 282 | } |
247 | return size; | 283 | return size; |
248 | } | 284 | } |
249 | 285 | ||
250 | @Override | 286 | @Override |
251 | protected MutableNode<KEY,VALUE> toMutable() { | 287 | protected MutableNode<KEY, VALUE> toMutable() { |
252 | return this; | 288 | return this; |
253 | } | 289 | } |
254 | 290 | ||
255 | @Override | 291 | @Override |
256 | public ImmutableNode<KEY, VALUE> toImmutable(Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) { | 292 | public ImmutableNode<KEY, VALUE> toImmutable(Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) { |
257 | return ImmutableNode.constructImmutable(this,cache); | 293 | return ImmutableNode.constructImmutable(this, cache); |
258 | } | 294 | } |
259 | 295 | ||
260 | @SuppressWarnings("unchecked") | 296 | @SuppressWarnings("unchecked") |
261 | @Override | 297 | @Override |
262 | boolean moveToNext(MapCursor<KEY, VALUE> cursor) { | 298 | boolean moveToNext(MapCursor<KEY, VALUE> cursor) { |
263 | // 1. try to move to data | 299 | // 1. try to move to data |
264 | if(cursor.dataIndex != MapCursor.IndexFinish) { | 300 | if (cursor.dataIndex != MapCursor.IndexFinish) { |
265 | for(int index = cursor.dataIndex+1; index < factor; index++) { | 301 | for (int index = cursor.dataIndex + 1; index < factor; index++) { |
266 | if(this.content[index*2]!=null) { | 302 | if (this.content[index * 2] != null) { |
267 | // 1.1 found next data | 303 | // 1.1 found next data |
268 | cursor.dataIndex = index; | 304 | cursor.dataIndex = index; |
269 | cursor.key = (KEY) this.content[index*2]; | 305 | cursor.key = (KEY) this.content[index * 2]; |
270 | cursor.value = (VALUE) this.content[index*2+1]; | 306 | cursor.value = (VALUE) this.content[index * 2 + 1]; |
271 | return true; | 307 | return true; |
272 | } | 308 | } |
273 | } | 309 | } |
274 | cursor.dataIndex = MapCursor.IndexFinish; | 310 | cursor.dataIndex = MapCursor.IndexFinish; |
275 | } | 311 | } |
276 | 312 | ||
277 | // 2. look inside the subnodes | 313 | // 2. look inside the subnodes |
278 | for(int index = cursor.nodeIndexStack.peek()+1; index < factor; index++) { | 314 | for (int index = cursor.nodeIndexStack.peek() + 1; index < factor; index++) { |
279 | if(this.content[index*2]==null && this.content[index*2+1] !=null) { | 315 | if (this.content[index * 2] == null && this.content[index * 2 + 1] != null) { |
280 | // 2.1 found next subnode, move down to the subnode | 316 | // 2.1 found next subnode, move down to the subnode |
281 | Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[index*2+1]; | 317 | Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[index * 2 + 1]; |
282 | 318 | ||
283 | cursor.dataIndex = MapCursor.IndexStart; | 319 | cursor.dataIndex = MapCursor.IndexStart; |
284 | cursor.nodeIndexStack.pop(); | 320 | cursor.nodeIndexStack.pop(); |
285 | cursor.nodeIndexStack.push(index); | 321 | cursor.nodeIndexStack.push(index); |
286 | cursor.nodeIndexStack.push(MapCursor.IndexStart); | 322 | cursor.nodeIndexStack.push(MapCursor.IndexStart); |
287 | cursor.nodeStack.push(subnode); | 323 | cursor.nodeStack.push(subnode); |
288 | 324 | ||
289 | |||
290 | return subnode.moveToNext(cursor); | 325 | return subnode.moveToNext(cursor); |
291 | } | 326 | } |
292 | } | 327 | } |
293 | // 3. no subnode found, move up | 328 | // 3. no subnode found, move up |
294 | cursor.nodeStack.pop(); | 329 | cursor.nodeStack.pop(); |
295 | cursor.nodeIndexStack.pop(); | 330 | cursor.nodeIndexStack.pop(); |
296 | if(!cursor.nodeStack.isEmpty()) { | 331 | if (!cursor.nodeStack.isEmpty()) { |
297 | Node<KEY, VALUE> supernode = cursor.nodeStack.peek(); | 332 | Node<KEY, VALUE> supernode = cursor.nodeStack.peek(); |
298 | return supernode.moveToNext(cursor); | 333 | return supernode.moveToNext(cursor); |
299 | } else { | 334 | } else { |
@@ -302,89 +337,98 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
302 | return false; | 337 | return false; |
303 | } | 338 | } |
304 | } | 339 | } |
305 | 340 | ||
306 | @Override | 341 | @Override |
307 | public void prettyPrint(StringBuilder builder, int depth, int code) { | 342 | public void prettyPrint(StringBuilder builder, int depth, int code) { |
308 | for(int i = 0; i<depth; i++) { | 343 | for (int i = 0; i < depth; i++) { |
309 | builder.append("\t"); | 344 | builder.append("\t"); |
310 | } | 345 | } |
311 | if(code>=0) { | 346 | if (code >= 0) { |
312 | builder.append(code); | 347 | builder.append(code); |
313 | builder.append(":"); | 348 | builder.append(":"); |
314 | } | 349 | } |
315 | builder.append("Mutable("); | 350 | builder.append("Mutable("); |
316 | // print content | 351 | // print content |
317 | boolean hadContent = false; | 352 | boolean hadContent = false; |
318 | for(int i = 0; i<factor; i++) { | 353 | for (int i = 0; i < factor; i++) { |
319 | if(content[2*i] != null) { | 354 | if (content[2 * i] != null) { |
320 | if(hadContent) { | 355 | if (hadContent) { |
321 | builder.append(","); | 356 | builder.append(","); |
322 | } | 357 | } |
323 | builder.append(i); | 358 | builder.append(i); |
324 | builder.append(":["); | 359 | builder.append(":["); |
325 | builder.append(content[2*i].toString()); | 360 | builder.append(content[2 * i].toString()); |
326 | builder.append("]->["); | 361 | builder.append("]->["); |
327 | builder.append(content[2*i+1].toString()); | 362 | builder.append(content[2 * i + 1].toString()); |
328 | builder.append("]"); | 363 | builder.append("]"); |
329 | hadContent = true; | 364 | hadContent = true; |
330 | } | 365 | } |
331 | } | 366 | } |
332 | builder.append(")"); | 367 | builder.append(")"); |
333 | // print subnodes | 368 | // print subnodes |
334 | for(int i = 0; i<factor; i++) { | 369 | for (int i = 0; i < factor; i++) { |
335 | if(content[2*i] == null && content[2*i+1]!=null) { | 370 | if (content[2 * i] == null && content[2 * i + 1] != null) { |
336 | @SuppressWarnings("unchecked") | 371 | @SuppressWarnings("unchecked") |
337 | Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) content[2*i+1]; | 372 | Node<KEY, VALUE> subNode = (Node<KEY, VALUE>) content[2 * i + 1]; |
338 | builder.append("\n"); | 373 | builder.append("\n"); |
339 | subNode.prettyPrint(builder, depth+1, i); | 374 | subNode.prettyPrint(builder, depth + 1, i); |
340 | } | 375 | } |
341 | } | 376 | } |
342 | } | 377 | } |
343 | @SuppressWarnings({"unchecked"}) | 378 | |
379 | @SuppressWarnings({ "unchecked" }) | ||
344 | @Override | 380 | @Override |
345 | public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) { | 381 | public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) { |
346 | for(int i = 0; i<factor; i++) { | 382 | // check for orphan nodes |
347 | if(this.content[2*i] != null) { | 383 | if(depth>0) { |
348 | KEY key = (KEY) this.content[2*i]; | 384 | int orphaned = isOrphaned(); |
349 | VALUE value = (VALUE) this.content[2*i+1]; | 385 | if(orphaned>=0) { |
350 | 386 | throw new IllegalStateException("Orphaned node! " + orphaned + ": " + content[2 * orphaned]); | |
351 | if(value == defaultValue) { | 387 | } |
388 | } | ||
389 | // check the place of data | ||
390 | for (int i = 0; i < factor; i++) { | ||
391 | if (this.content[2 * i] != null) { | ||
392 | KEY key = (KEY) this.content[2 * i]; | ||
393 | VALUE value = (VALUE) this.content[2 * i + 1]; | ||
394 | |||
395 | if (value == defaultValue) { | ||
352 | throw new IllegalStateException("Node contains default value!"); | 396 | throw new IllegalStateException("Node contains default value!"); |
353 | } | 397 | } |
354 | int hashCode = hashProvider.getHash(key, hashDepth(depth)); | 398 | int hashCode = hashProvider.getHash(key, hashDepth(depth)); |
355 | int shiftDepth = shiftDepth(depth); | 399 | int shiftDepth = shiftDepth(depth); |
356 | int selectedHashFragment = hashFragment(hashCode, shiftDepth); | 400 | int selectedHashFragment = hashFragment(hashCode, shiftDepth); |
357 | if(i != selectedHashFragment) { | 401 | if (i != selectedHashFragment) { |
358 | throw new IllegalStateException( | 402 | throw new IllegalStateException("Key " + key + " with hash code " + hashCode |
359 | "Key "+key+" with hash code "+hashCode+" is in bad place! Fragment=" + selectedHashFragment +", Place="+i); | 403 | + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i); |
360 | } | 404 | } |
361 | } | 405 | } |
362 | } | 406 | } |
363 | for(int i = 0; i<factor; i++) { | 407 | // check subnodes |
364 | if(this.content[2*i+1] != null && this.content[2*i] == null) { | 408 | for (int i = 0; i < factor; i++) { |
365 | Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) this.content[2*i+1]; | 409 | if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { |
366 | subNode.checkIntegrity(hashProvider, defaultValue, depth+1); | 410 | Node<KEY, VALUE> subNode = (Node<KEY, VALUE>) this.content[2 * i + 1]; |
411 | subNode.checkIntegrity(hashProvider, defaultValue, depth + 1); | ||
367 | } | 412 | } |
368 | } | 413 | } |
414 | // check the hash | ||
369 | int oldHash = this.cachedHash; | 415 | int oldHash = this.cachedHash; |
370 | updateHash(); | 416 | updateHash(); |
371 | int newHash = this.cachedHash; | 417 | int newHash = this.cachedHash; |
372 | if(oldHash != newHash) { | 418 | if (oldHash != newHash) { |
373 | throw new IllegalStateException("Hash code was not up to date! (old="+oldHash+",new="+newHash+")"); | 419 | throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")"); |
374 | } | 420 | } |
375 | } | 421 | } |
376 | 422 | ||
377 | |||
378 | protected void updateHash() { | 423 | protected void updateHash() { |
379 | this.cachedHash = Arrays.hashCode(content); | 424 | this.cachedHash = Arrays.hashCode(content); |
380 | } | 425 | } |
381 | 426 | ||
382 | @Override | 427 | @Override |
383 | public int hashCode() { | 428 | public int hashCode() { |
384 | return this.cachedHash; | 429 | return this.cachedHash; |
385 | } | 430 | } |
386 | 431 | ||
387 | |||
388 | @Override | 432 | @Override |
389 | public boolean equals(Object obj) { | 433 | public boolean equals(Object obj) { |
390 | if (this == obj) | 434 | if (this == obj) |
@@ -392,10 +436,10 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
392 | if (obj == null) | 436 | if (obj == null) |
393 | return false; | 437 | return false; |
394 | if (obj instanceof MutableNode<?, ?>) { | 438 | if (obj instanceof MutableNode<?, ?>) { |
395 | MutableNode<?,?> other = (MutableNode<?,?>) obj; | 439 | MutableNode<?, ?> other = (MutableNode<?, ?>) obj; |
396 | return Arrays.deepEquals(this.content, other.content); | 440 | return Arrays.deepEquals(this.content, other.content); |
397 | } else if(obj instanceof ImmutableNode<?,?>) { | 441 | } else if (obj instanceof ImmutableNode<?, ?>) { |
398 | ImmutableNode<?,?> other = (ImmutableNode<?,?>) obj; | 442 | ImmutableNode<?, ?> other = (ImmutableNode<?, ?>) obj; |
399 | return ImmutableNode.compareImmutableMutable(other, this); | 443 | return ImmutableNode.compareImmutableMutable(other, this); |
400 | } else { | 444 | } else { |
401 | return false; | 445 | return false; |
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java index f19ca06f..2176af87 100644 --- a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java | |||
@@ -5,8 +5,8 @@ import java.util.Map; | |||
5 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | 5 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; |
6 | 6 | ||
7 | public abstract class Node<KEY,VALUE>{ | 7 | public abstract class Node<KEY,VALUE>{ |
8 | protected static final int branchingFactorBit = 5; | 8 | public static final int branchingFactorBit = 5; |
9 | protected static final int factor = 1<<branchingFactorBit; | 9 | public 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 | public static final int effectiveBits = branchingFactorBit * numberOfFactors; |
@@ -35,7 +35,7 @@ public abstract class Node<KEY,VALUE>{ | |||
35 | * @return The segment as an integer. | 35 | * @return The segment as an integer. |
36 | */ | 36 | */ |
37 | protected static int hashFragment(int hash, int shiftDepth) { | 37 | protected static int hashFragment(int hash, int shiftDepth) { |
38 | if(shiftDepth<0 && 5<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth); | 38 | if(shiftDepth<0 || Node.numberOfFactors<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth); |
39 | return (hash >>> shiftDepth*branchingFactorBit) & factorMask; | 39 | return (hash >>> shiftDepth*branchingFactorBit) & factorMask; |
40 | } | 40 | } |
41 | 41 | ||
@@ -64,7 +64,7 @@ public abstract class Node<KEY,VALUE>{ | |||
64 | abstract MutableNode<KEY, VALUE> toMutable(); | 64 | abstract MutableNode<KEY, VALUE> toMutable(); |
65 | public abstract ImmutableNode<KEY, VALUE> toImmutable( | 65 | public abstract ImmutableNode<KEY, VALUE> toImmutable( |
66 | Map<Node<KEY, VALUE>,ImmutableNode<KEY, VALUE>> cache); | 66 | Map<Node<KEY, VALUE>,ImmutableNode<KEY, VALUE>> cache); |
67 | 67 | protected abstract MutableNode<KEY, VALUE> isMutable(); | |
68 | /** | 68 | /** |
69 | * Moves a {@link MapCursor} to its next position. | 69 | * Moves a {@link MapCursor} to its next position. |
70 | * @param cursor the cursor | 70 | * @param cursor the cursor |