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 de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator; |
---|
18 | import difflib.ChangeDelta; |
---|
19 | import difflib.Chunk; |
---|
20 | import difflib.DeleteDelta; |
---|
21 | import difflib.Delta; |
---|
22 | import difflib.InsertDelta; |
---|
23 | import difflib.Patch; |
---|
24 | import difflib.myers.DiffNode; |
---|
25 | import difflib.myers.MyersDiff; |
---|
26 | import difflib.myers.PathNode; |
---|
27 | import difflib.myers.Snake; |
---|
28 | |
---|
29 | /** |
---|
30 | * |
---|
31 | */ |
---|
32 | public class TaskTraversalMyersDiff extends MyersDiff { |
---|
33 | |
---|
34 | /** */ |
---|
35 | private final TaskComparator comparator; |
---|
36 | |
---|
37 | /** |
---|
38 | * |
---|
39 | */ |
---|
40 | public TaskTraversalMyersDiff(TaskComparator comparator) { |
---|
41 | this.comparator = comparator; |
---|
42 | } |
---|
43 | |
---|
44 | /** |
---|
45 | * |
---|
46 | */ |
---|
47 | public Patch getDiff(TaskTraversal variant1, TaskTraversal variant2) { |
---|
48 | PathNode path = buildPath(variant1, variant2); |
---|
49 | return buildRevision(path, variant1, variant2); |
---|
50 | } |
---|
51 | |
---|
52 | /** |
---|
53 | * overwrites the default implementation just to change the tree task comparison. |
---|
54 | * This is an extended version of the original implementation respecting the appropriate |
---|
55 | * copyrights. Please see the copyrights of the implementers of the base class for more |
---|
56 | * information |
---|
57 | */ |
---|
58 | private PathNode buildPath(TaskTraversal variant1, TaskTraversal variant2) { |
---|
59 | if (variant1 == null) { |
---|
60 | throw new IllegalArgumentException("variant1 is null"); |
---|
61 | } |
---|
62 | |
---|
63 | if (variant2 == null) { |
---|
64 | throw new IllegalArgumentException("variant2 is null"); |
---|
65 | } |
---|
66 | |
---|
67 | // these are local constants |
---|
68 | final int N = variant1.size(); |
---|
69 | final int M = variant2.size(); |
---|
70 | |
---|
71 | final int MAX = N + M + 1; |
---|
72 | final int size = 1 + 2 * MAX; |
---|
73 | final int middle = size / 2; |
---|
74 | final PathNode diagonal[] = new PathNode[size]; |
---|
75 | |
---|
76 | diagonal[middle + 1] = new Snake(0, -1, null); |
---|
77 | |
---|
78 | for (int d = 0; d < MAX; d++) { |
---|
79 | for (int k = -d; k <= d; k += 2) { |
---|
80 | final int kmiddle = middle + k; |
---|
81 | final int kplus = kmiddle + 1; |
---|
82 | final int kminus = kmiddle - 1; |
---|
83 | PathNode prev = null; |
---|
84 | |
---|
85 | int i; |
---|
86 | if ((k == -d) || ((k != d) && (diagonal[kminus].i < diagonal[kplus].i))) { |
---|
87 | i = diagonal[kplus].i; |
---|
88 | prev = diagonal[kplus]; |
---|
89 | } |
---|
90 | else { |
---|
91 | i = diagonal[kminus].i + 1; |
---|
92 | prev = diagonal[kminus]; |
---|
93 | } |
---|
94 | |
---|
95 | diagonal[kminus] = null; // no longer used |
---|
96 | |
---|
97 | int j = i - k; |
---|
98 | |
---|
99 | PathNode task = new DiffNode(i, j, prev); |
---|
100 | |
---|
101 | // orig and rev are zero-based |
---|
102 | // but the algorithm is one-based |
---|
103 | // that's why there's no +1 when indexing the sequences |
---|
104 | while ((i < N) && (j < M) && comparator.equals(variant1.get(i), variant2.get(j))) { |
---|
105 | i++; |
---|
106 | j++; |
---|
107 | } |
---|
108 | |
---|
109 | if (i > task.i) { |
---|
110 | task = new Snake(i, j, task); |
---|
111 | } |
---|
112 | |
---|
113 | diagonal[kmiddle] = task; |
---|
114 | |
---|
115 | if ((i >= N) && (j >= M)) { |
---|
116 | return diagonal[kmiddle]; |
---|
117 | } |
---|
118 | } |
---|
119 | diagonal[middle + d - 1] = null; |
---|
120 | |
---|
121 | } |
---|
122 | |
---|
123 | // According to Myers, this cannot happen |
---|
124 | throw new RuntimeException("could not find a diff path"); |
---|
125 | } |
---|
126 | |
---|
127 | /** |
---|
128 | * overwrites the default implementation just to change the tree task comparison. |
---|
129 | * This is an extended version of the original implementation respecting the appropriate |
---|
130 | * copyrights. Please see the copyrights of the implementers of the base class for more |
---|
131 | * information |
---|
132 | */ |
---|
133 | private Patch buildRevision(PathNode path, |
---|
134 | TaskTraversal variant1, |
---|
135 | TaskTraversal variant2) |
---|
136 | { |
---|
137 | if (path == null) { |
---|
138 | throw new IllegalArgumentException("path is null"); |
---|
139 | } |
---|
140 | |
---|
141 | if (variant1 == null) { |
---|
142 | throw new IllegalArgumentException("variant1 is null"); |
---|
143 | } |
---|
144 | |
---|
145 | if (variant2 == null) { |
---|
146 | throw new IllegalArgumentException("variant2 is null"); |
---|
147 | } |
---|
148 | |
---|
149 | Patch patch = new Patch(); |
---|
150 | if (path.isSnake()) { |
---|
151 | path = path.prev; |
---|
152 | } |
---|
153 | |
---|
154 | while ((path != null) && (path.prev != null) && (path.prev.j >= 0)) { |
---|
155 | if (path.isSnake()) { |
---|
156 | throw new IllegalStateException |
---|
157 | ("bad diffpath: found snake when looking for diff"); |
---|
158 | } |
---|
159 | |
---|
160 | int i = path.i; |
---|
161 | int j = path.j; |
---|
162 | |
---|
163 | path = path.prev; |
---|
164 | int ianchor = path.i; |
---|
165 | int janchor = path.j; |
---|
166 | |
---|
167 | Chunk original = new Chunk(ianchor, variant1.subList(ianchor, i)); |
---|
168 | int originalSize = original.size(); |
---|
169 | Chunk revised = new Chunk(janchor, variant2.subList(janchor, j)); |
---|
170 | int revisedSize = revised.size(); |
---|
171 | Delta delta = null; |
---|
172 | |
---|
173 | if ((originalSize == 0) && (revisedSize != 0)) { |
---|
174 | delta = new InsertDelta(original, revised); |
---|
175 | } |
---|
176 | else if ((originalSize > 0) && (revisedSize == 0)) { |
---|
177 | delta = new DeleteDelta(original, revised); |
---|
178 | } |
---|
179 | else { |
---|
180 | delta = new ChangeDelta(original, revised); |
---|
181 | } |
---|
182 | |
---|
183 | patch.addDelta(delta); |
---|
184 | |
---|
185 | if (path.isSnake()) { |
---|
186 | path = path.prev; |
---|
187 | } |
---|
188 | } |
---|
189 | return patch; |
---|
190 | } |
---|
191 | |
---|
192 | } |
---|