Lines Matching +full:right +full:- +full:most
35 * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
61 * k-1 0 1 2 3 4 5
63 * 0 o-o-o-o-o-o
65 * 1 o-o-o-o-o-o
67 * 2 o-o-o-o-o-o
69 * 3 o-o-o-o-o-o
71 * 4 o-o-o-o-o-o c1
73 * c-1 c0
75 * Moving right means delete an atom from the left-hand-side,
76 * Moving down means add an atom from the right-hand-side.
81 * bottom right, remembers all steps, and then backtraces to find the shortest
85 * Myers adds a variant that uses linear space -- note, not linear time, only
100 * ----+--------------------------------------------
108 * 1 | 1,0 4,3 >= 4,3 5,4<-- 0
110 * 0 | -->0,0 3,3 4,4 -1
112 * -1 | 0,1 1,2 3,4 -2
114 * -2 | 0,2 -3
117 * | forward-> <-backward
120 * x = atom index in left-side source, y = atom index in the right-side source.
123 * most left.len + 1 + right.len items. Note that each d step occupies either
130 * y = x - k
132 * in the left-hand file, and the y coordinate, i.e. position in the right-hand
143 * 0 o-o-o-o-o
145 * 1 o-o-o-o-o
147 * 2 o-o-o-o-o
149 * 3 o-o-o-o-*-o *: forward and backward meet here
151 * 4 o-o
157 * 0 o-o
159 * 1 o-b b: backward d=1 first reaches here (sliding up the snake)
163 * 3 f-o tail 3,3 to 4,3.
165 * 3 o-*
172 * A B C D E -A
173 * 0 o-o +X
176 * B \ -D
177 * 2 o -E
179 * 3 o-o-o
185 #define xk_to_y(X, K) ((X) - (K))
186 #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
188 #define c_to_k(C, DELTA) ((C) - (DELTA))
192 * right: the right side to diff against.
200 * Since forwards is done first, kd_backward will be valid for d -
213 struct diff_data *left, struct diff_data *right, in diff_divide_myers_forward() argument
217 int delta = (int)right->atoms.len - (int)left->atoms.len; in diff_divide_myers_forward()
225 for (k = d; k >= -d; k -= 2) { in diff_divide_myers_forward()
226 if (k < -(int)right->atoms.len || k > (int)left->atoms.len) { in diff_divide_myers_forward()
247 /* Favoring "-" lines first means favoring moving rightwards in in diff_divide_myers_forward()
249 * For this, all k should derive from k - 1, only the bottom in diff_divide_myers_forward()
250 * most k derive from k + 1: in diff_divide_myers_forward()
253 * ----+---------------- in diff_divide_myers_forward()
255 * 2 | 2,0 <-- from prev_k = 2 - 1 = 1 in diff_divide_myers_forward()
259 * 0 | -->0,0 3,3 in diff_divide_myers_forward()
261 * -1 | 0,1 <-- bottom most for d=1 from in diff_divide_myers_forward()
262 * | \\ prev_k = -1 + 1 = 0 in diff_divide_myers_forward()
263 * -2 | 0,2 <-- bottom most for d=2 from in diff_divide_myers_forward()
264 * prev_k = -2 + 1 = -1 in diff_divide_myers_forward()
268 * If k == d, there is no k + 1 and k - 1 is the only option. in diff_divide_myers_forward()
270 * k + 1 if k - 1 is outside the graph. in diff_divide_myers_forward()
272 else if (k > -d in diff_divide_myers_forward()
274 || (k - 1 >= -(int)right->atoms.len in diff_divide_myers_forward()
275 && kd_forward[k - 1] >= kd_forward[k + 1]))) { in diff_divide_myers_forward()
276 /* Advance from k - 1. in diff_divide_myers_forward()
277 * From position prev_k, step to the right in the Myers in diff_divide_myers_forward()
280 int prev_k = k - 1; in diff_divide_myers_forward()
285 /* The bottom most one. in diff_divide_myers_forward()
290 * (since we're deriving y from y = x - k). in diff_divide_myers_forward()
300 while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) { in diff_divide_myers_forward()
303 &left->atoms.head[x], in diff_divide_myers_forward()
304 &right->atoms.head[ in diff_divide_myers_forward()
315 debug(" down %d similar lines\n", x - x_before_slide); in diff_divide_myers_forward()
321 for (fi = d; fi >= k; fi--) { in diff_divide_myers_forward()
323 kd_forward[fi], kd_forward[fi] - fi); in diff_divide_myers_forward()
329 if (x < 0 || x > left->atoms.len in diff_divide_myers_forward()
330 || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len) in diff_divide_myers_forward()
339 * ----+---------------- ---------------- in diff_divide_myers_forward()
347 * 1 | 1,0 5,4<-- 0 in diff_divide_myers_forward()
349 * 0 | -->0,0 3,3====4,4 -1 in diff_divide_myers_forward()
351 * -1 | 0,1 -2 in diff_divide_myers_forward()
353 * -2 | 0,2 -3 in diff_divide_myers_forward()
356 * If the delta is even, they end up off-by-one, i.e. on in diff_divide_myers_forward()
360 * ----+---------------- ---------------- in diff_divide_myers_forward()
368 * 0 | -->0,0 3,3 4,4<-- 0 in diff_divide_myers_forward()
370 * -1 | 0,1 3,4 -1 in diff_divide_myers_forward()
372 * -2 | 0,2 -2 in diff_divide_myers_forward()
381 * d - 1. Can't do this for d == 0. */ in diff_divide_myers_forward()
382 int backwards_d = d - 1; in diff_divide_myers_forward()
400 if (c >= -backwards_d && c <= backwards_d) { in diff_divide_myers_forward()
404 * we've found a midpoint / a mid-box. in diff_divide_myers_forward()
407 * endpoints of the mid-snake are not the two points in in diff_divide_myers_forward()
424 * o-o-o o in diff_divide_myers_forward()
432 * o-o-o in diff_divide_myers_forward()
437 * anymore, so picking a mid-snake from M to X would in diff_divide_myers_forward()
440 * The correct mid-snake is between M and A. M is where in diff_divide_myers_forward()
448 /* met after sliding up a mid-snake */ in diff_divide_myers_forward()
457 /* met after a side step, non-identical in diff_divide_myers_forward()
470 debug("HIT x=(%u,%u) - y=(%u,%u)\n", in diff_divide_myers_forward()
471 meeting_snake->left_start, in diff_divide_myers_forward()
472 meeting_snake->right_start, in diff_divide_myers_forward()
473 meeting_snake->left_end, in diff_divide_myers_forward()
474 meeting_snake->right_end); in diff_divide_myers_forward()
475 debug_dump_myers_graph(left, right, NULL, in diff_divide_myers_forward()
477 kd_backward, d-1); in diff_divide_myers_forward()
489 * right: the right side to diff against.
504 * right of the Myers graph (left.len, right.len).
511 struct diff_data *left, struct diff_data *right, in diff_divide_myers_backward() argument
515 int delta = (int)right->atoms.len - (int)left->atoms.len; in diff_divide_myers_backward()
524 for (c = d; c >= -d; c -= 2) { in diff_divide_myers_backward()
525 if (c < -(int)left->atoms.len || c > (int)right->atoms.len) { in diff_divide_myers_backward()
538 * yet, get the initial x from the bottom right of the in diff_divide_myers_backward()
540 x = left->atoms.len; in diff_divide_myers_backward()
544 /* Favoring "-" lines first means favoring moving rightwards in in diff_divide_myers_backward()
546 * For this, all c should derive from c - 1, only the bottom in diff_divide_myers_backward()
547 * most c derive from c + 1: in diff_divide_myers_backward()
550 * --------------------------------------------------- in diff_divide_myers_backward()
554 * from prev_c = c - 1 --> 5,2 2 in diff_divide_myers_backward()
558 * 4,3 5,4<-- 0 in diff_divide_myers_backward()
560 * bottom most for d=1 from c + 1 --> 4,4 -1 in diff_divide_myers_backward()
562 * bottom most for d=2 --> 3,4 -2 in diff_divide_myers_backward()
566 * If c == d, there is no c + 1 and c - 1 is the only option. in diff_divide_myers_backward()
568 * Also use c + 1 if c - 1 is outside the graph. in diff_divide_myers_backward()
570 else if (c > -d && (c == d in diff_divide_myers_backward()
571 || (c - 1 >= -(int)right->atoms.len in diff_divide_myers_backward()
572 && kd_backward[c - 1] <= kd_backward[c + 1]))) { in diff_divide_myers_backward()
575 * graph: y -= 1. in diff_divide_myers_backward()
578 * y = x - c + delta). in diff_divide_myers_backward()
580 int prev_c = c - 1; in diff_divide_myers_backward()
585 /* The bottom most one. in diff_divide_myers_backward()
587 * graph: x -= 1. in diff_divide_myers_backward()
592 x = prev_x - 1; in diff_divide_myers_backward()
598 debug("c=%d x-1=%d Yb-1=%d-1=%d\n", c, x-1, xc_to_y(x, c, in diff_divide_myers_backward()
600 xc_to_y(x, c, delta)-1); in diff_divide_myers_backward()
603 debug_dump_atom(left, right, &left->atoms.head[x-1]); in diff_divide_myers_backward()
607 debug_dump_atom(right, left, in diff_divide_myers_backward()
608 &right->atoms.head[xc_to_y(x, c, delta)-1]); in diff_divide_myers_backward()
615 &left->atoms.head[x-1], in diff_divide_myers_backward()
616 &right->atoms.head[ in diff_divide_myers_backward()
617 xc_to_y(x, c, delta)-1]); in diff_divide_myers_backward()
622 x--; in diff_divide_myers_backward()
627 debug(" up %d similar lines\n", x_before_slide - x); in diff_divide_myers_backward()
632 for (fi = d; fi >= c; fi--) { in diff_divide_myers_backward()
636 kd_backward[fi] - fi + delta); in diff_divide_myers_backward()
641 if (x < 0 || x > left->atoms.len in diff_divide_myers_backward()
643 || xc_to_y(x, c, delta) > right->atoms.len) in diff_divide_myers_backward()
650 * the same state indexes -- note how this is different from in in diff_divide_myers_backward()
654 * ----+---------------- -------------------- in diff_divide_myers_backward()
664 * 0 | -->0,0 3,3====4,3 5,4<-- 0 in diff_divide_myers_backward()
666 * -1 | 0,1 4,4 -1 in diff_divide_myers_backward()
668 * -2 | 0,2 -2 in diff_divide_myers_backward()
670 * -3 in diff_divide_myers_backward()
671 * If the delta is odd, they end up off-by-one, i.e. on in diff_divide_myers_backward()
692 if (k >= -forwards_d && k <= forwards_d) { in diff_divide_myers_backward()
696 * we've found a midpoint / a mid-box. in diff_divide_myers_backward()
699 * endpoints of the mid-snake are not the two points in in diff_divide_myers_backward()
706 * o-o-o in diff_divide_myers_backward()
714 * o o-o-o in diff_divide_myers_backward()
727 * picking a mid-snake from M to X would yield a in diff_divide_myers_backward()
730 * The correct mid-snake is between M and A. M is where in diff_divide_myers_backward()
739 /* met after sliding down a mid-snake */ in diff_divide_myers_backward()
747 /* met after a side step, non-identical in diff_divide_myers_backward()
760 debug("HIT x=%u,%u - y=%u,%u\n", in diff_divide_myers_backward()
761 meeting_snake->left_start, in diff_divide_myers_backward()
762 meeting_snake->right_start, in diff_divide_myers_backward()
763 meeting_snake->left_end, in diff_divide_myers_backward()
764 meeting_snake->right_end); in diff_divide_myers_backward()
765 debug_dump_myers_graph(left, right, NULL, in diff_divide_myers_backward()
796 struct diff_data *left = &state->left; in diff_algo_myers_divide()
797 struct diff_data *right = &state->right; in diff_algo_myers_divide() local
803 debug("right:\n"); in diff_algo_myers_divide()
804 debug_dump(right); in diff_algo_myers_divide()
808 unsigned int max = left->atoms.len + right->atoms.len; in diff_algo_myers_divide()
812 if (state->kd_buf_size < kd_buf_size) { in diff_algo_myers_divide()
813 kd_buf = reallocarray(state->kd_buf, kd_buf_size, in diff_algo_myers_divide()
817 state->kd_buf = kd_buf; in diff_algo_myers_divide()
818 state->kd_buf_size = kd_buf_size; in diff_algo_myers_divide()
820 kd_buf = state->kd_buf; in diff_algo_myers_divide()
823 kd_buf[i] = -1; in diff_algo_myers_divide()
833 * It is then possible to index from -max/2 .. max/2. */ in diff_algo_myers_divide()
842 r = diff_divide_myers_forward(&found_midpoint, left, right, in diff_algo_myers_divide()
849 r = diff_divide_myers_backward(&found_midpoint, left, right, in diff_algo_myers_divide()
861 * the right, with a few useless matches here and there. */ in diff_algo_myers_divide()
867 int delta = (int)right->atoms.len - (int)left->atoms.len; in diff_algo_myers_divide()
882 debug_dump_myers_graph(left, right, NULL, in diff_algo_myers_divide()
886 for (i = d; i >= -d; i -= 2) { in diff_algo_myers_divide()
887 if (i >= -(int)right->atoms.len && i <= (int)left->atoms.len) { in diff_algo_myers_divide()
897 if (i >= -(int)left->atoms.len && i <= (int)right->atoms.len) { in diff_algo_myers_divide()
900 distance = (right->atoms.len - x) in diff_algo_myers_divide()
901 + (left->atoms.len - y); in diff_algo_myers_divide()
909 /* The myers-divide didn't meet in the middle. We just in diff_algo_myers_divide()
911 * advanced the most, and the backward path advanced the in diff_algo_myers_divide()
912 * most. Just divide at whichever one of those two is better. in diff_algo_myers_divide()
914 * o-o in diff_algo_myers_divide()
920 * F <-- cut here in diff_algo_myers_divide()
924 * or here --> B in diff_algo_myers_divide()
930 * o-o in diff_algo_myers_divide()
947 || x > left->atoms.len || y > right->atoms.len) in diff_algo_myers_divide()
972 mid_snake.left_start, mid_snake.left_end, left->atoms.len, in diff_algo_myers_divide()
974 right->atoms.len); in diff_algo_myers_divide()
976 /* Section before the mid-snake. */ in diff_algo_myers_divide()
977 debug("Section before the mid-snake\n"); in diff_algo_myers_divide()
979 struct diff_atom *left_atom = &left->atoms.head[0]; in diff_algo_myers_divide()
981 struct diff_atom *right_atom = &right->atoms.head[0]; in diff_algo_myers_divide()
993 /* Only left atoms and none on the right, they form a in diff_algo_myers_divide()
1000 /* No left atoms, only atoms on the right, they form a in diff_algo_myers_divide()
1009 * nothing before the mid-snake. */ in diff_algo_myers_divide()
1016 debug("the mid-snake\n"); in diff_algo_myers_divide()
1018 &left->atoms.head[mid_snake.left_start], in diff_algo_myers_divide()
1019 mid_snake.left_end - mid_snake.left_start, in diff_algo_myers_divide()
1020 &right->atoms.head[mid_snake.right_start], in diff_algo_myers_divide()
1021 mid_snake.right_end - mid_snake.right_start)) in diff_algo_myers_divide()
1025 /* Section after the mid-snake. */ in diff_algo_myers_divide()
1026 debug("Section after the mid-snake\n"); in diff_algo_myers_divide()
1030 left->atoms.len, right->atoms.len); in diff_algo_myers_divide()
1031 left_atom = &left->atoms.head[mid_snake.left_end]; in diff_algo_myers_divide()
1032 left_section_len = left->atoms.len - mid_snake.left_end; in diff_algo_myers_divide()
1033 right_atom = &right->atoms.head[mid_snake.right_end]; in diff_algo_myers_divide()
1034 right_section_len = right->atoms.len - mid_snake.right_end; in diff_algo_myers_divide()
1045 /* Only left atoms and none on the right, they form a in diff_algo_myers_divide()
1052 /* No left atoms, only atoms on the right, they form a in diff_algo_myers_divide()
1061 * nothing after the mid-snake. */ in diff_algo_myers_divide()
1073 * algo_config->permitted_state_size. */
1082 struct diff_data *left = &state->left; in diff_algo_myers()
1083 struct diff_data *right = &state->right; in diff_algo_myers() local
1089 debug("right:\n"); in diff_algo_myers()
1090 debug_dump(right); in diff_algo_myers()
1091 debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0); in diff_algo_myers()
1095 unsigned int max = left->atoms.len + right->atoms.len; in diff_algo_myers()
1102 || kd_state_size > algo_config->permitted_state_size) { in diff_algo_myers()
1104 kd_state_size, algo_config->permitted_state_size); in diff_algo_myers()
1108 if (state->kd_buf_size < kd_buf_size) { in diff_algo_myers()
1109 kd_buf = reallocarray(state->kd_buf, kd_buf_size, in diff_algo_myers()
1113 state->kd_buf = kd_buf; in diff_algo_myers()
1114 state->kd_buf_size = kd_buf_size; in diff_algo_myers()
1116 kd_buf = state->kd_buf; in diff_algo_myers()
1120 kd_buf[i] = -1; in diff_algo_myers()
1124 * It is then possible to index from -max .. max. */ in diff_algo_myers()
1129 int backtrack_d = -1; in diff_algo_myers()
1134 debug("-- %s d=%d\n", __func__, d); in diff_algo_myers()
1136 for (k = d; k >= -d; k -= 2) { in diff_algo_myers()
1137 if (k < -(int)right->atoms.len in diff_algo_myers()
1138 || k > (int)left->atoms.len) { in diff_algo_myers()
1141 if (k < -(int)right->atoms.len) in diff_algo_myers()
1143 " -(int)right->atoms.len %d\n", in diff_algo_myers()
1144 k, -(int)right->atoms.len); in diff_algo_myers()
1146 debug(" %d k > left->atoms.len %d\n", k, in diff_algo_myers()
1147 left->atoms.len); in diff_algo_myers()
1165 int *kd_prev_column = kd_column - kd_len; in diff_algo_myers()
1167 /* Favoring "-" lines first means favoring in diff_algo_myers()
1169 * For this, all k should derive from k - 1, in diff_algo_myers()
1170 * only the bottom most k derive from k + 1: in diff_algo_myers()
1173 * ----+---------------- in diff_algo_myers()
1175 * 2 | 2,0 <-- from in diff_algo_myers()
1176 * | / prev_k = 2 - 1 = 1 in diff_algo_myers()
1179 * 0 | -->0,0 3,3 in diff_algo_myers()
1181 * -1 | 0,1 <-- bottom most for d=1 in diff_algo_myers()
1182 * | \\ from prev_k = -1+1 = 0 in diff_algo_myers()
1183 * -2 | 0,2 <-- bottom most for in diff_algo_myers()
1185 * prev_k = -2+1 = -1 in diff_algo_myers()
1190 * If k == d, there is no k + 1 and k - 1 is the in diff_algo_myers()
1193 * larger x. Also use k + 1 if k - 1 is outside in diff_algo_myers()
1196 if (k > -d in diff_algo_myers()
1198 || (k - 1 >= -(int)right->atoms.len in diff_algo_myers()
1199 && kd_prev_column[k - 1] in diff_algo_myers()
1201 /* Advance from k - 1. in diff_algo_myers()
1203 * right in the Myers graph: x += 1. in diff_algo_myers()
1205 int prev_k = k - 1; in diff_algo_myers()
1209 /* The bottom most one. in diff_algo_myers()
1215 * x - k). in diff_algo_myers()
1224 while (x < left->atoms.len in diff_algo_myers()
1225 && xk_to_y(x, k) < right->atoms.len) { in diff_algo_myers()
1228 &left->atoms.head[x], in diff_algo_myers()
1229 &right->atoms.head[ in diff_algo_myers()
1239 if (x == left->atoms.len in diff_algo_myers()
1240 && xk_to_y(x, k) == right->atoms.len) { in diff_algo_myers()
1254 debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0); in diff_algo_myers()
1259 * ----+--------------------------------- in diff_algo_myers()
1267 * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0 in diff_algo_myers()
1269 * -1 | 0,1 3,4 in diff_algo_myers()
1271 * -2 | 0,2 in diff_algo_myers()
1277 for (d = backtrack_d, k = backtrack_k; d >= 0; d--) { in diff_algo_myers()
1284 * re-purpose kd_column[0] = x and kd_column[1] = y, in diff_algo_myers()
1295 int *kd_prev_column = kd_column - kd_len; in diff_algo_myers()
1297 /* When y == 0, backtracking downwards (k-1) is the only way. in diff_algo_myers()
1301 * ----+--------------------------------- in diff_algo_myers()
1309 * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, in diff_algo_myers()
1311 * -1 | 0,1 3,4 in diff_algo_myers()
1313 * -2 | 0,2__ in diff_algo_myers()
1318 && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) { in diff_algo_myers()
1319 k = k - 1; in diff_algo_myers()
1320 debug("prev k=k-1=%d x=%d y=%d\n", in diff_algo_myers()
1345 struct diff_atom *left_atom = &left->atoms.head[x]; in diff_algo_myers()
1346 int left_section_len = next_x - x; in diff_algo_myers()
1347 struct diff_atom *right_atom = &right->atoms.head[y]; in diff_algo_myers()
1348 int right_section_len = next_y - y; in diff_algo_myers()
1355 * lead-in is horizontal or vertical: in diff_algo_myers()
1358 * ----------> in diff_algo_myers()
1360 * r| o-o o in diff_algo_myers()
1367 * If left_section_len > right_section_len, the lead-in in diff_algo_myers()
1370 * If right_section_len > left_section_len, the lead-in in diff_algo_myers()
1371 * is vetical, so add one atom from the right before in diff_algo_myers()
1379 left_section_len--; in diff_algo_myers()
1386 right_section_len--; in diff_algo_myers()
1400 /* Only left atoms and none on the right, they form a in diff_algo_myers()
1407 /* No left atoms, only atoms on the right, they form a in diff_algo_myers()