Lines Matching +full:4 +full:k
61 * k-1 0 1 2 3 4 5
71 * 4 o-o-o-o-o-o c1
90 * d: the step number, starting with 0, a.k.a. the distance from the starting
92 * k: relative index in the state array for the forward scan, indicating on
101 * k= | c=
102 * 4 | 3
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
128 * Also note that from the diagonal index k and the x coordinate, the y
130 * y = x - k
135 * The two traces meet at 4,3, the first step (here found in the forward
141 * 0 1 2 3 4 5
151 * 4 o-o
155 * 0 1 2 3 4 5
163 * 3 f-o tail 3,3 to 4,3.
167 * 4 o *: forward and backward meet here
171 * 0 1 2 3 4 5
181 * 4 o
185 #define xk_to_y(X, K) ((X) - (K)) argument
187 #define k_to_c(K, DELTA) ((K) + (DELTA)) argument
218 int k; in diff_divide_myers_forward() local
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()
229 if (k < 0) { in diff_divide_myers_forward()
245 prev_y = xk_to_y(x, k); 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()
254 * k= | in diff_divide_myers_forward()
266 * Except when a k + 1 from a previous run already means a 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()
269 * If k < d, use k + 1 in case that yields a larger x. Also use 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()
273 && (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()
280 int prev_k = k - 1; in diff_divide_myers_forward()
288 * Incrementing y is achieved by decrementing k while in diff_divide_myers_forward()
290 * (since we're deriving y from y = x - k). in diff_divide_myers_forward()
292 int prev_k = k + 1; in diff_divide_myers_forward()
300 while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) { in diff_divide_myers_forward()
305 xk_to_y(x, k)]); in diff_divide_myers_forward()
312 kd_forward[k] = x; in diff_divide_myers_forward()
321 for (fi = d; fi >= k; fi--) { 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()
340 * k= | c= in diff_divide_myers_forward()
341 * 4 | 3 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()
366 * 1 | 1,0 4,3 1 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()
388 * c == k. in diff_divide_myers_forward()
390 * traversal starts on a different diagonal, and c = k shifted in diff_divide_myers_forward()
393 int c = k_to_c(k, delta); in diff_divide_myers_forward()
401 /* Current k is on a diagonal that exists in in diff_divide_myers_forward()
454 .right_end = xk_to_y(x, k), in diff_divide_myers_forward()
467 .right_end = xk_to_y(x, k), in diff_divide_myers_forward()
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()
655 * k= | c= in diff_divide_myers_backward()
656 * 4 | 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()
683 * and c = k shifted by the difference in length. in diff_divide_myers_backward()
685 int k = c_to_k(c, delta); in diff_divide_myers_backward() local
692 if (k >= -forwards_d && k <= forwards_d) { in diff_divide_myers_backward()
736 int forward_x = kd_forward[k]; in diff_divide_myers_backward()
744 .right_end = xk_to_y(x_before_slide, k), in diff_divide_myers_backward()
831 /* The 'k' axis in Myers spans positive and negative indexes, so point in diff_algo_myers_divide()
1122 /* The 'k' axis in Myers spans positive and negative indexes, so point in diff_algo_myers()
1131 int k; in diff_algo_myers() local
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()
1142 debug(" %d k <" 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()
1148 if (k < 0) { 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()
1174 * k= | in diff_algo_myers()
1187 * Except when a k + 1 from a previous run in diff_algo_myers()
1190 * If k == d, there is no k + 1 and k - 1 is the in diff_algo_myers()
1192 * If k < d, use k + 1 in case that yields a 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()
1197 && (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()
1200 >= kd_prev_column[k + 1]))) { in diff_algo_myers()
1201 /* Advance from k - 1. in diff_algo_myers()
1205 int prev_k = k - 1; in diff_algo_myers()
1213 * decrementing k while keeping the same in diff_algo_myers()
1215 * x - k). in diff_algo_myers()
1217 int prev_k = k + 1; in diff_algo_myers()
1225 && xk_to_y(x, k) < right->atoms.len) { in diff_algo_myers()
1230 xk_to_y(x, k)]); in diff_algo_myers()
1237 kd_column[k] = x; in diff_algo_myers()
1240 && xk_to_y(x, k) == right->atoms.len) { in diff_algo_myers()
1243 backtrack_k = k; in diff_algo_myers()
1244 debug("Reached the end at d = %d, k = %d\n", in diff_algo_myers()
1258 * | d= 0 1 2 3 4 in diff_algo_myers()
1260 * k= | in diff_algo_myers()
1265 * 1 | 1,0 4,3 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()
1274 * From (4,4) backwards, find the previous position that is the largest, and remember it. in diff_algo_myers()
1277 for (d = backtrack_d, k = backtrack_k; d >= 0; d--) { in diff_algo_myers()
1278 x = kd_column[k]; in diff_algo_myers()
1279 y = xk_to_y(x, k); in diff_algo_myers()
1297 /* When y == 0, backtracking downwards (k-1) is the only way. in diff_algo_myers()
1298 * When x == 0, backtracking upwards (k+1) is the only way. in diff_algo_myers()
1300 * | d= 0 1 2 3 4 in diff_algo_myers()
1302 * k= | in diff_algo_myers()
1307 * 1 | 1,0 4,3 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()
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()
1321 k, kd_prev_column[k], in diff_algo_myers()
1322 xk_to_y(kd_prev_column[k], k)); in diff_algo_myers()
1324 k = k + 1; in diff_algo_myers()
1325 debug("prev k=k+1=%d x=%d y=%d\n", in diff_algo_myers()
1326 k, kd_prev_column[k], in diff_algo_myers()
1327 xk_to_y(kd_prev_column[k], k)); in diff_algo_myers()