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. Args: text1: Old string to be diffed. text2: New string to be diffed.
(self, text1, text2, deadline, len_text1, len_text2)
| 248 | return self.bisect(text1, text2, deadline, len_text1, len_text2) |
| 249 | |
| 250 | def bisect(self, text1, text2, deadline, len_text1, len_text2): |
| 251 | """ |
| 252 | Find the 'middle snake' of a diff, split the problem in two |
| 253 | and return the recursively constructed diff. |
| 254 | See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations. |
| 255 | |
| 256 | Args: |
| 257 | text1: Old string to be diffed. |
| 258 | text2: New string to be diffed. |
| 259 | deadline: Time at which to bail if not yet complete. |
| 260 | |
| 261 | Returns: |
| 262 | Array of diff tuples. |
| 263 | """ |
| 264 | |
| 265 | max_d = (len_text1 + len_text2 + 1) // 2 |
| 266 | v_offset = max_d |
| 267 | v_length = 2 * max_d |
| 268 | v1 = [-1] * v_length |
| 269 | v1[v_offset + 1] = 0 |
| 270 | v2 = v1[:] |
| 271 | delta = len_text1 - len_text2 |
| 272 | # If the total number of characters is odd, then the front path will |
| 273 | # collide with the reverse path. |
| 274 | front = (delta % 2 != 0) |
| 275 | # Offsets for start and end of k loop. |
| 276 | # Prevents mapping of space beyond the grid. |
| 277 | k1start = 0 |
| 278 | k1end = 0 |
| 279 | k2start = 0 |
| 280 | k2end = 0 |
| 281 | for d in range(max_d): |
| 282 | # Bail out if deadline is reached. |
| 283 | if time.time() > deadline: |
| 284 | break |
| 285 | |
| 286 | # Walk the front path one step. |
| 287 | for k1 in range(-d + k1start, d + 1 - k1end, 2): |
| 288 | k1_offset = v_offset + k1 |
| 289 | |
| 290 | if k1 == -d or (k1 != d and v1[k1_offset - 1] < v1[k1_offset + 1]): |
| 291 | x1 = v1[k1_offset + 1] |
| 292 | else: |
| 293 | x1 = v1[k1_offset - 1] + 1 |
| 294 | |
| 295 | y1 = x1 - k1 |
| 296 | |
| 297 | while (x1 < len_text1 and y1 < len_text2 and text1[x1] == text2[y1]): |
| 298 | x1 += 1 |
| 299 | y1 += 1 |
| 300 | |
| 301 | v1[k1_offset] = x1 |
| 302 | |
| 303 | if x1 > len_text1: |
| 304 | # Ran off the right of the graph. |
| 305 | k1end += 2 |
| 306 | |
| 307 | elif y1 > len_text2: |