Remove uses of reverse_iterator in diff implementation

2 files changed, 22 insertions, 18 deletions

diff --git a/src/diff.hh b/src/diff.hh
index 20fd53d1..8d1abdc6 100644
--- a/src/diff.hh
+++ b/src/diff.hh
@@ -5,11 +5,8 @@
 // "An O(ND) Difference Algorithm and Its Variations"
 // (http://xmailserver.org/diff2.pdf)
 
-#include "array_view.hh"
-
 #include <algorithm>
 #include <functional>
-#include <iterator>
 #include <memory>
 
 namespace Kakoune
@@ -24,7 +21,7 @@ struct Snake
     enum Op { Add, Del, RevAdd, RevDel } op;
 };
 
-template<typename IteratorA, typename IteratorB, typename Equal>
+template<bool forward, typename IteratorA, typename IteratorB, typename Equal>
 Snake find_end_snake_of_further_reaching_dpath(IteratorA a, int N, IteratorB b, int M,
                                                const int* V, const int D, const int k, Equal eq)
 {
@@ -37,9 +34,13 @@ Snake find_end_snake_of_further_reaching_dpath(IteratorA a, int N, IteratorB b,
     // we are by construction on diagonal k, so our position along b (y) is x - k.
     const int y = x - k;
 
+    auto at = [](auto&& base, int index, int size) -> decltype(auto) {
+        return forward ? base[index] : base[size - 1 - index];
+    };
+
     int u = x, v = y;
     // follow end snake along diagonal k
-    while (u < N and v < M and eq(a[u], b[v]))
+    while (u < N and v < M and eq(at(a, u, N), at(b, v, M)))
         ++u, ++v;
 
     return { x, y, u, v, add ? Snake::Add : Snake::Del };
@@ -53,14 +54,12 @@ Snake find_middle_snake(IteratorA a, int N, IteratorB b, int M,
     V1[1] = 0;
     V2[1] = 0;
 
-    std::reverse_iterator<IteratorA> ra{a + N};
-    std::reverse_iterator<IteratorB> rb{b + M};
     const int max_D = std::min((M + N + 1) / 2 + 1, cost_limit);
     for (int D = 0; D < max_D; ++D)
     {
         for (int k1 = -D; k1 <= D; k1 += 2)
         {
-            auto p = find_end_snake_of_further_reaching_dpath(a, N, b, M, V1, D, k1, eq);
+            auto p = find_end_snake_of_further_reaching_dpath<true>(a, N, b, M, V1, D, k1, eq);
             V1[k1] = p.u;
 
             const int k2 = -(k1 - delta);
@@ -70,7 +69,7 @@ Snake find_middle_snake(IteratorA a, int N, IteratorB b, int M,
 
         for (int k2 = -D; k2 <= D; k2 += 2)
         {
-            auto p = find_end_snake_of_further_reaching_dpath(ra, N, rb, M, V2, D, k2, eq);
+            auto p = find_end_snake_of_further_reaching_dpath<false>(a, N, b, M, V2, D, k2, eq);
             V2[k2] = p.u;
 
             const int k1 = -(k2 - delta);
@@ -85,14 +84,14 @@ Snake find_middle_snake(IteratorA a, int N, IteratorB b, int M,
     auto score = [](const Snake& s) { return s.u + s.v; };
     for (int k1 = -max_D; k1 <= max_D; k1 += 2)
     {
-        auto p = find_end_snake_of_further_reaching_dpath(a, N, b, M, V1, max_D, k1, eq);
+        auto p = find_end_snake_of_further_reaching_dpath<true>(a, N, b, M, V1, max_D, k1, eq);
         V1[k1] = p.u;
         if ((delta % 2 != 0) and p.u <= N and p.v <= M and score(p) >= score(best))
             best = p;
     }
     for (int k2 = -max_D; k2 <= max_D; k2 += 2)
     {
-        auto p = find_end_snake_of_further_reaching_dpath(ra, N, rb, M, V2, max_D, k2, eq);
+        auto p = find_end_snake_of_further_reaching_dpath<false>(a, N, b, M, V2, max_D, k2, eq);
         V2[k2] = p.u;
         if ((delta % 2 == 0) and p.u <= N and p.v <= M and score(p) >= score(best))
             best = {p.x, p.y, p.u, p.v, (Snake::Op)(p.op + Snake::RevAdd)};
diff --git a/src/unit_tests.cc b/src/unit_tests.cc
index 694ad041..5b693026 100644
--- a/src/unit_tests.cc
+++ b/src/unit_tests.cc
@@ -17,7 +17,7 @@ UnitTest test_utf8{[]()
 
 UnitTest test_diff{[]()
 {
-    struct Diff{DiffOp op; int len; int posB;};
+    struct Diff{DiffOp op; int len; int posB = 0;};
     auto check_diff = [](StringView a, StringView b, std::initializer_list<Diff> diffs) {
         size_t count = 0;
         for_each_diff(a.begin(), (int)a.length(), b.begin(), (int)b.length(),
@@ -28,14 +28,19 @@ UnitTest test_diff{[]()
                       });
         kak_assert(count == diffs.size());
     };
-    check_diff("a?", "!", {{DiffOp::Remove, 1, 0}, {DiffOp::Add, 1, 0}, {DiffOp::Remove, 1, 0}});
-    check_diff("abcde", "cd", {{DiffOp::Remove, 2, 0}, {DiffOp::Keep, 2, 0}, {DiffOp::Remove, 1, 0}});
-    check_diff("abcd", "cdef", {{DiffOp::Remove, 2, 0}, {DiffOp::Keep, 2, 0}, {DiffOp::Add, 2, 2}});
+    check_diff("a?", "!", {{DiffOp::Remove, 1}, {DiffOp::Add, 1}, {DiffOp::Remove, 1}});
+    check_diff("abcde", "cd", {{DiffOp::Remove, 2}, {DiffOp::Keep, 2}, {DiffOp::Remove, 1}});
+    check_diff("abcd", "cdef", {{DiffOp::Remove, 2}, {DiffOp::Keep, 2}, {DiffOp::Add, 2, 2}});
 
     check_diff("mais que fais la police", "mais ou va la police",
-               {{DiffOp::Keep, 5, 0}, {DiffOp::Remove, 1, 0}, {DiffOp::Add, 1, 5}, {DiffOp::Keep, 1, 0},
-                {DiffOp::Remove, 1, 0}, {DiffOp::Keep, 1, 0}, {DiffOp::Add, 1, 8}, {DiffOp::Remove, 1, 0}, 
-                {DiffOp::Keep, 1, 0}, {DiffOp::Remove, 2, 0}, {DiffOp::Keep, 10, 0}} );
+               {{DiffOp::Keep, 5}, {DiffOp::Remove, 1}, {DiffOp::Add, 1, 5}, {DiffOp::Keep, 1},
+                {DiffOp::Remove, 1}, {DiffOp::Keep, 1}, {DiffOp::Add, 1, 8}, {DiffOp::Remove, 1}, 
+                {DiffOp::Keep, 1}, {DiffOp::Remove, 2}, {DiffOp::Keep, 10}} );
+
+    check_diff("abcdefghijk",  "1cdef2hij34",
+               {{DiffOp::Remove, 2}, {DiffOp::Add, 1, 0}, {DiffOp::Keep, 4}, {DiffOp::Remove, 1},
+                {DiffOp::Add, 1, 5}, {DiffOp::Keep, 3}, {DiffOp::Add, 2, 9}, {DiffOp::Remove, 1}});
+
 }};
 
 UnitTest* UnitTest::list = nullptr;