Lines Matching refs:first
79 tr_insertionsort(const saidx_t *ISAd, saidx_t *first, saidx_t *last) { in tr_insertionsort() argument
83 for(a = first + 1; a < last; ++a) { in tr_insertionsort()
85 do { *(b + 1) = *b; } while((first <= --b) && (*b < 0)); in tr_insertionsort()
86 if(b < first) { break; } in tr_insertionsort()
167 tr_pivot(const saidx_t *ISAd, saidx_t *first, saidx_t *last) { in tr_pivot() argument
171 t = last - first; in tr_pivot()
172 middle = first + t / 2; in tr_pivot()
176 return tr_median3(ISAd, first, middle, last - 1); in tr_pivot()
179 return tr_median5(ISAd, first, first + t, middle, last - 1 - t, last - 1); in tr_pivot()
183 first = tr_median3(ISAd, first, first + t, first + (t << 1)); in tr_pivot()
186 return tr_median3(ISAd, first, middle, last); in tr_pivot()
223 saidx_t *first, saidx_t *middle, saidx_t *last, in tr_partition() argument
253 if((s = a - first) > (t = b - a)) { s = t; } in tr_partition()
254 for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } in tr_partition()
257 first += (b - a), last -= (d - c); in tr_partition()
259 *pa = first, *pb = last; in tr_partition()
265 saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, in tr_copy() argument
273 for(c = first, d = a - 1; c <= d; ++c) { in tr_copy()
290 saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, in tr_partialcopy() argument
298 for(c = first, d = a - 1; c <= d; ++c) { in tr_partialcopy()
308 for(e = d; first <= e; --e) { in tr_partialcopy()
328 saidx_t *SA, saidx_t *first, saidx_t *last, in tr_introsort() argument
339 for(ssize = 0, limit = tr_ilg(last - first);;) { in tr_introsort()
344 tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1); in tr_introsort()
348 for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } in tr_introsort()
357 STACK_PUSH5(ISAd - incr, first, last, -2, trlink); in tr_introsort()
360 if((a - first) <= (last - b)) { in tr_introsort()
361 if(1 < (a - first)) { in tr_introsort()
363 last = a, limit = tr_ilg(a - first); in tr_introsort()
365 first = b, limit = tr_ilg(last - b); in tr_introsort()
367 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
371 STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink); in tr_introsort()
372 first = b, limit = tr_ilg(last - b); in tr_introsort()
373 } else if(1 < (a - first)) { in tr_introsort()
374 last = a, limit = tr_ilg(a - first); in tr_introsort()
376 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
383 tr_copy(ISA, SA, first, a, b, last, ISAd - ISA); in tr_introsort()
386 tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA); in tr_introsort()
388 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
391 if(0 <= *first) { in tr_introsort()
392 a = first; in tr_introsort()
394 first = a; in tr_introsort()
396 if(first < last) { in tr_introsort()
397 a = first; do { *a = ~*a; } while(*++a < 0); in tr_introsort()
398 next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1; in tr_introsort()
399 if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } } in tr_introsort()
402 if(trbudget_check(budget, a - first)) { in tr_introsort()
403 if((a - first) <= (last - a)) { in tr_introsort()
408 STACK_PUSH5(ISAd + incr, first, a, next, trlink); in tr_introsort()
409 first = a, limit = -3; in tr_introsort()
417 first = a, limit = -3; in tr_introsort()
419 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
423 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
429 if((last - first) <= TR_INSERTIONSORT_THRESHOLD) { in tr_introsort()
430 tr_insertionsort(ISAd, first, last); in tr_introsort()
436 tr_heapsort(ISAd, first, last - first); in tr_introsort()
437 for(a = last - 1; first < a; a = b) { in tr_introsort()
438 for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; } in tr_introsort()
445 a = tr_pivot(ISAd, first, last); in tr_introsort()
446 SWAP(*first, *a); in tr_introsort()
447 v = ISAd[*first]; in tr_introsort()
450 tr_partition(ISAd, first, first + 1, last, &a, &b, v); in tr_introsort()
451 if((last - first) != (b - a)) { in tr_introsort()
455 for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } in tr_introsort()
460 if((a - first) <= (last - b)) { in tr_introsort()
462 if(1 < (a - first)) { in tr_introsort()
468 first = b; in tr_introsort()
470 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
472 } else if((a - first) <= (b - a)) { in tr_introsort()
473 if(1 < (a - first)) { in tr_introsort()
479 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
483 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
484 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
487 if((a - first) <= (b - a)) { in tr_introsort()
490 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
491 first = b; in tr_introsort()
492 } else if(1 < (a - first)) { in tr_introsort()
496 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
500 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
502 first = b; in tr_introsort()
504 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
505 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
508 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
510 ISAd += incr, first = a, last = b, limit = next; in tr_introsort()
515 if((a - first) <= (last - b)) { in tr_introsort()
516 if(1 < (a - first)) { in tr_introsort()
520 first = b; in tr_introsort()
522 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
526 STACK_PUSH5(ISAd, first, a, limit, trlink); in tr_introsort()
527 first = b; in tr_introsort()
528 } else if(1 < (a - first)) { in tr_introsort()
531 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
536 if(trbudget_check(budget, last - first)) { in tr_introsort()
537 limit = tr_ilg(last - first), ISAd += incr; in tr_introsort()
540 STACK_POP5(ISAd, first, last, limit, trlink); in tr_introsort()
557 saidx_t *first, *last; in trsort() local
564 first = SA; in trsort()
568 if((t = *first) < 0) { first -= t; skip += t; } in trsort()
570 if(skip != 0) { *(first + skip) = skip; skip = 0; } in trsort()
572 if(1 < (last - first)) { in trsort()
574 tr_introsort(ISA, ISAd, SA, first, last, &budget); in trsort()
576 else { skip = first - last; } in trsort()
577 } else if((last - first) == 1) { in trsort()
580 first = last; in trsort()
582 } while(first < (SA + n)); in trsort()
583 if(skip != 0) { *(first + skip) = skip; } in trsort()