1 | // Copyright 2012 Georg-August-Universität Göttingen, Germany |
---|
2 | // |
---|
3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
---|
4 | // you may not use this file except in compliance with the License. |
---|
5 | // You may obtain a copy of the License at |
---|
6 | // |
---|
7 | // http://www.apache.org/licenses/LICENSE-2.0 |
---|
8 | // |
---|
9 | // Unless required by applicable law or agreed to in writing, software |
---|
10 | // distributed under the License is distributed on an "AS IS" BASIS, |
---|
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
---|
12 | // See the License for the specific language governing permissions and |
---|
13 | // limitations under the License. |
---|
14 | |
---|
15 | package de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils; |
---|
16 | |
---|
17 | import java.io.PrintStream; |
---|
18 | import java.util.HashSet; |
---|
19 | import java.util.LinkedList; |
---|
20 | import java.util.List; |
---|
21 | import java.util.Set; |
---|
22 | |
---|
23 | import de.ugoe.cs.autoquest.eventcore.gui.Scroll; |
---|
24 | import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator; |
---|
25 | import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskTraversingVisitor; |
---|
26 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask; |
---|
27 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance; |
---|
28 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; |
---|
29 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance; |
---|
30 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IMarkingTemporalRelationship; |
---|
31 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptionalInstance; |
---|
32 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection; |
---|
33 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance; |
---|
34 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance; |
---|
35 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IStructuringTemporalRelationship; |
---|
36 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask; |
---|
37 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance; |
---|
38 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITemporalRelationship; |
---|
39 | import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskPath; |
---|
40 | import difflib.Chunk; |
---|
41 | import difflib.Delta; |
---|
42 | import difflib.Patch; |
---|
43 | |
---|
44 | /** |
---|
45 | * <p> |
---|
46 | * This class represents a pair of tasks and their corresponding similarity level, respectively, |
---|
47 | * their diff level. In addition, it contains the task traversal, i.e., the flattened variants |
---|
48 | * of the compared tasks. It provides static methods to compare two tasks and get an object of this |
---|
49 | * class as result. Furthermore, it allows to adapt the contained traversals so that unmergable |
---|
50 | * subtasks are not traversed. |
---|
51 | * </p> |
---|
52 | * |
---|
53 | * @author Patrick Harms |
---|
54 | */ |
---|
55 | public class SimilarTasks { |
---|
56 | |
---|
57 | /** |
---|
58 | * default indicator for unequal tasks |
---|
59 | */ |
---|
60 | public static final SimilarTasks UNEQUAL_TASKS = new SimilarTasks(null, null, null); |
---|
61 | |
---|
62 | /** |
---|
63 | * result of the string like comparison of both task traversals |
---|
64 | */ |
---|
65 | private Patch patch; |
---|
66 | |
---|
67 | /** |
---|
68 | * the diff level resulting from the comparison |
---|
69 | */ |
---|
70 | private int diffLevel; |
---|
71 | |
---|
72 | /** |
---|
73 | * the first compared task |
---|
74 | */ |
---|
75 | private ITask leftHandSide; |
---|
76 | |
---|
77 | /** |
---|
78 | * the second compare task |
---|
79 | */ |
---|
80 | private ITask rightHandSide; |
---|
81 | |
---|
82 | /** |
---|
83 | * the traversal of the first task |
---|
84 | */ |
---|
85 | private TaskTraversal leftHandSideTraversal; |
---|
86 | |
---|
87 | /** |
---|
88 | * the traversal of the second task |
---|
89 | */ |
---|
90 | private TaskTraversal rightHandSideTraversal; |
---|
91 | |
---|
92 | /** |
---|
93 | * initialized a pair of tasks and calculates its diff level |
---|
94 | */ |
---|
95 | public SimilarTasks(Patch patch, |
---|
96 | TaskTraversal traversal1, |
---|
97 | TaskTraversal traversal2) |
---|
98 | { |
---|
99 | if (traversal1 != null) { |
---|
100 | this.leftHandSide = traversal1.getTask(); |
---|
101 | } |
---|
102 | |
---|
103 | this.leftHandSideTraversal = traversal1; |
---|
104 | |
---|
105 | if (traversal2 != null) { |
---|
106 | this.rightHandSide = traversal2.getTask(); |
---|
107 | } |
---|
108 | |
---|
109 | this.rightHandSideTraversal = traversal2; |
---|
110 | |
---|
111 | if (patch != null) { |
---|
112 | this.patch = patch; |
---|
113 | this.diffLevel = getDiffLevel(patch, traversal1, traversal2); |
---|
114 | } |
---|
115 | else { |
---|
116 | this.diffLevel = 100; |
---|
117 | } |
---|
118 | } |
---|
119 | |
---|
120 | /** |
---|
121 | * static convenience method to compare two tasks |
---|
122 | */ |
---|
123 | public static SimilarTasks compareTasks(ITask task1, |
---|
124 | ITask task2, |
---|
125 | TaskComparator comparator) |
---|
126 | { |
---|
127 | return compareTasks(task1, task2, comparator, null); |
---|
128 | } |
---|
129 | |
---|
130 | /** |
---|
131 | * static convenience method to compare two tasks but ignoring a given set of subtasks when |
---|
132 | * creating the traversals. |
---|
133 | */ |
---|
134 | public static SimilarTasks compareTasks(ITask task1, |
---|
135 | ITask task2, |
---|
136 | TaskComparator comparator, |
---|
137 | List<TaskPath> pathsNotToTraverse) |
---|
138 | { |
---|
139 | TaskTraversal traversal1 = TaskTraversal.getTraversal(task1, pathsNotToTraverse); |
---|
140 | TaskTraversal traversal2 = TaskTraversal.getTraversal(task2, pathsNotToTraverse); |
---|
141 | |
---|
142 | if ((traversal1.size() <= 0) || (traversal2.size() <= 0)) { |
---|
143 | return null; |
---|
144 | } |
---|
145 | |
---|
146 | return compareTraversals(traversal1, traversal2, comparator); |
---|
147 | } |
---|
148 | |
---|
149 | /** |
---|
150 | * <p> |
---|
151 | * TODO: comment |
---|
152 | * </p> |
---|
153 | * |
---|
154 | * @param traversal1 |
---|
155 | * @param traversal2 |
---|
156 | * @param comparator |
---|
157 | * @return |
---|
158 | */ |
---|
159 | public static SimilarTasks compareTraversals(TaskTraversal traversal1, |
---|
160 | TaskTraversal traversal2, |
---|
161 | TaskComparator comparator) |
---|
162 | { |
---|
163 | Patch patch = new TaskTraversalMyersDiff(comparator).getDiff(traversal1, traversal2); |
---|
164 | |
---|
165 | SimilarTasks result = new SimilarTasks(patch, traversal1, traversal2); |
---|
166 | |
---|
167 | return result; |
---|
168 | } |
---|
169 | |
---|
170 | |
---|
171 | /** |
---|
172 | * This method checks for mergability of the provided similar tasks and if this is not given, |
---|
173 | * it reduces the traversals by ignoring interleaving iterations and other situations until |
---|
174 | * the remaining traversals can be the basis of a merge. |
---|
175 | */ |
---|
176 | public static SimilarTasks getMergableLevelOfSimilarity(SimilarTasks source, |
---|
177 | TaskComparator comparator) |
---|
178 | { |
---|
179 | SimilarTasks similarTasks = source; |
---|
180 | |
---|
181 | List<TaskPath> pathsToIgnore = similarTasks.getPathsToIgnore(); |
---|
182 | |
---|
183 | int prevPathsToIgnoreCount = 0; |
---|
184 | |
---|
185 | do { |
---|
186 | prevPathsToIgnoreCount = pathsToIgnore.size(); |
---|
187 | |
---|
188 | similarTasks = compareTasks |
---|
189 | (similarTasks.getLeftHandSide(), similarTasks.getRightHandSide(), |
---|
190 | comparator, pathsToIgnore); |
---|
191 | |
---|
192 | // similarTasks.dump(System.out); |
---|
193 | |
---|
194 | List<TaskPath> furtherPathsToIgnore = similarTasks.getPathsToIgnore(); |
---|
195 | |
---|
196 | // System.out.println("further paths to ignore:"); |
---|
197 | // for (TaskPath path : furtherPathsToIgnore) { |
---|
198 | // System.out.println(" " + path); |
---|
199 | // } |
---|
200 | |
---|
201 | for (TaskPath pathToAdd : furtherPathsToIgnore) { |
---|
202 | boolean found = false; |
---|
203 | for (TaskPath pathToIgnore : pathsToIgnore) { |
---|
204 | if (pathToAdd.equals(pathToIgnore)) { |
---|
205 | found = true; |
---|
206 | break; |
---|
207 | } |
---|
208 | } |
---|
209 | |
---|
210 | if (!found) { |
---|
211 | pathsToIgnore.add(pathToAdd); |
---|
212 | } |
---|
213 | } |
---|
214 | } |
---|
215 | while (pathsToIgnore.size() > prevPathsToIgnoreCount); |
---|
216 | |
---|
217 | if (similarTasks.isStillWellAligned()) { |
---|
218 | return similarTasks; |
---|
219 | } |
---|
220 | else { |
---|
221 | // this may happen, if due to interleaving iterations the similarities of the task |
---|
222 | // move and the diff algorithm does not align them anymore as optimal as possible |
---|
223 | // because some similarities were lost due to not comparing all paths anymore. |
---|
224 | return null; |
---|
225 | } |
---|
226 | } |
---|
227 | |
---|
228 | /** |
---|
229 | * checks if the delta between the two traversals is at their border or not |
---|
230 | */ |
---|
231 | public boolean isInBetweenDifference() { |
---|
232 | List<Delta> deltas = patch.getDeltas(); |
---|
233 | |
---|
234 | for (Delta delta : deltas) { |
---|
235 | int origPos = delta.getOriginal().getPosition(); |
---|
236 | int origSize = delta.getOriginal().size(); |
---|
237 | int revPos = delta.getRevised().getPosition(); |
---|
238 | int revSize = delta.getRevised().size(); |
---|
239 | |
---|
240 | if ((origPos <= 0) || (revPos <= 0)) { |
---|
241 | // optional must not be the beginning of the task |
---|
242 | return false; |
---|
243 | } |
---|
244 | else if ((delta.getType() == Delta.TYPE.INSERT) && |
---|
245 | ((revPos + revSize) >= rightHandSideTraversal.size())) |
---|
246 | { |
---|
247 | // optional must not be the end of the right hand side task |
---|
248 | return false; |
---|
249 | } |
---|
250 | else if ((delta.getType() == Delta.TYPE.DELETE) && |
---|
251 | ((origPos + origSize) >= leftHandSideTraversal.size())) |
---|
252 | { |
---|
253 | // optional must not be the end of the left hand side task |
---|
254 | return false; |
---|
255 | } |
---|
256 | else if ((delta.getType() == Delta.TYPE.CHANGE) && |
---|
257 | (((revPos + revSize) >= rightHandSideTraversal.size()) || |
---|
258 | ((origPos + origSize) >= leftHandSideTraversal.size()))) |
---|
259 | { |
---|
260 | // selection must not be the end of the left hand or right hand side task |
---|
261 | return false; |
---|
262 | } |
---|
263 | } |
---|
264 | |
---|
265 | return deltas.size() > 0; |
---|
266 | } |
---|
267 | |
---|
268 | /** |
---|
269 | * <p> |
---|
270 | * TODO: comment |
---|
271 | * </p> |
---|
272 | * |
---|
273 | * @return |
---|
274 | */ |
---|
275 | public boolean isStillWellAligned() { |
---|
276 | if (isInBetweenDifference()) { |
---|
277 | return true; |
---|
278 | } |
---|
279 | else { |
---|
280 | for (Delta delta : patch.getDeltas()) { |
---|
281 | if (delta.getType() == Delta.TYPE.INSERT) { |
---|
282 | if ((delta.getOriginal().getPosition() == 0) || |
---|
283 | (delta.getOriginal().getPosition() == leftHandSideTraversal.size())) |
---|
284 | { |
---|
285 | return false; |
---|
286 | } |
---|
287 | } |
---|
288 | else if (delta.getType() == Delta.TYPE.DELETE) { |
---|
289 | if ((delta.getRevised().getPosition() == 0) || |
---|
290 | (delta.getRevised().getPosition() == rightHandSideTraversal.size())) |
---|
291 | { |
---|
292 | return false; |
---|
293 | } |
---|
294 | } |
---|
295 | } |
---|
296 | } |
---|
297 | |
---|
298 | return true; |
---|
299 | } |
---|
300 | |
---|
301 | /** |
---|
302 | * @return the patch |
---|
303 | */ |
---|
304 | public Patch getPatch() { |
---|
305 | return patch; |
---|
306 | } |
---|
307 | |
---|
308 | /** |
---|
309 | * @return the diff level |
---|
310 | */ |
---|
311 | public int getDiffLevel() { |
---|
312 | return diffLevel; |
---|
313 | } |
---|
314 | |
---|
315 | /** |
---|
316 | * @return the first task of the comparison |
---|
317 | */ |
---|
318 | public ITask getLeftHandSide() { |
---|
319 | return leftHandSide; |
---|
320 | } |
---|
321 | |
---|
322 | /** |
---|
323 | * @return the second task of the comparison |
---|
324 | */ |
---|
325 | public ITask getRightHandSide() { |
---|
326 | return rightHandSide; |
---|
327 | } |
---|
328 | |
---|
329 | /** |
---|
330 | * @return the traversal of the first task of the comparison |
---|
331 | */ |
---|
332 | public TaskTraversal getLeftHandSideTraversal() { |
---|
333 | return leftHandSideTraversal; |
---|
334 | } |
---|
335 | |
---|
336 | /** |
---|
337 | * @return the traversal of the second task of the comparison |
---|
338 | */ |
---|
339 | public TaskTraversal getRightHandSideTraversal() { |
---|
340 | return rightHandSideTraversal; |
---|
341 | } |
---|
342 | |
---|
343 | /** |
---|
344 | * returns paths to subtasks, that can not be merged. |
---|
345 | */ |
---|
346 | public List<TaskPath> getPathsToIgnore() { |
---|
347 | List<TaskPath> result = new LinkedList<TaskPath>(); |
---|
348 | |
---|
349 | if ((patch.getDeltas().size() == 1) && |
---|
350 | (patch.getDeltas().get(0).getType() == Delta.TYPE.CHANGE)) |
---|
351 | { |
---|
352 | // if it is a full change, then the parent of either side must be fully ignored |
---|
353 | Delta singleChangeDelta = patch.getDeltas().get(0); |
---|
354 | |
---|
355 | if ((singleChangeDelta.getOriginal().getPosition() == 0) && |
---|
356 | (singleChangeDelta.getOriginal().size() == leftHandSideTraversal.size())) |
---|
357 | { |
---|
358 | TaskPath path = new TaskPath(); |
---|
359 | path.add(leftHandSide, 0); |
---|
360 | result.add(path); |
---|
361 | } |
---|
362 | |
---|
363 | if ((singleChangeDelta.getRevised().getPosition() == 0) && |
---|
364 | (singleChangeDelta.getRevised().size() == rightHandSideTraversal.size())) |
---|
365 | { |
---|
366 | TaskPath path = new TaskPath(); |
---|
367 | path.add(rightHandSide, 0); |
---|
368 | result.add(path); |
---|
369 | } |
---|
370 | } |
---|
371 | |
---|
372 | if (result.size() < 2) { |
---|
373 | // if we do not already ignore both root tasks, check for overlapping |
---|
374 | // iterations that are executed multiple times for the tasks to be merged as they have |
---|
375 | // to be ignored |
---|
376 | result.addAll(getConflictingIterations()); |
---|
377 | |
---|
378 | // then check for tasks fully inside delta, which can be preserved |
---|
379 | for (Delta delta : patch.getDeltas()) { |
---|
380 | getNotFullyInterleavingIteration(delta, result); |
---|
381 | getPathsToParentTasksFullyInsideDelta(delta, result); |
---|
382 | } |
---|
383 | |
---|
384 | // check for any parent optional that are at least once empty in instances of the |
---|
385 | // tasks to be merged and that can, hence, not be flattened |
---|
386 | getUnexecutedParentOptionals(leftHandSide, result); |
---|
387 | getUnexecutedParentOptionals(rightHandSide, result); |
---|
388 | |
---|
389 | // check if there are common subtasks on both sides that lie outside any delta and |
---|
390 | // that hence should be ignored (especially when performing flattening of task |
---|
391 | // instances later with the goal to preserve as many subtasks and respective instances) |
---|
392 | int deltaIndex = 0; |
---|
393 | int leftTraversalIndex = 0; |
---|
394 | int rightTraversalIndex = 0; |
---|
395 | Set<ITask> commonInvolvedTasks = getCommonInvolvedTasks(leftHandSide, rightHandSide); |
---|
396 | |
---|
397 | do { |
---|
398 | Delta delta = deltaIndex < patch.getDeltas().size() |
---|
399 | ? patch.getDeltas().get(deltaIndex++) : null; |
---|
400 | |
---|
401 | int nextLeftTraversalIndex = leftHandSideTraversal.size(); |
---|
402 | int nextRightTraversalIndex = rightHandSideTraversal.size(); |
---|
403 | |
---|
404 | if (delta != null) { |
---|
405 | nextLeftTraversalIndex = delta.getOriginal().getPosition() + 1; |
---|
406 | nextRightTraversalIndex = delta.getRevised().getPosition() + 1; |
---|
407 | |
---|
408 | if (delta.getType() == Delta.TYPE.INSERT) { |
---|
409 | nextLeftTraversalIndex--; |
---|
410 | } |
---|
411 | else if (delta.getType() == Delta.TYPE.DELETE) { |
---|
412 | nextRightTraversalIndex--; |
---|
413 | } |
---|
414 | } |
---|
415 | |
---|
416 | TaskPath[] leftSubTraversal = |
---|
417 | leftHandSideTraversal.subList(leftTraversalIndex, nextLeftTraversalIndex); |
---|
418 | |
---|
419 | for (TaskPath path : leftSubTraversal) { |
---|
420 | for (int i = 0; i < path.size(); i++) { |
---|
421 | if (commonInvolvedTasks.contains(path.getTask(i))) { |
---|
422 | // found a candidate. Check if the candidate does not span more than |
---|
423 | // the sub traversal |
---|
424 | TaskPath parentPath = path.subPath(0, i + 1); |
---|
425 | int[] indexes = leftHandSideTraversal.getIndexesRootedBy(parentPath); |
---|
426 | |
---|
427 | if ((indexes[0] >= leftTraversalIndex) && |
---|
428 | (indexes[1] < nextLeftTraversalIndex)) |
---|
429 | { |
---|
430 | result.add(parentPath); |
---|
431 | break; // breaks only the path but the rest of the traversal is |
---|
432 | // checked too |
---|
433 | } |
---|
434 | } |
---|
435 | } |
---|
436 | } |
---|
437 | |
---|
438 | TaskPath[] rightSubTraversal = |
---|
439 | rightHandSideTraversal.subList(rightTraversalIndex, nextRightTraversalIndex); |
---|
440 | |
---|
441 | for (TaskPath path : rightSubTraversal) { |
---|
442 | for (int i = 0; i < path.size(); i++) { |
---|
443 | if (commonInvolvedTasks.contains(path.getTask(i))) { |
---|
444 | // found a candidate. Check if the candidate does not span more than |
---|
445 | // the sub traversal |
---|
446 | TaskPath parentPath = path.subPath(0, i + 1); |
---|
447 | int[] indexes = rightHandSideTraversal.getIndexesRootedBy(parentPath); |
---|
448 | |
---|
449 | if ((indexes[0] >= rightTraversalIndex) && |
---|
450 | (indexes[1] < nextRightTraversalIndex)) |
---|
451 | { |
---|
452 | result.add(parentPath); |
---|
453 | break; // breaks only the path but the rest of the traversal is |
---|
454 | // checked too |
---|
455 | } |
---|
456 | } |
---|
457 | } |
---|
458 | } |
---|
459 | |
---|
460 | leftTraversalIndex = nextLeftTraversalIndex; |
---|
461 | rightTraversalIndex = nextRightTraversalIndex; |
---|
462 | } |
---|
463 | while (leftTraversalIndex < leftHandSideTraversal.size()); |
---|
464 | |
---|
465 | } |
---|
466 | |
---|
467 | return result; |
---|
468 | } |
---|
469 | |
---|
470 | /** |
---|
471 | * |
---|
472 | */ |
---|
473 | public void dump(PrintStream out) { |
---|
474 | out.println(); |
---|
475 | out.print("similar tasks: left "); |
---|
476 | out.print(leftHandSide); |
---|
477 | out.print(" ("); |
---|
478 | out.print(leftHandSide.getInstances().size()); |
---|
479 | out.print(" instances), right "); |
---|
480 | out.print(rightHandSide); |
---|
481 | out.print(" ("); |
---|
482 | out.print(rightHandSide.getInstances().size()); |
---|
483 | out.print(" instances), diff level "); |
---|
484 | out.println(diffLevel); |
---|
485 | |
---|
486 | out.println("left traversal"); |
---|
487 | for (TaskPath path : leftHandSideTraversal.getTraversalPaths()) { |
---|
488 | out.println(path); |
---|
489 | } |
---|
490 | |
---|
491 | out.println("right traversal"); |
---|
492 | for (TaskPath path : rightHandSideTraversal.getTraversalPaths()) { |
---|
493 | out.println(path); |
---|
494 | } |
---|
495 | |
---|
496 | if (patch != null) { |
---|
497 | out.println("deltas:"); |
---|
498 | for (Delta delta : patch.getDeltas()) { |
---|
499 | out.println(delta); |
---|
500 | } |
---|
501 | } |
---|
502 | |
---|
503 | List<String> linesLeft = new LinkedList<String>(); |
---|
504 | TaskPath path = new TaskPath(); |
---|
505 | path.add(leftHandSide, 0); |
---|
506 | dumpToLineList(path, leftHandSideTraversal, linesLeft); |
---|
507 | path.removeLast(); |
---|
508 | |
---|
509 | List<String> linesRight = new LinkedList<String>(); |
---|
510 | path.add(rightHandSide, 0); |
---|
511 | dumpToLineList(path, rightHandSideTraversal, linesRight); |
---|
512 | |
---|
513 | |
---|
514 | /*System.out.println("\n#################################################"); |
---|
515 | for (int j = 0; ((j < linesLeft.size()) || (j < linesRight.size())); j++) { |
---|
516 | String left = j < linesLeft.size() ? linesLeft.get(j) : ""; |
---|
517 | String right = j < linesRight.size() ? linesRight.get(j) : ""; |
---|
518 | |
---|
519 | StringBuffer line = new StringBuffer(); |
---|
520 | line.append(j); |
---|
521 | line.append(":\t"); |
---|
522 | line.append(left); |
---|
523 | |
---|
524 | for (int k = line.length(); k < 60; k++) { |
---|
525 | line.append(' '); |
---|
526 | } |
---|
527 | |
---|
528 | line.append(right); |
---|
529 | System.out.println(line); |
---|
530 | }*/ |
---|
531 | |
---|
532 | // change lists to have the same length depending on the changes |
---|
533 | int lineIndexLeft = 0; |
---|
534 | int lineIndexRight = 0; |
---|
535 | int leftHandTraversalIndex = 0; |
---|
536 | while (leftHandTraversalIndex < leftHandSideTraversal.size()) { |
---|
537 | |
---|
538 | //System.out.println("\n" + lineIndexLeft + " " + lineIndexRight); |
---|
539 | |
---|
540 | Delta delta = null; |
---|
541 | |
---|
542 | for (Delta candidate : patch.getDeltas()) { |
---|
543 | if (candidate.getOriginal().getPosition() == leftHandTraversalIndex) { |
---|
544 | delta = candidate; |
---|
545 | break; |
---|
546 | } |
---|
547 | } |
---|
548 | |
---|
549 | if ((delta != null) && (delta.getType() == Delta.TYPE.DELETE)) { |
---|
550 | for (int j = 0; j < delta.getOriginal().size(); j++) { |
---|
551 | while (linesLeft.get(lineIndexLeft) != null) { |
---|
552 | lineIndexLeft++; |
---|
553 | } |
---|
554 | |
---|
555 | linesLeft.remove(lineIndexLeft); |
---|
556 | |
---|
557 | while (lineIndexRight < lineIndexLeft) { |
---|
558 | linesRight.add(lineIndexRight++, null); |
---|
559 | } |
---|
560 | |
---|
561 | leftHandTraversalIndex++; |
---|
562 | } |
---|
563 | |
---|
564 | linesLeft.add(lineIndexLeft++, "-------------------------------------"); |
---|
565 | linesRight.add(lineIndexRight++, "-------------------------------------"); |
---|
566 | } |
---|
567 | else if ((delta != null) && (delta.getType() == Delta.TYPE.INSERT)) { |
---|
568 | for (int j = 0; j < delta.getRevised().size(); j++) { |
---|
569 | while (linesRight.get(lineIndexRight) != null) { |
---|
570 | lineIndexRight++; |
---|
571 | } |
---|
572 | |
---|
573 | linesRight.remove(lineIndexRight); |
---|
574 | |
---|
575 | while (lineIndexLeft < lineIndexRight) { |
---|
576 | linesLeft.add(lineIndexLeft++, null); |
---|
577 | } |
---|
578 | } |
---|
579 | |
---|
580 | // ensure that what is equal is harmonized too (because after an insert always |
---|
581 | // comes something equal). The traversal index will be updated automatically, |
---|
582 | // too. |
---|
583 | delta = null; |
---|
584 | |
---|
585 | linesLeft.add(lineIndexLeft++, "-------------------------------------"); |
---|
586 | linesRight.add(lineIndexRight++, "-------------------------------------"); |
---|
587 | } |
---|
588 | |
---|
589 | if ((delta == null) || (delta.getType() == Delta.TYPE.CHANGE)) { |
---|
590 | int chunkSizeLeft = delta != null ? delta.getOriginal().size() : 1; |
---|
591 | int chunkSizeRight = delta != null ? delta.getRevised().size() : 1; |
---|
592 | |
---|
593 | int chunksHandledLeft = 0; |
---|
594 | int chunksHandledRight = 0; |
---|
595 | |
---|
596 | for (int j = 0; j < Math.max(chunkSizeLeft, chunkSizeRight); j++) { |
---|
597 | if (chunksHandledLeft < chunkSizeLeft) { |
---|
598 | while (linesLeft.get(lineIndexLeft) != null) { |
---|
599 | lineIndexLeft++; |
---|
600 | } |
---|
601 | |
---|
602 | linesLeft.remove(lineIndexLeft); |
---|
603 | chunksHandledLeft++; |
---|
604 | } |
---|
605 | |
---|
606 | if (chunksHandledRight < chunkSizeRight) { |
---|
607 | while (linesRight.get(lineIndexRight) != null) { |
---|
608 | lineIndexRight++; |
---|
609 | } |
---|
610 | |
---|
611 | linesRight.remove(lineIndexRight); |
---|
612 | chunksHandledRight++; |
---|
613 | } |
---|
614 | |
---|
615 | while (lineIndexLeft < lineIndexRight) { |
---|
616 | linesLeft.add(lineIndexLeft++, null); |
---|
617 | } |
---|
618 | while (lineIndexRight < lineIndexLeft) { |
---|
619 | linesRight.add(lineIndexRight++, null); |
---|
620 | } |
---|
621 | } |
---|
622 | |
---|
623 | linesLeft.add(lineIndexLeft++, "-------------------------------------"); |
---|
624 | linesRight.add(lineIndexRight++, "-------------------------------------"); |
---|
625 | |
---|
626 | leftHandTraversalIndex += delta != null ? delta.getOriginal().size() : 1; |
---|
627 | } |
---|
628 | |
---|
629 | /*System.out.println(delta + " " + leftHandTraversalIndex); |
---|
630 | System.out.println("\n#################################################"); |
---|
631 | for (int j = 0; ((j < linesLeft.size()) || (j < linesRight.size())); j++) { |
---|
632 | String left = j < linesLeft.size() ? linesLeft.get(j) : ""; |
---|
633 | String right = j < linesRight.size() ? linesRight.get(j) : ""; |
---|
634 | |
---|
635 | StringBuffer line = new StringBuffer(); |
---|
636 | line.append(j); |
---|
637 | line.append(":\t"); |
---|
638 | line.append(left); |
---|
639 | |
---|
640 | for (int k = line.length(); k < 60; k++) { |
---|
641 | line.append(' '); |
---|
642 | } |
---|
643 | |
---|
644 | line.append(right); |
---|
645 | System.out.println(line); |
---|
646 | }*/ |
---|
647 | } |
---|
648 | |
---|
649 | int indentLeft = 0; |
---|
650 | int indentRight = 0; |
---|
651 | |
---|
652 | for (int i = 0; i < linesLeft.size(); i++) { |
---|
653 | StringBuffer line = new StringBuffer(); |
---|
654 | String left = linesLeft.get(i); |
---|
655 | String right = linesRight.get(i); |
---|
656 | |
---|
657 | if (left != null) { |
---|
658 | if (left.indexOf('}') >= 0) { |
---|
659 | indentLeft -= 2; |
---|
660 | } |
---|
661 | |
---|
662 | for (int j = 0; j < indentLeft; j++) { |
---|
663 | line.append(' '); |
---|
664 | } |
---|
665 | |
---|
666 | if (left.indexOf('{') >= 0) { |
---|
667 | indentLeft += 2; |
---|
668 | } |
---|
669 | |
---|
670 | line.append(left); |
---|
671 | } |
---|
672 | |
---|
673 | if (right != null) { |
---|
674 | for (int j = line.length(); j < 100; j++) { |
---|
675 | line.append(' '); |
---|
676 | } |
---|
677 | if (right.indexOf('}') >= 0) { |
---|
678 | indentRight -= 2; |
---|
679 | } |
---|
680 | |
---|
681 | for (int j = 0; j < indentRight; j++) { |
---|
682 | line.append(' '); |
---|
683 | } |
---|
684 | |
---|
685 | if (right.indexOf('{') >= 0) { |
---|
686 | indentRight += 2; |
---|
687 | } |
---|
688 | |
---|
689 | line.append(right); |
---|
690 | } |
---|
691 | |
---|
692 | out.println(line); |
---|
693 | } |
---|
694 | } |
---|
695 | |
---|
696 | /** |
---|
697 | * |
---|
698 | */ |
---|
699 | private static Set<ITask> getCommonInvolvedTasks(ITask task1, ITask task2) { |
---|
700 | Set<ITask> result = getAllInvolvedTasks(task1); |
---|
701 | result.retainAll(getAllInvolvedTasks(task2)); |
---|
702 | return result; |
---|
703 | } |
---|
704 | |
---|
705 | /** |
---|
706 | * |
---|
707 | */ |
---|
708 | private static Set<ITask> getAllInvolvedTasks(ITask task) { |
---|
709 | final Set<ITask> result = new HashSet<ITask>(); |
---|
710 | |
---|
711 | task.accept(new DefaultTaskTraversingVisitor() { |
---|
712 | @Override |
---|
713 | public void visit(IEventTask eventTask) { |
---|
714 | result.add(eventTask); |
---|
715 | } |
---|
716 | |
---|
717 | @Override |
---|
718 | public void visit(IStructuringTemporalRelationship relationship) { |
---|
719 | result.add(relationship); |
---|
720 | super.visit(relationship); |
---|
721 | } |
---|
722 | |
---|
723 | @Override |
---|
724 | public void visit(IMarkingTemporalRelationship relationship) { |
---|
725 | result.add(relationship); |
---|
726 | super.visit(relationship); |
---|
727 | } |
---|
728 | }); |
---|
729 | |
---|
730 | return result; |
---|
731 | } |
---|
732 | |
---|
733 | /** |
---|
734 | * |
---|
735 | */ |
---|
736 | private void dumpToLineList(TaskPath path, |
---|
737 | TaskTraversal traversal, |
---|
738 | List<String> lines) |
---|
739 | { |
---|
740 | boolean isTraversalElement = false; |
---|
741 | |
---|
742 | for (TaskPath candidate : traversal.getTraversalPaths()) { |
---|
743 | if (path.equals(candidate)) { |
---|
744 | isTraversalElement = true; |
---|
745 | break; |
---|
746 | } |
---|
747 | } |
---|
748 | |
---|
749 | if (isTraversalElement) { |
---|
750 | lines.add(path.getLast().toString()); |
---|
751 | lines.add(null); |
---|
752 | /*ByteArrayOutputStream byteStream = new ByteArrayOutputStream(); |
---|
753 | PrintStream out = new PrintStream(byteStream); |
---|
754 | |
---|
755 | new TaskTreeEncoder().encode(path.getLast(), out); |
---|
756 | |
---|
757 | out.close(); |
---|
758 | |
---|
759 | BufferedReader reader = new BufferedReader |
---|
760 | (new InputStreamReader(new ByteArrayInputStream(byteStream.toByteArray()))); |
---|
761 | |
---|
762 | String line = null; |
---|
763 | do { |
---|
764 | try { |
---|
765 | line = reader.readLine(); |
---|
766 | } |
---|
767 | catch (IOException e) { |
---|
768 | // should not happen so dump hard |
---|
769 | e.printStackTrace(); |
---|
770 | } |
---|
771 | lines.add(line != null ? line.trim() : null); |
---|
772 | } |
---|
773 | while (line != null);*/ |
---|
774 | |
---|
775 | } |
---|
776 | else { |
---|
777 | ITask task = path.getLast(); |
---|
778 | if (task instanceof ITemporalRelationship) { |
---|
779 | lines.add(task + " {"); |
---|
780 | |
---|
781 | if (task instanceof IStructuringTemporalRelationship) { |
---|
782 | List<ITask> children = |
---|
783 | ((IStructuringTemporalRelationship) task).getChildren(); |
---|
784 | |
---|
785 | for (int i = 0; i < children.size(); i++) { |
---|
786 | path.add(children.get(i), i); |
---|
787 | dumpToLineList(path, traversal, lines); |
---|
788 | path.removeLast(); |
---|
789 | } |
---|
790 | } |
---|
791 | else if (task instanceof IMarkingTemporalRelationship) { |
---|
792 | IMarkingTemporalRelationship relationship = |
---|
793 | (IMarkingTemporalRelationship) task; |
---|
794 | |
---|
795 | path.add(relationship.getMarkedTask(), 0); |
---|
796 | dumpToLineList(path, traversal, lines); |
---|
797 | path.removeLast(); |
---|
798 | } |
---|
799 | |
---|
800 | if (lines.get(lines.size() - 1) != null) { |
---|
801 | lines.add("}"); |
---|
802 | } |
---|
803 | else { |
---|
804 | lines.add(lines.size() - 1, "}"); |
---|
805 | } |
---|
806 | } |
---|
807 | else { |
---|
808 | lines.add(task + " {}"); |
---|
809 | } |
---|
810 | } |
---|
811 | } |
---|
812 | |
---|
813 | /** |
---|
814 | * |
---|
815 | */ |
---|
816 | /*@SuppressWarnings("unchecked") |
---|
817 | private void getSelections(Delta delta, List<TaskPath> result) { |
---|
818 | TaskPath path1 = getCommonPath((List<TaskPath>) delta.getOriginal().getLines()); |
---|
819 | TaskPath path2 = getCommonPath((List<TaskPath>) delta.getRevised().getLines()); |
---|
820 | |
---|
821 | for (int i = 0; i < path1.size(); i++) { |
---|
822 | if (path1.getTask(i) instanceof ISelection) { |
---|
823 | System.out.println("found selection to ignore"); |
---|
824 | System.out.println(path1.subPath(0, i + 1)); |
---|
825 | result.add(path1.subPath(0, i + 1)); |
---|
826 | break; |
---|
827 | } |
---|
828 | } |
---|
829 | |
---|
830 | for (int i = 0; i < path2.size(); i++) { |
---|
831 | if (path2.getTask(i) instanceof ISelection) { |
---|
832 | System.out.println("found selection to ignore"); |
---|
833 | System.out.println(path2.subPath(0, i + 1)); |
---|
834 | result.add(path2.subPath(0, i + 1)); |
---|
835 | break; |
---|
836 | } |
---|
837 | } |
---|
838 | }*/ |
---|
839 | |
---|
840 | /** |
---|
841 | * conflicting iterations are those that belong to either side of the sequence pair, that cover |
---|
842 | * at least two actions, and that were executed multiple times in the context of the tasks |
---|
843 | * to be merged. Iterations do only conflict, if there are at least two, one belonging to the |
---|
844 | * left hand side, and the other to the right hand side. They conflict only, if they cover the |
---|
845 | * same terminal nodes in the task traversals. |
---|
846 | */ |
---|
847 | private List<TaskPath> getConflictingIterations() { |
---|
848 | List<TaskPath> iterationsWithMultipleExecutions = new LinkedList<>(); |
---|
849 | getIterationsWithMultipleExecutions(leftHandSide, iterationsWithMultipleExecutions); |
---|
850 | |
---|
851 | if (iterationsWithMultipleExecutions.size() > 0) { |
---|
852 | // only, if iterations are executed in both side, they are of interest. Hence, |
---|
853 | // check right hand side only, if left hand side contains repeated iterations. |
---|
854 | int noOfLeftHandSideRepeatedIterations = iterationsWithMultipleExecutions.size(); |
---|
855 | getIterationsWithMultipleExecutions(rightHandSide, iterationsWithMultipleExecutions); |
---|
856 | |
---|
857 | if (iterationsWithMultipleExecutions.size() > noOfLeftHandSideRepeatedIterations) { |
---|
858 | // also the right hand side contains problematic iterations. Check if they are |
---|
859 | // overlapping and drop all which are not. |
---|
860 | dropNonOverlappingIterations(iterationsWithMultipleExecutions); |
---|
861 | } |
---|
862 | else { |
---|
863 | // no conflict, clear the list |
---|
864 | iterationsWithMultipleExecutions.clear(); |
---|
865 | } |
---|
866 | } |
---|
867 | |
---|
868 | return iterationsWithMultipleExecutions; |
---|
869 | } |
---|
870 | |
---|
871 | /** |
---|
872 | * |
---|
873 | */ |
---|
874 | private void getIterationsWithMultipleExecutions(ITask task, |
---|
875 | List<TaskPath> result) |
---|
876 | { |
---|
877 | for (ITaskInstance instance : task.getInstances()) { |
---|
878 | TaskPath taskPath = new TaskPath(); |
---|
879 | taskPath.add(task, 0); |
---|
880 | getIterationsWithMultipleExecutions(instance, taskPath, result); |
---|
881 | } |
---|
882 | } |
---|
883 | |
---|
884 | /** |
---|
885 | * |
---|
886 | */ |
---|
887 | private void getIterationsWithMultipleExecutions(ITaskInstance instance, |
---|
888 | TaskPath currentPath, |
---|
889 | List<TaskPath> result) |
---|
890 | { |
---|
891 | if (instance instanceof IIterationInstance) { |
---|
892 | ITask markedTask = instance.getTask(); |
---|
893 | |
---|
894 | while (markedTask instanceof IMarkingTemporalRelationship) { |
---|
895 | markedTask = ((IMarkingTemporalRelationship) markedTask).getMarkedTask(); |
---|
896 | } |
---|
897 | |
---|
898 | if ((!(markedTask instanceof IEventTask)) && |
---|
899 | ((IIterationInstance) instance).size() > 1) |
---|
900 | { |
---|
901 | // iteration repeats multiple event tasks and is executed multiple times --> |
---|
902 | // store path |
---|
903 | result.add(currentPath.subPath(0, currentPath.size())); // ensure to create a copy |
---|
904 | } |
---|
905 | |
---|
906 | currentPath.add(((IIteration) instance.getTask()).getMarkedTask(), 0); |
---|
907 | |
---|
908 | for (ITaskInstance child : (IIterationInstance) instance) { |
---|
909 | getIterationsWithMultipleExecutions(child, currentPath, result); |
---|
910 | } |
---|
911 | |
---|
912 | currentPath.removeLast(); |
---|
913 | } |
---|
914 | else if (instance instanceof ISequenceInstance) { |
---|
915 | int index = 0; |
---|
916 | for (ITaskInstance child : (ISequenceInstance) instance) { |
---|
917 | currentPath.add(child.getTask(), index++); |
---|
918 | getIterationsWithMultipleExecutions(child, currentPath, result); |
---|
919 | currentPath.removeLast(); |
---|
920 | } |
---|
921 | } |
---|
922 | else if (instance instanceof ISelectionInstance) { |
---|
923 | ITaskInstance child = ((ISelectionInstance) instance).getChild(); |
---|
924 | currentPath.add(child.getTask(), 0); |
---|
925 | getIterationsWithMultipleExecutions(child, currentPath, result); |
---|
926 | currentPath.removeLast(); |
---|
927 | } |
---|
928 | else if (instance instanceof IOptionalInstance) { |
---|
929 | ITaskInstance child = ((IOptionalInstance) instance).getChild(); |
---|
930 | if (child != null) { |
---|
931 | currentPath.add(child.getTask(), 0); |
---|
932 | getIterationsWithMultipleExecutions(child, currentPath, result); |
---|
933 | currentPath.removeLast(); |
---|
934 | } |
---|
935 | } |
---|
936 | } |
---|
937 | |
---|
938 | /** |
---|
939 | * |
---|
940 | */ |
---|
941 | private void dropNonOverlappingIterations(List<TaskPath> iterationsWithMultipleExecutions) { |
---|
942 | // to check overlappings, iterate the iterations. Then check for each the indexes it covers |
---|
943 | // in its respective traversal. Adapt the indexes depending on deltas that an iteration |
---|
944 | // covers. Then check all other iterations. Consider also here the indexes in the traversal. |
---|
945 | // also here, the indexes must be adapted in case of covered deltas. |
---|
946 | List<TaskPath> overlappingIterations = new LinkedList<TaskPath>(); |
---|
947 | |
---|
948 | for (TaskPath leftPath : iterationsWithMultipleExecutions) { |
---|
949 | if (leftPath.getTask(0).equals(leftHandSide)) { |
---|
950 | for (TaskPath rightPath : iterationsWithMultipleExecutions) { |
---|
951 | if (rightPath.getTask(0).equals(rightHandSide)) { |
---|
952 | int[] leftIdxs = leftHandSideTraversal.getIndexesRootedBy(leftPath); |
---|
953 | int[] rightIdxs = rightHandSideTraversal.getIndexesRootedBy(rightPath); |
---|
954 | |
---|
955 | adaptIndexesBasedOnDeltas(leftIdxs, rightIdxs, patch.getDeltas()); |
---|
956 | |
---|
957 | if (((leftIdxs[0] <= rightIdxs[0]) && (rightIdxs[0] <= leftIdxs[1])) || |
---|
958 | ((rightIdxs[0] <= leftIdxs[0]) && (leftIdxs[0] <= rightIdxs[1]))) |
---|
959 | { |
---|
960 | overlappingIterations.add(leftPath); |
---|
961 | overlappingIterations.add(rightPath); |
---|
962 | } |
---|
963 | } |
---|
964 | } |
---|
965 | } |
---|
966 | } |
---|
967 | |
---|
968 | iterationsWithMultipleExecutions.retainAll(overlappingIterations); |
---|
969 | } |
---|
970 | |
---|
971 | /** |
---|
972 | * |
---|
973 | */ |
---|
974 | private void adaptIndexesBasedOnDeltas(int[] originalIndexes, |
---|
975 | int[] revisedIndexes, |
---|
976 | List<Delta> deltas) |
---|
977 | { |
---|
978 | int originalStartUpdate = 0; |
---|
979 | int originalEndUpdate = 0; |
---|
980 | int revisedStartUpdate = 0; |
---|
981 | int revisedEndUpdate = 0; |
---|
982 | |
---|
983 | for (Delta delta : deltas) { |
---|
984 | if (delta.getType() == Delta.TYPE.INSERT) { |
---|
985 | // for insert deltas only the original indexes must be adapted |
---|
986 | if (delta.getOriginal().getPosition() <= originalIndexes[0]) { |
---|
987 | originalStartUpdate += delta.getRevised().size(); |
---|
988 | } |
---|
989 | if (delta.getOriginal().getPosition() <= originalIndexes[1]) { |
---|
990 | originalEndUpdate += delta.getRevised().size(); |
---|
991 | } |
---|
992 | } |
---|
993 | else if (delta.getType() == Delta.TYPE.DELETE) { |
---|
994 | // for delete deltas only the revised indexes must be adapted |
---|
995 | if (delta.getRevised().getPosition() <= revisedIndexes[0]) { |
---|
996 | revisedStartUpdate += delta.getOriginal().size(); |
---|
997 | } |
---|
998 | if (delta.getRevised().getPosition() <= revisedIndexes[1]) { |
---|
999 | revisedEndUpdate += delta.getOriginal().size(); |
---|
1000 | } |
---|
1001 | } |
---|
1002 | else if (delta.getType() == Delta.TYPE.CHANGE) { |
---|
1003 | // for change deltas we adapt only the revision indexes. |
---|
1004 | // If the revised variant is longer than the original, the indexes become smaller. |
---|
1005 | // else, the other way around |
---|
1006 | int lengthDiff = delta.getOriginal().size() - delta.getRevised().size(); |
---|
1007 | |
---|
1008 | if (lengthDiff < 0) { |
---|
1009 | // the revised variant is longer --> adapt indexes of original |
---|
1010 | lengthDiff = 0 - lengthDiff; |
---|
1011 | int start = delta.getOriginal().getPosition(); |
---|
1012 | int end = start + delta.getOriginal().size() - 1; |
---|
1013 | |
---|
1014 | if (end < originalIndexes[0]) { |
---|
1015 | // delta is before indexes |
---|
1016 | originalStartUpdate += lengthDiff; |
---|
1017 | } |
---|
1018 | if ((end <= originalIndexes[1]) || (start <= originalIndexes[1])) { |
---|
1019 | // delta and indexes overlap |
---|
1020 | originalEndUpdate += lengthDiff; |
---|
1021 | } |
---|
1022 | } |
---|
1023 | else if (lengthDiff > 0) { |
---|
1024 | // the original variant is longer --> adapt indexes of revised |
---|
1025 | int start = delta.getRevised().getPosition(); |
---|
1026 | int end = start + delta.getRevised().size() - 1; |
---|
1027 | |
---|
1028 | if (end < revisedIndexes[0]) { |
---|
1029 | // delta is before indexes |
---|
1030 | revisedStartUpdate += lengthDiff; |
---|
1031 | } |
---|
1032 | if ((end <= revisedIndexes[1]) || (start <= revisedIndexes[1])) { |
---|
1033 | // delta and indexes overlap |
---|
1034 | revisedEndUpdate += lengthDiff; |
---|
1035 | } |
---|
1036 | } |
---|
1037 | } |
---|
1038 | } |
---|
1039 | |
---|
1040 | originalIndexes[0] += originalStartUpdate; |
---|
1041 | originalIndexes[1] += originalEndUpdate; |
---|
1042 | revisedIndexes[0] += revisedStartUpdate; |
---|
1043 | revisedIndexes[1] += revisedEndUpdate; |
---|
1044 | } |
---|
1045 | |
---|
1046 | /** |
---|
1047 | * |
---|
1048 | */ |
---|
1049 | private TaskPath getCommonPath(List<TaskPath> paths) { |
---|
1050 | TaskPath commonPath; |
---|
1051 | |
---|
1052 | if (paths.size() > 0) { |
---|
1053 | commonPath = new TaskPath(paths.get(0)); |
---|
1054 | |
---|
1055 | for (int i = 1; i < paths.size(); i++) { |
---|
1056 | TaskPath comparePath = paths.get(i); |
---|
1057 | for (int j = 0; (j < commonPath.size()) && (j < comparePath.size()); j++) { |
---|
1058 | if (!commonPath.get(j).equals(comparePath.get(j))) { |
---|
1059 | while (commonPath.size() > j) { |
---|
1060 | commonPath.removeLast(); |
---|
1061 | } |
---|
1062 | break; |
---|
1063 | } |
---|
1064 | } |
---|
1065 | } |
---|
1066 | } |
---|
1067 | else { |
---|
1068 | commonPath = new TaskPath(); |
---|
1069 | } |
---|
1070 | |
---|
1071 | return commonPath; |
---|
1072 | } |
---|
1073 | |
---|
1074 | /** |
---|
1075 | * |
---|
1076 | */ |
---|
1077 | private void getNotFullyInterleavingIteration(Delta delta, List<TaskPath> result) { |
---|
1078 | getNotFullyInterleavingIterations(delta.getOriginal(), leftHandSideTraversal, result); |
---|
1079 | getNotFullyInterleavingIterations(delta.getRevised(), rightHandSideTraversal, result); |
---|
1080 | } |
---|
1081 | |
---|
1082 | /** |
---|
1083 | * If a chunk has a minimum number of 2 entries and at least one of them belongs to an iteration |
---|
1084 | * that does not cover the other and also expands to preceding or succeeding paths in the |
---|
1085 | * traversal, we can not merge the situation. |
---|
1086 | */ |
---|
1087 | private void getNotFullyInterleavingIterations(Chunk chunk, |
---|
1088 | TaskTraversal traversal, |
---|
1089 | List<TaskPath> result) |
---|
1090 | { |
---|
1091 | @SuppressWarnings("unchecked") |
---|
1092 | List<TaskPath> paths = (List<TaskPath>) chunk.getLines(); |
---|
1093 | |
---|
1094 | TaskPath commonPath = getCommonPath(paths); |
---|
1095 | |
---|
1096 | if (paths.size() > 1) { |
---|
1097 | TaskPath firstPath = paths.get(0); |
---|
1098 | TaskPath lastPath = paths.get(paths.size() - 1); |
---|
1099 | |
---|
1100 | for (int i = commonPath.size(); i < firstPath.size(); i++) { |
---|
1101 | if (firstPath.get(i).getTask() instanceof IIteration) { |
---|
1102 | // check, if the iteration covers things preceding the delta but not the whole |
---|
1103 | // delta |
---|
1104 | int[] indexes = traversal.getIndexesRootedBy(firstPath.subPath(0, i + 1)); |
---|
1105 | |
---|
1106 | if ((indexes[0] < chunk.getPosition()) && // starts before the delta |
---|
1107 | (indexes[1] < (chunk.getPosition() + chunk.size() - 1))) // does not cover delta |
---|
1108 | { |
---|
1109 | result.add(firstPath.subPath(0, i + 1)); |
---|
1110 | break; |
---|
1111 | } |
---|
1112 | } |
---|
1113 | } |
---|
1114 | |
---|
1115 | for (int i = commonPath.size(); i < lastPath.size(); i++) { |
---|
1116 | if (lastPath.get(i).getTask() instanceof IIteration) { |
---|
1117 | // check, if the iteration covers things preceding the delta but not the whole |
---|
1118 | // delta |
---|
1119 | int[] indexes = traversal.getIndexesRootedBy(lastPath.subPath(0, i + 1)); |
---|
1120 | |
---|
1121 | if ((indexes[0] > chunk.getPosition()) && // starts in between the delta |
---|
1122 | (indexes[1] >= (chunk.getPosition() + chunk.size()))) // ends after the delta |
---|
1123 | { |
---|
1124 | result.add(lastPath.subPath(0, i + 1)); |
---|
1125 | break; |
---|
1126 | } |
---|
1127 | } |
---|
1128 | } |
---|
1129 | } |
---|
1130 | } |
---|
1131 | |
---|
1132 | /** |
---|
1133 | * |
---|
1134 | */ |
---|
1135 | private void getPathsToParentTasksFullyInsideDelta(Delta delta, List<TaskPath> result) { |
---|
1136 | getPathsToParentTasksFullyInsideChunk(delta.getOriginal(), leftHandSideTraversal, result); |
---|
1137 | getPathsToParentTasksFullyInsideChunk(delta.getRevised(), rightHandSideTraversal, result); |
---|
1138 | } |
---|
1139 | |
---|
1140 | /** |
---|
1141 | * If a chunk has a minimum number of 2 entries and at least one of them belongs to an iteration |
---|
1142 | * the does not cover the other and also expands to preceding or succeeding paths in the |
---|
1143 | * traversal, we can no merge the situation. |
---|
1144 | */ |
---|
1145 | private void getPathsToParentTasksFullyInsideChunk(Chunk chunk, |
---|
1146 | TaskTraversal traversal, |
---|
1147 | List<TaskPath> result) |
---|
1148 | { |
---|
1149 | @SuppressWarnings("unchecked") |
---|
1150 | List<TaskPath> paths = (List<TaskPath>) chunk.getLines(); |
---|
1151 | |
---|
1152 | for (TaskPath path : paths) { |
---|
1153 | for (int i = path.size() - 1; i >= 0; i--) { |
---|
1154 | // check, if the parent task covers things fully inside the delta |
---|
1155 | TaskPath parentPath = path.subPath(0, i); |
---|
1156 | |
---|
1157 | //System.out.println("checking parent path " + parentPath); |
---|
1158 | int[] indexes = traversal.getIndexesRootedBy(parentPath); |
---|
1159 | //System.out.println("indexes are " + indexes[0] + " " + indexes[1]); |
---|
1160 | |
---|
1161 | if ((chunk.getPosition() <= indexes[0]) && // starts in the delta |
---|
1162 | (indexes[1] < (chunk.getPosition() + chunk.size()))) // ends in the delta |
---|
1163 | { |
---|
1164 | //System.out.println("found path to parent task lying completely in the " + |
---|
1165 | // "delta: " + parentPath); |
---|
1166 | result.add(parentPath); |
---|
1167 | } |
---|
1168 | else { |
---|
1169 | // further parents can not be inside the delta |
---|
1170 | break; |
---|
1171 | } |
---|
1172 | } |
---|
1173 | } |
---|
1174 | } |
---|
1175 | |
---|
1176 | /** |
---|
1177 | * |
---|
1178 | */ |
---|
1179 | private void getUnexecutedParentOptionals(ITask task, |
---|
1180 | List<TaskPath> result) |
---|
1181 | { |
---|
1182 | for (ITaskInstance instance : task.getInstances()) { |
---|
1183 | TaskPath taskPath = new TaskPath(); |
---|
1184 | taskPath.add(task, 0); |
---|
1185 | getUnexecutedParentOptionals(instance, taskPath, result); |
---|
1186 | } |
---|
1187 | } |
---|
1188 | |
---|
1189 | /** |
---|
1190 | * |
---|
1191 | */ |
---|
1192 | private void getUnexecutedParentOptionals(ITaskInstance instance, |
---|
1193 | TaskPath currentPath, |
---|
1194 | List<TaskPath> result) |
---|
1195 | { |
---|
1196 | if (instance instanceof IOptionalInstance) { |
---|
1197 | ITaskInstance child = ((IOptionalInstance) instance).getChild(); |
---|
1198 | if (child != null) { |
---|
1199 | currentPath.add(child.getTask(), 0); |
---|
1200 | getUnexecutedParentOptionals(child, currentPath, result); |
---|
1201 | currentPath.removeLast(); |
---|
1202 | } |
---|
1203 | else { |
---|
1204 | result.add(currentPath.subPath(0, currentPath.size())); // ensure to create a copy |
---|
1205 | } |
---|
1206 | } |
---|
1207 | else if (instance instanceof IIterationInstance) { |
---|
1208 | currentPath.add(((IIteration) instance.getTask()).getMarkedTask(), 0); |
---|
1209 | |
---|
1210 | for (ITaskInstance child : (IIterationInstance) instance) { |
---|
1211 | getUnexecutedParentOptionals(child, currentPath, result); |
---|
1212 | } |
---|
1213 | |
---|
1214 | currentPath.removeLast(); |
---|
1215 | } |
---|
1216 | else if (instance instanceof ISequenceInstance) { |
---|
1217 | int index = 0; |
---|
1218 | for (ITaskInstance child : (ISequenceInstance) instance) { |
---|
1219 | currentPath.add(child.getTask(), index++); |
---|
1220 | getUnexecutedParentOptionals(child, currentPath, result); |
---|
1221 | currentPath.removeLast(); |
---|
1222 | } |
---|
1223 | } |
---|
1224 | else if (instance instanceof ISelectionInstance) { |
---|
1225 | ITaskInstance child = ((ISelectionInstance) instance).getChild(); |
---|
1226 | currentPath.add(child.getTask(), 0); |
---|
1227 | getUnexecutedParentOptionals(child, currentPath, result); |
---|
1228 | currentPath.removeLast(); |
---|
1229 | } |
---|
1230 | } |
---|
1231 | |
---|
1232 | /** |
---|
1233 | * |
---|
1234 | */ |
---|
1235 | @SuppressWarnings("unchecked") |
---|
1236 | private int getDiffLevel(Patch patch, |
---|
1237 | TaskTraversal traversal1, |
---|
1238 | TaskTraversal traversal2) |
---|
1239 | { |
---|
1240 | if (patch.getDeltas().size() == 0) { |
---|
1241 | return 0; |
---|
1242 | } |
---|
1243 | |
---|
1244 | int diffCount = 0; |
---|
1245 | int allCount = 0; |
---|
1246 | |
---|
1247 | for (Delta delta : patch.getDeltas()) { |
---|
1248 | for (TaskPath path : (List<TaskPath>) delta.getOriginal().getLines()) { |
---|
1249 | // inefficient actions are counted later. |
---|
1250 | if (!isInefficientAction(path.getLast())) { |
---|
1251 | diffCount += getDiffPenalty(path.getLast()); |
---|
1252 | } |
---|
1253 | } |
---|
1254 | for (TaskPath path : (List<TaskPath>) delta.getRevised().getLines()) { |
---|
1255 | // inefficient actions are counted later. |
---|
1256 | if (!isInefficientAction(path.getLast())) { |
---|
1257 | diffCount += getDiffPenalty(path.getLast()); |
---|
1258 | } |
---|
1259 | } |
---|
1260 | } |
---|
1261 | |
---|
1262 | //if (getPathsToRealIntersectingIterations().size() > 0) { |
---|
1263 | // add a penalty if intersecting iterations are present |
---|
1264 | //count += 10; |
---|
1265 | //} |
---|
1266 | |
---|
1267 | // add a penalty for inefficient actions which are equal as they have to be treated |
---|
1268 | // unequal, too. Otherwise, many scrolls, e.g., would pretend a high equality of tasks |
---|
1269 | // which contain only some non inefficient actions |
---|
1270 | for (TaskPath path : traversal1.getTraversalPaths()) { |
---|
1271 | if (isInefficientAction(path.getLast())) { |
---|
1272 | diffCount++; |
---|
1273 | allCount++; |
---|
1274 | } |
---|
1275 | else { |
---|
1276 | allCount += getDiffPenalty(path.getLast()); |
---|
1277 | } |
---|
1278 | } |
---|
1279 | |
---|
1280 | for (TaskPath path : traversal2.getTraversalPaths()) { |
---|
1281 | if (isInefficientAction(path.getLast())) { |
---|
1282 | diffCount++; |
---|
1283 | allCount++; |
---|
1284 | } |
---|
1285 | else { |
---|
1286 | allCount += getDiffPenalty(path.getLast()); |
---|
1287 | } |
---|
1288 | } |
---|
1289 | |
---|
1290 | if (allCount == 0) { |
---|
1291 | // this happens, if all actions are inefficient. Return the highest diff level |
---|
1292 | return 100; |
---|
1293 | } |
---|
1294 | else { |
---|
1295 | return (100 * diffCount) / allCount; |
---|
1296 | } |
---|
1297 | } |
---|
1298 | |
---|
1299 | /** |
---|
1300 | * |
---|
1301 | */ |
---|
1302 | private boolean isInefficientAction(ITask task) { |
---|
1303 | if (task instanceof IEventTask) { |
---|
1304 | IEventTaskInstance inst = (IEventTaskInstance) task.getInstances().iterator().next(); |
---|
1305 | if (inst.getEvent().getType() instanceof Scroll) { |
---|
1306 | return true; |
---|
1307 | } |
---|
1308 | else { |
---|
1309 | return false; |
---|
1310 | } |
---|
1311 | } |
---|
1312 | else if (task instanceof IMarkingTemporalRelationship) { |
---|
1313 | return isInefficientAction(((IMarkingTemporalRelationship) task).getMarkedTask()); |
---|
1314 | } |
---|
1315 | else { |
---|
1316 | return false; |
---|
1317 | } |
---|
1318 | } |
---|
1319 | |
---|
1320 | |
---|
1321 | /** |
---|
1322 | * |
---|
1323 | */ |
---|
1324 | private int getDiffPenalty(ITask task) { |
---|
1325 | if (task instanceof IEventTask) { |
---|
1326 | return 1; |
---|
1327 | } |
---|
1328 | else if (task instanceof IMarkingTemporalRelationship) { |
---|
1329 | return getDiffPenalty(((IMarkingTemporalRelationship) task).getMarkedTask()); |
---|
1330 | } |
---|
1331 | else if (task instanceof IStructuringTemporalRelationship) { |
---|
1332 | int result = 0; |
---|
1333 | |
---|
1334 | for (ITask child : ((IStructuringTemporalRelationship) task).getChildren()) { |
---|
1335 | result += getDiffPenalty(child); |
---|
1336 | } |
---|
1337 | |
---|
1338 | if (task instanceof ISelection) { |
---|
1339 | result /= ((IStructuringTemporalRelationship) task).getChildren().size(); |
---|
1340 | } |
---|
1341 | |
---|
1342 | return result; |
---|
1343 | } |
---|
1344 | |
---|
1345 | throw new IllegalArgumentException("unknown type of task: " + task); |
---|
1346 | } |
---|
1347 | } |
---|