// --------------------
// NextPermutation.java
// --------------------

import java.util.Arrays;

final class NextPermutation {
    /**
     * O(1) in space
     * O(n) in time
     * Precondition: must be sorted
     */
    public static boolean eval (long[] a, int b, int e) {
        assert b <= e;
        if ((e - b) < 2)
            return false;
        final int p = e;
        --e;
        while (b != e) {
            final int q = e;
            --e;
            if (a[e] < a[q]) {
                int r = p;
                while (!(a[e] < a[--r])) {}
                Swap.eval(a, e, r);
                Reverse.eval(a, q, p);
                return true;}}
        Reverse.eval(a, b, p);
        return false;}}

final class NextPermutationTest { // 2 3 5 4 1
    public static void main (String[] args) {
        System.out.println("NextPermutation.java");

        {
        final long[] a = {1, 2, 3, 4, 5};
        for (int i = 0; i < 59; ++i)
            assert NextPermutation.eval(a, 0, a.length);
        assert Arrays.equals(a, new long[] {3, 2, 5, 4, 1});
        assert NextPermutation.eval(a, 0, a.length);
        assert Arrays.equals(a, new long[] {3, 4, 1, 2, 5});
        for (int i = 0; i < 59; ++i)
            assert NextPermutation.eval(a, 0, a.length);
        assert Arrays.equals(a, new long[] {5, 4, 3, 2, 1});
        assert !NextPermutation.eval(a, 0, a.length);
        assert Arrays.equals(a, new long[] {1, 2, 3, 4, 5});
        }

        {
        final long[] a = {1, 2, 3, 3, 5};
        for (int i = 0; i < 29; ++i)
            assert NextPermutation.eval(a, 0, a.length);
        assert Arrays.equals(a, new long[] {3, 1, 5, 3, 2});
        assert NextPermutation.eval(a, 0, a.length);
        assert Arrays.equals(a, new long[] {3, 2, 1, 3, 5});
        for (int i = 0; i < 29; ++i)
            assert NextPermutation.eval(a, 0, a.length);
        assert Arrays.equals(a, new long[] {5, 3, 3, 2, 1});
        assert !NextPermutation.eval(a, 0, a.length);
        assert Arrays.equals(a, new long[] {1, 2, 3, 3, 5});
        }

        System.out.println("Done.");}}