1 /*
2 * Copyright 2014 The Netty Project
3 *
4 * The Netty Project licenses this file to you under the Apache License,
5 * version 2.0 (the "License"); you may not use this file except in compliance
6 * with the License. You may obtain a copy of the License at:
7 *
8 * https://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13 * License for the specific language governing permissions and limitations
14 * under the License.
15 */
16 package io.netty.handler.codec.compression;
17
18 /**
19 * DivSufSort suffix array generator.<br>
20 *
21 * Based on <a href="https://code.google.com/p/libdivsufsort/">libdivsufsort</a> 1.2.3 patched to support Bzip2.<br>
22 * This is a simple conversion of the original C with two minor bugfixes applied (see "BUGFIX"
23 * comments within the class). Documentation within the class is largely absent.
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 * @param block The input array
50 * @param bwtBlock The output array
51 * @param blockLength The length of the input data
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 // pointers within T
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; // pointer within SA
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) {
572 SA[i++] = buf[j]; buf[j++] = SA[i];
573 }
574 SA[i] = buf[j]; buf[j] = t;
575 return;
576 }
577 } while (SA[k] < 0);
578 } else {
579 SA[k] = ~SA[k];
580 do {
581 SA[i++] = buf[j];
582 if (bufend <= j) {
583 buf[j] = t;
584 return;
585 }
586 buf[j++] = SA[i];
587 } while (buf[j] < 0);
588
589 do {
590 SA[i++] = SA[k];
591 SA[k++] = SA[i];
592 if (last <= k) {
593 while (j < bufend) {
594 SA[i++] = buf[j];
595 buf[j++] = SA[i];
596 }
597 SA[i] = buf[j]; buf[j] = t;
598 return;
599 }
600 } while (SA[k] < 0);
601 }
602 }
603 }
604
605 private void ssMergeBackward(final int pa, int[] buf, final int bufoffset,
606 final int first, final int middle, final int last, final int depth) {
607 final int[] SA = this.SA;
608
609 int p1, p2;
610 int bufend;
611 int i, j, k;
612 int t;
613 int r;
614 int x;
615
616 bufend = bufoffset + (last - middle);
617 ssBlockSwap(buf, bufoffset, SA, middle, last - middle);
618
619 x = 0;
620 if (buf[bufend - 1] < 0) {
621 x |= 1;
622 p1 = pa + ~buf[bufend - 1];
623 } else {
624 p1 = pa + buf[bufend - 1];
625 }
626 if (SA[middle - 1] < 0) {
627 x |= 2;
628 p2 = pa + ~SA[middle - 1];
629 } else {
630 p2 = pa + SA[middle - 1];
631 }
632 for (t = SA[last - 1], i = last - 1, j = bufend - 1, k = middle - 1;;) {
633
634 r = ssCompare(p1, p2, depth);
635 if (r > 0) {
636 if ((x & 1) != 0) {
637 do {
638 SA[i--] = buf[j];
639 buf[j--] = SA[i];
640 } while (buf[j] < 0);
641 x ^= 1;
642 }
643 SA[i--] = buf[j];
644 if (j <= bufoffset) {
645 buf[j] = t;
646 return;
647 }
648 buf[j--] = SA[i];
649
650 if (buf[j] < 0) {
651 x |= 1;
652 p1 = pa + ~buf[j];
653 } else {
654 p1 = pa + buf[j];
655 }
656 } else if (r < 0) {
657 if ((x & 2) != 0) {
658 do {
659 SA[i--] = SA[k];
660 SA[k--] = SA[i];
661 } while (SA[k] < 0);
662 x ^= 2;
663 }
664 SA[i--] = SA[k];
665 SA[k--] = SA[i];
666 if (k < first) {
667 while (bufoffset < j) {
668 SA[i--] = buf[j];
669 buf[j--] = SA[i];
670 }
671 SA[i] = buf[j];
672 buf[j] = t;
673 return;
674 }
675
676 if (SA[k] < 0) {
677 x |= 2;
678 p2 = pa + ~SA[k];
679 } else {
680 p2 = pa + SA[k];
681 }
682 } else {
683 if ((x & 1) != 0) {
684 do {
685 SA[i--] = buf[j];
686 buf[j--] = SA[i];
687 } while (buf[j] < 0);
688 x ^= 1;
689 }
690 SA[i--] = ~buf[j];
691 if (j <= bufoffset) {
692 buf[j] = t;
693 return;
694 }
695 buf[j--] = SA[i];
696
697 if ((x & 2) != 0) {
698 do {
699 SA[i--] = SA[k];
700 SA[k--] = SA[i];
701 } while (SA[k] < 0);
702 x ^= 2;
703 }
704 SA[i--] = SA[k];
705 SA[k--] = SA[i];
706 if (k < first) {
707 while (bufoffset < j) {
708 SA[i--] = buf[j];
709 buf[j--] = SA[i];
710 }
711 SA[i] = buf[j];
712 buf[j] = t;
713 return;
714 }
715
716 if (buf[j] < 0) {
717 x |= 1;
718 p1 = pa + ~buf[j];
719 } else {
720 p1 = pa + buf[j];
721 }
722 if (SA[k] < 0) {
723 x |= 2;
724 p2 = pa + ~SA[k];
725 } else {
726 p2 = pa + SA[k];
727 }
728 }
729 }
730 }
731
732 private static int getIDX(final int a) {
733 return 0 <= a ? a : ~a;
734 }
735
736 private void ssMergeCheckEqual(final int pa, final int depth, final int a) {
737 final int[] SA = this.SA;
738
739 if (0 <= SA[a] && ssCompare(pa + getIDX(SA[a - 1]), pa + SA[a], depth) == 0) {
740 SA[a] = ~SA[a];
741 }
742 }
743
744 private void ssMerge(final int pa, int first, int middle, int last, int[] buf,
745 final int bufoffset, final int bufsize, final int depth) {
746 final int[] SA = this.SA;
747
748 final StackEntry[] stack = new StackEntry[STACK_SIZE];
749
750 int i, j;
751 int m, len, half;
752 int ssize;
753 int check, next;
754
755 for (check = 0, ssize = 0;;) {
756
757 if (last - middle <= bufsize) {
758 if (first < middle && middle < last) {
759 ssMergeBackward(pa, buf, bufoffset, first, middle, last, depth);
760 }
761
762 if ((check & 1) != 0) {
763 ssMergeCheckEqual(pa, depth, first);
764 }
765 if ((check & 2) != 0) {
766 ssMergeCheckEqual(pa, depth, last);
767 }
768 if (ssize == 0) {
769 return;
770 }
771 StackEntry entry = stack[--ssize];
772 first = entry.a;
773 middle = entry.b;
774 last = entry.c;
775 check = entry.d;
776 continue;
777 }
778
779 if (middle - first <= bufsize) {
780 if (first < middle) {
781 ssMergeForward(pa, buf, bufoffset, first, middle, last, depth);
782 }
783 if ((check & 1) != 0) {
784 ssMergeCheckEqual(pa, depth, first);
785 }
786 if ((check & 2) != 0) {
787 ssMergeCheckEqual(pa, depth, last);
788 }
789 if (ssize == 0) {
790 return;
791 }
792 StackEntry entry = stack[--ssize];
793 first = entry.a;
794 middle = entry.b;
795 last = entry.c;
796 check = entry.d;
797 continue;
798 }
799
800 for (m = 0, len = Math.min(middle - first, last - middle), half = len >> 1;
801 0 < len;
802 len = half, half >>= 1) {
803
804 if (ssCompare(pa + getIDX(SA[middle + m + half]),
805 pa + getIDX(SA[middle - m - half - 1]), depth) < 0) {
806 m += half + 1;
807 half -= (len & 1) ^ 1;
808 }
809 }
810
811 if (0 < m) {
812 ssBlockSwap(SA, middle - m, SA, middle, m);
813 i = j = middle;
814 next = 0;
815 if (middle + m < last) {
816 if (SA[middle + m] < 0) {
817 while (SA[i - 1] < 0) {
818 --i;
819 }
820 SA[middle + m] = ~SA[middle + m];
821 }
822 for (j = middle; SA[j] < 0;) {
823 ++j;
824 }
825 next = 1;
826 }
827 if (i - first <= last - j) {
828 stack[ssize++] = new StackEntry(j, middle + m, last, (check & 2) | (next & 1));
829 middle -= m;
830 last = i;
831 check &= 1;
832 } else {
833 if (i == middle && middle == j) {
834 next <<= 1;
835 }
836 stack[ssize++] = new StackEntry(first, middle - m, i, (check & 1) | (next & 2));
837 first = j;
838 middle += m;
839 check = (check & 2) | (next & 1);
840 }
841 } else {
842 if ((check & 1) != 0) {
843 ssMergeCheckEqual(pa, depth, first);
844 }
845 ssMergeCheckEqual(pa, depth, middle);
846 if ((check & 2) != 0) {
847 ssMergeCheckEqual(pa, depth, last);
848 }
849 if (ssize == 0) {
850 return;
851 }
852 StackEntry entry = stack[--ssize];
853 first = entry.a;
854 middle = entry.b;
855 last = entry.c;
856 check = entry.d;
857 }
858 }
859 }
860
861 private void subStringSort(final int pa, int first, final int last,
862 final int[] buf, final int bufoffset, final int bufsize,
863 final int depth, final boolean lastsuffix, final int size) {
864 final int[] SA = this.SA;
865
866 int a, b;
867 int[] curbuf;
868 int curbufoffset;
869 int i, j, k;
870 int curbufsize;
871
872 if (lastsuffix) {
873 ++first;
874 }
875 for (a = first, i = 0; a + SS_BLOCKSIZE < last; a += SS_BLOCKSIZE, ++i) {
876 ssMultiKeyIntroSort(pa, a, a + SS_BLOCKSIZE, depth);
877 curbuf = SA;
878 curbufoffset = a + SS_BLOCKSIZE;
879 curbufsize = last - (a + SS_BLOCKSIZE);
880 if (curbufsize <= bufsize) {
881 curbufsize = bufsize;
882 curbuf = buf;
883 curbufoffset = bufoffset;
884 }
885 for (b = a, k = SS_BLOCKSIZE, j = i; (j & 1) != 0; b -= k, k <<= 1, j >>>= 1) {
886 ssMerge(pa, b - k, b, b + k, curbuf, curbufoffset, curbufsize, depth);
887 }
888 }
889
890 ssMultiKeyIntroSort(pa, a, last, depth);
891
892 for (k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
893 if ((i & 1) != 0) {
894 ssMerge(pa, a - k, a, last, buf, bufoffset, bufsize, depth);
895 a -= k;
896 }
897 }
898
899 if (lastsuffix) {
900 int r;
901 for (a = first, i = SA[first - 1], r = 1;
902 a < last && (SA[a] < 0 || 0 < (r = ssCompareLast(pa, pa + i, pa + SA[a], depth, size)));
903 ++a) {
904 SA[a - 1] = SA[a];
905 }
906 if (r == 0) {
907 SA[a] = ~SA[a];
908 }
909 SA[a - 1] = i;
910 }
911 }
912
913 /*----------------------------------------------------------------------------*/
914
915 private int trGetC(final int isa, final int isaD, final int isaN, final int p) {
916 return isaD + p < isaN ?
917 SA[isaD + p]
918 : SA[isa + ((isaD - isa + p) % (isaN - isa))];
919 }
920
921 private void trFixdown(final int isa, final int isaD, final int isaN, final int sa, int i, final int size) {
922 final int[] SA = this.SA;
923
924 int j, k;
925 int v;
926 int c, d, e;
927
928 for (v = SA[sa + i], c = trGetC(isa, isaD, isaN, v); (j = 2 * i + 1) < size; SA[sa + i] = SA[sa + k], i = k) {
929 k = j++;
930 d = trGetC(isa, isaD, isaN, SA[sa + k]);
931 if (d < (e = trGetC(isa, isaD, isaN, SA[sa + j]))) {
932 k = j;
933 d = e;
934 }
935 if (d <= c) {
936 break;
937 }
938 }
939 SA[sa + i] = v;
940 }
941
942 private void trHeapSort(final int isa, final int isaD, final int isaN, final int sa, final int size) {
943 final int[] SA = this.SA;
944
945 int i, m;
946 int t;
947
948 m = size;
949 if (size % 2 == 0) {
950 m--;
951 if (trGetC(isa, isaD, isaN, SA[sa + m / 2]) < trGetC(isa, isaD, isaN, SA[sa + m])) {
952 swapElements(SA, sa + m, SA, sa + m / 2);
953 }
954 }
955
956 for (i = m / 2 - 1; 0 <= i; --i) {
957 trFixdown(isa, isaD, isaN, sa, i, m);
958 }
959
960 if (size % 2 == 0) {
961 swapElements(SA, sa, SA, sa + m);
962 trFixdown(isa, isaD, isaN, sa, 0, m);
963 }
964
965 for (i = m - 1; 0 < i; --i) {
966 t = SA[sa];
967 SA[sa] = SA[sa + i];
968 trFixdown(isa, isaD, isaN, sa, 0, i);
969 SA[sa + i] = t;
970 }
971 }
972
973 private void trInsertionSort(final int isa, final int isaD, final int isaN, int first, int last) {
974 final int[] SA = this.SA;
975
976 int a, b;
977 int t, r;
978
979 for (a = first + 1; a < last; ++a) {
980 for (t = SA[a], b = a - 1; 0 > (r = trGetC(isa, isaD, isaN, t) - trGetC(isa, isaD, isaN, SA[b]));) {
981 do {
982 SA[b + 1] = SA[b];
983 } while (first <= --b && SA[b] < 0);
984 if (b < first) {
985 break;
986 }
987 }
988 if (r == 0) {
989 SA[b] = ~SA[b];
990 }
991 SA[b + 1] = t;
992 }
993 }
994
995 private static int trLog(int n) {
996 return (n & 0xffff0000) != 0 ?
997 (n & 0xff000000) != 0 ? 24 + LOG_2_TABLE[n >> 24 & 0xff] : LOG_2_TABLE[n >> 16 & 0xff + 16]
998 : (n & 0x0000ff00) != 0 ? 8 + LOG_2_TABLE[n >> 8 & 0xff] : LOG_2_TABLE[n & 0xff];
999 }
1000
1001 private int trMedian3(final int isa, final int isaD, final int isaN, int v1, int v2, int v3) {
1002 final int[] SA = this.SA;
1003
1004 int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
1005 int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
1006 int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);
1007
1008 if (SA_v1 > SA_v2) {
1009 final int temp = v1;
1010 v1 = v2;
1011 v2 = temp;
1012 final int SA_vtemp = SA_v1;
1013 SA_v1 = SA_v2;
1014 SA_v2 = SA_vtemp;
1015 }
1016 if (SA_v2 > SA_v3) {
1017 if (SA_v1 > SA_v3) {
1018 return v1;
1019 }
1020 return v3;
1021 }
1022
1023 return v2;
1024 }
1025
1026 private int trMedian5(final int isa, final int isaD, final int isaN, int v1, int v2, int v3, int v4, int v5) {
1027 final int[] SA = this.SA;
1028
1029 int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
1030 int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
1031 int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);
1032 int SA_v4 = trGetC(isa, isaD, isaN, SA[v4]);
1033 int SA_v5 = trGetC(isa, isaD, isaN, SA[v5]);
1034 int temp;
1035 int SA_vtemp;
1036
1037 if (SA_v2 > SA_v3) {
1038 temp = v2;
1039 v2 = v3;
1040 v3 = temp;
1041 SA_vtemp = SA_v2;
1042 SA_v2 = SA_v3;
1043 SA_v3 = SA_vtemp;
1044 }
1045 if (SA_v4 > SA_v5) {
1046 temp = v4;
1047 v4 = v5;
1048 v5 = temp;
1049 SA_vtemp = SA_v4;
1050 SA_v4 = SA_v5;
1051 SA_v5 = SA_vtemp;
1052 }
1053 if (SA_v2 > SA_v4) {
1054 temp = v2;
1055 v4 = temp;
1056 SA_vtemp = SA_v2;
1057 SA_v4 = SA_vtemp;
1058 temp = v3;
1059 v3 = v5;
1060 v5 = temp;
1061 SA_vtemp = SA_v3;
1062 SA_v3 = SA_v5;
1063 SA_v5 = SA_vtemp;
1064 }
1065 if (SA_v1 > SA_v3) {
1066 temp = v1;
1067 v1 = v3;
1068 v3 = temp;
1069 SA_vtemp = SA_v1;
1070 SA_v1 = SA_v3;
1071 SA_v3 = SA_vtemp;
1072 }
1073 if (SA_v1 > SA_v4) {
1074 temp = v1;
1075 v4 = temp;
1076 SA_vtemp = SA_v1;
1077 SA_v4 = SA_vtemp;
1078 v3 = v5;
1079 SA_v3 = SA_v5;
1080 }
1081 if (SA_v3 > SA_v4) {
1082 return v4;
1083 }
1084 return v3;
1085 }
1086
1087 private int trPivot(final int isa, final int isaD, final int isaN, final int first, final int last) {
1088 final int middle;
1089 int t;
1090
1091 t = last - first;
1092 middle = first + t / 2;
1093
1094 if (t <= 512) {
1095 if (t <= 32) {
1096 return trMedian3(isa, isaD, isaN, first, middle, last - 1);
1097 }
1098 t >>= 2;
1099 return trMedian5(
1100 isa, isaD, isaN,
1101 first, first + t,
1102 middle,
1103 last - 1 - t, last - 1
1104 );
1105 }
1106 t >>= 3;
1107 return trMedian3(
1108 isa, isaD, isaN,
1109 trMedian3(isa, isaD, isaN, first, first + t, first + (t << 1)),
1110 trMedian3(isa, isaD, isaN, middle - t, middle, middle + t),
1111 trMedian3(isa, isaD, isaN, last - 1 - (t << 1), last - 1 - t, last - 1)
1112 );
1113 }
1114
1115 /*---------------------------------------------------------------------------*/
1116
1117 private void lsUpdateGroup(final int isa, final int first, final int last) {
1118 final int[] SA = this.SA;
1119
1120 int a, b;
1121 int t;
1122
1123 for (a = first; a < last; ++a) {
1124 if (0 <= SA[a]) {
1125 b = a;
1126 do {
1127 SA[isa + SA[a]] = a;
1128 } while (++a < last && 0 <= SA[a]);
1129 SA[b] = b - a;
1130 if (last <= a) {
1131 break;
1132 }
1133 }
1134 b = a;
1135 do {
1136 SA[a] = ~SA[a];
1137 } while (SA[++a] < 0);
1138 t = a;
1139 do {
1140 SA[isa + SA[b]] = t;
1141 } while (++b <= a);
1142 }
1143 }
1144
1145 private void lsIntroSort(final int isa, final int isaD, final int isaN, int first, int last) {
1146 final int[] SA = this.SA;
1147
1148 final StackEntry[] stack = new StackEntry[STACK_SIZE];
1149
1150 int a, b, c, d, e, f;
1151 int s, t;
1152 int limit;
1153 int v, x = 0;
1154 int ssize;
1155
1156 for (ssize = 0, limit = trLog(last - first);;) {
1157 if (last - first <= INSERTIONSORT_THRESHOLD) {
1158 if (1 < last - first) {
1159 trInsertionSort(isa, isaD, isaN, first, last);
1160 lsUpdateGroup(isa, first, last);
1161 } else if (last - first == 1) {
1162 SA[first] = -1;
1163 }
1164 if (ssize == 0) {
1165 return;
1166 }
1167 StackEntry entry = stack[--ssize];
1168 first = entry.a;
1169 last = entry.b;
1170 limit = entry.c;
1171 continue;
1172 }
1173
1174 if (limit-- == 0) {
1175 trHeapSort(isa, isaD, isaN, first, last - first);
1176 for (a = last - 1; first < a; a = b) {
1177 for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
1178 first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
1179 --b) {
1180 SA[b] = ~SA[b];
1181 }
1182 }
1183 lsUpdateGroup(isa, first, last);
1184 if (ssize == 0) {
1185 return;
1186 }
1187 StackEntry entry = stack[--ssize];
1188 first = entry.a;
1189 last = entry.b;
1190 limit = entry.c;
1191 continue;
1192 }
1193
1194 a = trPivot(isa, isaD, isaN, first, last);
1195 swapElements(SA, first, SA, a);
1196 v = trGetC(isa, isaD, isaN, SA[first]);
1197
1198 b = first + 1;
1199 while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1200 ++b;
1201 }
1202 if ((a = b) < last && x < v) {
1203 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1204 if (x == v) {
1205 swapElements(SA, b, SA, a);
1206 ++a;
1207 }
1208 }
1209 }
1210
1211 c = last - 1;
1212 while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1213 --c;
1214 }
1215 if (b < (d = c) && x > v) {
1216 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1217 if (x == v) {
1218 swapElements(SA, c, SA, d);
1219 --d;
1220 }
1221 }
1222 }
1223 while (b < c) {
1224 swapElements(SA, b, SA, c);
1225 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1226 if (x == v) {
1227 swapElements(SA, b, SA, a);
1228 ++a;
1229 }
1230 }
1231 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1232 if (x == v) {
1233 swapElements(SA, c, SA, d);
1234 --d;
1235 }
1236 }
1237 }
1238
1239 if (a <= d) {
1240 c = b - 1;
1241
1242 if ((s = a - first) > (t = b - a)) {
1243 s = t;
1244 }
1245 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1246 swapElements(SA, e, SA, f);
1247 }
1248 if ((s = d - c) > (t = last - d - 1)) {
1249 s = t;
1250 }
1251 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1252 swapElements(SA, e, SA, f);
1253 }
1254
1255 a = first + (b - a);
1256 b = last - (d - c);
1257
1258 for (c = first, v = a - 1; c < a; ++c) {
1259 SA[isa + SA[c]] = v;
1260 }
1261 if (b < last) {
1262 for (c = a, v = b - 1; c < b; ++c) {
1263 SA[isa + SA[c]] = v;
1264 }
1265 }
1266 if ((b - a) == 1) {
1267 SA[a] = - 1;
1268 }
1269
1270 if (a - first <= last - b) {
1271 if (first < a) {
1272 stack[ssize++] = new StackEntry(b, last, limit, 0);
1273 last = a;
1274 } else {
1275 first = b;
1276 }
1277 } else {
1278 if (b < last) {
1279 stack[ssize++] = new StackEntry(first, a, limit, 0);
1280 first = b;
1281 } else {
1282 last = a;
1283 }
1284 }
1285 } else {
1286 if (ssize == 0) {
1287 return;
1288 }
1289 StackEntry entry = stack[--ssize];
1290 first = entry.a;
1291 last = entry.b;
1292 limit = entry.c;
1293 }
1294 }
1295 }
1296
1297 private void lsSort(final int isa, final int n, final int depth) {
1298 final int[] SA = this.SA;
1299
1300 int isaD;
1301 int first, last, i;
1302 int t, skip;
1303
1304 for (isaD = isa + depth; -n < SA[0]; isaD += isaD - isa) {
1305 first = 0;
1306 skip = 0;
1307 do {
1308 if ((t = SA[first]) < 0) {
1309 first -= t;
1310 skip += t;
1311 } else {
1312 if (skip != 0) {
1313 SA[first + skip] = skip;
1314 skip = 0;
1315 }
1316 last = SA[isa + t] + 1;
1317 lsIntroSort(isa, isaD, isa + n, first, last);
1318 first = last;
1319 }
1320 } while (first < n);
1321 if (skip != 0) {
1322 SA[first + skip] = skip;
1323 }
1324 if (n < isaD - isa) {
1325 first = 0;
1326 do {
1327 if ((t = SA[first]) < 0) {
1328 first -= t;
1329 } else {
1330 last = SA[isa + t] + 1;
1331 for (i = first; i < last; ++i) {
1332 SA[isa + SA[i]] = i;
1333 }
1334 first = last;
1335 }
1336 } while (first < n);
1337 break;
1338 }
1339 }
1340 }
1341
1342 /*---------------------------------------------------------------------------*/
1343
1344 private static class PartitionResult {
1345 final int first;
1346 final int last;
1347
1348 PartitionResult(final int first, final int last) {
1349 this.first = first;
1350 this.last = last;
1351 }
1352 }
1353
1354 private PartitionResult trPartition(final int isa, final int isaD, final int isaN,
1355 int first, int last, final int v) {
1356 final int[] SA = this.SA;
1357
1358 int a, b, c, d, e, f;
1359 int t, s;
1360 int x = 0;
1361
1362 b = first;
1363 while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1364 ++b;
1365 }
1366 if ((a = b) < last && x < v) {
1367 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1368 if (x == v) {
1369 swapElements(SA, b, SA, a);
1370 ++a;
1371 }
1372 }
1373 }
1374
1375 c = last - 1;
1376 while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1377 --c;
1378 }
1379 if (b < (d = c) && x > v) {
1380 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1381 if (x == v) {
1382 swapElements(SA, c, SA, d);
1383 --d;
1384 }
1385 }
1386 }
1387 while (b < c) {
1388 swapElements(SA, b, SA, c);
1389 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1390 if (x == v) {
1391 swapElements(SA, b, SA, a);
1392 ++a;
1393 }
1394 }
1395 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1396 if (x == v) {
1397 swapElements(SA, c, SA, d);
1398 --d;
1399 }
1400 }
1401 }
1402
1403 if (a <= d) {
1404 c = b - 1;
1405 if ((s = a - first) > (t = b - a)) {
1406 s = t;
1407 }
1408 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1409 swapElements(SA, e, SA, f);
1410 }
1411 if ((s = d - c) > (t = last - d - 1)) {
1412 s = t;
1413 }
1414 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1415 swapElements(SA, e, SA, f);
1416 }
1417 first += b - a;
1418 last -= d - c;
1419 }
1420 return new PartitionResult(first, last);
1421 }
1422
1423 private void trCopy(final int isa, final int isaN, final int first,
1424 final int a, final int b, final int last, final int depth) {
1425 final int[] SA = this.SA;
1426
1427 int c, d, e;
1428 int s, v;
1429
1430 v = b - 1;
1431
1432 for (c = first, d = a - 1; c <= d; ++c) {
1433 if ((s = SA[c] - depth) < 0) {
1434 s += isaN - isa;
1435 }
1436 if (SA[isa + s] == v) {
1437 SA[++d] = s;
1438 SA[isa + s] = d;
1439 }
1440 }
1441 for (c = last - 1, e = d + 1, d = b; e < d; --c) {
1442 if ((s = SA[c] - depth) < 0) {
1443 s += isaN - isa;
1444 }
1445 if (SA[isa + s] == v) {
1446 SA[--d] = s;
1447 SA[isa + s] = d;
1448 }
1449 }
1450 }
1451
1452 private void trIntroSort(final int isa, int isaD, int isaN, int first,
1453 int last, final TRBudget budget, final int size) {
1454 final int[] SA = this.SA;
1455
1456 final StackEntry[] stack = new StackEntry[STACK_SIZE];
1457
1458 int a, b, c, d, e, f;
1459 int s, t;
1460 int v, x = 0;
1461 int limit, next;
1462 int ssize;
1463
1464 for (ssize = 0, limit = trLog(last - first);;) {
1465 if (limit < 0) {
1466 if (limit == -1) {
1467 if (!budget.update(size, last - first)) {
1468 break;
1469 }
1470 PartitionResult result = trPartition(isa, isaD - 1, isaN, first, last, last - 1);
1471 a = result.first;
1472 b = result.last;
1473 if (first < a || b < last) {
1474 if (a < last) {
1475 for (c = first, v = a - 1; c < a; ++c) {
1476 SA[isa + SA[c]] = v;
1477 }
1478 }
1479 if (b < last) {
1480 for (c = a, v = b - 1; c < b; ++c) {
1481 SA[isa + SA[c]] = v;
1482 }
1483 }
1484
1485 stack[ssize++] = new StackEntry(0, a, b, 0);
1486 stack[ssize++] = new StackEntry(isaD - 1, first, last, -2);
1487 if (a - first <= last - b) {
1488 if (1 < a - first) {
1489 stack[ssize++] = new StackEntry(isaD, b, last, trLog(last - b));
1490 last = a; limit = trLog(a - first);
1491 } else if (1 < last - b) {
1492 first = b; limit = trLog(last - b);
1493 } else {
1494 if (ssize == 0) {
1495 return;
1496 }
1497 StackEntry entry = stack[--ssize];
1498 isaD = entry.a;
1499 first = entry.b;
1500 last = entry.c;
1501 limit = entry.d;
1502 }
1503 } else {
1504 if (1 < last - b) {
1505 stack[ssize++] = new StackEntry(isaD, first, a, trLog(a - first));
1506 first = b;
1507 limit = trLog(last - b);
1508 } else if (1 < a - first) {
1509 last = a;
1510 limit = trLog(a - first);
1511 } else {
1512 if (ssize == 0) {
1513 return;
1514 }
1515 StackEntry entry = stack[--ssize];
1516 isaD = entry.a;
1517 first = entry.b;
1518 last = entry.c;
1519 limit = entry.d;
1520 }
1521 }
1522 } else {
1523 for (c = first; c < last; ++c) {
1524 SA[isa + SA[c]] = c;
1525 }
1526 if (ssize == 0) {
1527 return;
1528 }
1529 StackEntry entry = stack[--ssize];
1530 isaD = entry.a;
1531 first = entry.b;
1532 last = entry.c;
1533 limit = entry.d;
1534 }
1535 } else if (limit == -2) {
1536 a = stack[--ssize].b;
1537 b = stack[ssize].c;
1538 trCopy(isa, isaN, first, a, b, last, isaD - isa);
1539 if (ssize == 0) {
1540 return;
1541 }
1542 StackEntry entry = stack[--ssize];
1543 isaD = entry.a;
1544 first = entry.b;
1545 last = entry.c;
1546 limit = entry.d;
1547 } else {
1548 if (0 <= SA[first]) {
1549 a = first;
1550 do {
1551 SA[isa + SA[a]] = a;
1552 } while (++a < last && 0 <= SA[a]);
1553 first = a;
1554 }
1555 if (first < last) {
1556 a = first;
1557 do {
1558 SA[a] = ~SA[a];
1559 } while (SA[++a] < 0);
1560 next = SA[isa + SA[a]] != SA[isaD + SA[a]] ? trLog(a - first + 1) : -1;
1561 if (++a < last) {
1562 for (b = first, v = a - 1; b < a; ++b) {
1563 SA[isa + SA[b]] = v;
1564 }
1565 }
1566
1567 if (a - first <= last - a) {
1568 stack[ssize++] = new StackEntry(isaD, a, last, -3);
1569 isaD += 1; last = a; limit = next;
1570 } else {
1571 if (1 < last - a) {
1572 stack[ssize++] = new StackEntry(isaD + 1, first, a, next);
1573 first = a; limit = -3;
1574 } else {
1575 isaD += 1; last = a; limit = next;
1576 }
1577 }
1578 } else {
1579 if (ssize == 0) {
1580 return;
1581 }
1582 StackEntry entry = stack[--ssize];
1583 isaD = entry.a;
1584 first = entry.b;
1585 last = entry.c;
1586 limit = entry.d;
1587 }
1588 }
1589 continue;
1590 }
1591
1592 if (last - first <= INSERTIONSORT_THRESHOLD) {
1593 if (!budget.update(size, last - first)) {
1594 break;
1595 }
1596 trInsertionSort(isa, isaD, isaN, first, last);
1597 limit = -3;
1598 continue;
1599 }
1600
1601 if (limit-- == 0) {
1602 if (!budget.update(size, last - first)) {
1603 break;
1604 }
1605 trHeapSort(isa, isaD, isaN, first, last - first);
1606 for (a = last - 1; first < a; a = b) {
1607 for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
1608 first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
1609 --b) {
1610 SA[b] = ~SA[b];
1611 }
1612 }
1613 limit = -3;
1614 continue;
1615 }
1616
1617 a = trPivot(isa, isaD, isaN, first, last);
1618
1619 swapElements(SA, first, SA, a);
1620 v = trGetC(isa, isaD, isaN, SA[first]);
1621
1622 b = first + 1;
1623 while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
1624 ++b;
1625 }
1626 if ((a = b) < last && x < v) {
1627 while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1628 if (x == v) {
1629 swapElements(SA, b, SA, a);
1630 ++a;
1631 }
1632 }
1633 }
1634
1635 c = last - 1;
1636 while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
1637 --c;
1638 }
1639 if (b < (d = c) && x > v) {
1640 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1641 if (x == v) {
1642 swapElements(SA, c, SA, d);
1643 --d;
1644 }
1645 }
1646 }
1647 while (b < c) {
1648 swapElements(SA, b, SA, c);
1649 while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
1650 if (x == v) {
1651 swapElements(SA, b, SA, a);
1652 ++a;
1653 }
1654 }
1655 while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
1656 if (x == v) {
1657 swapElements(SA, c, SA, d);
1658 --d;
1659 }
1660 }
1661 }
1662
1663 if (a <= d) {
1664 c = b - 1;
1665
1666 if ((s = a - first) > (t = b - a)) {
1667 s = t;
1668 }
1669 for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
1670 swapElements(SA, e, SA, f);
1671 }
1672 if ((s = d - c) > (t = last - d - 1)) {
1673 s = t;
1674 }
1675 for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
1676 swapElements(SA, e, SA, f);
1677 }
1678
1679 a = first + (b - a);
1680 b = last - (d - c);
1681 next = SA[isa + SA[a]] != v ? trLog(b - a) : -1;
1682
1683 for (c = first, v = a - 1; c < a; ++c) {
1684 SA[isa + SA[c]] = v;
1685 }
1686 if (b < last) {
1687 for (c = a, v = b - 1; c < b; ++c) {
1688 SA[isa + SA[c]] = v; }
1689 }
1690
1691 if (a - first <= last - b) {
1692 if (last - b <= b - a) {
1693 if (1 < a - first) {
1694 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1695 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1696 last = a;
1697 } else if (1 < last - b) {
1698 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1699 first = b;
1700 } else if (1 < b - a) {
1701 isaD += 1;
1702 first = a;
1703 last = b;
1704 limit = next;
1705 } else {
1706 if (ssize == 0) {
1707 return;
1708 }
1709 StackEntry entry = stack[--ssize];
1710 isaD = entry.a;
1711 first = entry.b;
1712 last = entry.c;
1713 limit = entry.d;
1714 }
1715 } else if (a - first <= b - a) {
1716 if (1 < a - first) {
1717 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1718 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1719 last = a;
1720 } else if (1 < b - a) {
1721 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1722 isaD += 1;
1723 first = a;
1724 last = b;
1725 limit = next;
1726 } else {
1727 first = b;
1728 }
1729 } else {
1730 if (1 < b - a) {
1731 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1732 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1733 isaD += 1;
1734 first = a;
1735 last = b;
1736 limit = next;
1737 } else {
1738 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1739 last = a;
1740 }
1741 }
1742 } else {
1743 if (a - first <= b - a) {
1744 if (1 < last - b) {
1745 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1746 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1747 first = b;
1748 } else if (1 < a - first) {
1749 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1750 last = a;
1751 } else if (1 < b - a) {
1752 isaD += 1;
1753 first = a;
1754 last = b;
1755 limit = next;
1756 } else {
1757 stack[ssize++] = new StackEntry(isaD, first, last, limit);
1758 }
1759 } else if (last - b <= b - a) {
1760 if (1 < last - b) {
1761 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1762 stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
1763 first = b;
1764 } else if (1 < b - a) {
1765 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1766 isaD += 1;
1767 first = a;
1768 last = b;
1769 limit = next;
1770 } else {
1771 last = a;
1772 }
1773 } else {
1774 if (1 < b - a) {
1775 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1776 stack[ssize++] = new StackEntry(isaD, b, last, limit);
1777 isaD += 1;
1778 first = a;
1779 last = b;
1780 limit = next;
1781 } else {
1782 stack[ssize++] = new StackEntry(isaD, first, a, limit);
1783 first = b;
1784 }
1785 }
1786 }
1787 } else {
1788 if (!budget.update(size, last - first)) {
1789 break; // BUGFIX : Added to prevent an infinite loop in the original code
1790 }
1791 limit += 1; isaD += 1;
1792 }
1793 }
1794
1795 for (s = 0; s < ssize; ++s) {
1796 if (stack[s].d == -3) {
1797 lsUpdateGroup(isa, stack[s].b, stack[s].c);
1798 }
1799 }
1800 }
1801
1802 private static class TRBudget {
1803 int budget;
1804 int chance;
1805
1806 TRBudget(final int budget, final int chance) {
1807 this.budget = budget;
1808 this.chance = chance;
1809 }
1810
1811 boolean update(final int size, final int n) {
1812 budget -= n;
1813 if (budget <= 0) {
1814 if (--chance == 0) {
1815 return false;
1816 }
1817 budget += size;
1818 }
1819 return true;
1820 }
1821 }
1822
1823 private void trSort(final int isa, final int n, final int depth) {
1824 final int[] SA = this.SA;
1825
1826 int first = 0, last;
1827 int t;
1828
1829 if (-n < SA[0]) {
1830 TRBudget budget = new TRBudget(n, trLog(n) * 2 / 3 + 1);
1831 do {
1832 if ((t = SA[first]) < 0) {
1833 first -= t;
1834 } else {
1835 last = SA[isa + t] + 1;
1836 if (1 < last - first) {
1837 trIntroSort(isa, isa + depth, isa + n, first, last, budget, n);
1838 if (budget.chance == 0) {
1839 /* Switch to Larsson-Sadakane sorting algorithm */
1840 if (0 < first) {
1841 SA[0] = -first;
1842 }
1843 lsSort(isa, n, depth);
1844 break;
1845 }
1846 }
1847 first = last;
1848 }
1849 } while (first < n);
1850 }
1851 }
1852
1853 /*---------------------------------------------------------------------------*/
1854
1855 private static int BUCKET_B(final int c0, final int c1) {
1856 return (c1 << 8) | c0;
1857 }
1858
1859 private static int BUCKET_BSTAR(final int c0, final int c1) {
1860 return (c0 << 8) | c1;
1861 }
1862
1863 private int sortTypeBstar(final int[] bucketA, final int[] bucketB) {
1864 final byte[] T = this.T;
1865 final int[] SA = this.SA;
1866 final int n = this.n;
1867 final int[] tempbuf = new int[256];
1868
1869 int[] buf;
1870 int PAb, ISAb, bufoffset;
1871 int i, j, k, t, m, bufsize;
1872 int c0, c1;
1873 int flag;
1874
1875 for (i = 1, flag = 1; i < n; ++i) {
1876 if (T[i - 1] != T[i]) {
1877 if ((T[i - 1] & 0xff) > (T[i] & 0xff)) {
1878 flag = 0;
1879 }
1880 break;
1881 }
1882 }
1883 i = n - 1;
1884 m = n;
1885
1886 int ti, ti1, t0;
1887 if ((ti = T[i] & 0xff) < (t0 = T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
1888 if (flag == 0) {
1889 ++bucketB[BUCKET_BSTAR(ti, t0)];
1890 SA[--m] = i;
1891 } else {
1892 ++bucketB[BUCKET_B(ti, t0)];
1893 }
1894 for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
1895 ++bucketB[BUCKET_B(ti, ti1)];
1896 }
1897 }
1898
1899 while (0 <= i) {
1900 do {
1901 ++bucketA[T[i] & 0xff];
1902 } while (0 <= --i && (T[i] & 0xff) >= (T[i + 1] & 0xff));
1903 if (0 <= i) {
1904 ++bucketB[BUCKET_BSTAR(T[i] & 0xff, T[i + 1] & 0xff)];
1905 SA[--m] = i;
1906 for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
1907 ++bucketB[BUCKET_B(ti, ti1)];
1908 }
1909 }
1910 }
1911 m = n - m;
1912 if (m == 0) {
1913 for (i = 0; i < n; ++i) {
1914 SA[i] = i;
1915 }
1916 return 0;
1917 }
1918
1919 for (c0 = 0, i = -1, j = 0; c0 < 256; ++c0) {
1920 t = i + bucketA[c0];
1921 bucketA[c0] = i + j;
1922 i = t + bucketB[BUCKET_B(c0, c0)];
1923 for (c1 = c0 + 1; c1 < 256; ++c1) {
1924 j += bucketB[BUCKET_BSTAR(c0, c1)];
1925 bucketB[(c0 << 8) | c1] = j;
1926 i += bucketB[BUCKET_B(c0, c1)];
1927 }
1928 }
1929
1930 PAb = n - m;
1931 ISAb = m;
1932 for (i = m - 2; 0 <= i; --i) {
1933 t = SA[PAb + i];
1934 c0 = T[t] & 0xff;
1935 c1 = T[t + 1] & 0xff;
1936 SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = i;
1937 }
1938 t = SA[PAb + m - 1];
1939 c0 = T[t] & 0xff;
1940 c1 = T[t + 1] & 0xff;
1941 SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = m - 1;
1942
1943 buf = SA;
1944 bufoffset = m;
1945 bufsize = n - 2 * m;
1946 if (bufsize <= 256) {
1947 buf = tempbuf;
1948 bufoffset = 0;
1949 bufsize = 256;
1950 }
1951
1952 for (c0 = 255, j = m; 0 < j; --c0) {
1953 for (c1 = 255; c0 < c1; j = i, --c1) {
1954 i = bucketB[BUCKET_BSTAR(c0, c1)];
1955 if (1 < j - i) {
1956 subStringSort(PAb, i, j, buf, bufoffset, bufsize, 2, SA[i] == m - 1, n);
1957 }
1958 }
1959 }
1960
1961 for (i = m - 1; 0 <= i; --i) {
1962 if (0 <= SA[i]) {
1963 j = i;
1964 do {
1965 SA[ISAb + SA[i]] = i;
1966 } while (0 <= --i && 0 <= SA[i]);
1967 SA[i + 1] = i - j;
1968 if (i <= 0) {
1969 break;
1970 }
1971 }
1972 j = i;
1973 do {
1974 SA[ISAb + (SA[i] = ~SA[i])] = j;
1975 } while (SA[--i] < 0);
1976 SA[ISAb + SA[i]] = j;
1977 }
1978
1979 trSort(ISAb, m, 1);
1980
1981 i = n - 1; j = m;
1982 if ((T[i] & 0xff) < (T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
1983 if (flag == 0) {
1984 SA[SA[ISAb + --j]] = i;
1985 }
1986 for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
1987 --i;
1988 }
1989 }
1990 while (0 <= i) {
1991 for (--i; 0 <= i && (T[i] & 0xff) >= (T[i + 1] & 0xff);) {
1992 --i;
1993 }
1994 if (0 <= i) {
1995 SA[SA[ISAb + --j]] = i;
1996 for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
1997 --i;
1998 }
1999 }
2000 }
2001
2002 for (c0 = 255, i = n - 1, k = m - 1; 0 <= c0; --c0) {
2003 for (c1 = 255; c0 < c1; --c1) {
2004 t = i - bucketB[BUCKET_B(c0, c1)];
2005 bucketB[BUCKET_B(c0, c1)] = i + 1;
2006
2007 for (i = t, j = bucketB[BUCKET_BSTAR(c0, c1)]; j <= k; --i, --k) {
2008 SA[i] = SA[k];
2009 }
2010 }
2011 t = i - bucketB[BUCKET_B(c0, c0)];
2012 bucketB[BUCKET_B(c0, c0)] = i + 1;
2013 if (c0 < 255) {
2014 bucketB[BUCKET_BSTAR(c0, c0 + 1)] = t + 1;
2015 }
2016 i = bucketA[c0];
2017 }
2018 return m;
2019 }
2020
2021 private int constructBWT(final int[] bucketA, final int[] bucketB) {
2022 final byte[] T = this.T;
2023 final int[] SA = this.SA;
2024 final int n = this.n;
2025
2026 int i, j, t = 0;
2027 int s, s1;
2028 int c0, c1, c2 = 0;
2029 int orig = -1;
2030
2031 for (c1 = 254; 0 <= c1; --c1) {
2032 for (i = bucketB[BUCKET_BSTAR(c1, c1 + 1)], j = bucketA[c1 + 1], t = 0, c2 = -1;
2033 i <= j;
2034 --j) {
2035 if (0 <= (s1 = s = SA[j])) {
2036 if (--s < 0) {
2037 s = n - 1;
2038 }
2039 if ((c0 = T[s] & 0xff) <= c1) {
2040 SA[j] = ~s1;
2041 if (0 < s && (T[s - 1] & 0xff) > c0) {
2042 s = ~s;
2043 }
2044 if (c2 == c0) {
2045 SA[--t] = s;
2046 } else {
2047 if (0 <= c2) {
2048 bucketB[BUCKET_B(c2, c1)] = t;
2049 }
2050 SA[t = bucketB[BUCKET_B(c2 = c0, c1)] - 1] = s;
2051 }
2052 }
2053 } else {
2054 SA[j] = ~s;
2055 }
2056 }
2057 }
2058
2059 for (i = 0; i < n; ++i) {
2060 if (0 <= (s1 = s = SA[i])) {
2061 if (--s < 0) {
2062 s = n - 1;
2063 }
2064 if ((c0 = T[s] & 0xff) >= (T[s + 1] & 0xff)) {
2065 if (0 < s && (T[s - 1] & 0xff) < c0) {
2066 s = ~s;
2067 }
2068 if (c0 == c2) {
2069 SA[++t] = s;
2070 } else {
2071 if (c2 != -1) {
2072 bucketA[c2] = t; // BUGFIX: Original code can write to bucketA[-1]
2073 }
2074 SA[t = bucketA[c2 = c0] + 1] = s;
2075 }
2076 }
2077 } else {
2078 s1 = ~s1;
2079 }
2080
2081 if (s1 == 0) {
2082 SA[i] = T[n - 1];
2083 orig = i;
2084 } else {
2085 SA[i] = T[s1 - 1];
2086 }
2087 }
2088 return orig;
2089 }
2090
2091 /**
2092 * Performs a Burrows Wheeler Transform on the input array.
2093 * @return the index of the first character of the input array within the output array
2094 */
2095 public int bwt() {
2096 final int[] SA = this.SA;
2097 final byte[] T = this.T;
2098 final int n = this.n;
2099
2100 final int[] bucketA = new int[BUCKET_A_SIZE];
2101 final int[] bucketB = new int[BUCKET_B_SIZE];
2102
2103 if (n == 0) {
2104 return 0;
2105 }
2106 if (n == 1) {
2107 SA[0] = T[0];
2108 return 0;
2109 }
2110
2111 int m = sortTypeBstar(bucketA, bucketB);
2112 if (0 < m) {
2113 return constructBWT(bucketA, bucketB);
2114 }
2115 return 0;
2116 }
2117 }
以上源码来自： 即时通讯网 - 即时通讯开发者社区！