aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorLibravatar OszkarSemerath <semerath@mit.bme.hu>2021-08-01 21:59:06 +0200
committerLibravatar OszkarSemerath <semerath@mit.bme.hu>2021-08-01 21:59:06 +0200
commitbd4a77df9e4cda57806c9df2b272b40e82e9ae65 (patch)
tree921b2ac22e1712c7c2383595dc09b46212c31aea
parentMerge remote-tracking branch 'origin/web-demo' (diff)
downloadrefinery-bd4a77df9e4cda57806c9df2b272b40e82e9ae65.tar.gz
refinery-bd4a77df9e4cda57806c9df2b272b40e82e9ae65.tar.zst
refinery-bd4a77df9e4cda57806c9df2b272b40e82e9ae65.zip
Hashprovide + Node update to make better equals/hashcodes services
Diffstat
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/ContinousHashProvider.java13
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java29
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java380
-rw-r--r--model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/Node.java8
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
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<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;
5import org.eclipse.viatra.solver.data.map.ContinousHashProvider; 5import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
6 6
7public abstract class Node<KEY,VALUE>{ 7public 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
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-07-20 21:04:11 +0000