| 367 | |
| 368 | |
| 369 | QList<Diff> diff_match_patch::diff_bisect(const QString &text1, |
| 370 | const QString &text2, clock_t deadline) { |
| 371 | // Cache the text lengths to prevent multiple calls. |
| 372 | const int text1_length = text1.length(); |
| 373 | const int text2_length = text2.length(); |
| 374 | const int max_d = (text1_length + text2_length + 1) / 2; |
| 375 | const int v_offset = max_d; |
| 376 | const int v_length = 2 * max_d; |
| 377 | int *v1 = new int[v_length]; |
| 378 | int *v2 = new int[v_length]; |
| 379 | for (int x = 0; x < v_length; x++) { |
| 380 | v1[x] = -1; |
| 381 | v2[x] = -1; |
| 382 | } |
| 383 | v1[v_offset + 1] = 0; |
| 384 | v2[v_offset + 1] = 0; |
| 385 | const int delta = text1_length - text2_length; |
| 386 | // If the total number of characters is odd, then the front path will |
| 387 | // collide with the reverse path. |
| 388 | const bool front = (delta % 2 != 0); |
| 389 | // Offsets for start and end of k loop. |
| 390 | // Prevents mapping of space beyond the grid. |
| 391 | int k1start = 0; |
| 392 | int k1end = 0; |
| 393 | int k2start = 0; |
| 394 | int k2end = 0; |
| 395 | for (int d = 0; d < max_d; d++) { |
| 396 | // Bail out if deadline is reached. |
| 397 | if (clock() > deadline) { |
| 398 | break; |
| 399 | } |
| 400 | |
| 401 | // Walk the front path one step. |
| 402 | for (int k1 = -d + k1start; k1 <= d - k1end; k1 += 2) { |
| 403 | const int k1_offset = v_offset + k1; |
| 404 | int x1; |
| 405 | if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) { |
| 406 | x1 = v1[k1_offset + 1]; |
| 407 | } else { |
| 408 | x1 = v1[k1_offset - 1] + 1; |
| 409 | } |
| 410 | int y1 = x1 - k1; |
| 411 | while (x1 < text1_length && y1 < text2_length |
| 412 | && text1[x1] == text2[y1]) { |
| 413 | x1++; |
| 414 | y1++; |
| 415 | } |
| 416 | v1[k1_offset] = x1; |
| 417 | if (x1 > text1_length) { |
| 418 | // Ran off the right of the graph. |
| 419 | k1end += 2; |
| 420 | } else if (y1 > text2_length) { |
| 421 | // Ran off the bottom of the graph. |
| 422 | k1start += 2; |
| 423 | } else if (front) { |
| 424 | int k2_offset = v_offset + delta - k1; |
| 425 | if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) { |
| 426 | // Mirror x2 onto top-left coordinate system. |