+ // The lengths of the old and new chunks.
+ n_ = rp.o.length();
+ m_ = rp.n.length();
+
+ // Forward paths are centered around the 0-diagonal; reverse paths
+ // are centered around the diagonal N - M. (Delta in the article)
+ offset_reverse_diagonal_ = n_ - m_;
+
+ // If the offset is odd, only check for overlap while extending forward
+ // paths, otherwise only check while extending reverse paths.
+ odd_offset_ = (offset_reverse_diagonal_ % 2 != 0);
+
+ ofp.reset(rp.o.from);
+ nfp.reset(rp.n.from);
+ ofs.reset(DocIterator());
+ nfs.reset(DocIterator());
+ orp.reset(rp.o.to);
+ nrp.reset(rp.n.to);
+ ors.reset(DocIterator());
+ nrs.reset(DocIterator());
+
+ // In the formula below, the "+ 1" ensures we round like ceil()
+ int const D_max = (m_ + n_ + 1)/2;
+ // D is the number of horizontal and vertical steps, i.e.
+ // different characters in the old and new chunk.
+ for (int D = 0; D <= D_max; ++D) {
+ // to be used in the status messages
+ D_ = D;
+
+ // Forward and reverse paths
+ for (int f = 0; f < 2; ++f) {
+ Direction direction = f == 0 ? Forward : Backward;
+
+ // Diagonals between -D and D can be reached by a D-path
+ for (int k = -D; k <= D; k += 2) {
+ // Find the furthest reaching D-path on this diagonal
+ furthestDpathKdiagonal(D, k, rp, direction);
+
+ // Only check for overlap for forward paths if the offset is odd
+ // and only for reverse paths if the offset is even.
+ if (odd_offset_ == (direction == Forward)) {
+
+ // Do the forward and backward paths overlap ?
+ if (overlap(k, D - odd_offset_)) {
+ retrieveMiddleSnake(k, D, direction, middle_snake);
+ return 2 * D - odd_offset_;
+ }
+ }
+ if (abort_)
+ return 0;
+ }
+ }
+ }
+ // This should never be reached
+ return -2;