/*
 * Copyright 2014 The Netty Project
 *
 * The Netty Project licenses this file to you under the Apache License,
 * version 2.0 (the "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at:
 *
 *   https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 */
package io.netty.handler.codec.compression;

/**
 * DivSufSort suffix array generator.<br>
 *
 * Based on <a href="https://code.google.com/p/libdivsufsort/">libdivsufsort</a> 1.2.3 patched to support Bzip2.<br>
 * This is a simple conversion of the original C with two minor bugfixes applied (see "BUGFIX"
 * comments within the class). Documentation within the class is largely absent.
 */
final class Bzip2DivSufSort {

    private static final int STACK_SIZE = 64;
    private static final int BUCKET_A_SIZE = 256;
    private static final int BUCKET_B_SIZE = 65536;
    private static final int SS_BLOCKSIZE = 1024;
    private static final int INSERTIONSORT_THRESHOLD = 8;

    private static final int[] LOG_2_TABLE = {
        -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,
         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,
         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,
         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,
         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,
         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,
         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,
         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
    };

    private final int[] SA;
    private final byte[] T;
    private final int n;

    /**
     * @param block The input array
     * @param bwtBlock The output array
     * @param blockLength The length of the input data
     */
    Bzip2DivSufSort(final byte[] block, final int[] bwtBlock, final int blockLength) {
        T = block;
        SA = bwtBlock;
        n = blockLength;
    }

    private static void swapElements(final int[] array1, final int idx1, final int[] array2, final int idx2) {
        final int temp = array1[idx1];
        array1[idx1] = array2[idx2];
        array2[idx2] = temp;
    }

    private int ssCompare(final int p1, final int p2, final int depth) {
        final int[] SA = this.SA;
        final byte[] T = this.T;

        // pointers within T
        final int U1n = SA[p1 + 1] + 2;
        final int  U2n = SA[p2 + 1] + 2;

        int U1 = depth + SA[p1];
        int U2 = depth + SA[p2];

        while (U1 < U1n && U2 < U2n && T[U1] == T[U2]) {
            ++U1;
            ++U2;
        }

        return U1 < U1n ?
                   U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1
                 : U2 < U2n ? -1 : 0;
    }

    private int ssCompareLast(int pa, int p1, int p2, int depth, int size) {
        final int[] SA = this.SA;
        final byte[] T = this.T;

        int U1 = depth + SA[p1];
        int U2 = depth + SA[p2];
        int U1n = size;
        int U2n = SA[p2 + 1] + 2;

        while (U1 < U1n && U2 < U2n && T[U1] == T[U2]) {
            ++U1;
            ++U2;
        }

        if (U1 < U1n) {
            return U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1;
        }
        if (U2 == U2n) {
            return 1;
        }

        U1 %= size;
        U1n = SA[pa] + 2;
        while (U1 < U1n && U2 < U2n && T[U1] == T[U2]) {
            ++U1;
            ++U2;
        }

        return U1 < U1n ?
                   U2 < U2n ? (T[U1] & 0xff) - (T[U2] & 0xff) : 1
                 : U2 < U2n ? -1 : 0;
    }

    private void ssInsertionSort(int pa, int first, int last, int depth) {
        final int[] SA = this.SA;

        int i, j; // pointer within SA
        int t;
        int r;

        for (i = last - 2; first <= i; --i) {
            for (t = SA[i], j = i + 1; 0 < (r = ssCompare(pa + t, pa + SA[j], depth));) {
                do {
                    SA[j - 1] = SA[j];
                } while (++j < last && SA[j] < 0);
                if (last <= j) {
                    break;
                }
            }
            if (r == 0) {
                SA[j] = ~SA[j];
            }
            SA[j - 1] = t;
        }
    }

