diff.hh (6852B)
1 #ifndef diff_hh_INCLUDED 2 #define diff_hh_INCLUDED 3 4 // Implementation of the linear space variant of the algorithm described in 5 // "An O(ND) Difference Algorithm and Its Variations" 6 // (http://xmailserver.org/diff2.pdf) 7 8 #include <algorithm> 9 #include "function.hh" 10 #include "unique_ptr.hh" 11 12 namespace Kakoune 13 { 14 15 // A snake is an edit followed by a (possibly empty) diagonal 16 struct Snake 17 { 18 // The end points of the diagonal (x, y) -> (u, v) 19 int x, y, u, v; 20 // the edit op, reverse op happen at the end of the diagonal 21 enum Op { Add, Del, RevAdd, RevDel } op; 22 }; 23 24 template<bool forward, typename IteratorA, typename IteratorB, typename Equal> 25 Snake find_end_snake_of_further_reaching_dpath(IteratorA a, int N, IteratorB b, int M, 26 const int* V, const int D, const int k, Equal&& eq) 27 { 28 const bool add = k == -D or (k != D and V[k-1] < V[k+1]); 29 30 // if diagonal on the right goes further along x than diagonal on the left, 31 // then we take a vertical edge from it to this diagonal, hence x = V[k+1] 32 // else, we take an horizontal edge from our left diagonal,x = V[k-1]+1 33 const int x = add ? V[k+1] : V[k-1]+1; 34 // we are by construction on diagonal k, so our position along b (y) is x - k. 35 const int y = x - k; 36 37 auto at = [](auto&& base, int index, int size) -> decltype(auto) { 38 return forward ? base[index] : base[size - 1 - index]; 39 }; 40 41 int u = x, v = y; 42 // follow end snake along diagonal k 43 while (u < N and v < M and eq(at(a, u, N), at(b, v, M))) 44 ++u, ++v; 45 46 return { x, y, u, v, add ? Snake::Add : Snake::Del }; 47 } 48 49 template<typename IteratorA, typename IteratorB, typename Equal> 50 Snake find_middle_snake(IteratorA a, int N, IteratorB b, int M, 51 int* V1, int* V2, int cost_limit, Equal&& eq) 52 { 53 const int delta = N - M; 54 V1[1] = 0; 55 V2[1] = 0; 56 57 const int max_D = std::min((M + N + 1) / 2 + 1, cost_limit); 58 for (int D = 0; D < max_D; ++D) 59 { 60 for (int k1 = -D; k1 <= D; k1 += 2) 61 { 62 auto p = find_end_snake_of_further_reaching_dpath<true>(a, N, b, M, V1, D, k1, eq); 63 V1[k1] = p.u; 64 65 const int k2 = -(k1 - delta); 66 if ((delta % 2 != 0) and -(D-1) <= k2 and k2 <= (D-1) and V1[k1] + V2[k2] >= N) 67 return p;// return last snake on forward path, len = (2 * D - 1) 68 } 69 70 for (int k2 = -D; k2 <= D; k2 += 2) 71 { 72 auto p = find_end_snake_of_further_reaching_dpath<false>(a, N, b, M, V2, D, k2, eq); 73 V2[k2] = p.u; 74 75 const int k1 = -(k2 - delta); 76 if ((delta % 2 == 0) and -D <= k1 and k1 <= D and V1[k1] + V2[k2] >= N) 77 return { N - p.u, M - p.v, N - p.x , M - p.y, 78 (Snake::Op)(p.op + Snake::RevAdd) };// return last snake on reverse path, len = 2 * D 79 } 80 } 81 82 // We did not find a minimal path in less than max_D iterations, iterate one more time finding the best 83 Snake best{}; 84 auto score = [](const Snake& s) { return s.u + s.v; }; 85 for (int k1 = -max_D; k1 <= max_D; k1 += 2) 86 { 87 auto p = find_end_snake_of_further_reaching_dpath<true>(a, N, b, M, V1, max_D, k1, eq); 88 V1[k1] = p.u; 89 if ((delta % 2 != 0) and p.u <= N and p.v <= M and score(p) >= score(best)) 90 best = p; 91 } 92 for (int k2 = -max_D; k2 <= max_D; k2 += 2) 93 { 94 auto p = find_end_snake_of_further_reaching_dpath<false>(a, N, b, M, V2, max_D, k2, eq); 95 V2[k2] = p.u; 96 if ((delta % 2 == 0) and p.u <= N and p.v <= M and score(p) >= score(best)) 97 best = {p.x, p.y, p.u, p.v, (Snake::Op)(p.op + Snake::RevAdd)}; 98 } 99 100 if (best.op >= Snake::RevAdd) // reverse the snake now, as we were comparing snake length 101 best = { N - best.u, M - best.v, N - best.x , M - best.y, best.op }; 102 return best; 103 } 104 105 enum class DiffOp 106 { 107 Keep, 108 Add, 109 Remove 110 }; 111 112 template<typename IteratorA, typename IteratorB, typename Equal, typename OnDiff> 113 void find_diff_rec(IteratorA a, int begA, int endA, 114 IteratorB b, int begB, int endB, 115 int* V1, int* V2, int cost_limit, 116 Equal&& eq, OnDiff&& on_diff) 117 { 118 auto on_diff_ifn = [&](DiffOp op, int len) { 119 if (len != 0) 120 on_diff(op, len); 121 }; 122 123 int prefix_len = 0; 124 while (begA != endA and begB != endB and eq(a[begA], b[begB])) 125 ++begA, ++begB, ++prefix_len; 126 127 int suffix_len = 0; 128 while (begA != endA and begB != endB and eq(a[endA-1], b[endB-1])) 129 --endA, --endB, ++suffix_len; 130 131 on_diff_ifn(DiffOp::Keep, prefix_len); 132 133 const auto lenA = endA - begA, lenB = endB - begB; 134 135 if (lenA == 0) 136 on_diff_ifn(DiffOp::Add, lenB); 137 else if (lenB == 0) 138 on_diff_ifn(DiffOp::Remove, lenA); 139 else 140 { 141 auto snake = find_middle_snake(a + begA, lenA, b + begB, lenB, V1, V2, cost_limit, eq); 142 kak_assert(snake.u <= lenA and snake.v <= lenB); 143 144 find_diff_rec(a, begA, begA + snake.x - (int)(snake.op == Snake::Del), 145 b, begB, begB + snake.y - (int)(snake.op == Snake::Add), 146 V1, V2, cost_limit, eq, on_diff); 147 148 if (snake.op == Snake::Add) 149 on_diff_ifn(DiffOp::Add, 1); 150 if (snake.op == Snake::Del) 151 on_diff_ifn(DiffOp::Remove, 1); 152 153 on_diff_ifn(DiffOp::Keep, snake.u - snake.x); 154 155 if (snake.op == Snake::RevAdd) 156 on_diff_ifn(DiffOp::Add, 1); 157 if (snake.op == Snake::RevDel) 158 on_diff_ifn(DiffOp::Remove, 1); 159 160 find_diff_rec(a, begA + snake.u + (int)(snake.op == Snake::RevDel), endA, 161 b, begB + snake.v + (int)(snake.op == Snake::RevAdd), endB, 162 V1, V2, cost_limit, eq, on_diff); 163 } 164 165 on_diff_ifn(DiffOp::Keep, suffix_len); 166 } 167 168 struct Diff 169 { 170 DiffOp op; 171 int len; 172 }; 173 174 template<typename IteratorA, typename IteratorB, typename OnDiff, typename Equal = std::equal_to<>> 175 void for_each_diff(IteratorA a, int N, IteratorB b, int M, OnDiff&& on_diff, Equal&& eq = Equal{}) 176 { 177 const int max = 2 * (N + M) + 1; 178 UniquePtr<int[]> data(new int[2*max]); 179 constexpr int cost_limit = 1000; 180 181 Diff last{}; 182 find_diff_rec(a, 0, N, b, 0, M, &data[N+M], &data[max + N+M], cost_limit, eq, 183 [&last, &on_diff](DiffOp op, int len) { 184 if (last.op == op) 185 last.len += len; 186 else 187 { 188 if (last.len != 0) 189 on_diff(last.op, last.len); 190 last = Diff{op, len}; 191 } 192 }); 193 if (last.op != DiffOp{} or last.len != 0) 194 on_diff(last.op, last.len); 195 } 196 197 } 198 199 #endif // diff_hh_INCLUDED