diff options
Diffstat (limited to 'model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java')
-rw-r--r-- | model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java | 208 |
1 files changed, 208 insertions, 0 deletions
diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java new file mode 100644 index 00000000..8d7cda14 --- /dev/null +++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapDiffCursor.java | |||
@@ -0,0 +1,208 @@ | |||
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<KEY,VALUE> implements DiffCursor<KEY, VALUE>, Cursor<KEY,VALUE>{ | ||
18 | /** | ||
19 | * Default value representing missing elements. | ||
20 | */ | ||
21 | private VALUE defaultValue; | ||
22 | private MapCursor<KEY,VALUE> cursor1; | ||
23 | private MapCursor<KEY,VALUE> cursor2; | ||
24 | private ContinousHashProvider<? super KEY> hashProvider; | ||
25 | |||
26 | // Values | ||
27 | private KEY key; | ||
28 | private VALUE fromValue; | ||
29 | private VALUE 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 KEY> hashProvider, VALUE defaultValue, Cursor<KEY, VALUE> cursor1, Cursor<KEY, VALUE> cursor2) { | ||
48 | super(); | ||
49 | this.hashProvider = hashProvider; | ||
50 | this.defaultValue = defaultValue; | ||
51 | this.cursor1 = (MapCursor<KEY, VALUE>) cursor1; | ||
52 | this.cursor2 = (MapCursor<KEY, VALUE>) cursor2; | ||
53 | } | ||
54 | |||
55 | public KEY getKey() { | ||
56 | return key; | ||
57 | } | ||
58 | public VALUE getFromValue() { | ||
59 | return fromValue; | ||
60 | } | ||
61 | public VALUE getToValue() { | ||
62 | return toValue; | ||
63 | } | ||
64 | @Override | ||
65 | public VALUE getValue() { | ||
66 | return getToValue(); | ||
67 | } | ||
68 | public boolean isTerminated() { | ||
69 | return cursor1.isTerminated() && cursor2.isTerminated(); | ||
70 | } | ||
71 | @Override | ||
72 | public boolean isDirty() { | ||
73 | return this.cursor1.isDirty() || this.cursor2.isDirty(); | ||
74 | } | ||
75 | @Override | ||
76 | public List<VersionedMap<KEY, VALUE>> getDependingMaps() { | ||
77 | return Stream.concat( | ||
78 | cursor1.getDependingMaps().stream(), | ||
79 | cursor2.getDependingMaps().stream() | ||
80 | ).collect(Collectors.toList()); | ||
81 | } | ||
82 | |||
83 | protected void updateState() { | ||
84 | if(!isTerminated()) { | ||
85 | this.cursorRelation = MapCursor.compare(cursor1, cursor2); | ||
86 | if(cursorRelation > 0 || cursor2.isTerminated()) { | ||
87 | this.key = cursor1.getKey(); | ||
88 | this.fromValue = cursor1.getValue(); | ||
89 | this.toValue = defaultValue; | ||
90 | } else if(cursorRelation < 0 || cursor1.isTerminated()){ | ||
91 | this.key = cursor2.getKey(); | ||
92 | this.fromValue = defaultValue; | ||
93 | this.toValue = cursor1.getValue(); | ||
94 | } else { | ||
95 | // cursor1 = cursor2 | ||
96 | if(cursor1.getKey().equals(cursor2.getKey())) { | ||
97 | this.key = cursor1.getKey(); | ||
98 | this.fromValue = cursor1.getValue(); | ||
99 | this.toValue = defaultValue; | ||
100 | } else { | ||
101 | resolveHashClash1(); | ||
102 | } | ||
103 | } | ||
104 | } | ||
105 | } | ||
106 | protected void resolveHashClash1() { | ||
107 | int compareResult = this.hashProvider.compare(cursor1.key, cursor2.key); | ||
108 | if(compareResult<0) { | ||
109 | this.hashClash = 2; | ||
110 | this.cursorRelation = 0; | ||
111 | this.key = cursor1.key; | ||
112 | this.fromValue = cursor1.value; | ||
113 | this.toValue = defaultValue; | ||
114 | } else if(compareResult>0) { | ||
115 | this.hashClash = 1; | ||
116 | this.cursorRelation = 0; | ||
117 | this.key = cursor2.key; | ||
118 | this.fromValue = defaultValue; | ||
119 | this.toValue = cursor2.value; | ||
120 | } else { | ||
121 | throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | ||
122 | } | ||
123 | } | ||
124 | protected boolean isInHashClash() { | ||
125 | return this.hashClash != 0; | ||
126 | } | ||
127 | protected void resolveHashClash2() { | ||
128 | if(hashClash == 1) { | ||
129 | this.hashClash = 0; | ||
130 | this.cursorRelation = 0; | ||
131 | this.key = cursor1.key; | ||
132 | this.fromValue = cursor1.value; | ||
133 | this.toValue = defaultValue; | ||
134 | } else if(hashClash == 2) { | ||
135 | this.hashClash = 0; | ||
136 | this.cursorRelation = 0; | ||
137 | this.key = cursor2.key; | ||
138 | this.fromValue = defaultValue; | ||
139 | this.toValue = cursor2.value; | ||
140 | } else throw new IllegalArgumentException("Inconsistent compare result for diffcursor"); | ||
141 | } | ||
142 | |||
143 | |||
144 | protected boolean sameValues() { | ||
145 | return this.fromValue == this.toValue; | ||
146 | } | ||
147 | protected boolean moveOne() { | ||
148 | if(isTerminated()) { | ||
149 | return false; | ||
150 | } | ||
151 | if(this.cursorRelation > 0 || cursor2.isTerminated()) { | ||
152 | return cursor1.move(); | ||
153 | } else if(this.cursorRelation < 0 || cursor1.isTerminated()) { | ||
154 | return cursor2.move(); | ||
155 | } else { | ||
156 | boolean moved1 = cursor1.move(); | ||
157 | boolean moved2 = cursor2.move(); | ||
158 | return moved1 && moved2; | ||
159 | } | ||
160 | } | ||
161 | private boolean skipNode() { | ||
162 | if(isTerminated()) { | ||
163 | throw new IllegalStateException("DiffCursor tries to skip when terminated!"); | ||
164 | } | ||
165 | boolean update1 = cursor1.skipCurrentNode(); | ||
166 | boolean update2 = cursor2.skipCurrentNode(); | ||
167 | updateState(); | ||
168 | return update1 && update2; | ||
169 | } | ||
170 | |||
171 | protected boolean moveToConsistentState() { | ||
172 | if(!isTerminated()) { | ||
173 | boolean changed; | ||
174 | boolean lastResult = true; | ||
175 | do { | ||
176 | changed = false; | ||
177 | if(MapCursor.sameSubnode(cursor1, cursor2)) { | ||
178 | lastResult = skipNode(); | ||
179 | changed = true; | ||
180 | } | ||
181 | if(sameValues()) { | ||
182 | lastResult = moveOne(); | ||
183 | changed = true; | ||
184 | } | ||
185 | updateState(); | ||
186 | } while(changed && !isTerminated()); | ||
187 | return lastResult; | ||
188 | } else { | ||
189 | return false; | ||
190 | } | ||
191 | } | ||
192 | |||
193 | public boolean move() { | ||
194 | if(!isTerminated()) { | ||
195 | if(isInHashClash()) { | ||
196 | this.resolveHashClash2(); | ||
197 | return true; | ||
198 | } else { | ||
199 | if(moveOne()) { | ||
200 | return moveToConsistentState(); | ||
201 | } else { | ||
202 | return false; | ||
203 | } | ||
204 | } | ||
205 | |||
206 | } else return false; | ||
207 | } | ||
208 | } | ||