aboutsummaryrefslogtreecommitdiffstats
path: root/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
diff options
context:
space:
mode:
authorLibravatar OszkarSemerath <semerath@mit.bme.hu>2021-08-01 22:13:49 +0200
committerLibravatar OszkarSemerath <semerath@mit.bme.hu>2021-08-01 22:13:49 +0200
commit59fd43462a7c5aa076c10ce3bb16121a7dc7edcc (patch)
tree1bd28bda68125fc70ce9bc330c7bafb2016ae8bf /model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
parentContentEquals test + typo fix (diff)
downloadrefinery-59fd43462a7c5aa076c10ce3bb16121a7dc7edcc.tar.gz
refinery-59fd43462a7c5aa076c10ce3bb16121a7dc7edcc.tar.zst
refinery-59fd43462a7c5aa076c10ce3bb16121a7dc7edcc.zip
KEY,VALUE replaced with K,V to please Sonar
Diffstat (limited to 'model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java')
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java82
1 files changed, 41 insertions, 41 deletions
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 f28405da..322e2128 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,7 +5,7 @@ import java.util.Map;
5 5
6import org.eclipse.viatra.solver.data.map.ContinousHashProvider; 6import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
7 7
8public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> { 8public class MutableNode<K, V> extends Node<K, V> {
9 int cachedHash; 9 int cachedHash;
10 protected Object[] content; 10 protected Object[] content;
11 11
@@ -14,14 +14,14 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
14 updateHash(); 14 updateHash();
15 } 15 }
16 16
17 public static <KEY, VALUE> MutableNode<KEY, VALUE> initialize(KEY key, VALUE value, 17 public static <K, V> MutableNode<K, V> initialize(K key, V value,
18 ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue) { 18 ContinousHashProvider<? super K> hashProvider, V defaultValue) {
19 if (value == defaultValue) { 19 if (value == defaultValue) {
20 return null; 20 return null;
21 } else { 21 } else {
22 int hash = hashProvider.getHash(key, 0); 22 int hash = hashProvider.getHash(key, 0);
23 int fragment = hashFragment(hash, 0); 23 int fragment = hashFragment(hash, 0);
24 MutableNode<KEY, VALUE> res = new MutableNode<KEY, VALUE>(); 24 MutableNode<K, V> res = new MutableNode<K, V>();
25 res.content[2 * fragment] = key; 25 res.content[2 * fragment] = key;
26 res.content[2 * fragment + 1] = value; 26 res.content[2 * fragment + 1] = value;
27 res.updateHash(); 27 res.updateHash();
@@ -34,7 +34,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
34 * 34 *
35 * @param node 35 * @param node
36 */ 36 */
37 protected MutableNode(ImmutableNode<KEY, VALUE> node) { 37 protected MutableNode(ImmutableNode<K, V> node) {
38 this.content = new Object[2 * factor]; 38 this.content = new Object[2 * factor];
39 int dataUsed = 0; 39 int dataUsed = 0;
40 int nodeUsed = 0; 40 int nodeUsed = 0;
@@ -54,18 +54,18 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
54 54
55 @SuppressWarnings("unchecked") 55 @SuppressWarnings("unchecked")
56 @Override 56 @Override
57 public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, 57 public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash,
58 int depth) { 58 int depth) {
59 int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); 59 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
60 KEY keyCandidate = (KEY) this.content[2 * selectedHashFragment]; 60 K keyCandidate = (K) this.content[2 * selectedHashFragment];
61 if (keyCandidate != null) { 61 if (keyCandidate != null) {
62 if (keyCandidate.equals(key)) { 62 if (keyCandidate.equals(key)) {
63 return (VALUE) this.content[2 * selectedHashFragment + 1]; 63 return (V) 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<K, V> nodeCandidate = (Node<K, V>) 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);
@@ -78,10 +78,10 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
78 78
79 @SuppressWarnings("unchecked") 79 @SuppressWarnings("unchecked")
80 @Override 80 @Override
81 public Node<KEY, VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, 81 public Node<K, V> putValue(K key, V value, ContinousHashProvider<? super K> hashProvider,
82 VALUE defaultValue, int hash, int depth) { 82 V defaultValue, int hash, int depth) {
83 int selectedHashFragment = hashFragment(hash, shiftDepth(depth)); 83 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
84 KEY keyCandidate = (KEY) content[2 * selectedHashFragment]; 84 K keyCandidate = (K) content[2 * selectedHashFragment];
85 if (keyCandidate != null) { 85 if (keyCandidate != null) {
86 // If has key 86 // If has key
87 if (keyCandidate.equals(key)) { 87 if (keyCandidate.equals(key)) {
@@ -104,10 +104,10 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
104 } 104 }
105 } else { 105 } else {
106 // If it does not have key, check for value 106 // If it does not have key, check for value
107 Node<KEY, VALUE> nodeCandidate = (Node<KEY, VALUE>) content[2 * selectedHashFragment + 1]; 107 Node<K, V> nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
108 if (nodeCandidate != null) { 108 if (nodeCandidate != null) {
109 // If it has value, it is a subnode -> upate that 109 // If it has value, it is a subnode -> upate that
110 Node<KEY, VALUE> newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, 110 Node<K, V> newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue,
111 newHash(hashProvider, key, hash, depth + 1), depth + 1); 111 newHash(hashProvider, key, hash, depth + 1), depth + 1);
112 return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue)); 112 return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue));
113 } else { 113 } else {
@@ -123,7 +123,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
123 } 123 }
124 } 124 }
125 125
126 private Node<KEY, VALUE> addEntry(KEY key, VALUE value, int selectedHashFragment) { 126 private Node<K, V> addEntry(K key, V value, int selectedHashFragment) {
127 content[2 * selectedHashFragment] = key; 127 content[2 * selectedHashFragment] = key;
128 content[2 * selectedHashFragment + 1] = value; 128 content[2 * selectedHashFragment + 1] = value;
129 updateHash(); 129 updateHash();
@@ -137,7 +137,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
137 * @param selectedHashFragment 137 * @param selectedHashFragment
138 * @return 138 * @return
139 */ 139 */
140 Node<KEY, VALUE> updateValue(VALUE value, int selectedHashFragment) { 140 Node<K, V> updateValue(V value, int selectedHashFragment) {
141 content[2 * selectedHashFragment + 1] = value; 141 content[2 * selectedHashFragment + 1] = value;
142 updateHash(); 142 updateHash();
143 return this; 143 return this;
@@ -149,7 +149,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
149 * @param newNode 149 * @param newNode
150 * @return 150 * @return
151 */ 151 */
152 Node<KEY, VALUE> updateWithSubNode(int selectedHashFragment, Node<KEY, VALUE> newNode, boolean deletionHappened) { 152 Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) {
153 if (deletionHappened) { 153 if (deletionHappened) {
154 if (newNode == null) { 154 if (newNode == null) {
155 // Check whether this node become empty 155 // Check whether this node become empty
@@ -162,7 +162,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
162 } 162 }
163 } else { 163 } else {
164 // check whether newNode is orphan; 164 // check whether newNode is orphan;
165 MutableNode<KEY, VALUE> immutableNewNode = newNode.isMutable(); 165 MutableNode<K, V> immutableNewNode = newNode.isMutable();
166 if (immutableNewNode != null) { 166 if (immutableNewNode != null) {
167 int orphaned = immutableNewNode.isOrphaned(); 167 int orphaned = immutableNewNode.isOrphaned();
168 if (orphaned >= 0) { 168 if (orphaned >= 0) {
@@ -191,7 +191,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
191 } 191 }
192 192
193 @Override 193 @Override
194 protected MutableNode<KEY, VALUE> isMutable() { 194 protected MutableNode<K, V> isMutable() {
195 return this; 195 return this;
196 } 196 }
197 197
@@ -212,12 +212,12 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
212 } 212 }
213 213
214 @SuppressWarnings("unchecked") 214 @SuppressWarnings("unchecked")
215 private Node<KEY, VALUE> moveDownAndSplit(ContinousHashProvider<? super KEY> hashProvider, KEY newKey, 215 private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey,
216 VALUE newValue, KEY previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) { 216 V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) {
217 VALUE previousValue = (VALUE) content[2 * selectedHashFragmentOfCurrentDepth + 1]; 217 V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1];
218 218
219 // final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth); 219 // final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth);
220 MutableNode<KEY, VALUE> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, 220 MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue,
221 hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1); 221 hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1);
222 222
223 content[2 * selectedHashFragmentOfCurrentDepth] = null; 223 content[2 * selectedHashFragmentOfCurrentDepth] = null;
@@ -226,8 +226,8 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
226 return this; 226 return this;
227 } 227 }
228 228
229 private MutableNode<KEY, VALUE> newNodeWithTwoEntries(ContinousHashProvider<? super KEY> hashProvider, KEY key1, 229 private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1,
230 VALUE value1, int oldHash1, KEY key2, VALUE value2, int oldHash2, int newdepth) { 230 V value1, int oldHash1, K key2, V value2, int oldHash2, int newdepth) {
231// final int depthLimit = 4000; 231// final int depthLimit = 4000;
232// if(newdepth>depthLimit) { 232// if(newdepth>depthLimit) {
233// final int newHashes = 4000/numberOfFactors; 233// final int newHashes = 4000/numberOfFactors;
@@ -239,7 +239,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
239 int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); 239 int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth));
240 int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); 240 int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth));
241 241
242 MutableNode<KEY, VALUE> subNode = new MutableNode<KEY, VALUE>(); 242 MutableNode<K, V> subNode = new MutableNode<K, V>();
243 if (newFragment1 != newFragment2) { 243 if (newFragment1 != newFragment2) {
244 subNode.content[newFragment1 * 2] = key1; 244 subNode.content[newFragment1 * 2] = key1;
245 subNode.content[newFragment1 * 2 + 1] = value1; 245 subNode.content[newFragment1 * 2 + 1] = value1;
@@ -247,7 +247,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
247 subNode.content[newFragment2 * 2] = key2; 247 subNode.content[newFragment2 * 2] = key2;
248 subNode.content[newFragment2 * 2 + 1] = value2; 248 subNode.content[newFragment2 * 2 + 1] = value2;
249 } else { 249 } else {
250 MutableNode<KEY, VALUE> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, 250 MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2,
251 value2, newHash2, newdepth + 1); 251 value2, newHash2, newdepth + 1);
252 subNode.content[newFragment1 * 2 + 1] = subSubNode; 252 subNode.content[newFragment1 * 2 + 1] = subSubNode;
253 } 253 }
@@ -255,7 +255,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
255 return subNode; 255 return subNode;
256 } 256 }
257 257
258 Node<KEY, VALUE> removeEntry(int selectedHashFragment) { 258 Node<K, V> removeEntry(int selectedHashFragment) {
259 content[2 * selectedHashFragment] = null; 259 content[2 * selectedHashFragment] = null;
260 content[2 * selectedHashFragment + 1] = null; 260 content[2 * selectedHashFragment + 1] = null;
261 if (hasContent()) { 261 if (hasContent()) {
@@ -274,7 +274,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
274 if (content[i * 2] != null) { 274 if (content[i * 2] != null) {
275 size++; 275 size++;
276 } else { 276 } else {
277 Node<KEY, VALUE> nodeCandidate = (Node<KEY, VALUE>) content[i * 2 + 1]; 277 Node<K, V> nodeCandidate = (Node<K, V>) content[i * 2 + 1];
278 if (nodeCandidate != null) { 278 if (nodeCandidate != null) {
279 size += nodeCandidate.getSize(); 279 size += nodeCandidate.getSize();
280 } 280 }
@@ -284,26 +284,26 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
284 } 284 }
285 285
286 @Override 286 @Override
287 protected MutableNode<KEY, VALUE> toMutable() { 287 protected MutableNode<K, V> toMutable() {
288 return this; 288 return this;
289 } 289 }
290 290
291 @Override 291 @Override
292 public ImmutableNode<KEY, VALUE> toImmutable(Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) { 292 public ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache) {
293 return ImmutableNode.constructImmutable(this, cache); 293 return ImmutableNode.constructImmutable(this, cache);
294 } 294 }
295 295
296 @SuppressWarnings("unchecked") 296 @SuppressWarnings("unchecked")
297 @Override 297 @Override
298 boolean moveToNext(MapCursor<KEY, VALUE> cursor) { 298 boolean moveToNext(MapCursor<K, V> cursor) {
299 // 1. try to move to data 299 // 1. try to move to data
300 if (cursor.dataIndex != MapCursor.IndexFinish) { 300 if (cursor.dataIndex != MapCursor.IndexFinish) {
301 for (int index = cursor.dataIndex + 1; index < factor; index++) { 301 for (int index = cursor.dataIndex + 1; index < factor; index++) {
302 if (this.content[index * 2] != null) { 302 if (this.content[index * 2] != null) {
303 // 1.1 found next data 303 // 1.1 found next data
304 cursor.dataIndex = index; 304 cursor.dataIndex = index;
305 cursor.key = (KEY) this.content[index * 2]; 305 cursor.key = (K) this.content[index * 2];
306 cursor.value = (VALUE) this.content[index * 2 + 1]; 306 cursor.value = (V) this.content[index * 2 + 1];
307 return true; 307 return true;
308 } 308 }
309 } 309 }
@@ -314,7 +314,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
314 for (int index = cursor.nodeIndexStack.peek() + 1; index < factor; index++) { 314 for (int index = cursor.nodeIndexStack.peek() + 1; index < factor; index++) {
315 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) {
316 // 2.1 found next subnode, move down to the subnode 316 // 2.1 found next subnode, move down to the subnode
317 Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[index * 2 + 1]; 317 Node<K, V> subnode = (Node<K, V>) this.content[index * 2 + 1];
318 318
319 cursor.dataIndex = MapCursor.IndexStart; 319 cursor.dataIndex = MapCursor.IndexStart;
320 cursor.nodeIndexStack.pop(); 320 cursor.nodeIndexStack.pop();
@@ -329,7 +329,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
329 cursor.nodeStack.pop(); 329 cursor.nodeStack.pop();
330 cursor.nodeIndexStack.pop(); 330 cursor.nodeIndexStack.pop();
331 if (!cursor.nodeStack.isEmpty()) { 331 if (!cursor.nodeStack.isEmpty()) {
332 Node<KEY, VALUE> supernode = cursor.nodeStack.peek(); 332 Node<K, V> supernode = cursor.nodeStack.peek();
333 return supernode.moveToNext(cursor); 333 return supernode.moveToNext(cursor);
334 } else { 334 } else {
335 cursor.key = null; 335 cursor.key = null;
@@ -369,7 +369,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
369 for (int i = 0; i < factor; i++) { 369 for (int i = 0; i < factor; i++) {
370 if (content[2 * i] == null && content[2 * i + 1] != null) { 370 if (content[2 * i] == null && content[2 * i + 1] != null) {
371 @SuppressWarnings("unchecked") 371 @SuppressWarnings("unchecked")
372 Node<KEY, VALUE> subNode = (Node<KEY, VALUE>) content[2 * i + 1]; 372 Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
373 builder.append("\n"); 373 builder.append("\n");
374 subNode.prettyPrint(builder, depth + 1, i); 374 subNode.prettyPrint(builder, depth + 1, i);
375 } 375 }
@@ -378,7 +378,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
378 378
379 @SuppressWarnings({ "unchecked" }) 379 @SuppressWarnings({ "unchecked" })
380 @Override 380 @Override
381 public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) { 381 public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
382 // check for orphan nodes 382 // check for orphan nodes
383 if(depth>0) { 383 if(depth>0) {
384 int orphaned = isOrphaned(); 384 int orphaned = isOrphaned();
@@ -389,8 +389,8 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
389 // check the place of data 389 // check the place of data
390 for (int i = 0; i < factor; i++) { 390 for (int i = 0; i < factor; i++) {
391 if (this.content[2 * i] != null) { 391 if (this.content[2 * i] != null) {
392 KEY key = (KEY) this.content[2 * i]; 392 K key = (K) this.content[2 * i];
393 VALUE value = (VALUE) this.content[2 * i + 1]; 393 V value = (V) this.content[2 * i + 1];
394 394
395 if (value == defaultValue) { 395 if (value == defaultValue) {
396 throw new IllegalStateException("Node contains default value!"); 396 throw new IllegalStateException("Node contains default value!");
@@ -407,7 +407,7 @@ public class MutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
407 // check subnodes 407 // check subnodes
408 for (int i = 0; i < factor; i++) { 408 for (int i = 0; i < factor; i++) {
409 if (this.content[2 * i + 1] != null && this.content[2 * i] == null) { 409 if (this.content[2 * i + 1] != null && this.content[2 * i] == null) {
410 Node<KEY, VALUE> subNode = (Node<KEY, VALUE>) this.content[2 * i + 1]; 410 Node<K, V> subNode = (Node<K, V>) this.content[2 * i + 1];
411 subNode.checkIntegrity(hashProvider, defaultValue, depth + 1); 411 subNode.checkIntegrity(hashProvider, defaultValue, depth + 1);
412 } 412 }
413 } 413 }