// Path: src/main/java/org/jsuffixarrays/Tools.java
// static final void assertAlways(boolean condition, String msg)
// {
//     if (!condition)
//     {
//         throw new AssertionError(msg);
//     }
// }


import static org.jsuffixarrays.Tools.assertAlways;
package org.jsuffixarrays;


/**
 * <p>
 * Straightforward reimplementation of the qsufsort algorithm given in:
 * 
 * <pre>
 * &lt;code&gt;
 * Larsson, N. Jesper and Sadakane, Kunihiko. Faster Suffix Sorting. 
 * Report number LU-CS-TR:99-214, LUNDFD6/(NFCS-3140)/1--20/(1999). Department of Computer Science, Lund University&quot;
 * &lt;/code&gt;
 * </pre>
 * <p>
 * This implementation is basically a translation of the C version given by Peter Sanders:
 * <tt>http://www.mpi-inf.mpg.de/~sanders/programs/suffix/</tt>
 * <p>
 * The implementation of this algorithm makes some assumptions about the input. See
 * {@link #buildSuffixArray(int[], int, int)} for details.
 * <p>
 * Algorithm modifies input during processing, see {@link #QSufSort(boolean)}.
 */
public class QSufSort implements ISuffixArrayBuilder
{
    /** group array, ultimately suffix array. */
    private int I[];

    /** inverse array, ultimately inverse of I. */
    private int V[];

    /** number of symbols aggregated by transform. */
    private int r;

    /** length of already-sorted prefixes. */
    private int h;

    /**
     * If <code>true</code>, {@link #buildSuffixArray(int[], int, int)} uses copy of input
     * so it is left intact.
     */
    private final boolean preserveInput;

    private int start;

    /**
     * Default constructor, uses the input array of symbols to preserve memory (and
     * destroys it).
     */
    public QSufSort()
    {
        this.preserveInput = true;
    }

    /**
     * If <code>true</code>, the algorithm will use a copy of the input so it is left
     * intact.
     */
    public QSufSort(boolean preserveInput)
    {
        this.preserveInput = preserveInput;
    }

    /**
     * {@inheritDoc}
     * <p>
     * Additional constraints enforced by qsufsort algorithm:
     * <ul>
     * <li>non-negative (&ge;0) symbols in the input</li>
     * <li>length >= 2</li>
     * </ul>
     * <p>
     */
    @Override
    public final int [] buildSuffixArray(int [] input, int start, int length)
    {
// Path: src/main/java/org/jsuffixarrays/Tools.java
// static final void assertAlways(boolean condition, String msg)
// {
//     if (!condition)
//     {
//         throw new AssertionError(msg);
//     }
// }


// Path: src/main/java/org/jsuffixarrays/QSufSort.java
import static org.jsuffixarrays.Tools.assertAlways;

package org.jsuffixarrays;


/**
 * <p>
 * Straightforward reimplementation of the qsufsort algorithm given in:
 * 
 * <pre>
 * &lt;code&gt;
 * Larsson, N. Jesper and Sadakane, Kunihiko. Faster Suffix Sorting. 
 * Report number LU-CS-TR:99-214, LUNDFD6/(NFCS-3140)/1--20/(1999). Department of Computer Science, Lund University&quot;
 * &lt;/code&gt;
 * </pre>
 * <p>
 * This implementation is basically a translation of the C version given by Peter Sanders:
 * <tt>http://www.mpi-inf.mpg.de/~sanders/programs/suffix/</tt>
 * <p>
 * The implementation of this algorithm makes some assumptions about the input. See
 * {@link #buildSuffixArray(int[], int, int)} for details.
 * <p>
 * Algorithm modifies input during processing, see {@link #QSufSort(boolean)}.
 */
public class QSufSort implements ISuffixArrayBuilder
{
    /** group array, ultimately suffix array. */
    private int I[];

    /** inverse array, ultimately inverse of I. */
    private int V[];

    /** number of symbols aggregated by transform. */
    private int r;

    /** length of already-sorted prefixes. */
    private int h;

    /**
     * If <code>true</code>, {@link #buildSuffixArray(int[], int, int)} uses copy of input
     * so it is left intact.
     */
    private final boolean preserveInput;

    private int start;

    /**
     * Default constructor, uses the input array of symbols to preserve memory (and
     * destroys it).
     */
    public QSufSort()
    {
        this.preserveInput = true;
    }

    /**
     * If <code>true</code>, the algorithm will use a copy of the input so it is left
     * intact.
     */
    public QSufSort(boolean preserveInput)
    {
        this.preserveInput = preserveInput;
    }

    /**
     * {@inheritDoc}
     * <p>
     * Additional constraints enforced by qsufsort algorithm:
     * <ul>
     * <li>non-negative (&ge;0) symbols in the input</li>
     * <li>length >= 2</li>
     * </ul>
     * <p>
     */
    @Override
    public final int [] buildSuffixArray(int [] input, int start, int length)
    {
        assertAlways(input.length >= start + length + 1, "no extra space after input end");