1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package io.netty.handler.codec.compression;
17
18
19
20
21
22
23
24
25 final class Bzip2DivSufSort {
26
27 private static final int STACK_SIZE = 64;
28 private static final int BUCKET_A_SIZE = 256;
29 private static final int BUCKET_B_SIZE = 65536;
30 private static final int SS_BLOCKSIZE = 1024;
31 private static final int INSERTIONSORT_THRESHOLD = 8;
32
33 private static final int[] LOG_2_TABLE = {
34 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
35 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
36 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
37 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
38 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
39 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
40 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
41 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
42 };
43
44 private final int[] SA;
45 private final byte[] T;
46 private final int n;
47
48
49
50
51
52
53 Bzip2DivSufSort(final byte[] block, final int[] bwtBlock, final int blockLength) {
54 T = block;
55 SA = bwtBlock;
56 n = blockLength;
57 }
58
59 private static void swapElements(final int[] array1, final int idx1, final int[] array2, final int idx2) {
60 final int temp = array1[idx1];
61 array1[idx1] = array2[idx2];
62 array2[idx2] = temp;
63 }
64
65 private int ssCompare(final int p1, final int p2, final int depth) {
66 final int[] SA = this.SA;
67 final byte[] T = this.T;
68
69
70 final int U1n = SA[p1 + 1] + 2;
71 final int U2n = SA[p2 + 1] + 2;
72
73 int U1 = depth + SA[p1];
74 int U2 = depth + SA[p2];
75
76 while (U1 < U1n && U2 < U2n && T[U1] == T[U2]) {
77 ++U1;
78 ++U2;
79 }
80
81 return U1 < U1n ?
82 U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1
83 : U2 < U2n ? -1 : 0;
84 }
85
86 private int ssCompareLast(int pa, int p1, int p2, int depth, int size) {
87 final int[] SA = this.SA;
88 final byte[] T = this.T;
89
90 int U1 = depth + SA[p1];
91 int U2 = depth + SA[p2];
92 int U1n = size;
93 int U2n = SA[p2 + 1] + 2;
94
95 while (U1 < U1n && U2 < U2n && T[U1] == T[U2]) {
96 ++U1;
97 ++U2;
98 }
99
100 if (U1 < U1n) {
101 return U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1;
102 }
103 if (U2 == U2n) {
104 return 1;
105 }
106
107 U1 %= size;
108 U1n = SA[pa] + 2;
109 while (U1 < U1n && U2 < U2n && T[U1] == T[U2]) {
110 ++U1;
111 ++U2;
112 }
113
114 return U1 < U1n ?
115 U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1
116 : U2 < U2n ? -1 : 0;
117 }
118
119 private void ssInsertionSort(int pa, int first, int last, int depth) {
120 final int[] SA = this.SA;
121
122 int i, j;
123 int t;
124 int r;
125
126 for (i = last - 2; first <= i; --i) {
127 for (t = SA[i], j = i + 1; 0 < (r = ssCompare(pa + t, pa + SA[j], depth));) {
128 do {
129 SA[j - 1] = SA[j];
130 } while (++j < last && SA[j] < 0);
131 if (last <= j) {
132 break;
133 }
134 }
135 if (r == 0) {
136 SA[j] = ~SA[j];
137 }
138 SA[j - 1] = t;
139 }
140 }
141
142 private void ssFixdown(int td, int pa, int sa, int i, int size) {
143 final int[] SA = this.SA;
144 final byte[] T = this.T;
145
146 int j, k;
147 int v;
148 int c, d, e;
149
150 for (v = SA[sa + i], c = T[td + SA[pa + v]] & 0xff; (j = 2 * i + 1) < size; SA[sa + i] = SA[sa + k], i = k) {
151 d = T[td + SA[pa + SA[sa + (k = j++)]]] & 0xff;
152 if (d < (e = T[td + SA[pa + SA[sa + j]]] & 0xff)) {
153 k = j;
154 d = e;
155 }
156 if (d <= c) {
157 break;
158 }
159 }
160 SA[sa + i] = v;
161 }
162
163 private void ssHeapSort(int td, int pa, int sa, int size) {
164 final int[] SA = this.SA;
165 final byte[] T = this.T;
166
167 int i, m;
168 int t;
169
170 m = size;
171 if (size % 2 == 0) {
172 m--;
173 if ((T[td + SA[pa + SA[sa + m / 2]]] & 0xff) < (T[td + SA[pa + SA[sa + m]]] & 0xff)) {
174 swapElements(SA, sa + m, SA, sa + m / 2);
175 }
176 }
177
178 for (i = m / 2 - 1; 0 <= i; --i) {
179 ssFixdown(td, pa, sa, i, m);
180 }
181
182 if (size % 2 == 0) {
183 swapElements(SA, sa, SA, sa + m);
184 ssFixdown(td, pa, sa, 0, m);
185 }
186
187 for (i = m - 1; 0 < i; --i) {
188 t = SA[sa];
189 SA[sa] = SA[sa + i];
190 ssFixdown(td, pa, sa, 0, i);
191 SA[sa + i] = t;
192 }
193 }
194
195 private int ssMedian3(final int td, final int pa, int v1, int v2, int v3) {
196 final int[] SA = this.SA;
197 final byte[] T = this.T;
198
199 int T_v1 = T[td + SA[pa + SA[v1]]] & 0xff;
200 int T_v2 = T[td + SA[pa + SA[v2]]] & 0xff;
201 int T_v3 = T[td + SA[pa + SA[v3]]] & 0xff;
202
203 if (T_v1 > T_v2) {
204 final int temp = v1;
205 v1 = v2;
206 v2 = temp;
207 final int T_vtemp = T_v1;
208 T_v1 = T_v2;
209 T_v2 = T_vtemp;
210 }
211 if (T_v2 > T_v3) {
212 if (T_v1 > T_v3) {
213 return v1;
214 }
215 return v3;
216 }
217 return v2;
218 }
219
220 private int ssMedian5(final int td, final int pa, int v1, int v2, int v3, int v4, int v5) {
221 final int[] SA = this.SA;
222 final byte[] T = this.T;
223
224 int T_v1 = T[td + SA[pa + SA[v1]]] & 0xff;
225 int T_v2 = T[td + SA[pa + SA[v2]]] & 0xff;
226 int T_v3 = T[td + SA[pa + SA[v3]]] & 0xff;
227 int T_v4 = T[td + SA[pa + SA[v4]]] & 0xff;
228 int T_v5 = T[td + SA[pa + SA[v5]]] & 0xff;
229 int temp;
230 int T_vtemp;
231
232 if (T_v2 > T_v3) {
233 temp = v2;
234 v2 = v3;
235 v3 = temp;
236 T_vtemp = T_v2;
237 T_v2 = T_v3;
238 T_v3 = T_vtemp;
239 }
240 if (T_v4 > T_v5) {
241 temp = v4;
242 v4 = v5;
243 v5 = temp;
244 T_vtemp = T_v4;
245 T_v4 = T_v5;
246 T_v5 = T_vtemp;
247 }
248 if (T_v2 > T_v4) {
249 temp = v2;
250 v4 = temp;
251 T_vtemp = T_v2;
252 T_v4 = T_vtemp;
253 temp = v3;
254 v3 = v5;
255 v5 = temp;
256 T_vtemp = T_v3;
257 T_v3 = T_v5;
258 T_v5 = T_vtemp;
259 }
260 if (T_v1 > T_v3) {
261 temp = v1;
262 v1 = v3;
263 v3 = temp;
264 T_vtemp = T_v1;
265 T_v1 = T_v3;
266 T_v3 = T_vtemp;
267 }
268 if (T_v1 > T_v4) {
269 temp = v1;
270 v4 = temp;
271 T_vtemp = T_v1;
272 T_v4 = T_vtemp;
273 v3 = v5;
274 T_v3 = T_v5;
275 }
276 if (T_v3 > T_v4) {
277 return v4;
278 }
279 return v3;
280 }
281
282 private int ssPivot(final int td, final int pa, final int first, final int last) {
283 int middle;
284 int t;
285
286 t = last - first;
287 middle = first + t / 2;
288
289 if (t <= 512) {
290 if (t <= 32) {
291 return ssMedian3(td, pa, first, middle, last - 1);
292 }
293 t >>= 2;
294 return ssMedian5(td, pa, first, first + t, middle, last - 1 - t, last - 1);
295 }
296 t >>= 3;
297 return ssMedian3(
298 td, pa,
299 ssMedian3(td, pa, first, first + t, first + (t << 1)),
300 ssMedian3(td, pa, middle - t, middle, middle + t),
301 ssMedian3(td, pa, last - 1 - (t << 1), last - 1 - t, last - 1)
302 );
303 }
304
305 private static int ssLog(final int n) {
306 return (n & 0xff00) != 0 ?
307 8 + LOG_2_TABLE[n >> 8 & 0xff]
308 : LOG_2_TABLE[n & 0xff];
309 }
310
311 private int ssSubstringPartition(final int pa, final int first, final int last, final int depth) {
312 final int[] SA = this.SA;
313
314 int a, b;
315 int t;
316
317 for (a = first - 1, b = last;;) {
318 while (++a < b && (SA[pa + SA[a]] + depth >= SA[pa + SA[a] + 1] + 1)) {
319 SA[a] = ~SA[a];
320 }
321 --b;
322 while (a < b && (SA[pa + SA[b]] + depth < SA[pa + SA[b] + 1] + 1)) {
323 --b;
324 }
325
326 if (b <= a) {
327 break;
328 }
329 t = ~SA[b];
330 SA[b] = SA[a];
331 SA[a] = t;
332 }
333 if (first < a) {
334 SA[first] = ~SA[first];
335 }
336 return a;
337 }
338
339 private static class StackEntry {
340 final int a;
341 final int b;
342 final int c;
343 final int d;
344
345 StackEntry(final int a, final int b, final int c, final int d) {
346 this.a = a;
347 this.b = b;
348 this.c = c;
349 this.d = d;
350 }
351 }
352
353 private void ssMultiKeyIntroSort(final int pa, int first, int last, int depth) {
354 final int[] SA = this.SA;
355 final byte[] T = this.T;
356
357 final StackEntry[] stack = new StackEntry[STACK_SIZE];
358
359 int Td;
360 int a, b, c, d, e, f;
361 int s, t;
362 int ssize;
363 int limit;
364 int v, x = 0;
365
366 for (ssize = 0, limit = ssLog(last - first);;) {
367 if (last - first <= INSERTIONSORT_THRESHOLD) {
368 if (1 < last - first) {
369 ssInsertionSort(pa, first, last, depth);
370 }
371 if (ssize == 0) {
372 return;
373 }
374 StackEntry entry = stack[--ssize];
375 first = entry.a;
376 last = entry.b;
377 depth = entry.c;
378 limit = entry.d;
379 continue;
380 }
381
382 Td = depth;
383 if (limit-- == 0) {
384 ssHeapSort(Td, pa, first, last - first);
385 }
386 if (limit < 0) {
387 for (a = first + 1, v = T[Td + SA[pa + SA[first]]] & 0xff; a < last; ++a) {
388 if ((x = T[Td + SA[pa + SA[a]]] & 0xff) != v) {
389 if (1 < a - first) {
390 break;
391 }
392 v = x;
393 first = a;
394 }
395 }
396 if ((T[Td + SA[pa + SA[first]] - 1] & 0xff) < v) {
397 first = ssSubstringPartition(pa, first, a, depth);
398 }
399 if (a - first <= last - a) {
400 if (1 < a - first) {
401 stack[ssize++] = new StackEntry(a, last, depth, -1);
402 last = a;
403 depth += 1;
404 limit = ssLog(a - first);
405 } else {
406 first = a;
407 limit = -1;
408 }
409 } else {
410 if (1 < last - a) {
411 stack[ssize++] = new StackEntry(first, a, depth + 1, ssLog(a - first));
412 first = a;
413 limit = -1;
414 } else {
415 last = a;
416 depth += 1;
417 limit = ssLog(a - first);
418 }
419 }
420 continue;
421 }
422
423 a = ssPivot(Td, pa, first, last);
424 v = T[Td + SA[pa + SA[a]]] & 0xff;
425 swapElements(SA, first, SA, a);
426
427 b = first + 1;
428 while (b < last && (x = T[Td + SA[pa + SA[b]]] & 0xff) == v) {
429 ++b;
430 }
431 if ((a = b) < last && x < v) {
432 while (++b < last && (x = T[Td + SA[pa + SA[b]]] & 0xff) <= v) {
433 if (x == v) {
434 swapElements(SA, b, SA, a);
435 ++a;
436 }
437 }
438 }
439
440 c = last - 1;
441 while (b < c && (x = T[Td + SA[pa + SA[c]]] & 0xff) == v) {
442 --c;
443 }
444 if (b < (d = c) && x > v) {
445 while (b < --c && (x = T[Td + SA[pa + SA[c]]] & 0xff) >= v) {
446 if (x == v) {
447 swapElements(SA, c, SA, d);
448 --d;
449 }
450 }
451 }
452 while (b < c) {
453 swapElements(SA, b, SA, c);
454 while (++b < c && (x = T[Td + SA[pa + SA[b]]] & 0xff) <= v) {
455 if (x == v) {
456 swapElements(SA, b, SA, a);
457 ++a;
458 }
459 }
460 while (b < --c && (x = T[Td + SA[pa + SA[c]]] & 0xff) >= v) {
461 if (x == v) {
462 swapElements(SA, c, SA, d);
463 --d;
464 }
465 }
466 }
467
468 if (a <= d) {
469 c = b - 1;
470
471 if ((s = a - first) > (t = b - a)) {
472 s = t;
473 }
474 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
475 swapElements(SA, e, SA, f);
476 }
477 if ((s = d - c) > (t = last - d - 1)) {
478 s = t;
479 }
480 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
481 swapElements(SA, e, SA, f);
482 }
483
484 a = first + (b - a);
485 c = last - (d - c);
486 b = v <= (T[Td + SA[pa + SA[a]] - 1] & 0xff) ? a : ssSubstringPartition(pa, a, c, depth);
487
488 if (a - first <= last - c) {
489 if (last - c <= c - b) {
490 stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
491 stack[ssize++] = new StackEntry(c, last, depth, limit);
492 last = a;
493 } else if (a - first <= c - b) {
494 stack[ssize++] = new StackEntry(c, last, depth, limit);
495 stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
496 last = a;
497 } else {
498 stack[ssize++] = new StackEntry(c, last, depth, limit);
499 stack[ssize++] = new StackEntry(first, a, depth, limit);
500 first = b;
501 last = c;
502 depth += 1;
503 limit = ssLog(c - b);
504 }
505 } else {
506 if (a - first <= c - b) {
507 stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
508 stack[ssize++] = new StackEntry(first, a, depth, limit);
509 first = c;
510 } else if (last - c <= c - b) {
511 stack[ssize++] = new StackEntry(first, a, depth, limit);
512 stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
513 first = c;
514 } else {
515 stack[ssize++] = new StackEntry(first, a, depth, limit);
516 stack[ssize++] = new StackEntry(c, last, depth, limit);
517 first = b;
518 last = c;
519 depth += 1;
520 limit = ssLog(c - b);
521 }
522 }
523 } else {
524 limit += 1;
525 if ((T[Td + SA[pa + SA[first]] - 1] & 0xff) < v) {
526 first = ssSubstringPartition(pa, first, last, depth);
527 limit = ssLog(last - first);
528 }
529 depth += 1;
530 }
531 }
532 }
533
534 private static void ssBlockSwap(final int[] array1, final int first1,
535 final int[] array2, final int first2, final int size) {
536 int a, b;
537 int i;
538 for (i = size, a = first1, b = first2; 0 < i; --i, ++a, ++b) {
539 swapElements(array1, a, array2, b);
540 }
541 }
542
543 private void ssMergeForward(final int pa, int[] buf, final int bufoffset,
544 final int first, final int middle, final int last, final int depth) {
545 final int[] SA = this.SA;
546
547 int bufend;
548 int i, j, k;
549 int t;
550 int r;
551
552 bufend = bufoffset + (middle - first) - 1;
553 ssBlockSwap(buf, bufoffset, SA, first, middle - first);
554
555 for (t = SA[first], i = first, j = bufoffset, k = middle;;) {
556 r = ssCompare(pa + buf[j], pa + SA[k], depth);
557 if (r < 0) {
558 do {
559 SA[i++] = buf[j];
560 if (bufend <= j) {
561 buf[j] = t;
562 return;
563 }
564 buf[j++] = SA[i];
565 } while (buf[j] < 0);
566 } else if (r > 0) {
567 do {
568 SA[i++] = SA[k];
569 SA[k++] = SA[i];
570 if (last <= k) {
571 while (j < bufend) { SA[i++] = buf[j]; buf[j++] = SA[i]; }
572 SA[i] = buf[j]; buf[j] = t;
573 return;
574 }
575 } while (SA[k] < 0);
576 } else {
577 SA[k] = ~SA[k];
578 do {
579 SA[i++] = buf[j];
580 if (bufend <= j) {
581 buf[j] = t;
582 return;
583 }
584 buf[j++] = SA[i];
585 } while (buf[j] < 0);
586
587 do {
588 SA[i++] = SA[k];
589 SA[k++] = SA[i];
590 if (last <= k) {
591 while (j < bufend) {
592 SA[i++] = buf[j];
593 buf[j++] = SA[i];
594 }
595 SA[i] = buf[j]; buf[j] = t;
596 return;
597 }
598 } while (SA[k] < 0);
599 }
600 }
601 }
602
603 private void ssMergeBackward(final int pa, int[] buf, final int bufoffset,
604 final int first, final int middle, final int last, final int depth) {
605 final int[] SA = this.SA;
606
607 int p1, p2;
608 int bufend;
609 int i, j, k;
610 int t;
611 int r;
612 int x;
613
614 bufend = bufoffset + (last - middle);
615 ssBlockSwap(buf, bufoffset, SA, middle, last - middle);
616
617 x = 0;
618 if (buf[bufend - 1] < 0) {
619 x |= 1;
620 p1 = pa + ~buf[bufend - 1];
621 } else {
622 p1 = pa + buf[bufend - 1];
623 }
624 if (SA[middle - 1] < 0) {
625 x |= 2;
626 p2 = pa + ~SA[middle - 1];
627 } else {
628 p2 = pa + SA[middle - 1];
629 }
630 for (t = SA[last - 1], i = last - 1, j = bufend - 1, k = middle - 1;;) {
631
632 r = ssCompare(p1, p2, depth);
633 if (r > 0) {
634 if ((x & 1) != 0) {
635 do {
636 SA[i--] = buf[j];
637 buf[j--] = SA[i];
638 } while (buf[j] < 0);
639 x ^= 1;
640 }
641 SA[i--] = buf[j];
642 if (j <= bufoffset) {
643 buf[j] = t;
644 return;
645 }
646 buf[j--] = SA[i];
647
648 if (buf[j] < 0) {
649 x |= 1;
650 p1 = pa + ~buf[j];
651 } else {
652 p1 = pa + buf[j];
653 }
654 } else if (r < 0) {
655 if ((x & 2) != 0) {
656 do {
657 SA[i--] = SA[k];
658 SA[k--] = SA[i];
659 } while (SA[k] < 0);
660 x ^= 2;
661 }
662 SA[i--] = SA[k];
663 SA[k--] = SA[i];
664 if (k < first) {
665 while (bufoffset < j) {
666 SA[i--] = buf[j];
667 buf[j--] = SA[i];
668 }
669 SA[i] = buf[j];
670 buf[j] = t;
671 return;
672 }
673
674 if (SA[k] < 0) {
675 x |= 2;
676 p2 = pa + ~SA[k];
677 } else {
678 p2 = pa + SA[k];
679 }
680 } else {
681 if ((x & 1) != 0) {
682 do {
683 SA[i--] = buf[j];
684 buf[j--] = SA[i];
685 } while (buf[j] < 0);
686 x ^= 1;
687 }
688 SA[i--] = ~buf[j];
689 if (j <= bufoffset) {
690 buf[j] = t;
691 return;
692 }
693 buf[j--] = SA[i];
694
695 if ((x & 2) != 0) {
696 do {
697 SA[i--] = SA[k];
698 SA[k--] = SA[i];
699 } while (SA[k] < 0);
700 x ^= 2;
701 }
702 SA[i--] = SA[k];
703 SA[k--] = SA[i];
704 if (k < first) {
705 while (bufoffset < j) {
706 SA[i--] = buf[j];
707 buf[j--] = SA[i];
708 }
709 SA[i] = buf[j];
710 buf[j] = t;
711 return;
712 }
713
714 if (buf[j] < 0) {
715 x |= 1;
716 p1 = pa + ~buf[j];
717 } else {
718 p1 = pa + buf[j];
719 }
720 if (SA[k] < 0) {
721 x |= 2;
722 p2 = pa + ~SA[k];
723 } else {
724 p2 = pa + SA[k];
725 }
726 }
727 }
728 }
729
730 private static int getIDX(final int a) {
731 return 0 <= a ? a : ~a;
732 }
733
734 private void ssMergeCheckEqual(final int pa, final int depth, final int a) {
735 final int[] SA = this.SA;
736
737 if (0 <= SA[a] && ssCompare(pa + getIDX(SA[a - 1]), pa + SA[a], depth) == 0) {
738 SA[a] = ~SA[a];
739 }
740 }
741
742 private void ssMerge(final int pa, int first, int middle, int last, int[] buf,
743 final int bufoffset, final int bufsize, final int depth) {
744 final int[] SA = this.SA;
745
746 final StackEntry[] stack = new StackEntry[STACK_SIZE];
747
748 int i, j;
749 int m, len, half;
750 int ssize;
751 int check, next;
752
753 for (check = 0, ssize = 0;;) {
754
755 if (last - middle <= bufsize) {
756 if (first < middle && middle < last) {
757 ssMergeBackward(pa, buf, bufoffset, first, middle, last, depth);
758 }
759
760 if ((check & 1) != 0) {
761 ssMergeCheckEqual(pa, depth, first);
762 }
763 if ((check & 2) != 0) {
764 ssMergeCheckEqual(pa, depth, last);
765 }
766 if (ssize == 0) {
767 return;
768 }
769 StackEntry entry = stack[--ssize];
770 first = entry.a;
771 middle = entry.b;
772 last = entry.c;
773 check = entry.d;
774 continue;
775 }
776
777 if (middle - first <= bufsize) {
778 if (first < middle) {
779 ssMergeForward(pa, buf, bufoffset, first, middle, last, depth);
780 }
781 if ((check & 1) != 0) {
782 ssMergeCheckEqual(pa, depth, first);
783 }
784 if ((check & 2) != 0) {
785 ssMergeCheckEqual(pa, depth, last);
786 }
787 if (ssize == 0) {
788 return;
789 }
790 StackEntry entry = stack[--ssize];
791 first = entry.a;
792 middle = entry.b;
793 last = entry.c;
794 check = entry.d;
795 continue;
796 }
797
798 for (m = 0, len = Math.min(middle - first, last - middle), half = len >> 1;
799 0 < len;
800 len = half, half >>= 1) {
801
802 if (ssCompare(pa + getIDX(SA[middle + m + half]),
803 pa + getIDX(SA[middle - m - half - 1]), depth) < 0) {
804 m += half + 1;
805 half -= (len & 1) ^ 1;
806 }
807 }
808
809 if (0 < m) {
810 ssBlockSwap(SA, middle - m, SA, middle, m);
811 i = j = middle;
812 next = 0;
813 if (middle + m < last) {
814 if (SA[middle + m] < 0) {
815 while (SA[i - 1] < 0) {
816 --i;
817 }
818 SA[middle + m] = ~SA[middle + m];
819 }
820 for (j = middle; SA[j] < 0;) {
821 ++j;
822 }
823 next = 1;
824 }
825 if (i - first <= last - j) {
826 stack[ssize++] = new StackEntry(j, middle + m, last, (check & 2) | (next & 1));
827 middle -= m;
828 last = i;
829 check &= 1;
830 } else {
831 if (i == middle && middle == j) {
832 next <<= 1;
833 }
834 stack[ssize++] = new StackEntry(first, middle - m, i, (check & 1) | (next & 2));
835 first = j;
836 middle += m;
837 check = (check & 2) | (next & 1);
838 }
839 } else {
840 if ((check & 1) != 0) {
841 ssMergeCheckEqual(pa, depth, first);
842 }
843 ssMergeCheckEqual(pa, depth, middle);
844 if ((check & 2) != 0) {
845 ssMergeCheckEqual(pa, depth, last);
846 }
847 if (ssize == 0) {
848 return;
849 }
850 StackEntry entry = stack[--ssize];
851 first = entry.a;
852 middle = entry.b;
853 last = entry.c;
854 check = entry.d;
855 }
856 }
857 }
858
859 private void subStringSort(final int pa, int first, final int last,
860 final int[] buf, final int bufoffset, final int bufsize,
861 final int depth, final boolean lastsuffix, final int size) {
862 final int[] SA = this.SA;
863
864 int a, b;
865 int[] curbuf;
866 int curbufoffset;
867 int i, j, k;
868 int curbufsize;
869
870 if (lastsuffix) {
871 ++first;
872 }
873 for (a = first, i = 0; a + SS_BLOCKSIZE < last; a += SS_BLOCKSIZE, ++i) {
874 ssMultiKeyIntroSort(pa, a, a + SS_BLOCKSIZE, depth);
875 curbuf = SA;
876 curbufoffset = a + SS_BLOCKSIZE;
877 curbufsize = last - (a + SS_BLOCKSIZE);
878 if (curbufsize <= bufsize) {
879 curbufsize = bufsize;
880 curbuf = buf;
881 curbufoffset = bufoffset;
882 }
883 for (b = a, k = SS_BLOCKSIZE, j = i; (j & 1) != 0; b -= k, k <<= 1, j >>>= 1) {
884 ssMerge(pa, b - k, b, b + k, curbuf, curbufoffset, curbufsize, depth);
885 }
886 }
887
888 ssMultiKeyIntroSort(pa, a, last, depth);
889
890 for (k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
891 if ((i & 1) != 0) {
892 ssMerge(pa, a - k, a, last, buf, bufoffset, bufsize, depth);
893 a -= k;
894 }
895 }
896
897 if (lastsuffix) {
898 int r;
899 for (a = first, i = SA[first - 1], r = 1;
900 a < last && (SA[a] < 0 || 0 < (r = ssCompareLast(pa, pa + i, pa + SA[a], depth, size)));
901 ++a) {
902 SA[a - 1] = SA[a];
903 }
904 if (r == 0) {
905 SA[a] = ~SA[a];
906 }
907 SA[a - 1] = i;
908 }
909 }
910
911
912
913 private int trGetC(final int isa, final int isaD, final int isaN, final int p) {
914 return isaD + p < isaN ?
915 SA[isaD + p]
916 : SA[isa + ((isaD - isa + p) % (isaN - isa))];
917 }
918
919 private void trFixdown(final int isa, final int isaD, final int isaN, final int sa, int i, final int size) {
920 final int[] SA = this.SA;
921
922 int j, k;
923 int v;
924 int c, d, e;
925
926 for (v = SA[sa + i], c = trGetC(isa, isaD, isaN, v); (j = 2 * i + 1) < size; SA[sa + i] = SA[sa + k], i = k) {
927 k = j++;
928 d = trGetC(isa, isaD, isaN, SA[sa + k]);
929 if (d < (e = trGetC(isa, isaD, isaN, SA[sa + j]))) {
930 k = j;
931 d = e;
932 }
933 if (d <= c) {
934 break;
935 }
936 }
937 SA[sa + i] = v;
938 }
939
940 private void trHeapSort(final int isa, final int isaD, final int isaN, final int sa, final int size) {
941 final int[] SA = this.SA;
942
943 int i, m;
944 int t;
945
946 m = size;
947 if (size % 2 == 0) {
948 m--;
949 if (trGetC(isa, isaD, isaN, SA[sa + m / 2]) < trGetC(isa, isaD, isaN, SA[sa + m])) {
950 swapElements(SA, sa + m, SA, sa + m / 2);
951 }
952 }
953
954 for (i = m / 2 - 1; 0 <= i; --i) {
955 trFixdown(isa, isaD, isaN, sa, i, m);
956 }
957
958 if (size % 2 == 0) {
959 swapElements(SA, sa, SA, sa + m);
960 trFixdown(isa, isaD, isaN, sa, 0, m);
961 }
962
963 for (i = m - 1; 0 < i; --i) {
964 t = SA[sa];
965 SA[sa] = SA[sa + i];
966 trFixdown(isa, isaD, isaN, sa, 0, i);
967 SA[sa + i] = t;
968 }
969 }
970
971 private void trInsertionSort(final int isa, final int isaD, final int isaN, int first, int last) {
972 final int[] SA = this.SA;
973
974 int a, b;
975 int t, r;
976
977 for (a = first + 1; a < last; ++a) {
978 for (t = SA[a], b = a - 1; 0 > (r = trGetC(isa, isaD, isaN, t) - trGetC(isa, isaD, isaN, SA[b]));) {
979 do {
980 SA[b + 1] = SA[b];
981 } while (first <= --b && SA[b] < 0);
982 if (b < first) {
983 break;
984 }
985 }
986 if (r == 0) {
987 SA[b] = ~SA[b];
988 }
989 SA[b + 1] = t;
990 }
991 }
992
993 private static int trLog(int n) {
994 return (n & 0xffff0000) != 0 ?
995 (n & 0xff000000) != 0 ? 24 + LOG_2_TABLE[n >> 24 & 0xff] : LOG_2_TABLE[n >> 16 & 0xff + 16]
996 : (n & 0x0000ff00) != 0 ? 8 + LOG_2_TABLE[n >> 8 & 0xff] : LOG_2_TABLE[n & 0xff];
997 }
998
999 private int trMedian3(final int isa, final int isaD, final int isaN, int v1, int v2, int v3) {
1000 final int[] SA = this.SA;
1001
1002 int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
1003 int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
1004 int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);
1005
1006 if (SA_v1 > SA_v2) {
1007 final int temp = v1;
1008 v1 = v2;
1009 v2 = temp;
1010 final int SA_vtemp = SA_v1;
1011 SA_v1 = SA_v2;
1012 SA_v2 = SA_vtemp;
1013 }
1014 if (SA_v2 > SA_v3) {
1015 if (SA_v1 > SA_v3) {
1016 return v1;
1017 }
1018 return v3;
1019 }
1020
1021 return v2;
1022 }
1023
1024 private int trMedian5(final int isa, final int isaD, final int isaN, int v1, int v2, int v3, int v4, int v5) {
1025 final int[] SA = this.SA;
1026
1027 int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
1028 int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
1029 int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);
1030 int SA_v4 = trGetC(isa, isaD, isaN, SA[v4]);
1031 int SA_v5 = trGetC(isa, isaD, isaN, SA[v5]);
1032 int temp;
1033 int SA_vtemp;
1034
1035 if (SA_v2 > SA_v3) {
1036 temp = v2;
1037 v2 = v3;
1038 v3 = temp;
1039 SA_vtemp = SA_v2;
1040 SA_v2 = SA_v3;
1041 SA_v3 = SA_vtemp;
1042 }
1043 if (SA_v4 > SA_v5) {
1044 temp = v4;
1045 v4 = v5;
1046 v5 = temp;
1047 SA_vtemp = SA_v4;
1048 SA_v4 = SA_v5;
1049 SA_v5 = SA_vtemp;
1050 }
1051 if (SA_v2 > SA_v4) {
1052 temp = v2;
1053 v4 = temp;
1054 SA_vtemp = SA_v2;
1055 SA_v4 = SA_vtemp;
1056 temp = v3;
1057 v3 = v5;
1058 v5 = temp;
1059 SA_vtemp = SA_v3;
1060 SA_v3 = SA_v5;
1061 SA_v5 = SA_vtemp;
1062 }
1063 if (SA_v1 > SA_v3) {
1064 temp = v1;
1065 v1 = v3;
1066 v3 = temp;
1067 SA_vtemp = SA_v1;
1068 SA_v1 = SA_v3;
1069 SA_v3 = SA_vtemp;
1070 }
1071 if (SA_v1 > SA_v4) {
1072 temp = v1;
1073 v4 = temp;
1074 SA_vtemp = SA_v1;
1075 SA_v4 = SA_vtemp;
1076 v3 = v5;
1077 SA_v3 = SA_v5;
1078 }
1079 if (SA_v3 > SA_v4) {
1080 return v4;
1081 }
1082 return v3;
1083 }
1084
1085 private int trPivot(final int isa, final int isaD, final int isaN, final int first, final int last) {
1086 final int middle;
1087 int t;
1088
1089 t = last - first;
1090 middle = first + t / 2;
1091
1092 if (t <= 512) {
1093 if (t <= 32) {
1094 return trMedian3(isa, isaD, isaN, first, middle, last - 1);
1095 }
1096 t >>= 2;
1097 return trMedian5(
1098 isa, isaD, isaN,
1099 first, first + t,
1100 middle,
1101 last - 1 - t, last - 1
1102 );
1103 }
1104 t >>= 3;
1105 return trMedian3(
1106 isa, isaD, isaN,
1107 trMedian3(isa, isaD, isaN, first, first + t, first + (t << 1)),
1108 trMedian3(isa, isaD, isaN, middle - t, middle, middle + t),
1109 trMedian3(isa, isaD, isaN, last - 1 - (t << 1), last - 1 - t, last - 1)
1110 );
1111 }
1112
1113
1114
1115 private void lsUpdateGroup(final int isa, final int first, final int last) {
1116 final int[] SA = this.SA;
1117
1118 int a, b;
1119 int t;
1120
1121 for (a = first; a < last; ++a) {
1122 if (0 <= SA[a]) {
1123 b = a;
1124 do {
1125 SA[isa + SA[a]] = a;
1126 } while (++a < last && 0 <= SA[a]);
1127 SA[b] = b - a;
1128 if (last <= a) {
1129 break;
1130 }
1131 }
1132 b = a;
1133 do {
1134 SA[a] = ~SA[a];
1135 } while (SA[++a] < 0);
1136 t = a;
1137 do {
1138 SA[isa + SA[b]] = t;
1139 } while (++b <= a);
1140 }
1141 }
1142
1143 private void lsIntroSort(final int isa, final int isaD, final int isaN, int first, int last) {
1144 final int[] SA = this.SA;
1145
1146 final StackEntry[] stack = new StackEntry[STACK_SIZE];
1147
1148 int a, b, c, d, e, f;
1149 int s, t;
1150 int limit;
1151 int v, x = 0;
1152 int ssize;
1153
1154 for (ssize = 0, limit = trLog(last - first);;) {
1155 if (last - first <= INSERTIONSORT_THRESHOLD) {
1156 if (1 < last - first) {
1157 trInsertionSort(isa, isaD, isaN, first, last);
1158 lsUpdateGroup(isa, first, last);
1159 } else if (last - first == 1) {
1160 SA[first] = -1;
1161 }
1162 if (ssize == 0) {
1163 return;
1164 }
1165 StackEntry entry = stack[--ssize];
1166 first = entry.a;
1167 last = entry.b;
1168 limit = entry.c;
1169 continue;
1170 }
1171
1172 if (limit-- == 0) {
1173 trHeapSort(isa, isaD, isaN, first, last - first);
1174 for (a = last - 1; first < a; a = b) {
1175 for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
1176 first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
1177 --b) {
1178 SA[b] = ~SA[b];
1179 }
1180 }
1181 lsUpdateGroup(isa, first, last);
1182 if (ssize == 0) {
1183 return;
1184 }
1185 StackEntry entry = stack[--ssize];
1186 first = entry.a;
1187 last = entry.b;
1188 limit = entry.c;
1189 continue;
1190 }
1191
1192 a = trPivot(isa, isaD, isaN, first, last);
1193 swapElements(SA, first, SA, a);
1194 v = trGetC(isa, isaD, isaN, SA[first]);
1195
1196 b = first + 1;
1197 while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1198 ++b;
1199 }
1200 if ((a = b) < last && x < v) {
1201 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1202 if (x == v) {
1203 swapElements(SA, b, SA, a);
1204 ++a;
1205 }
1206 }
1207 }
1208
1209 c = last - 1;
1210 while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1211 --c;
1212 }
1213 if (b < (d = c) && x > v) {
1214 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1215 if (x == v) {
1216 swapElements(SA, c, SA, d);
1217 --d;
1218 }
1219 }
1220 }
1221 while (b < c) {
1222 swapElements(SA, b, SA, c);
1223 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1224 if (x == v) {
1225 swapElements(SA, b, SA, a);
1226 ++a;
1227 }
1228 }
1229 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1230 if (x == v) {
1231 swapElements(SA, c, SA, d);
1232 --d;
1233 }
1234 }
1235 }
1236
1237 if (a <= d) {
1238 c = b - 1;
1239
1240 if ((s = a - first) > (t = b - a)) {
1241 s = t;
1242 }
1243 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1244 swapElements(SA, e, SA, f);
1245 }
1246 if ((s = d - c) > (t = last - d - 1)) {
1247 s = t;
1248 }
1249 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1250 swapElements(SA, e, SA, f);
1251 }
1252
1253 a = first + (b - a);
1254 b = last - (d - c);
1255
1256 for (c = first, v = a - 1; c < a; ++c) {
1257 SA[isa + SA[c]] = v;
1258 }
1259 if (b < last) {
1260 for (c = a, v = b - 1; c < b; ++c) {
1261 SA[isa + SA[c]] = v;
1262 }
1263 }
1264 if ((b - a) == 1) {
1265 SA[a] = - 1;
1266 }
1267
1268 if (a - first <= last - b) {
1269 if (first < a) {
1270 stack[ssize++] = new StackEntry(b, last, limit, 0);
1271 last = a;
1272 } else {
1273 first = b;
1274 }
1275 } else {
1276 if (b < last) {
1277 stack[ssize++] = new StackEntry(first, a, limit, 0);
1278 first = b;
1279 } else {
1280 last = a;
1281 }
1282 }
1283 } else {
1284 if (ssize == 0) {
1285 return;
1286 }
1287 StackEntry entry = stack[--ssize];
1288 first = entry.a;
1289 last = entry.b;
1290 limit = entry.c;
1291 }
1292 }
1293 }
1294
1295 private void lsSort(final int isa, final int n, final int depth) {
1296 final int[] SA = this.SA;
1297
1298 int isaD;
1299 int first, last, i;
1300 int t, skip;
1301
1302 for (isaD = isa + depth; -n < SA[0]; isaD += isaD - isa) {
1303 first = 0;
1304 skip = 0;
1305 do {
1306 if ((t = SA[first]) < 0) {
1307 first -= t;
1308 skip += t;
1309 } else {
1310 if (skip != 0) {
1311 SA[first + skip] = skip;
1312 skip = 0;
1313 }
1314 last = SA[isa + t] + 1;
1315 lsIntroSort(isa, isaD, isa + n, first, last);
1316 first = last;
1317 }
1318 } while (first < n);
1319 if (skip != 0) {
1320 SA[first + skip] = skip;
1321 }
1322 if (n < isaD - isa) {
1323 first = 0;
1324 do {
1325 if ((t = SA[first]) < 0) {
1326 first -= t;
1327 } else {
1328 last = SA[isa + t] + 1;
1329 for (i = first; i < last; ++i) {
1330 SA[isa + SA[i]] = i;
1331 }
1332 first = last;
1333 }
1334 } while (first < n);
1335 break;
1336 }
1337 }
1338 }
1339
1340
1341
1342 private static class PartitionResult {
1343 final int first;
1344 final int last;
1345
1346 PartitionResult(final int first, final int last) {
1347 this.first = first;
1348 this.last = last;
1349 }
1350 }
1351
1352 private PartitionResult trPartition(final int isa, final int isaD, final int isaN,
1353 int first, int last, final int v) {
1354 final int[] SA = this.SA;
1355
1356 int a, b, c, d, e, f;
1357 int t, s;
1358 int x = 0;
1359
1360 b = first;
1361 while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1362 ++b;
1363 }
1364 if ((a = b) < last && x < v) {
1365 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1366 if (x == v) {
1367 swapElements(SA, b, SA, a);
1368 ++a;
1369 }
1370 }
1371 }
1372
1373 c = last - 1;
1374 while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1375 --c;
1376 }
1377 if (b < (d = c) && x > v) {
1378 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1379 if (x == v) {
1380 swapElements(SA, c, SA, d);
1381 --d;
1382 }
1383 }
1384 }
1385 while (b < c) {
1386 swapElements(SA, b, SA, c);
1387 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1388 if (x == v) {
1389 swapElements(SA, b, SA, a);
1390 ++a;
1391 }
1392 }
1393 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1394 if (x == v) {
1395 swapElements(SA, c, SA, d);
1396 --d;
1397 }
1398 }
1399 }
1400
1401 if (a <= d) {
1402 c = b - 1;
1403 if ((s = a - first) > (t = b - a)) {
1404 s = t;
1405 }
1406 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1407 swapElements(SA, e, SA, f);
1408 }
1409 if ((s = d - c) > (t = last - d - 1)) {
1410 s = t;
1411 }
1412 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1413 swapElements(SA, e, SA, f);
1414 }
1415 first += b - a;
1416 last -= d - c;
1417 }
1418 return new PartitionResult(first, last);
1419 }
1420
1421 private void trCopy(final int isa, final int isaN, final int first,
1422 final int a, final int b, final int last, final int depth) {
1423 final int[] SA = this.SA;
1424
1425 int c, d, e;
1426 int s, v;
1427
1428 v = b - 1;
1429
1430 for (c = first, d = a - 1; c <= d; ++c) {
1431 if ((s = SA[c] - depth) < 0) {
1432 s += isaN - isa;
1433 }
1434 if (SA[isa + s] == v) {
1435 SA[++d] = s;
1436 SA[isa + s] = d;
1437 }
1438 }
1439 for (c = last - 1, e = d + 1, d = b; e < d; --c) {
1440 if ((s = SA[c] - depth) < 0) {
1441 s += isaN - isa;
1442 }
1443 if (SA[isa + s] == v) {
1444 SA[--d] = s;
1445 SA[isa + s] = d;
1446 }
1447 }
1448 }
1449
1450 private void trIntroSort(final int isa, int isaD, int isaN, int first,
1451 int last, final TRBudget budget, final int size) {
1452 final int[] SA = this.SA;
1453
1454 final StackEntry[] stack = new StackEntry[STACK_SIZE];
1455
1456 int a, b, c, d, e, f;
1457 int s, t;
1458 int v, x = 0;
1459 int limit, next;
1460 int ssize;
1461
1462 for (ssize = 0, limit = trLog(last - first);;) {
1463 if (limit < 0) {
1464 if (limit == -1) {
1465 if (!budget.update(size, last - first)) {
1466 break;
1467 }
1468 PartitionResult result = trPartition(isa, isaD - 1, isaN, first, last, last - 1);
1469 a = result.first;
1470 b = result.last;
1471 if (first < a || b < last) {
1472 if (a < last) {
1473 for (c = first, v = a - 1; c < a; ++c) {
1474 SA[isa + SA[c]] = v;
1475 }
1476 }
1477 if (b < last) {
1478 for (c = a, v = b - 1; c < b; ++c) {
1479 SA[isa + SA[c]] = v;
1480 }
1481 }
1482
1483 stack[ssize++] = new StackEntry(0, a, b, 0);
1484 stack[ssize++] = new StackEntry(isaD - 1, first, last, -2);
1485 if (a - first <= last - b) {
1486 if (1 < a - first) {
1487 stack[ssize++] = new StackEntry(isaD, b, last, trLog(last - b));
1488 last = a; limit = trLog(a - first);
1489 } else if (1 < last - b) {
1490 first = b; limit = trLog(last - b);
1491 } else {
1492 if (ssize == 0) {
1493 return;
1494 }
1495 StackEntry entry = stack[--ssize];
1496 isaD = entry.a;
1497 first = entry.b;
1498 last = entry.c;
1499 limit = entry.d;
1500 }
1501 } else {
1502 if (1 < last - b) {
1503 stack[ssize++] = new StackEntry(isaD, first, a, trLog(a - first));
1504 first = b;
1505 limit = trLog(last - b);
1506 } else if (1 < a - first) {
1507 last = a;
1508 limit = trLog(a - first);
1509 } else {
1510 if (ssize == 0) {
1511 return;
1512 }
1513 StackEntry entry = stack[--ssize];
1514 isaD = entry.a;
1515 first = entry.b;
1516 last = entry.c;
1517 limit = entry.d;
1518 }
1519 }
1520 } else {
1521 for (c = first; c < last; ++c) {
1522 SA[isa + SA[c]] = c;
1523 }
1524 if (ssize == 0) {
1525 return;
1526 }
1527 StackEntry entry = stack[--ssize];
1528 isaD = entry.a;
1529 first = entry.b;
1530 last = entry.c;
1531 limit = entry.d;
1532 }
1533 } else if (limit == -2) {
1534 a = stack[--ssize].b;
1535 b = stack[ssize].c;
1536 trCopy(isa, isaN, first, a, b, last, isaD - isa);
1537 if (ssize == 0) {
1538 return;
1539 }
1540 StackEntry entry = stack[--ssize];
1541 isaD = entry.a;
1542 first = entry.b;
1543 last = entry.c;
1544 limit = entry.d;
1545 } else {
1546 if (0 <= SA[first]) {
1547 a = first;
1548 do {
1549 SA[isa + SA[a]] = a;
1550 } while (++a < last && 0 <= SA[a]);
1551 first = a;
1552 }
1553 if (first < last) {
1554 a = first;
1555 do {
1556 SA[a] = ~SA[a];
1557 } while (SA[++a] < 0);
1558 next = SA[isa + SA[a]] != SA[isaD + SA[a]] ? trLog(a - first + 1) : -1;
1559 if (++a < last) {
1560 for (b = first, v = a - 1; b < a; ++b) {
1561 SA[isa + SA[b]] = v;
1562 }
1563 }
1564
1565 if (a - first <= last - a) {
1566 stack[ssize++] = new StackEntry(isaD, a, last, -3);
1567 isaD += 1; last = a; limit = next;
1568 } else {
1569 if (1 < last - a) {
1570 stack[ssize++] = new StackEntry(isaD + 1, first, a, next);
1571 first = a; limit = -3;
1572 } else {
1573 isaD += 1; last = a; limit = next;
1574 }
1575 }
1576 } else {
1577 if (ssize == 0) {
1578 return;
1579 }
1580 StackEntry entry = stack[--ssize];
1581 isaD = entry.a;
1582 first = entry.b;
1583 last = entry.c;
1584 limit = entry.d;
1585 }
1586 }
1587 continue;
1588 }
1589
1590 if (last - first <= INSERTIONSORT_THRESHOLD) {
1591 if (!budget.update(size, last - first)) {
1592 break;
1593 }
1594 trInsertionSort(isa, isaD, isaN, first, last);
1595 limit = -3;
1596 continue;
1597 }
1598
1599 if (limit-- == 0) {
1600 if (!budget.update(size, last - first)) {
1601 break;
1602 }
1603 trHeapSort(isa, isaD, isaN, first, last - first);
1604 for (a = last - 1; first < a; a = b) {
1605 for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
1606 first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
1607 --b) {
1608 SA[b] = ~SA[b];
1609 }
1610 }
1611 limit = -3;
1612 continue;
1613 }
1614
1615 a = trPivot(isa, isaD, isaN, first, last);
1616
1617 swapElements(SA, first, SA, a);
1618 v = trGetC(isa, isaD, isaN, SA[first]);
1619
1620 b = first + 1;
1621 while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1622 ++b;
1623 }
1624 if ((a = b) < last && x < v) {
1625 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1626 if (x == v) {
1627 swapElements(SA, b, SA, a);
1628 ++a;
1629 }
1630 }
1631 }
1632
1633 c = last - 1;
1634 while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1635 --c;
1636 }
1637 if (b < (d = c) && x > v) {
1638 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1639 if (x == v) {
1640 swapElements(SA, c, SA, d);
1641 --d;
1642 }
1643 }
1644 }
1645 while (b < c) {
1646 swapElements(SA, b, SA, c);
1647 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1648 if (x == v) {
1649 swapElements(SA, b, SA, a);
1650 ++a;
1651 }
1652 }
1653 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1654 if (x == v) {
1655 swapElements(SA, c, SA, d);
1656 --d;
1657 }
1658 }
1659 }
1660
1661 if (a <= d) {
1662 c = b - 1;
1663
1664 if ((s = a - first) > (t = b - a)) {
1665 s = t;
1666 }
1667 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1668 swapElements(SA, e, SA, f);
1669 }
1670 if ((s = d - c) > (t = last - d - 1)) {
1671 s = t;
1672 }
1673 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1674 swapElements(SA, e, SA, f);
1675 }
1676
1677 a = first + (b - a);
1678 b = last - (d - c);
1679 next = SA[isa + SA[a]] != v ? trLog(b - a) : -1;
1680
1681 for (c = first, v = a - 1; c < a; ++c) {
1682 SA[isa + SA[c]] = v;
1683 }
1684 if (b < last) {
1685 for (c = a, v = b - 1; c < b; ++c) {
1686 SA[isa + SA[c]] = v; }
1687 }
1688
1689 if (a - first <= last - b) {
1690 if (last - b <= b - a) {
1691 if (1 < a - first) {
1692 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1693 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1694 last = a;
1695 } else if (1 < last - b) {
1696 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1697 first = b;
1698 } else if (1 < b - a) {
1699 isaD += 1;
1700 first = a;
1701 last = b;
1702 limit = next;
1703 } else {
1704 if (ssize == 0) {
1705 return;
1706 }
1707 StackEntry entry = stack[--ssize];
1708 isaD = entry.a;
1709 first = entry.b;
1710 last = entry.c;
1711 limit = entry.d;
1712 }
1713 } else if (a - first <= b - a) {
1714 if (1 < a - first) {
1715 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1716 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1717 last = a;
1718 } else if (1 < b - a) {
1719 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1720 isaD += 1;
1721 first = a;
1722 last = b;
1723 limit = next;
1724 } else {
1725 first = b;
1726 }
1727 } else {
1728 if (1 < b - a) {
1729 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1730 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1731 isaD += 1;
1732 first = a;
1733 last = b;
1734 limit = next;
1735 } else {
1736 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1737 last = a;
1738 }
1739 }
1740 } else {
1741 if (a - first <= b - a) {
1742 if (1 < last - b) {
1743 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1744 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1745 first = b;
1746 } else if (1 < a - first) {
1747 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1748 last = a;
1749 } else if (1 < b - a) {
1750 isaD += 1;
1751 first = a;
1752 last = b;
1753 limit = next;
1754 } else {
1755 stack[ssize++] = new StackEntry(isaD, first, last, limit);
1756 }
1757 } else if (last - b <= b - a) {
1758 if (1 < last - b) {
1759 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1760 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1761 first = b;
1762 } else if (1 < b - a) {
1763 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1764 isaD += 1;
1765 first = a;
1766 last = b;
1767 limit = next;
1768 } else {
1769 last = a;
1770 }
1771 } else {
1772 if (1 < b - a) {
1773 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1774 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1775 isaD += 1;
1776 first = a;
1777 last = b;
1778 limit = next;
1779 } else {
1780 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1781 first = b;
1782 }
1783 }
1784 }
1785 } else {
1786 if (!budget.update(size, last - first)) {
1787 break;
1788 }
1789 limit += 1; isaD += 1;
1790 }
1791 }
1792
1793 for (s = 0; s < ssize; ++s) {
1794 if (stack[s].d == -3) {
1795 lsUpdateGroup(isa, stack[s].b, stack[s].c);
1796 }
1797 }
1798 }
1799
1800 private static class TRBudget {
1801 int budget;
1802 int chance;
1803
1804 TRBudget(final int budget, final int chance) {
1805 this.budget = budget;
1806 this.chance = chance;
1807 }
1808
1809 boolean update(final int size, final int n) {
1810 budget -= n;
1811 if (budget <= 0) {
1812 if (--chance == 0) {
1813 return false;
1814 }
1815 budget += size;
1816 }
1817 return true;
1818 }
1819 }
1820
1821 private void trSort(final int isa, final int n, final int depth) {
1822 final int[] SA = this.SA;
1823
1824 int first = 0, last;
1825 int t;
1826
1827 if (-n < SA[0]) {
1828 TRBudget budget = new TRBudget(n, trLog(n) * 2 / 3 + 1);
1829 do {
1830 if ((t = SA[first]) < 0) {
1831 first -= t;
1832 } else {
1833 last = SA[isa + t] + 1;
1834 if (1 < last - first) {
1835 trIntroSort(isa, isa + depth, isa + n, first, last, budget, n);
1836 if (budget.chance == 0) {
1837
1838 if (0 < first) {
1839 SA[0] = -first;
1840 }
1841 lsSort(isa, n, depth);
1842 break;
1843 }
1844 }
1845 first = last;
1846 }
1847 } while (first < n);
1848 }
1849 }
1850
1851
1852
1853 private static int BUCKET_B(final int c0, final int c1) {
1854 return (c1 << 8) | c0;
1855 }
1856
1857 private static int BUCKET_BSTAR(final int c0, final int c1) {
1858 return (c0 << 8) | c1;
1859 }
1860
1861 private int sortTypeBstar(final int[] bucketA, final int[] bucketB) {
1862 final byte[] T = this.T;
1863 final int[] SA = this.SA;
1864 final int n = this.n;
1865 final int[] tempbuf = new int[256];
1866
1867 int[] buf;
1868 int PAb, ISAb, bufoffset;
1869 int i, j, k, t, m, bufsize;
1870 int c0, c1;
1871 int flag;
1872
1873 for (i = 1, flag = 1; i < n; ++i) {
1874 if (T[i - 1] != T[i]) {
1875 if ((T[i - 1] & 0xff) > (T[i] & 0xff)) {
1876 flag = 0;
1877 }
1878 break;
1879 }
1880 }
1881 i = n - 1;
1882 m = n;
1883
1884 int ti, ti1, t0;
1885 if ((ti = T[i] & 0xff) < (t0 = T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
1886 if (flag == 0) {
1887 ++bucketB[BUCKET_BSTAR(ti, t0)];
1888 SA[--m] = i;
1889 } else {
1890 ++bucketB[BUCKET_B(ti, t0)];
1891 }
1892 for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
1893 ++bucketB[BUCKET_B(ti, ti1)];
1894 }
1895 }
1896
1897 while (0 <= i) {
1898 do {
1899 ++bucketA[T[i] & 0xff];
1900 } while (0 <= --i && (T[i] & 0xff) >= (T[i + 1] & 0xff));
1901 if (0 <= i) {
1902 ++bucketB[BUCKET_BSTAR(T[i] & 0xff, T[i + 1] & 0xff)];
1903 SA[--m] = i;
1904 for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
1905 ++bucketB[BUCKET_B(ti, ti1)];
1906 }
1907 }
1908 }
1909 m = n - m;
1910 if (m == 0) {
1911 for (i = 0; i < n; ++i) {
1912 SA[i] = i;
1913 }
1914 return 0;
1915 }
1916
1917 for (c0 = 0, i = -1, j = 0; c0 < 256; ++c0) {
1918 t = i + bucketA[c0];
1919 bucketA[c0] = i + j;
1920 i = t + bucketB[BUCKET_B(c0, c0)];
1921 for (c1 = c0 + 1; c1 < 256; ++c1) {
1922 j += bucketB[BUCKET_BSTAR(c0, c1)];
1923 bucketB[(c0 << 8) | c1] = j;
1924 i += bucketB[BUCKET_B(c0, c1)];
1925 }
1926 }
1927
1928 PAb = n - m;
1929 ISAb = m;
1930 for (i = m - 2; 0 <= i; --i) {
1931 t = SA[PAb + i];
1932 c0 = T[t] & 0xff;
1933 c1 = T[t + 1] & 0xff;
1934 SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = i;
1935 }
1936 t = SA[PAb + m - 1];
1937 c0 = T[t] & 0xff;
1938 c1 = T[t + 1] & 0xff;
1939 SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = m - 1;
1940
1941 buf = SA;
1942 bufoffset = m;
1943 bufsize = n - 2 * m;
1944 if (bufsize <= 256) {
1945 buf = tempbuf;
1946 bufoffset = 0;
1947 bufsize = 256;
1948 }
1949
1950 for (c0 = 255, j = m; 0 < j; --c0) {
1951 for (c1 = 255; c0 < c1; j = i, --c1) {
1952 i = bucketB[BUCKET_BSTAR(c0, c1)];
1953 if (1 < j - i) {
1954 subStringSort(PAb, i, j, buf, bufoffset, bufsize, 2, SA[i] == m - 1, n);
1955 }
1956 }
1957 }
1958
1959 for (i = m - 1; 0 <= i; --i) {
1960 if (0 <= SA[i]) {
1961 j = i;
1962 do {
1963 SA[ISAb + SA[i]] = i;
1964 } while (0 <= --i && 0 <= SA[i]);
1965 SA[i + 1] = i - j;
1966 if (i <= 0) {
1967 break;
1968 }
1969 }
1970 j = i;
1971 do {
1972 SA[ISAb + (SA[i] = ~SA[i])] = j;
1973 } while (SA[--i] < 0);
1974 SA[ISAb + SA[i]] = j;
1975 }
1976
1977 trSort(ISAb, m, 1);
1978
1979 i = n - 1; j = m;
1980 if ((T[i] & 0xff) < (T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
1981 if (flag == 0) {
1982 SA[SA[ISAb + --j]] = i;
1983 }
1984 for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
1985 --i;
1986 }
1987 }
1988 while (0 <= i) {
1989 for (--i; 0 <= i && (T[i] & 0xff) >= (T[i + 1] & 0xff);) {
1990 --i;
1991 }
1992 if (0 <= i) {
1993 SA[SA[ISAb + --j]] = i;
1994 for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
1995 --i;
1996 }
1997 }
1998 }
1999
2000 for (c0 = 255, i = n - 1, k = m - 1; 0 <= c0; --c0) {
2001 for (c1 = 255; c0 < c1; --c1) {
2002 t = i - bucketB[BUCKET_B(c0, c1)];
2003 bucketB[BUCKET_B(c0, c1)] = i + 1;
2004
2005 for (i = t, j = bucketB[BUCKET_BSTAR(c0, c1)]; j <= k; --i, --k) {
2006 SA[i] = SA[k];
2007 }
2008 }
2009 t = i - bucketB[BUCKET_B(c0, c0)];
2010 bucketB[BUCKET_B(c0, c0)] = i + 1;
2011 if (c0 < 255) {
2012 bucketB[BUCKET_BSTAR(c0, c0 + 1)] = t + 1;
2013 }
2014 i = bucketA[c0];
2015 }
2016 return m;
2017 }
2018
2019 private int constructBWT(final int[] bucketA, final int[] bucketB) {
2020 final byte[] T = this.T;
2021 final int[] SA = this.SA;
2022 final int n = this.n;
2023
2024 int i, j, t = 0;
2025 int s, s1;
2026 int c0, c1, c2 = 0;
2027 int orig = -1;
2028
2029 for (c1 = 254; 0 <= c1; --c1) {
2030 for (i = bucketB[BUCKET_BSTAR(c1, c1 + 1)], j = bucketA[c1 + 1], t = 0, c2 = -1;
2031 i <= j;
2032 --j) {
2033 if (0 <= (s1 = s = SA[j])) {
2034 if (--s < 0) {
2035 s = n - 1;
2036 }
2037 if ((c0 = T[s] & 0xff) <= c1) {
2038 SA[j] = ~s1;
2039 if (0 < s && (T[s - 1] & 0xff) > c0) {
2040 s = ~s;
2041 }
2042 if (c2 == c0) {
2043 SA[--t] = s;
2044 } else {
2045 if (0 <= c2) {
2046 bucketB[BUCKET_B(c2, c1)] = t;
2047 }
2048 SA[t = bucketB[BUCKET_B(c2 = c0, c1)] - 1] = s;
2049 }
2050 }
2051 } else {
2052 SA[j] = ~s;
2053 }
2054 }
2055 }
2056
2057 for (i = 0; i < n; ++i) {
2058 if (0 <= (s1 = s = SA[i])) {
2059 if (--s < 0) {
2060 s = n - 1;
2061 }
2062 if ((c0 = T[s] & 0xff) >= (T[s + 1] & 0xff)) {
2063 if (0 < s && (T[s - 1] & 0xff) < c0) {
2064 s = ~s;
2065 }
2066 if (c0 == c2) {
2067 SA[++t] = s;
2068 } else {
2069 if (c2 != -1) {
2070 bucketA[c2] = t;
2071 }
2072 SA[t = bucketA[c2 = c0] + 1] = s;
2073 }
2074 }
2075 } else {
2076 s1 = ~s1;
2077 }
2078
2079 if (s1 == 0) {
2080 SA[i] = T[n - 1];
2081 orig = i;
2082 } else {
2083 SA[i] = T[s1 - 1];
2084 }
2085 }
2086 return orig;
2087 }
2088
2089
2090
2091
2092
2093 public int bwt() {
2094 final int[] SA = this.SA;
2095 final byte[] T = this.T;
2096 final int n = this.n;
2097
2098 final int[] bucketA = new int[BUCKET_A_SIZE];
2099 final int[] bucketB = new int[BUCKET_B_SIZE];
2100
2101 if (n == 0) {
2102 return 0;
2103 }
2104 if (n == 1) {
2105 SA[0] = T[0];
2106 return 0;
2107 }
2108
2109 int m = sortTypeBstar(bucketA, bucketB);
2110 if (0 < m) {
2111 return constructBWT(bucketA, bucketB);
2112 }
2113 return 0;
2114 }
2115 }