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