>>> adds = [[11, 1], [32, 1]] >>> dels = [[11, 11], [31, 32]] >>> _inverse_diff_result(adds, dels) ([[10, 1], [30, 2]], [[11, 11], [31, 31]])
(adds, dels)
| 1 | |
| 2 | def inverse_diff(adds, dels): |
| 3 | """ |
| 4 | >>> adds = [[11, 1], [32, 1]] |
| 5 | >>> dels = [[11, 11], [31, 32]] |
| 6 | >>> _inverse_diff_result(adds, dels) |
| 7 | ([[10, 1], [30, 2]], [[11, 11], [31, 31]]) |
| 8 | """ |
| 9 | diff = 0 |
| 10 | add_ptr, del_ptr = 0, 0 |
| 11 | num_adds, num_dels = len(adds), len(dels) |
| 12 | inv_adds, inv_dels = [], [] |
| 13 | |
| 14 | def _handle_a(a): |
| 15 | nonlocal diff |
| 16 | inv_dels.append([diff + a[0] + 1, diff + a[0] + a[1]]) |
| 17 | diff += a[1] |
| 18 | |
| 19 | def _handle_d(d): |
| 20 | nonlocal diff |
| 21 | inv_adds.append([diff + d[0] - 1, d[1] - d[0] + 1]) |
| 22 | diff -= (d[1] - d[0] + 1) |
| 23 | |
| 24 | while add_ptr < num_adds or del_ptr < num_dels: |
| 25 | if add_ptr < num_adds and del_ptr < num_dels: |
| 26 | if adds[add_ptr][0] < dels[del_ptr][0]: |
| 27 | _handle_a(adds[add_ptr]) |
| 28 | add_ptr += 1 |
| 29 | else: |
| 30 | _handle_d(dels[del_ptr]) |
| 31 | del_ptr += 1 |
| 32 | elif add_ptr < num_adds and del_ptr >= num_dels: |
| 33 | # we have finished dels |
| 34 | _handle_a(adds[add_ptr]) |
| 35 | add_ptr += 1 |
| 36 | else: |
| 37 | # we have finished adds |
| 38 | _handle_d(dels[del_ptr]) |
| 39 | del_ptr += 1 |
| 40 | |
| 41 | return inv_adds, inv_dels |