Lines Matching refs:PA
167 ss_insertionsort(const sauchar_t *T, const saidx_t *PA,
174 for(t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) {
192 ss_fixdown(const sauchar_t *Td, const saidx_t *PA,
198 for(v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) {
199 d = Td[PA[SA[k = j++]]];
200 if(d < (e = Td[PA[SA[j]]])) { k = j; d = e; }
209 ss_heapsort(const sauchar_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t size) {
216 if(Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); }
219 for(i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); }
220 if((size % 2) == 0) { SWAP(SA[0], SA[m]); ss_fixdown(Td, PA, SA, 0, m); }
223 ss_fixdown(Td, PA, SA, 0, i);
234 ss_median3(const sauchar_t *Td, const saidx_t *PA,
237 if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); }
238 if(Td[PA[*v2]] > Td[PA[*v3]]) {
239 if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; }
248 ss_median5(const sauchar_t *Td, const saidx_t *PA,
251 if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); }
252 if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); }
253 if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); }
254 if(Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); }
255 if(Td[PA[*v1]] > Td[PA[*v4]]) { SWAP(v1, v4); SWAP(v3, v5); }
256 if(Td[PA[*v3]] > Td[PA[*v4]]) { return v4; }
263 ss_pivot(const sauchar_t *Td, const saidx_t *PA, saidx_t *first, saidx_t *last) {
272 return ss_median3(Td, PA, first, middle, last - 1);
275 return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1);
279 first = ss_median3(Td, PA, first, first + t, first + (t << 1));
280 middle = ss_median3(Td, PA, middle - t, middle, middle + t);
281 last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1);
282 return ss_median3(Td, PA, first, middle, last);
291 ss_partition(const saidx_t *PA,
296 for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; }
297 for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { }
310 ss_mintrosort(const sauchar_t *T, const saidx_t *PA,
326 if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); }
333 if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); }
335 for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) {
336 if((x = Td[PA[*a]]) != v) {
342 if(Td[PA[*first] - 1] < v) {
343 first = ss_partition(PA, first, a, depth);
364 a = ss_pivot(Td, PA, first, last);
365 v = Td[PA[*a]];
369 for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { }
371 for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) {
375 for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { }
377 for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
383 for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) {
386 for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) {
400 b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth);
433 if(Td[PA[*first] - 1] < v) {
434 first = ss_partition(PA, first, last, depth);
502 ss_inplacemerge(const sauchar_t *T, const saidx_t *PA,
512 if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); }
513 else { x = 0; p = PA + *(last - 1); }
518 q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth);
545 ss_mergeforward(const sauchar_t *T, const saidx_t *PA,
556 r = ss_compare(T, PA + *b, PA + *c, depth);
595 ss_mergebackward(const sauchar_t *T, const saidx_t *PA,
608 if(*bufend < 0) { p1 = PA + ~*bufend; x |= 1; }
609 else { p1 = PA + *bufend; }
610 if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; }
611 else { p2 = PA + *(middle - 1); }
619 if(*b < 0) { p1 = PA + ~*b; x |= 1; }
620 else { p1 = PA + *b; }
629 if(*c < 0) { p2 = PA + ~*c; x |= 2; }
630 else { p2 = PA + *c; }
643 if(*b < 0) { p1 = PA + ~*b; x |= 1; }
644 else { p1 = PA + *b; }
645 if(*c < 0) { p2 = PA + ~*c; x |= 2; }
646 else { p2 = PA + *c; }
654 ss_swapmerge(const sauchar_t *T, const saidx_t *PA,
662 (((c) & 2) && (ss_compare(T, PA + GETIDX(*((a) - 1)), PA + *(a), depth) == 0))) {\
665 if(((c) & 4) && ((ss_compare(T, PA + GETIDX(*((b) - 1)), PA + *(b), depth) == 0))) {\
678 ss_mergebackward(T, PA, first, middle, last, buf, depth);
687 ss_mergeforward(T, PA, first, middle, last, buf, depth);
697 if(ss_compare(T, PA + GETIDX(*(middle + m + half)),
698 PA + GETIDX(*(middle - m - half - 1)), depth) < 0) {
728 if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) {
747 sssort(const sauchar_t *T, const saidx_t *PA,
761 ss_mintrosort(T, PA, first, last, depth);
773 ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth);
775 ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth);
781 ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth);
785 ss_mintrosort(T, PA, a, middle, depth);
787 ss_insertionsort(T, PA, a, middle, depth);
791 ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth);
797 ss_mintrosort(T, PA, middle, last, depth);
799 ss_insertionsort(T, PA, middle, last, depth);
801 ss_inplacemerge(T, PA, first, middle, last, depth);
807 saidx_t PAi[2]; PAi[0] = PA[*(first - 1)], PAi[1] = n - 2;
809 (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth)));