kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

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