diff options
Diffstat (limited to 'store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java')
-rw-r--r-- | store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java | 125 |
1 files changed, 66 insertions, 59 deletions
diff --git a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java index e97e4aa1..35d20539 100644 --- a/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java +++ b/store/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java | |||
@@ -1,7 +1,6 @@ | |||
1 | package org.eclipse.viatra.solver.data.map.internal; | 1 | package org.eclipse.viatra.solver.data.map.internal; |
2 | 2 | ||
3 | import java.util.List; | 3 | import java.util.List; |
4 | import java.util.stream.Collectors; | ||
5 | import java.util.stream.Stream; | 4 | import java.util.stream.Stream; |
6 | 5 | ||
7 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | 6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; |
@@ -11,110 +10,109 @@ import org.eclipse.viatra.solver.data.map.VersionedMap; | |||
11 | 10 | ||
12 | /** | 11 | /** |
13 | * A cursor representing the difference between two states of a map. | 12 | * A cursor representing the difference between two states of a map. |
13 | * | ||
14 | * @author Oszkar Semerath | 14 | * @author Oszkar Semerath |
15 | * | 15 | * |
16 | */ | 16 | */ |
17 | public class MapDiffCursor<K,V> implements DiffCursor<K, V>, Cursor<K,V>{ | 17 | public class MapDiffCursor<K, V> implements DiffCursor<K, V>, Cursor<K, V> { |
18 | /** | 18 | /** |
19 | * Default value representing missing elements. | 19 | * Default value representing missing elements. |
20 | */ | 20 | */ |
21 | private V defaultValue; | 21 | private V defaultValue; |
22 | private MapCursor<K,V> cursor1; | 22 | private MapCursor<K, V> cursor1; |
23 | private MapCursor<K,V> cursor2; | 23 | private MapCursor<K, V> cursor2; |
24 | private ContinousHashProvider<? super K> hashProvider; | 24 | private ContinousHashProvider<? super K> hashProvider; |
25 | 25 | ||
26 | // Values | 26 | // Values |
27 | private K key; | 27 | private K key; |
28 | private V fromValue; | 28 | private V fromValue; |
29 | private V toValue; | 29 | private V toValue; |
30 | 30 | ||
31 | // State | 31 | // State |
32 | /** | 32 | /** |
33 | * 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, |
34 | * and 0 if they are at the same position. | ||
34 | */ | 35 | */ |
35 | private int cursorRelation; | 36 | private int cursorRelation; |
36 | /** | 37 | private HashClash hashClash = HashClash.NONE; |
37 | * Denotes a state when two cursors are in the same position, but they contain different keys. | 38 | |
38 | * Possible values: | 39 | public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1, |
39 | * <ul> | 40 | Cursor<K, V> cursor2) { |
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; | ||
46 | |||
47 | public MapDiffCursor(ContinousHashProvider<? super K> hashProvider, V defaultValue, Cursor<K, V> cursor1, Cursor<K, V> cursor2) { | ||
48 | super(); | 41 | super(); |
49 | this.hashProvider = hashProvider; | 42 | this.hashProvider = hashProvider; |
50 | this.defaultValue = defaultValue; | 43 | this.defaultValue = defaultValue; |
51 | this.cursor1 = (MapCursor<K, V>) cursor1; | 44 | this.cursor1 = (MapCursor<K, V>) cursor1; |
52 | this.cursor2 = (MapCursor<K, V>) cursor2; | 45 | this.cursor2 = (MapCursor<K, V>) cursor2; |
53 | } | 46 | } |
47 | |||
54 | @Override | 48 | @Override |
55 | public K getKey() { | 49 | public K getKey() { |
56 | return key; | 50 | return key; |
57 | } | 51 | } |
52 | |||
58 | @Override | 53 | @Override |
59 | public V getFromValue() { | 54 | public V getFromValue() { |
60 | return fromValue; | 55 | return fromValue; |
61 | } | 56 | } |
57 | |||
62 | @Override | 58 | @Override |
63 | public V getToValue() { | 59 | public V getToValue() { |
64 | return toValue; | 60 | return toValue; |
65 | } | 61 | } |
62 | |||
66 | @Override | 63 | @Override |
67 | public V getValue() { | 64 | public V getValue() { |
68 | return getToValue(); | 65 | return getToValue(); |
69 | } | 66 | } |
67 | |||
70 | public boolean isTerminated() { | 68 | public boolean isTerminated() { |
71 | return cursor1.isTerminated() && cursor2.isTerminated(); | 69 | return cursor1.isTerminated() && cursor2.isTerminated(); |
72 | } | 70 | } |
71 | |||
73 | @Override | 72 | @Override |
74 | public boolean isDirty() { | 73 | public boolean isDirty() { |
75 | return this.cursor1.isDirty() || this.cursor2.isDirty(); | 74 | return this.cursor1.isDirty() || this.cursor2.isDirty(); |
76 | } | 75 | } |
76 | |||
77 | @Override | 77 | @Override |
78 | public List<VersionedMap<?, ?>> getDependingMaps() { | 78 | public List<VersionedMap<?, ?>> getDependingMaps() { |
79 | return Stream.concat( | 79 | return Stream.concat(cursor1.getDependingMaps().stream(), cursor2.getDependingMaps().stream()).toList(); |
80 | cursor1.getDependingMaps().stream(), | ||
81 | cursor2.getDependingMaps().stream() | ||
82 | ).collect(Collectors.toList()); | ||
83 | } | 80 | } |
84 | 81 | ||
85 | protected void updateState() { | 82 | protected void updateState() { |
86 | if(!isTerminated()) { | 83 | if (!isTerminated()) { |
87 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); | 84 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); |
88 | if(cursorRelation > 0 || cursor2.isTerminated()) { | 85 | if (cursorRelation > 0 || cursor2.isTerminated()) { |
89 | this.key = cursor1.getKey(); | 86 | this.key = cursor1.getKey(); |
90 | this.fromValue = cursor1.getValue(); | 87 | this.fromValue = cursor1.getValue(); |
91 | this.toValue = defaultValue; | 88 | this.toValue = defaultValue; |
92 | } else if(cursorRelation < 0 || cursor1.isTerminated()){ | 89 | } else if (cursorRelation < 0 || cursor1.isTerminated()) { |
93 | this.key = cursor2.getKey(); | 90 | this.key = cursor2.getKey(); |
94 | this.fromValue = defaultValue; | 91 | this.fromValue = defaultValue; |
95 | this.toValue = cursor1.getValue(); | 92 | this.toValue = cursor1.getValue(); |
96 | } else { | 93 | } else { |
97 | // cursor1 = cursor2 | 94 | // cursor1 = cursor2 |
98 | if(cursor1.getKey().equals(cursor2.getKey())) { | 95 | if (cursor1.getKey().equals(cursor2.getKey())) { |
99 | this.key = cursor1.getKey(); | 96 | this.key = cursor1.getKey(); |
100 | this.fromValue = cursor1.getValue(); | 97 | this.fromValue = cursor1.getValue(); |
101 | this.toValue = defaultValue; | 98 | this.toValue = defaultValue; |
102 | } else { | 99 | } else { |
103 | resolveHashClash1(); | 100 | resolveHashClashWithFirstEntry(); |
104 | } | 101 | } |
105 | } | 102 | } |
106 | } | 103 | } |
107 | } | 104 | } |
108 | protected void resolveHashClash1() { | 105 | |
106 | protected void resolveHashClashWithFirstEntry() { | ||
109 | int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); | 107 | int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); |
110 | if(compareResult<0) { | 108 | if (compareResult < 0) { |
111 | this.hashClash = 2; | 109 | this.hashClash = HashClash.STUCK_CURSOR_2; |
112 | this.cursorRelation = 0; | 110 | this.cursorRelation = 0; |
113 | this.key = cursor1.key; | 111 | this.key = cursor1.key; |
114 | this.fromValue = cursor1.value; | 112 | this.fromValue = cursor1.value; |
115 | this.toValue = defaultValue; | 113 | this.toValue = defaultValue; |
116 | } else if(compareResult>0) { | 114 | } else if (compareResult > 0) { |
117 | this.hashClash = 1; | 115 | this.hashClash = HashClash.STUCK_CURSOR_1; |
118 | this.cursorRelation = 0; | 116 | this.cursorRelation = 0; |
119 | this.key = cursor2.key; | 117 | this.key = cursor2.key; |
120 | this.fromValue = defaultValue; | 118 | this.fromValue = defaultValue; |
@@ -123,40 +121,47 @@ public class MapDiffCursor<K,V> implements DiffCursor<K, V>, Cursor<K,V>{ | |||
123 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | 121 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); |
124 | } | 122 | } |
125 | } | 123 | } |
124 | |||
126 | protected boolean isInHashClash() { | 125 | protected boolean isInHashClash() { |
127 | return this.hashClash != 0; | 126 | return this.hashClash != HashClash.NONE; |
128 | } | 127 | } |
129 | protected void resolveHashClash2() { | 128 | |
130 | if(hashClash == 1) { | 129 | protected void resolveHashClashWithSecondEntry() { |
131 | this.hashClash = 0; | 130 | switch (this.hashClash) { |
131 | case STUCK_CURSOR_1: | ||
132 | this.hashClash = HashClash.NONE; | ||
132 | this.cursorRelation = 0; | 133 | this.cursorRelation = 0; |
133 | this.key = cursor1.key; | 134 | this.key = cursor1.key; |
134 | this.fromValue = cursor1.value; | 135 | this.fromValue = cursor1.value; |
135 | this.toValue = defaultValue; | 136 | this.toValue = defaultValue; |
136 | } else if(hashClash == 2) { | 137 | break; |
137 | this.hashClash = 0; | 138 | case STUCK_CURSOR_2: |
139 | this.hashClash = HashClash.NONE; | ||
138 | this.cursorRelation = 0; | 140 | this.cursorRelation = 0; |
139 | this.key = cursor2.key; | 141 | this.key = cursor2.key; |
140 | this.fromValue = defaultValue; | 142 | this.fromValue = defaultValue; |
141 | this.toValue = cursor2.value; | 143 | this.toValue = cursor2.value; |
142 | } else throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | 144 | break; |
145 | default: | ||
146 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | ||
147 | } | ||
143 | } | 148 | } |
144 | 149 | ||
145 | |||
146 | protected boolean sameValues() { | 150 | protected boolean sameValues() { |
147 | if(this.fromValue == null) { | 151 | if (this.fromValue == null) { |
148 | return this.toValue == null; | 152 | return this.toValue == null; |
149 | } else { | 153 | } else { |
150 | return this.fromValue.equals(this.toValue); | 154 | return this.fromValue.equals(this.toValue); |
151 | } | 155 | } |
152 | } | 156 | } |
157 | |||
153 | protected boolean moveOne() { | 158 | protected boolean moveOne() { |
154 | if(isTerminated()) { | 159 | if (isTerminated()) { |
155 | return false; | 160 | return false; |
156 | } | 161 | } |
157 | if(this.cursorRelation > 0 || cursor2.isTerminated()) { | 162 | if (this.cursorRelation > 0 || cursor2.isTerminated()) { |
158 | return cursor1.move(); | 163 | return cursor1.move(); |
159 | } else if(this.cursorRelation < 0 || cursor1.isTerminated()) { | 164 | } else if (this.cursorRelation < 0 || cursor1.isTerminated()) { |
160 | return cursor2.move(); | 165 | return cursor2.move(); |
161 | } else { | 166 | } else { |
162 | boolean moved1 = cursor1.move(); | 167 | boolean moved1 = cursor1.move(); |
@@ -164,8 +169,9 @@ public class MapDiffCursor<K,V> implements DiffCursor<K, V>, Cursor<K,V>{ | |||
164 | return moved1 && moved2; | 169 | return moved1 && moved2; |
165 | } | 170 | } |
166 | } | 171 | } |
172 | |||
167 | private boolean skipNode() { | 173 | private boolean skipNode() { |
168 | if(isTerminated()) { | 174 | if (isTerminated()) { |
169 | throw new IllegalStateException("DiffCursor tries to skip when terminated!"); | 175 | throw new IllegalStateException("DiffCursor tries to skip when terminated!"); |
170 | } | 176 | } |
171 | boolean update1 = cursor1.skipCurrentNode(); | 177 | boolean update1 = cursor1.skipCurrentNode(); |
@@ -173,42 +179,43 @@ public class MapDiffCursor<K,V> implements DiffCursor<K, V>, Cursor<K,V>{ | |||
173 | updateState(); | 179 | updateState(); |
174 | return update1 && update2; | 180 | return update1 && update2; |
175 | } | 181 | } |
176 | 182 | ||
177 | protected boolean moveToConsistentState() { | 183 | protected boolean moveToConsistentState() { |
178 | if(!isTerminated()) { | 184 | if (!isTerminated()) { |
179 | boolean changed; | 185 | boolean changed; |
180 | boolean lastResult = true; | 186 | boolean lastResult = true; |
181 | do { | 187 | do { |
182 | changed = false; | 188 | changed = false; |
183 | if(MapCursor.sameSubnode(cursor1, cursor2)) { | 189 | if (MapCursor.sameSubnode(cursor1, cursor2)) { |
184 | lastResult = skipNode(); | 190 | lastResult = skipNode(); |
185 | changed = true; | 191 | changed = true; |
186 | } | 192 | } |
187 | if(sameValues()) { | 193 | if (sameValues()) { |
188 | lastResult = moveOne(); | 194 | lastResult = moveOne(); |
189 | changed = true; | 195 | changed = true; |
190 | } | 196 | } |
191 | updateState(); | 197 | updateState(); |
192 | } while(changed && !isTerminated()); | 198 | } while (changed && !isTerminated()); |
193 | return lastResult; | 199 | return lastResult; |
194 | } else { | 200 | } else { |
195 | return false; | 201 | return false; |
196 | } | 202 | } |
197 | } | 203 | } |
198 | 204 | ||
199 | public boolean move() { | 205 | public boolean move() { |
200 | if(!isTerminated()) { | 206 | if (!isTerminated()) { |
201 | if(isInHashClash()) { | 207 | if (isInHashClash()) { |
202 | this.resolveHashClash2(); | 208 | this.resolveHashClashWithSecondEntry(); |
203 | return true; | 209 | return true; |
204 | } else { | 210 | } else { |
205 | if(moveOne()) { | 211 | if (moveOne()) { |
206 | return moveToConsistentState(); | 212 | return moveToConsistentState(); |
207 | } else { | 213 | } else { |
208 | return false; | 214 | return false; |
209 | } | 215 | } |
210 | } | 216 | } |
211 | 217 | ||
212 | } else return false; | 218 | } else |
219 | return false; | ||
213 | } | 220 | } |
214 | } | 221 | } |