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