    private void ssFixdown(int td, int pa, int sa, int i, int size) {
        final int[] SA = this.SA;
        final byte[] T = this.T;

        int j, k;
        int v;
        int c, d, e;

        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) {
            d = T[td + SA[pa + SA[sa + (k = j++)]]] & 0xff;
            if (d < (e = T[td + SA[pa + SA[sa + j]]] & 0xff)) {
                k = j;
                d = e;
            }
            if (d <= c) {
                break;
            }
        }
        SA[sa + i] = v;
    }

    private void ssHeapSort(int td, int pa, int sa, int size) {
        final int[] SA = this.SA;
        final byte[] T = this.T;

        int i, m;
        int t;

        m = size;
        if (size % 2 == 0) {
            m--;
            if ((T[td + SA[pa + SA[sa + m / 2]]] & 0xff) < (T[td + SA[pa + SA[sa + m]]] & 0xff)) {
                swapElements(SA, sa + m, SA, sa + m / 2);
            }
        }

        for (i = m / 2 - 1; 0 <= i; --i) {
            ssFixdown(td, pa, sa, i, m);
        }

        if (size % 2 == 0) {
            swapElements(SA, sa, SA, sa + m);
            ssFixdown(td, pa, sa, 0, m);
        }

        for (i = m - 1; 0 < i; --i) {
            t = SA[sa];
            SA[sa] = SA[sa + i];
            ssFixdown(td, pa, sa, 0, i);
            SA[sa + i] = t;
        }
    }

    private int ssMedian3(final int td, final int pa, int v1, int v2, int v3) {
        final int[] SA = this.SA;
        final byte[] T = this.T;

        int T_v1 = T[td + SA[pa + SA[v1]]] & 0xff;
        int T_v2 = T[td + SA[pa + SA[v2]]] & 0xff;
        int T_v3 = T[td + SA[pa + SA[v3]]] & 0xff;

        if (T_v1 > T_v2) {
            final int temp = v1;
            v1 = v2;
            v2 = temp;
            final int T_vtemp = T_v1;
            T_v1 = T_v2;
            T_v2 = T_vtemp;
        }
        if (T_v2 > T_v3) {
            if (T_v1 > T_v3) {
                return v1;
            }
            return v3;
        }
        return v2;
    }

    private int ssMedian5(final int td, final int pa, int v1, int v2, int v3, int v4, int v5) {
        final int[] SA = this.SA;
        final byte[] T = this.T;

        int T_v1 = T[td + SA[pa + SA[v1]]] & 0xff;
        int T_v2 = T[td + SA[pa + SA[v2]]] & 0xff;
        int T_v3 = T[td + SA[pa + SA[v3]]] & 0xff;
        int T_v4 = T[td + SA[pa + SA[v4]]] & 0xff;
        int T_v5 = T[td + SA[pa + SA[v5]]] & 0xff;
        int temp;
        int T_vtemp;

        if (T_v2 > T_v3) {
            temp = v2;
            v2 = v3;
            v3 = temp;
            T_vtemp = T_v2;
            T_v2 = T_v3;
            T_v3 = T_vtemp;
        }
        if (T_v4 > T_v5) {
            temp = v4;
            v4 = v5;
            v5 = temp;
            T_vtemp = T_v4;
            T_v4 = T_v5;
            T_v5 = T_vtemp;
        }
        if (T_v2 > T_v4) {
            temp = v2;
            v4 = temp;
            T_vtemp = T_v2;
            T_v4 = T_vtemp;
            temp = v3;
            v3 = v5;
            v5 = temp;
            T_vtemp = T_v3;
            T_v3 = T_v5;
            T_v5 = T_vtemp;
        }
        if (T_v1 > T_v3) {
            temp = v1;
            v1 = v3;
            v3 = temp;
            T_vtemp = T_v1;
            T_v1 = T_v3;
            T_v3 = T_vtemp;
        }
        if (T_v1 > T_v4) {
            temp = v1;
            v4 = temp;
            T_vtemp = T_v1;
            T_v4 = T_vtemp;
            v3 = v5;
            T_v3 = T_v5;
        }
        if (T_v3 > T_v4) {
            return v4;
        }
        return v3;
    }

    private int ssPivot(final int td, final int pa, final int first, final int last) {
        int middle;
        int t;

        t = last - first;
        middle = first + t / 2;

        if (t <= 512) {
            if (t <= 32) {
                return ssMedian3(td, pa, first, middle, last - 1);
            }
            t >>= 2;
            return ssMedian5(td, pa, first, first + t, middle, last - 1 - t, last - 1);
        }
        t >>= 3;
        return ssMedian3(
                td, pa,
                ssMedian3(td, pa, first, first + t, first + (t << 1)),
                ssMedian3(td, pa, middle - t, middle, middle + t),
                ssMedian3(td, pa, last - 1 - (t << 1), last - 1 - t, last - 1)
        );
    }

    private static int ssLog(final int n) {
        return (n & 0xff00) != 0 ?
                  8 + LOG_2_TABLE[n >> 8 & 0xff]
                : LOG_2_TABLE[n & 0xff];
    }

    private int ssSubstringPartition(final int pa, final int first, final int last, final int depth) {
        final int[] SA = this.SA;

        int a, b;
        int t;

        for (a = first - 1, b = last;;) {
            while (++a < b && (SA[pa + SA[a]] + depth >= SA[pa + SA[a] + 1] + 1)) {
                SA[a] = ~SA[a];
            }
            --b;
            while (a < b && (SA[pa + SA[b]] + depth < SA[pa + SA[b] + 1] + 1)) {
                --b;
            }

            if (b <= a) {
                break;
            }
            t = ~SA[b];
            SA[b] = SA[a];
            SA[a] = t;
        }
        if (first < a) {
            SA[first] = ~SA[first];
        }
        return a;
    }

    private static class StackEntry {
        final int a;
        final int b;
        final int c;
        final int d;

        StackEntry(final int a, final int b, final int c, final int d) {
            this.a = a;
            this.b = b;
            this.c = c;
            this.d = d;
        }
    }

    private void ssMultiKeyIntroSort(final int pa, int first, int last, int depth) {
        final int[] SA = this.SA;
        final byte[] T = this.T;

        final StackEntry[] stack = new StackEntry[STACK_SIZE];

        int Td;
        int a, b, c, d, e, f;
        int s, t;
        int ssize;
        int limit;
        int v, x = 0;

        for (ssize = 0, limit = ssLog(last - first);;) {
            if (last - first <= INSERTIONSORT_THRESHOLD) {
                if (1 < last - first) {
                    ssInsertionSort(pa, first, last, depth);
                }
                if (ssize == 0) {
                    return;
                }
                StackEntry entry = stack[--ssize];
                first = entry.a;
                last = entry.b;
                depth = entry.c;
                limit = entry.d;
                continue;
            }

            Td = depth;
            if (limit-- == 0) {
                ssHeapSort(Td, pa, first, last - first);
            }
            if (limit < 0) {
                for (a = first + 1, v = T[Td + SA[pa + SA[first]]] & 0xff; a < last; ++a) {
                    if ((x = T[Td + SA[pa + SA[a]]] & 0xff) != v) {
                        if (1 < a - first) {
                            break;
                        }
                        v = x;
                        first = a;
                    }
                }
                if ((T[Td + SA[pa + SA[first]] - 1] & 0xff) < v) {
                    first = ssSubstringPartition(pa, first, a, depth);
                }
                if (a - first <= last - a) {
                    if (1 < a - first) {
                        stack[ssize++] = new StackEntry(a, last, depth, -1);
                        last = a;
                        depth += 1;
                        limit = ssLog(a - first);
                    } else {
                        first = a;
                        limit = -1;
                    }
                } else {
                    if (1 < last - a) {
                        stack[ssize++] = new StackEntry(first, a, depth + 1, ssLog(a - first));
                        first = a;
                        limit = -1;
                    } else {
                        last = a;
                        depth += 1;
                        limit = ssLog(a - first);
                    }
                }
                continue;
            }

            a = ssPivot(Td, pa, first, last);
            v = T[Td + SA[pa + SA[a]]] & 0xff;
            swapElements(SA, first, SA, a);

            b = first + 1;
            while (b < last && (x = T[Td + SA[pa + SA[b]]] & 0xff) == v) {
                ++b;
            }
            if ((a = b) < last && x < v) {
                while (++b < last && (x = T[Td + SA[pa + SA[b]]] & 0xff) <= v) {
                    if (x == v) {
                        swapElements(SA, b, SA, a);
                        ++a;
                    }
                }
            }

            c = last - 1;
            while (b < c && (x = T[Td + SA[pa + SA[c]]] & 0xff) == v) {
                --c;
            }
            if (b < (d = c) && x > v) {
                while (b < --c && (x = T[Td + SA[pa + SA[c]]] & 0xff) >= v) {
                    if (x == v) {
                        swapElements(SA, c, SA, d);
                        --d;
                    }
                }
            }
            while (b < c) {
                swapElements(SA, b, SA, c);
                while (++b < c && (x = T[Td + SA[pa + SA[b]]] & 0xff) <= v) {
                    if (x == v) {
                        swapElements(SA, b, SA, a);
                        ++a;
                    }
                }
                while (b < --c && (x = T[Td + SA[pa + SA[c]]] & 0xff) >= v) {
                    if (x == v) {
                        swapElements(SA, c, SA, d);
                        --d;
                    }
                }
            }

            if (a <= d) {
                c = b - 1;

                if ((s = a - first) > (t = b - a)) {
                    s = t;
                }
                for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
                    swapElements(SA, e, SA, f);
                }
                if ((s = d - c) > (t = last - d - 1)) {
                    s = t;
                }
                for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
                    swapElements(SA, e, SA, f);
                }

                a = first + (b - a);
                c = last - (d - c);
                b = v <= (T[Td + SA[pa + SA[a]] - 1] & 0xff) ? a : ssSubstringPartition(pa, a, c, depth);

                if (a - first <= last - c) {
                    if (last - c <= c - b) {
                        stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
                        stack[ssize++] = new StackEntry(c, last, depth, limit);
                        last = a;
                    } else if (a - first <= c - b) {
                        stack[ssize++] = new StackEntry(c, last, depth, limit);
                        stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
                        last = a;
                    } else {
                        stack[ssize++] = new StackEntry(c, last, depth, limit);
                        stack[ssize++] = new StackEntry(first, a, depth, limit);
                        first = b;
                        last = c;
                        depth += 1;
                        limit = ssLog(c - b);
                    }
                } else {
                    if (a - first <= c - b) {
                        stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
                        stack[ssize++] = new StackEntry(first, a, depth, limit);
                        first = c;
                    } else if (last - c <= c - b) {
                        stack[ssize++] = new StackEntry(first, a, depth, limit);
                        stack[ssize++] = new StackEntry(b, c, depth + 1, ssLog(c - b));
                        first = c;
                    } else {
                        stack[ssize++] = new StackEntry(first, a, depth, limit);
                        stack[ssize++] = new StackEntry(c, last, depth, limit);
                        first = b;
                        last = c;
                        depth += 1;
                        limit = ssLog(c - b);
                    }
                }
            } else {
                limit += 1;
                if ((T[Td + SA[pa + SA[first]] - 1] & 0xff) < v) {
                    first = ssSubstringPartition(pa, first, last, depth);
                    limit = ssLog(last - first);
                }
                depth += 1;
            }
        }
    }

    private static void ssBlockSwap(final int[] array1, final int first1,
                                    final int[] array2, final int first2, final int size) {
        int a, b;
        int i;
        for (i = size, a = first1, b = first2; 0 < i; --i, ++a, ++b) {
            swapElements(array1, a, array2, b);
        }
    }

    private void ssMergeForward(final int pa, int[] buf, final int bufoffset,
                                final int first, final int middle, final int last, final int depth) {
        final int[] SA = this.SA;

        int bufend;
        int i, j, k;
        int t;
        int r;

        bufend = bufoffset + (middle - first) - 1;
        ssBlockSwap(buf, bufoffset, SA, first, middle - first);

        for (t = SA[first], i = first, j = bufoffset, k = middle;;) {
            r = ssCompare(pa + buf[j], pa + SA[k], depth);
            if (r < 0) {
                do {
                    SA[i++] = buf[j];
                    if (bufend <= j) {
                        buf[j] = t;
                        return;
                    }
                    buf[j++] = SA[i];
                } while (buf[j] < 0);
            } else if (r > 0) {
                do {
                    SA[i++] = SA[k];
                    SA[k++] = SA[i];
                    if (last <= k) {
                        while (j < bufend) {
                            SA[i++] = buf[j]; buf[j++] = SA[i];
                        }
                        SA[i] = buf[j]; buf[j] = t;
                        return;
                    }
                } while (SA[k] < 0);
            } else {
                SA[k] = ~SA[k];
                do {
                    SA[i++] = buf[j];
                    if (bufend <= j) {
                        buf[j] = t;
                        return;
                    }
                    buf[j++] = SA[i];
                } while (buf[j] < 0);

                do {
                    SA[i++] = SA[k];
                    SA[k++] = SA[i];
                    if (last <= k) {
                        while (j < bufend) {
                            SA[i++] = buf[j];
                            buf[j++] = SA[i];
                        }
                        SA[i] = buf[j]; buf[j] = t;
                        return;
                    }
                } while (SA[k] < 0);
            }
        }
    }

    private void ssMergeBackward(final int pa, int[] buf, final int bufoffset,
                                 final int first, final int middle, final int last, final int depth) {
        final int[] SA = this.SA;

        int p1, p2;
        int bufend;
        int i, j, k;
        int t;
        int r;
        int x;

        bufend = bufoffset + (last - middle);
        ssBlockSwap(buf, bufoffset, SA, middle, last - middle);

        x = 0;
        if (buf[bufend - 1] < 0) {
            x |=  1;
            p1 = pa + ~buf[bufend - 1];
        } else {
            p1 = pa +  buf[bufend - 1];
        }
        if (SA[middle - 1] < 0) {
            x |=  2;
            p2 = pa + ~SA[middle - 1];
        } else {
            p2 = pa +  SA[middle - 1];
        }
        for (t = SA[last - 1], i = last - 1, j = bufend - 1, k = middle - 1;;) {

            r = ssCompare(p1, p2, depth);
            if (r > 0) {
                if ((x & 1) != 0) {
                    do {
                        SA[i--] = buf[j];
                        buf[j--] = SA[i];
                    } while (buf[j] < 0);
                    x ^= 1;
                }
                SA[i--] = buf[j];
                if (j <= bufoffset) {
                    buf[j] = t;
                    return;
                }
                buf[j--] = SA[i];

                if (buf[j] < 0) {
                    x |=  1;
                    p1 = pa + ~buf[j];
                } else {
                    p1 = pa +  buf[j];
                }
            } else if (r < 0) {
                if ((x & 2) != 0) {
                    do {
                        SA[i--] = SA[k];
                        SA[k--] = SA[i];
                    } while (SA[k] < 0);
                    x ^= 2;
                }
                SA[i--] = SA[k];
                SA[k--] = SA[i];
                if (k < first) {
                    while (bufoffset < j) {
                        SA[i--] = buf[j];
                        buf[j--] = SA[i];
                    }
                    SA[i] = buf[j];
                    buf[j] = t;
                    return;
                }

                if (SA[k] < 0) {
                    x |=  2;
                    p2 = pa + ~SA[k];
                } else {
                    p2 = pa +  SA[k];
                }
            } else {
                if ((x & 1) != 0) {
                    do {
                        SA[i--] = buf[j];
                        buf[j--] = SA[i];
                    } while (buf[j] < 0);
                    x ^= 1;
                }
                SA[i--] = ~buf[j];
                if (j <= bufoffset) {
                    buf[j] = t;
                    return;
                }
                buf[j--] = SA[i];

                if ((x & 2) != 0) {
                    do {
                        SA[i--] = SA[k];
                        SA[k--] = SA[i];
                    } while (SA[k] < 0);
                    x ^= 2;
                }
                SA[i--] = SA[k];
                SA[k--] = SA[i];
                if (k < first) {
                    while (bufoffset < j) {
                        SA[i--] = buf[j];
                        buf[j--] = SA[i];
                    }
                    SA[i] = buf[j];
                    buf[j] = t;
                    return;
                }

                if (buf[j] < 0) {
                    x |=  1;
                    p1 = pa + ~buf[j];
                } else {
                    p1 = pa +  buf[j];
                }
                if (SA[k] < 0) {
                    x |=  2;
                    p2 = pa + ~SA[k];
                } else {
                    p2 = pa +  SA[k];
                }
            }
        }
    }

    private static int getIDX(final int a) {
        return 0 <= a ? a : ~a;
    }

    private void ssMergeCheckEqual(final int pa, final int depth, final int a) {
        final int[] SA = this.SA;

        if (0 <= SA[a] && ssCompare(pa + getIDX(SA[a - 1]), pa + SA[a], depth) == 0) {
            SA[a] = ~SA[a];
        }
    }

    private void ssMerge(final int pa, int first, int middle, int last, int[] buf,
                         final int bufoffset, final int bufsize, final int depth) {
        final int[] SA = this.SA;

        final StackEntry[] stack = new StackEntry[STACK_SIZE];

        int i, j;
        int m, len, half;
        int ssize;
        int check, next;

        for (check = 0, ssize = 0;;) {

            if (last - middle <= bufsize) {
                if (first < middle && middle < last) {
                    ssMergeBackward(pa, buf, bufoffset, first, middle, last, depth);
                }

                if ((check & 1) != 0) {
                    ssMergeCheckEqual(pa, depth, first);
                }
                if ((check & 2) != 0) {
                    ssMergeCheckEqual(pa, depth, last);
                }
                if (ssize == 0) {
                    return;
                }
                StackEntry entry = stack[--ssize];
                first = entry.a;
                middle = entry.b;
                last = entry.c;
                check = entry.d;
                continue;
            }

            if (middle - first <= bufsize) {
                if (first < middle) {
                    ssMergeForward(pa, buf, bufoffset, first, middle, last, depth);
                }
                if ((check & 1) != 0) {
                    ssMergeCheckEqual(pa, depth, first);
                }
                if ((check & 2) != 0) {
                    ssMergeCheckEqual(pa, depth, last);
                }
                if (ssize == 0) {
                    return;
                }
                StackEntry entry = stack[--ssize];
                first = entry.a;
                middle = entry.b;
                last = entry.c;
                check = entry.d;
                continue;
            }

            for (m = 0, len = Math.min(middle - first, last - middle), half = len >> 1;
                    0 < len;
                    len = half, half >>= 1) {

                if (ssCompare(pa + getIDX(SA[middle + m + half]),
                        pa + getIDX(SA[middle - m - half - 1]), depth) < 0) {
                    m += half + 1;
                    half -= (len & 1) ^ 1;
                }
            }

            if (0 < m) {
                ssBlockSwap(SA, middle - m, SA, middle, m);
                i = j = middle;
                next = 0;
                if (middle + m < last) {
                    if (SA[middle + m] < 0) {
                        while (SA[i - 1] < 0) {
                            --i;
                        }
                        SA[middle + m] = ~SA[middle + m];
                    }
                    for (j = middle; SA[j] < 0;) {
                        ++j;
                    }
                    next = 1;
                }
                if (i - first <= last - j) {
                    stack[ssize++] = new StackEntry(j, middle + m, last, (check &  2) | (next & 1));
                    middle -= m;
                    last = i;
                    check &= 1;
                } else {
                    if (i == middle && middle == j) {
                        next <<= 1;
                    }
                    stack[ssize++] = new StackEntry(first, middle - m, i, (check & 1) | (next & 2));
                    first = j;
                    middle += m;
                    check = (check & 2) | (next & 1);
                }
            } else {
                if ((check & 1) != 0) {
                    ssMergeCheckEqual(pa, depth, first);
                }
                ssMergeCheckEqual(pa, depth, middle);
                if ((check & 2) != 0) {
                    ssMergeCheckEqual(pa, depth, last);
                }
                if (ssize == 0) {
                    return;
                }
                StackEntry entry = stack[--ssize];
                first = entry.a;
                middle = entry.b;
                last = entry.c;
                check = entry.d;
            }
        }
    }

    private void subStringSort(final int pa, int first, final int last,
                               final int[] buf, final int bufoffset, final int bufsize,
                               final int depth, final boolean lastsuffix, final int size) {
        final int[] SA = this.SA;

        int a, b;
        int[] curbuf;
        int curbufoffset;
        int i, j, k;
        int curbufsize;

        if (lastsuffix) {
            ++first;
        }
        for (a = first, i = 0; a + SS_BLOCKSIZE < last; a += SS_BLOCKSIZE, ++i) {
            ssMultiKeyIntroSort(pa, a, a + SS_BLOCKSIZE, depth);
            curbuf = SA;
            curbufoffset = a + SS_BLOCKSIZE;
            curbufsize = last - (a + SS_BLOCKSIZE);
            if (curbufsize <= bufsize) {
                curbufsize = bufsize;
                curbuf = buf;
                curbufoffset = bufoffset;
            }
            for (b = a, k = SS_BLOCKSIZE, j = i; (j & 1) != 0; b -= k, k <<= 1, j >>>= 1) {
                ssMerge(pa, b - k, b, b + k, curbuf, curbufoffset, curbufsize, depth);
            }
        }

        ssMultiKeyIntroSort(pa, a, last, depth);

        for (k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) {
            if ((i & 1) != 0) {
                ssMerge(pa, a - k, a, last, buf, bufoffset, bufsize, depth);
                a -= k;
            }
        }

        if (lastsuffix) {
            int r;
            for (a = first, i = SA[first - 1], r = 1;
                    a < last && (SA[a] < 0 || 0 < (r = ssCompareLast(pa, pa + i, pa + SA[a], depth, size)));
                    ++a) {
                SA[a - 1] = SA[a];
            }
            if (r == 0) {
                SA[a] = ~SA[a];
            }
            SA[a - 1] = i;
        }
    }

    /*----------------------------------------------------------------------------*/

    private int trGetC(final int isa, final int isaD, final int isaN, final int p) {
        return isaD + p < isaN ?
                SA[isaD + p]
              : SA[isa + ((isaD - isa + p) % (isaN - isa))];
    }

    private void trFixdown(final int isa, final int isaD, final int isaN, final int sa, int i, final int size) {
        final int[] SA = this.SA;

        int j, k;
        int v;
        int c, d, e;

        for (v = SA[sa + i], c = trGetC(isa, isaD, isaN, v); (j = 2 * i + 1) < size; SA[sa + i] = SA[sa + k], i = k) {
            k = j++;
            d = trGetC(isa, isaD, isaN, SA[sa + k]);
            if (d < (e = trGetC(isa, isaD, isaN, SA[sa + j]))) {
                k = j;
                d = e;
            }
            if (d <= c) {
                break;
            }
        }
        SA[sa + i] = v;
    }

    private void trHeapSort(final int isa, final int isaD, final int isaN, final int sa, final int size) {
        final int[] SA = this.SA;

        int i, m;
        int t;

        m = size;
        if (size % 2 == 0) {
            m--;
            if (trGetC(isa, isaD, isaN, SA[sa + m / 2]) < trGetC(isa, isaD, isaN, SA[sa + m])) {
                swapElements(SA, sa + m, SA, sa + m / 2);
            }
        }

        for (i = m / 2 - 1; 0 <= i; --i) {
            trFixdown(isa, isaD, isaN, sa, i, m);
        }

        if (size % 2 == 0) {
            swapElements(SA, sa, SA, sa + m);
            trFixdown(isa, isaD, isaN, sa, 0, m);
        }

        for (i = m - 1; 0 < i; --i) {
            t = SA[sa];
            SA[sa] = SA[sa + i];
            trFixdown(isa, isaD, isaN, sa, 0, i);
            SA[sa + i] = t;
        }
    }

    private void trInsertionSort(final int isa, final int isaD, final int isaN, int first, int last) {
        final int[] SA = this.SA;

        int a, b;
        int t, r;

        for (a = first + 1; a < last; ++a) {
            for (t = SA[a], b = a - 1; 0 > (r = trGetC(isa, isaD, isaN, t) - trGetC(isa, isaD, isaN, SA[b]));) {
                do {
                    SA[b + 1] = SA[b];
                } while (first <= --b && SA[b] < 0);
                if (b < first) {
                    break;
                }
            }
            if (r == 0) {
                SA[b] = ~SA[b];
            }
            SA[b + 1] = t;
        }
    }

    private static int trLog(int n) {
        return (n & 0xffff0000) != 0 ?
                  (n & 0xff000000) != 0 ? 24 + LOG_2_TABLE[n >> 24 & 0xff] : LOG_2_TABLE[n >> 16 & 0xff + 16]
                : (n & 0x0000ff00) != 0 ?  8 + LOG_2_TABLE[n >>  8 & 0xff] : LOG_2_TABLE[n & 0xff];
    }

    private int trMedian3(final int isa, final int isaD, final int isaN, int v1, int v2, int v3) {
        final int[] SA = this.SA;

        int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
        int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
        int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);

        if (SA_v1 > SA_v2) {
            final int temp = v1;
            v1 = v2;
            v2 = temp;
            final int SA_vtemp = SA_v1;
            SA_v1 = SA_v2;
            SA_v2 = SA_vtemp;
        }
        if (SA_v2 > SA_v3) {
            if (SA_v1 > SA_v3) {
                return v1;
            }
            return v3;
        }

        return v2;
    }

    private int trMedian5(final int isa, final int isaD, final int isaN, int v1, int v2, int v3, int v4, int v5) {
        final int[] SA = this.SA;

        int SA_v1 = trGetC(isa, isaD, isaN, SA[v1]);
        int SA_v2 = trGetC(isa, isaD, isaN, SA[v2]);
        int SA_v3 = trGetC(isa, isaD, isaN, SA[v3]);
        int SA_v4 = trGetC(isa, isaD, isaN, SA[v4]);
        int SA_v5 = trGetC(isa, isaD, isaN, SA[v5]);
        int temp;
        int SA_vtemp;

        if (SA_v2 > SA_v3) {
            temp = v2;
            v2 = v3;
            v3 = temp;
            SA_vtemp = SA_v2;
            SA_v2 = SA_v3;
            SA_v3 = SA_vtemp;
        }
        if (SA_v4 > SA_v5) {
            temp = v4;
            v4 = v5;
            v5 = temp;
            SA_vtemp = SA_v4;
            SA_v4 = SA_v5;
            SA_v5 = SA_vtemp;
        }
        if (SA_v2 > SA_v4) {
            temp = v2;
            v4 = temp;
            SA_vtemp = SA_v2;
            SA_v4 = SA_vtemp;
            temp = v3;
            v3 = v5;
            v5 = temp;
            SA_vtemp = SA_v3;
            SA_v3 = SA_v5;
            SA_v5 = SA_vtemp;
        }
        if (SA_v1 > SA_v3) {
            temp = v1;
            v1 = v3;
            v3 = temp;
            SA_vtemp = SA_v1;
            SA_v1 = SA_v3;
            SA_v3 = SA_vtemp;
        }
        if (SA_v1 > SA_v4) {
            temp = v1;
            v4 = temp;
            SA_vtemp = SA_v1;
            SA_v4 = SA_vtemp;
            v3 = v5;
            SA_v3 = SA_v5;
        }
        if (SA_v3 > SA_v4) {
            return v4;
        }
        return v3;
    }

    private int trPivot(final int isa, final int isaD, final int isaN, final int first, final int last) {
        final int middle;
        int t;

        t = last - first;
        middle = first + t / 2;

        if (t <= 512) {
            if (t <= 32) {
                return trMedian3(isa, isaD, isaN, first, middle, last - 1);
            }
            t >>= 2;
            return trMedian5(
                    isa, isaD, isaN,
                    first, first + t,
                    middle,
                    last - 1 - t, last - 1
            );
        }
        t >>= 3;
        return trMedian3(
                isa, isaD, isaN,
                trMedian3(isa, isaD, isaN, first, first + t, first + (t << 1)),
                trMedian3(isa, isaD, isaN, middle - t, middle, middle + t),
                trMedian3(isa, isaD, isaN, last - 1 - (t << 1), last - 1 - t, last - 1)
        );
    }

    /*---------------------------------------------------------------------------*/

    private void lsUpdateGroup(final int isa, final int first, final int last) {
        final int[] SA = this.SA;

        int a, b;
        int t;

        for (a = first; a < last; ++a) {
            if (0 <= SA[a]) {
                b = a;
                do {
                    SA[isa + SA[a]] = a;
                } while (++a < last && 0 <= SA[a]);
                SA[b] = b - a;
                if (last <= a) {
                    break;
                }
            }
            b = a;
            do {
                SA[a] = ~SA[a];
            } while (SA[++a] < 0);
            t = a;
            do {
                SA[isa + SA[b]] = t;
            } while (++b <= a);
        }
    }

    private void lsIntroSort(final int isa, final int isaD, final int isaN, int first, int last) {
        final int[] SA = this.SA;

        final StackEntry[] stack = new StackEntry[STACK_SIZE];

        int a, b, c, d, e, f;
        int s, t;
        int limit;
        int v, x = 0;
        int ssize;

        for (ssize = 0, limit = trLog(last - first);;) {
            if (last - first <= INSERTIONSORT_THRESHOLD) {
                if (1 < last - first) {
                    trInsertionSort(isa, isaD, isaN, first, last);
                    lsUpdateGroup(isa, first, last);
                } else if (last - first == 1) {
                    SA[first] = -1;
                }
                if (ssize == 0) {
                    return;
                }
                StackEntry entry = stack[--ssize];
                first = entry.a;
                last = entry.b;
                limit = entry.c;
                continue;
            }

            if (limit-- == 0) {
                trHeapSort(isa, isaD, isaN, first, last - first);
                for (a = last - 1; first < a; a = b) {
                    for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
                            first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
                            --b) {
                        SA[b] = ~SA[b];
                    }
                }
                lsUpdateGroup(isa, first, last);
                if (ssize == 0) {
                    return;
                }
                StackEntry entry = stack[--ssize];
                first = entry.a;
                last = entry.b;
                limit = entry.c;
                continue;
            }

            a = trPivot(isa, isaD, isaN, first, last);
            swapElements(SA, first, SA, a);
            v = trGetC(isa, isaD, isaN, SA[first]);

            b = first + 1;
            while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
                ++b;
            }
            if ((a = b) < last && x < v) {
                while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
                    if (x == v) {
                        swapElements(SA, b, SA, a);
                        ++a;
                    }
                }
            }

            c = last - 1;
            while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
                --c;
            }
            if (b < (d = c) && x > v) {
                while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
                    if (x == v) {
                        swapElements(SA, c, SA, d);
                        --d;
                    }
                }
            }
            while (b < c) {
                swapElements(SA, b, SA, c);
                while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
                    if (x == v) {
                        swapElements(SA, b, SA, a);
                        ++a;
                    }
                }
                while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
                    if (x == v) {
                        swapElements(SA, c, SA, d);
                        --d;
                    }
                }
            }

            if (a <= d) {
                c = b - 1;

                if ((s = a - first) > (t = b - a)) {
                    s = t;
                }
                for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
                    swapElements(SA, e, SA, f);
                }
                if ((s = d - c) > (t = last - d - 1)) {
                    s = t;
                }
                for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
                    swapElements(SA, e, SA, f);
                }

                a = first + (b - a);
                b = last - (d - c);

                for (c = first, v = a - 1; c < a; ++c) {
                    SA[isa + SA[c]] = v;
                }
                if (b < last) {
                    for (c = a, v = b - 1; c < b; ++c) {
                        SA[isa + SA[c]] = v;
                    }
                }
                if ((b - a) == 1) {
                    SA[a] = - 1;
                }

                if (a - first <= last - b) {
                    if (first < a) {
                        stack[ssize++] = new StackEntry(b, last, limit, 0);
                        last = a;
                    } else {
                        first = b;
                    }
                } else {
                    if (b < last) {
                        stack[ssize++] = new StackEntry(first, a, limit, 0);
                        first = b;
                    } else {
                        last = a;
                    }
                }
            } else {
                if (ssize == 0) {
                    return;
                }
                StackEntry entry = stack[--ssize];
                first = entry.a;
                last = entry.b;
                limit = entry.c;
            }
        }
    }

    private void lsSort(final int isa, final int n, final int depth) {
        final int[] SA = this.SA;

        int isaD;
        int first, last, i;
        int t, skip;

        for (isaD = isa + depth; -n < SA[0]; isaD += isaD - isa) {
            first = 0;
            skip = 0;
            do {
                if ((t = SA[first]) < 0) {
                    first -= t;
                    skip += t;
                } else {
                    if (skip != 0) {
                        SA[first + skip] = skip;
                        skip = 0;
                    }
                    last = SA[isa + t] + 1;
                    lsIntroSort(isa, isaD, isa + n, first, last);
                    first = last;
                }
            } while (first < n);
            if (skip != 0) {
                SA[first + skip] = skip;
            }
            if (n < isaD - isa) {
                first = 0;
                do {
                    if ((t = SA[first]) < 0) {
                        first -= t;
                    } else {
                        last = SA[isa + t] + 1;
                        for (i = first; i < last; ++i) {
                            SA[isa + SA[i]] = i;
                        }
                        first = last;
                    }
                } while (first < n);
                break;
            }
        }
    }

    /*---------------------------------------------------------------------------*/

    private static class PartitionResult {
        final int first;
        final int last;

        PartitionResult(final int first, final int last) {
            this.first = first;
            this.last = last;
        }
    }

    private PartitionResult trPartition(final int isa, final int isaD, final int isaN,
                                        int first, int last, final int v) {
        final int[] SA = this.SA;

        int a, b, c, d, e, f;
        int t, s;
        int x = 0;

        b = first;
        while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
            ++b;
        }
        if ((a = b) < last && x < v) {
            while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
                if (x == v) {
                    swapElements(SA, b, SA, a);
                    ++a;
                }
            }
        }

        c = last - 1;
        while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
            --c;
        }
        if (b < (d = c) && x > v) {
            while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
                if (x == v) {
                    swapElements(SA, c, SA, d);
                    --d;
                }
            }
        }
        while (b < c) {
            swapElements(SA, b, SA, c);
            while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
                if (x == v) {
                    swapElements(SA, b, SA, a);
                    ++a;
                }
            }
            while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
                if (x == v) {
                    swapElements(SA, c, SA, d);
                    --d;
                }
            }
        }

        if (a <= d) {
            c = b - 1;
            if ((s = a - first) > (t = b - a)) {
                s = t;
            }
            for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
                swapElements(SA, e, SA, f);
            }
            if ((s = d - c) > (t = last - d - 1)) {
                s = t;
            }
            for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
                swapElements(SA, e, SA, f);
            }
            first += b - a;
            last -= d - c;
        }
        return new PartitionResult(first, last);
    }

    private void trCopy(final int isa, final int isaN, final int first,
                        final int a, final int b, final int last, final int depth) {
        final int[] SA = this.SA;

        int c, d, e;
        int s, v;

        v = b - 1;

        for (c = first, d = a - 1; c <= d; ++c) {
            if ((s = SA[c] - depth) < 0) {
                s += isaN - isa;
            }
            if (SA[isa + s] == v) {
                SA[++d] = s;
                SA[isa + s] = d;
            }
        }
        for (c = last - 1, e = d + 1, d = b; e < d; --c) {
            if ((s = SA[c] - depth) < 0) {
                s += isaN - isa;
            }
            if (SA[isa + s] == v) {
                SA[--d] = s;
                SA[isa + s] = d;
            }
        }
    }

    private void trIntroSort(final int isa, int isaD, int isaN, int first,
                             int last, final TRBudget budget, final int size) {
        final int[] SA = this.SA;

        final StackEntry[] stack = new StackEntry[STACK_SIZE];

        int a, b, c, d, e, f;
        int s, t;
        int v, x = 0;
        int limit, next;
        int ssize;

        for (ssize = 0, limit = trLog(last - first);;) {
            if (limit < 0) {
                if (limit == -1) {
                    if (!budget.update(size, last - first)) {
                        break;
                    }
                    PartitionResult result = trPartition(isa, isaD - 1, isaN, first, last, last - 1);
                    a = result.first;
                    b = result.last;
                    if (first < a || b < last) {
                        if (a < last) {
                            for (c = first, v = a - 1; c < a; ++c) {
                                SA[isa + SA[c]] = v;
                            }
                        }
                        if (b < last) {
                            for (c = a, v = b - 1; c < b; ++c) {
                                SA[isa + SA[c]] = v;
                            }
                        }

                        stack[ssize++] = new StackEntry(0, a, b, 0);
                        stack[ssize++] = new StackEntry(isaD - 1, first, last, -2);
                        if (a - first <= last - b) {
                            if (1 < a - first) {
                                stack[ssize++] = new StackEntry(isaD, b, last, trLog(last - b));
                                last = a; limit = trLog(a - first);
                            } else if (1 < last - b) {
                                first = b; limit = trLog(last - b);
                            } else {
                                if (ssize == 0) {
                                    return;
                                }
                                StackEntry entry = stack[--ssize];
                                isaD = entry.a;
                                first = entry.b;
                                last = entry.c;
                                limit = entry.d;
                            }
                        } else {
                            if (1 < last - b) {
                                stack[ssize++] = new StackEntry(isaD, first, a, trLog(a - first));
                                first = b;
                                limit = trLog(last - b);
                            } else if (1 < a - first) {
                                last = a;
                                limit = trLog(a - first);
                            } else {
                                if (ssize == 0) {
                                    return;
                                }
                                StackEntry entry = stack[--ssize];
                                isaD = entry.a;
                                first = entry.b;
                                last = entry.c;
                                limit = entry.d;
                            }
                        }
                    } else {
                        for (c = first; c < last; ++c) {
                            SA[isa + SA[c]] = c;
                        }
                        if (ssize == 0) {
                            return;
                        }
                        StackEntry entry = stack[--ssize];
                        isaD = entry.a;
                        first = entry.b;
                        last = entry.c;
                        limit = entry.d;
                    }
                } else if (limit == -2) {
                    a = stack[--ssize].b;
                    b = stack[ssize].c;
                    trCopy(isa, isaN, first, a, b, last, isaD - isa);
                    if (ssize == 0) {
                        return;
                    }
                    StackEntry entry = stack[--ssize];
                    isaD = entry.a;
                    first = entry.b;
                    last = entry.c;
                    limit = entry.d;
                } else {
                    if (0 <= SA[first]) {
                        a = first;
                        do {
                            SA[isa + SA[a]] = a;
                        } while (++a < last && 0 <= SA[a]);
                        first = a;
                    }
                    if (first < last) {
                        a = first;
                        do {
                            SA[a] = ~SA[a];
                        } while (SA[++a] < 0);
                        next = SA[isa + SA[a]] != SA[isaD + SA[a]] ? trLog(a - first + 1) : -1;
                        if (++a < last) {
                            for (b = first, v = a - 1; b < a; ++b) {
                                SA[isa + SA[b]] = v;
                            }
                        }

                        if (a - first <= last - a) {
                            stack[ssize++] = new StackEntry(isaD, a, last, -3);
                            isaD += 1; last = a; limit = next;
                        } else {
                            if (1 < last - a) {
                                stack[ssize++] = new StackEntry(isaD + 1, first, a, next);
                                first = a; limit = -3;
                            } else {
                                isaD += 1; last = a; limit = next;
                            }
                        }
                    } else {
                        if (ssize == 0) {
                            return;
                        }
                        StackEntry entry = stack[--ssize];
                        isaD = entry.a;
                        first = entry.b;
                        last = entry.c;
                        limit = entry.d;
                    }
                }
                continue;
            }

            if (last - first <= INSERTIONSORT_THRESHOLD) {
                if (!budget.update(size, last - first)) {
                    break;
                }
                trInsertionSort(isa, isaD, isaN, first, last);
                limit = -3;
                continue;
            }

            if (limit-- == 0) {
                if (!budget.update(size, last - first)) {
                    break;
                }
                trHeapSort(isa, isaD, isaN, first, last - first);
                for (a = last - 1; first < a; a = b) {
                    for (x = trGetC(isa, isaD, isaN, SA[a]), b = a - 1;
                            first <= b && trGetC(isa, isaD, isaN, SA[b]) == x;
                            --b) {
                        SA[b] = ~SA[b];
                    }
                }
                limit = -3;
                continue;
            }

            a = trPivot(isa, isaD, isaN, first, last);

            swapElements(SA, first, SA, a);
            v = trGetC(isa, isaD, isaN, SA[first]);

            b = first + 1;
            while (b < last && (x = trGetC(isa, isaD, isaN, SA[b])) == v) {
                ++b;
            }
            if ((a = b) < last && x < v) {
                while (++b < last && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
                    if (x == v) {
                        swapElements(SA, b, SA, a);
                        ++a;
                    }
                }
            }

            c = last - 1;
            while (b < c && (x = trGetC(isa, isaD, isaN, SA[c])) == v) {
                --c;
            }
            if (b < (d = c) && x > v) {
                while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
                    if (x == v) {
                        swapElements(SA, c, SA, d);
                        --d;
                    }
                }
            }
            while (b < c) {
                swapElements(SA, b, SA, c);
                while (++b < c && (x = trGetC(isa, isaD, isaN, SA[b])) <= v) {
                    if (x == v) {
                        swapElements(SA, b, SA, a);
                        ++a;
                    }
                }
                while (b < --c && (x = trGetC(isa, isaD, isaN, SA[c])) >= v) {
                    if (x == v) {
                        swapElements(SA, c, SA, d);
                        --d;
                    }
                }
            }

            if (a <= d) {
                c = b - 1;

                if ((s = a - first) > (t = b - a)) {
                    s = t;
                }
                for (e = first, f = b - s; 0 < s; --s, ++e, ++f) {
                    swapElements(SA, e, SA, f);
                }
                if ((s = d - c) > (t = last - d - 1)) {
                    s = t;
                }
                for (e = b, f = last - s; 0 < s; --s, ++e, ++f) {
                    swapElements(SA, e, SA, f);
                }

                a = first + (b - a);
                b = last - (d - c);
                next = SA[isa + SA[a]] != v ? trLog(b - a) : -1;

                for (c = first, v = a - 1; c < a; ++c) {
                    SA[isa + SA[c]] = v;
                }
                if (b < last) {
                    for (c = a, v = b - 1; c < b; ++c) {
                        SA[isa + SA[c]] = v; }
                }

                if (a - first <= last - b) {
                    if (last - b <= b - a) {
                        if (1 < a - first) {
                            stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
                            stack[ssize++] = new StackEntry(isaD, b, last, limit);
                            last = a;
                        } else if (1 < last - b) {
                            stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
                            first = b;
                        } else if (1 < b - a) {
                            isaD += 1;
                            first = a;
                            last = b;
                            limit = next;
                        } else {
                            if (ssize == 0) {
                                return;
                            }
                            StackEntry entry = stack[--ssize];
                            isaD = entry.a;
                            first = entry.b;
                            last = entry.c;
                            limit = entry.d;
                        }
                    } else if (a - first <= b - a) {
                        if (1 < a - first) {
                            stack[ssize++] = new StackEntry(isaD, b, last, limit);
                            stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
                            last = a;
                        } else if (1 < b - a) {
                            stack[ssize++] = new StackEntry(isaD, b, last, limit);
                            isaD += 1;
                            first = a;
                            last = b;
                            limit = next;
                        } else {
                            first = b;
                        }
                    } else {
                        if (1 < b - a) {
                            stack[ssize++] = new StackEntry(isaD, b, last, limit);
                            stack[ssize++] = new StackEntry(isaD, first, a, limit);
                            isaD += 1;
                            first = a;
                            last = b;
                            limit = next;
                        } else {
                            stack[ssize++] = new StackEntry(isaD, b, last, limit);
                            last = a;
                        }
                    }
                } else {
                    if (a - first <= b - a) {
                        if (1 < last - b) {
                            stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
                            stack[ssize++] = new StackEntry(isaD, first, a, limit);
                            first = b;
                        } else if (1 < a - first) {
                            stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
                            last = a;
                        } else if (1 < b - a) {
                            isaD += 1;
                            first = a;
                            last = b;
                            limit = next;
                        } else {
                            stack[ssize++] = new StackEntry(isaD, first, last, limit);
                        }
                    } else if (last - b <= b - a) {
                        if (1 < last - b) {
                            stack[ssize++] = new StackEntry(isaD, first, a, limit);
                            stack[ssize++] = new StackEntry(isaD + 1, a, b, next);
                            first = b;
                        } else if (1 < b - a) {
                            stack[ssize++] = new StackEntry(isaD, first, a, limit);
                            isaD += 1;
                            first = a;
                            last = b;
                            limit = next;
                        } else {
                            last = a;
                        }
                    } else {
                        if (1 < b - a) {
                            stack[ssize++] = new StackEntry(isaD, first, a, limit);
                            stack[ssize++] = new StackEntry(isaD, b, last, limit);
                            isaD += 1;
                            first = a;
                            last = b;
                            limit = next;
                        } else {
                            stack[ssize++] = new StackEntry(isaD, first, a, limit);
                            first = b;
                        }
                    }
                }
            } else {
                if (!budget.update(size, last - first)) {
                    break; // BUGFIX : Added to prevent an infinite loop in the original code
                }
                limit += 1; isaD += 1;
            }
        }

        for (s = 0; s < ssize; ++s) {
            if (stack[s].d == -3) {
                lsUpdateGroup(isa, stack[s].b, stack[s].c);
            }
        }
    }

    private static class TRBudget {
        int budget;
        int chance;

        TRBudget(final int budget, final int chance) {
            this.budget = budget;
            this.chance = chance;
        }

        boolean update(final int size, final int n) {
            budget -= n;
            if (budget <= 0) {
                if (--chance == 0) {
                    return false;
                }
                budget += size;
            }
            return true;
        }
    }

    private void trSort(final int isa, final int n, final int depth) {
        final int[] SA = this.SA;

        int first = 0, last;
        int t;

        if (-n < SA[0]) {
            TRBudget budget = new TRBudget(n, trLog(n) * 2 / 3 + 1);
            do {
                if ((t = SA[first]) < 0) {
                    first -= t;
                } else {
                    last = SA[isa + t] + 1;
                    if (1 < last - first) {
                        trIntroSort(isa, isa + depth, isa + n, first, last, budget, n);
                        if (budget.chance == 0) {
                            /* Switch to Larsson-Sadakane sorting algorithm */
                            if (0 < first) {
                                SA[0] = -first;
                            }
                            lsSort(isa, n, depth);
                            break;
                        }
                    }
                    first = last;
                }
            } while (first < n);
        }
    }

    /*---------------------------------------------------------------------------*/

    private static int BUCKET_B(final int c0, final int c1) {
        return (c1 << 8) | c0;
    }

    private static int BUCKET_BSTAR(final int c0, final int c1) {
        return (c0 << 8) | c1;
    }

    private int sortTypeBstar(final int[] bucketA, final int[] bucketB) {
        final byte[] T = this.T;
        final int[] SA = this.SA;
        final int n = this.n;
        final int[] tempbuf = new int[256];

        int[] buf;
        int PAb, ISAb, bufoffset;
        int i, j, k, t, m, bufsize;
        int c0, c1;
        int flag;

        for (i = 1, flag = 1; i < n; ++i) {
            if (T[i - 1] != T[i]) {
                if ((T[i - 1] & 0xff) > (T[i] & 0xff)) {
                    flag = 0;
                }
                break;
            }
        }
        i = n - 1;
        m = n;

        int ti, ti1, t0;
        if ((ti = T[i] & 0xff) < (t0 = T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
            if (flag == 0) {
                ++bucketB[BUCKET_BSTAR(ti, t0)];
                SA[--m] = i;
            } else {
                ++bucketB[BUCKET_B(ti, t0)];
            }
            for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
                ++bucketB[BUCKET_B(ti, ti1)];
            }
        }

        while (0 <= i) {
            do {
                ++bucketA[T[i] & 0xff];
            } while (0 <= --i && (T[i] & 0xff) >= (T[i + 1] & 0xff));
            if (0 <= i) {
                ++bucketB[BUCKET_BSTAR(T[i] & 0xff, T[i + 1] & 0xff)];
                SA[--m] = i;
                for (--i; 0 <= i && (ti = T[i] & 0xff) <= (ti1 = T[i + 1] & 0xff); --i) {
                    ++bucketB[BUCKET_B(ti, ti1)];
                }
            }
        }
        m = n - m;
        if (m == 0) {
            for (i = 0; i < n; ++i) {
                SA[i] = i;
            }
            return 0;
        }

        for (c0 = 0, i = -1, j = 0; c0 < 256; ++c0) {
            t = i + bucketA[c0];
            bucketA[c0] = i + j;
            i = t + bucketB[BUCKET_B(c0, c0)];
            for (c1 = c0 + 1; c1 < 256; ++c1) {
                j += bucketB[BUCKET_BSTAR(c0, c1)];
                bucketB[(c0 << 8) | c1] = j;
                i += bucketB[BUCKET_B(c0, c1)];
            }
        }

        PAb = n - m;
        ISAb = m;
        for (i = m - 2; 0 <= i; --i) {
            t = SA[PAb + i];
            c0 = T[t] & 0xff;
            c1 = T[t + 1] & 0xff;
            SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = i;
        }
        t = SA[PAb + m - 1];
        c0 = T[t] & 0xff;
        c1 = T[t + 1] & 0xff;
        SA[--bucketB[BUCKET_BSTAR(c0, c1)]] = m - 1;

        buf = SA;
        bufoffset = m;
        bufsize = n - 2 * m;
        if (bufsize <= 256) {
            buf = tempbuf;
            bufoffset = 0;
            bufsize = 256;
        }

        for (c0 = 255, j = m; 0 < j; --c0) {
            for (c1 = 255; c0 < c1; j = i, --c1) {
                i = bucketB[BUCKET_BSTAR(c0, c1)];
                if (1 < j - i) {
                    subStringSort(PAb, i, j, buf, bufoffset, bufsize, 2, SA[i] == m - 1, n);
                }
            }
        }

        for (i = m - 1; 0 <= i; --i) {
            if (0 <= SA[i]) {
                j = i;
                do {
                    SA[ISAb + SA[i]] = i;
                } while (0 <= --i && 0 <= SA[i]);
                SA[i + 1] = i - j;
                if (i <= 0) {
                    break;
                }
            }
            j = i;
            do {
                SA[ISAb + (SA[i] = ~SA[i])] = j;
            } while (SA[--i] < 0);
            SA[ISAb + SA[i]] = j;
        }

        trSort(ISAb, m, 1);

        i = n - 1; j = m;
        if ((T[i] & 0xff) < (T[0] & 0xff) || (T[i] == T[0] && flag != 0)) {
            if (flag == 0) {
                SA[SA[ISAb + --j]] = i;
            }
            for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
                --i;
            }
        }
        while (0 <= i) {
            for (--i; 0 <= i && (T[i] & 0xff) >= (T[i + 1] & 0xff);) {
                --i;
            }
            if (0 <= i) {
                SA[SA[ISAb + --j]] = i;
                for (--i; 0 <= i && (T[i] & 0xff) <= (T[i + 1] & 0xff);) {
                    --i;
                }
            }
        }

        for (c0 = 255, i = n - 1, k = m - 1; 0 <= c0; --c0) {
            for (c1 = 255; c0 < c1; --c1) {
                t = i - bucketB[BUCKET_B(c0, c1)];
                bucketB[BUCKET_B(c0, c1)] = i + 1;

                for (i = t, j = bucketB[BUCKET_BSTAR(c0, c1)]; j <= k; --i, --k) {
                    SA[i] = SA[k];
                }
            }
            t = i - bucketB[BUCKET_B(c0, c0)];
            bucketB[BUCKET_B(c0, c0)] = i + 1;
            if (c0 < 255) {
                bucketB[BUCKET_BSTAR(c0, c0 + 1)] = t + 1;
            }
            i = bucketA[c0];
        }
        return m;
    }

    private int constructBWT(final int[] bucketA, final int[] bucketB) {
        final byte[] T = this.T;
        final int[] SA = this.SA;
        final int n = this.n;

        int i, j, t = 0;
        int s, s1;
        int c0, c1, c2 = 0;
        int orig = -1;

        for (c1 = 254; 0 <= c1; --c1) {
            for (i = bucketB[BUCKET_BSTAR(c1, c1 + 1)], j = bucketA[c1 + 1], t = 0, c2 = -1;
                    i <= j;
                    --j) {
                if (0 <= (s1 = s = SA[j])) {
                    if (--s < 0) {
                        s = n - 1;
                    }
                    if ((c0 = T[s] & 0xff) <= c1) {
                        SA[j] = ~s1;
                        if (0 < s && (T[s - 1] & 0xff) > c0) {
                            s = ~s;
                        }
                        if (c2 == c0) {
                            SA[--t] = s;
                        } else {
                            if (0 <= c2) {
                                bucketB[BUCKET_B(c2, c1)] = t;
                            }
                            SA[t = bucketB[BUCKET_B(c2 = c0, c1)] - 1] = s;
                        }
                    }
                } else {
                    SA[j] = ~s;
                }
            }
        }

        for (i = 0; i < n; ++i) {
            if (0 <= (s1 = s = SA[i])) {
                if (--s < 0) {
                    s = n - 1;
                }
                if ((c0 = T[s] & 0xff) >= (T[s + 1] & 0xff)) {
                    if (0 < s && (T[s - 1] & 0xff) < c0) {
                        s = ~s;
                    }
                    if (c0 == c2) {
                        SA[++t] = s;
                    } else {
                        if (c2 != -1) {
                            bucketA[c2] = t;    // BUGFIX: Original code can write to bucketA[-1]
                        }
                        SA[t = bucketA[c2 = c0] + 1] = s;
                    }
                }
            } else {
                s1 = ~s1;
            }

            if (s1 == 0) {
                SA[i] = T[n - 1];
                orig = i;
            } else {
                SA[i] = T[s1 - 1];
            }
        }
        return orig;
    }

    /**
     * Performs a Burrows Wheeler Transform on the input array.
     * @return the index of the first character of the input array within the output array
     */
    public int bwt() {
        final int[] SA = this.SA;
        final byte[] T = this.T;
        final int n = this.n;

        final int[] bucketA = new int[BUCKET_A_SIZE];
        final int[] bucketB = new int[BUCKET_B_SIZE];

        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            SA[0] = T[0];
            return 0;
        }

        int m = sortTypeBstar(bucketA, bucketB);
        if (0 < m) {
            return constructBWT(bucketA, bucketB);
        }
        return 0;
    }
}
