Find the 'middle snake' of a diff, split the problem in two and return the recursively constructed diff. See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations. @param text1 Old string to be diffed. @param text2 New string to be diffed. @param deadline Time at which to bail if not y
(String text1, String text2,
long deadline)
| 366 | * @return LinkedList of Diff objects. |
| 367 | */ |
| 368 | public LinkedList<Diff> diff_bisect(String text1, String text2, |
| 369 | long deadline) { |
| 370 | // Cache the text lengths to prevent multiple calls. |
| 371 | int text1_length = text1.length(); |
| 372 | int text2_length = text2.length(); |
| 373 | int max_d = (text1_length + text2_length + 1) / 2; |
| 374 | int v_offset = max_d; |
| 375 | int v_length = 2 * max_d; |
| 376 | int[] v1 = new int[v_length]; |
| 377 | int[] v2 = new int[v_length]; |
| 378 | for (int x = 0; x < v_length; x++) { |
| 379 | v1[x] = -1; |
| 380 | v2[x] = -1; |
| 381 | } |
| 382 | v1[v_offset + 1] = 0; |
| 383 | v2[v_offset + 1] = 0; |
| 384 | int delta = text1_length - text2_length; |
| 385 | // If the total number of characters is odd, then the front path will |
| 386 | // collide with the reverse path. |
| 387 | boolean front = (delta % 2 != 0); |
| 388 | // Offsets for start and end of k loop. |
| 389 | // Prevents mapping of space beyond the grid. |
| 390 | int k1start = 0; |
| 391 | int k1end = 0; |
| 392 | int k2start = 0; |
| 393 | int k2end = 0; |
| 394 | for (int d = 0; d < max_d; d++) { |
| 395 | // Bail out if deadline is reached. |
| 396 | if (System.currentTimeMillis() > deadline) { |
| 397 | break; |
| 398 | } |
| 399 | |
| 400 | // Walk the front path one step. |
| 401 | for (int k1 = -d + k1start; k1 <= d - k1end; k1 += 2) { |
| 402 | int k1_offset = v_offset + k1; |
| 403 | int x1; |
| 404 | if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) { |
| 405 | x1 = v1[k1_offset + 1]; |
| 406 | } else { |
| 407 | x1 = v1[k1_offset - 1] + 1; |
| 408 | } |
| 409 | int y1 = x1 - k1; |
| 410 | while (x1 < text1_length && y1 < text2_length |
| 411 | && text1.charAt(x1) == text2.charAt(y1)) { |
| 412 | x1++; |
| 413 | y1++; |
| 414 | } |
| 415 | v1[k1_offset] = x1; |
| 416 | if (x1 > text1_length) { |
| 417 | // Ran off the right of the graph. |
| 418 | k1end += 2; |
| 419 | } else if (y1 > text2_length) { |
| 420 | // Ran off the bottom of the graph. |
| 421 | k1start += 2; |
| 422 | } else if (front) { |
| 423 | int k2_offset = v_offset + delta - k1; |
| 424 | if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) { |
| 425 | // Mirror x2 onto top-left coordinate system. |
no test coverage detected