[1767] | 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 | |
---|
[1848] | 17 | import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskComparator; |
---|
[1767] | 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 | /** */ |
---|
[1848] | 35 | private final TaskComparator comparator; |
---|
[1767] | 36 | |
---|
| 37 | /** |
---|
| 38 | * |
---|
| 39 | */ |
---|
[1848] | 40 | public TaskTraversalMyersDiff(TaskComparator comparator) { |
---|
[1767] | 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 |
---|
[1848] | 104 | while ((i < N) && (j < M) && comparator.equals(variant1.get(i), variant2.get(j))) { |
---|
| 105 | i++; |
---|
| 106 | j++; |
---|
[1767] | 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)); |
---|
[1848] | 168 | int originalSize = original.size(); |
---|
[1767] | 169 | Chunk revised = new Chunk(janchor, variant2.subList(janchor, j)); |
---|
[1848] | 170 | int revisedSize = revised.size(); |
---|
[1767] | 171 | Delta delta = null; |
---|
| 172 | |
---|
[1848] | 173 | if ((originalSize == 0) && (revisedSize != 0)) { |
---|
[1767] | 174 | delta = new InsertDelta(original, revised); |
---|
| 175 | } |
---|
[1848] | 176 | else if ((originalSize > 0) && (revisedSize == 0)) { |
---|
[1767] | 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 | } |
---|