@title: MyersDiff @Author rezeros.github.io @Date: 2021/2/19 @Version 1.0.0
| 18 | * @Version 1.0.0 |
| 19 | */ |
| 20 | @Slf4j |
| 21 | public class MyersDiff implements DiffAlgorithm { |
| 22 | |
| 23 | /** |
| 24 | * complexity of both time and space : O ((N + M)D) |
| 25 | * k = x - y |
| 26 | * 0 - 1 - 2 - 3 // x |
| 27 | * | |
| 28 | * 1 |
| 29 | * | |
| 30 | * 2 // y |
| 31 | */ |
| 32 | @Override |
| 33 | public List<LineObject> diff(List<LineObject> fromLineObjects, List<LineObject> targetLineObjects) { |
| 34 | |
| 35 | // init step |
| 36 | int finalStep = 0; |
| 37 | // we set from as x anxious |
| 38 | final int fromLineCount = fromLineObjects.size(); |
| 39 | |
| 40 | // we set target as y anxious |
| 41 | final int targetLineCount = targetLineObjects.size(); |
| 42 | |
| 43 | // sum of from and target lines count |
| 44 | final int totalLineCount = targetLineCount + fromLineCount; |
| 45 | |
| 46 | int vSize = Math.max(fromLineCount, targetLineCount) * 2 + 1; |
| 47 | |
| 48 | // do snapshot for v while iterate step |
| 49 | int [][] vList = new int[totalLineCount + 1][vSize]; |
| 50 | |
| 51 | // k can be zero, so plus one |
| 52 | //todo optimize for minimize v.length |
| 53 | final int[] v = new int[vSize]; |
| 54 | |
| 55 | // set the previous start point |
| 56 | v[v.length / 2 + 1] = 0; |
| 57 | |
| 58 | boolean foundShortest = false; |
| 59 | for (int step = 0; step <= totalLineCount; step++) { |
| 60 | |
| 61 | // little trick, java can not use negative number as array index |
| 62 | int negativeStep = v.length / 2 - step; |
| 63 | int positiveStep = v.length / 2 + step; |
| 64 | for (int k = negativeStep; k >= 0 && k <= positiveStep; k += 2) { |
| 65 | int kAimD = k - v.length / 2; |
| 66 | boolean down = (kAimD == -step || (kAimD != step && v[k - 1] < v[k + 1])); |
| 67 | |
| 68 | int xStart = down? v[k + 1]: v[k - 1]; |
| 69 | |
| 70 | int xEnd = down? xStart: xStart + 1; |
| 71 | int yEnd = xEnd - kAimD; |
| 72 | // diagonal |
| 73 | while ((0 <= xEnd && xEnd < fromLineCount) && (0 <= yEnd && yEnd < targetLineCount) |
| 74 | && (fromLineObjects.get(xEnd).getLineContent().equals(targetLineObjects.get(yEnd).getLineContent()))){ |
| 75 | xEnd++; yEnd++; |
| 76 | } |
| 77 | v[k] = xEnd; |
nothing calls this directly
no outgoing calls
no test coverage detected