/*
 * qsort.oad - quicksort implementation. Two versions - one with a comparison
 * function, the other relying on built-in comparison operators
 *
 * Copyright (c) 2023 Ross Cunniff
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

proc qsort;

proc main()
{
    var i, sorted;
    const cmp = proc(a,b) { return (a==b) ? 0 : (a < b) ? -1 : 1; };

    sorted = qsort(cmp, {"3", "4", "2", "3", "1"});

    "sorted = {";
    for (i = 0; i < sorted.length(); i++) {
        if (i > 0) ",";
        " \"", sorted[i], "\"";
    }
    " }\n";

    sorted = qsort({3, 4, 2, 3, 1});

    "sorted = {";
    for (i = 0; i < sorted.length(); i++) {
        if (i > 0) ",";
        " ", sorted[i];
    }
    " }\n";

}

proc qsort()
{
    const quicksort_cmp = proc(cmp, a, lo, hi)
    {
        const partition = proc(cmp, a, lo, hi) {
            // Select the median of 3 values using the provided cmp proc
            const med3 = proc(cmp,a,b,c) {
                if (cmp(a,b) < 0) {                   // ? a ? b ?
                    if (cmp(b,c) < 0)       return b; // a b c
                    else if (cmp(a,c) < 0)  return c; // a c b
                    else                    return a; // c a b
                }
                else {                                // ? b ? a ?
                    if (cmp(b,c) > 0)       return b; // c b a
                    else if (cmp(a,c) > 0)  return c; // b c a
                    else                    return a; // b a c
                }
            };
            var i, j;

            // The pivot is the median of the left, middle, and right values
            var pivot = med3(cmp, a[lo], a[(lo+hi)/2], a[hi]);

            // Walk the array from the outside in, swapping
            // items less than the pivot with those greater than
            // the pivot. Original Hoare algorithm.
            i = lo - 1;
            j = hi + 1;
            while (1) {
                do i++; while (cmp(a[i], pivot) < 0);
                do j--; while (cmp(a[j], pivot) > 0);
                if (i >= j) return j;
                var tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            }
        };

        // Idiom for recursive nested procedures. A nested procedure
        // does not have access to its name in the enclosing procedure's
        // symbol table, so assign the (proc) value to an appropriately
        // named variable
        var quicksort_cmp = (proc);
        if (lo < hi) {
            var p = partition(cmp, a, lo, hi);
            quicksort_cmp(cmp, a, lo, p);
            quicksort_cmp(cmp, a, p+1, hi);
        }
    };

    const quicksort = proc(a, lo, hi)
    {
        const partition = proc(a, lo, hi) {
            // Select the median of 3 values using comparison operators
            const med3 = proc(a,b,c) {
                if (a < b) {                          // ? a ? b ?
                    if (b < c)              return b; // a b c
                    else if (a < c)         return c; // a c b
                    else                    return a; // c a b
                }
                else {                                // ? b ? a ?
                    if (b > c)              return b; // c b a
                    else if (a > c)         return c; // b c a
                    else                    return a; // b a c
                }
            };
            var i, j;

            // The pivot is the median of the left, middle, and right values
            var pivot = med3(a[lo], a[(lo+hi)/2], a[hi]);

            // Walk the array from the outside in, swapping
            // items less than the pivot with those greater than
            // the pivot. Original Hoare algorithm.
            i = lo - 1;
            j = hi + 1;
            while (1) {
                do i++; while (a[i] < pivot);
                do j--; while (a[j] > pivot);
                if (i >= j) return j;
                var tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            }
        };

        // Idiom for recursive nested procedures. A nested procedure
        // does not have access to its name in the enclosing procedure's
        // symbol table, so assign the (proc) value to an appropriately
        // named variable
        var quicksort = (proc);
        if (lo < hi) {
            var p = partition(a, lo, hi);
            quicksort(a, lo, p);
            quicksort(a, p+1, hi);
        }
    };

    // Create a copy of an array without creating copies of its
    // contents (copy the contents by reference)
    const arrcopy = proc(arr)
    {
        var n = arr.length();
        var res = new Array(n);
        for (var i = 0; i < n; i++) {
            res[i] = arr[i];
        }
        return res.pack();
    };

    var cmp, arr;
    using namespace oadl;

    switch (nargs()) {
    case 1 :
        arr = arrcopy(arg(0));
        quicksort(arr, 0, arr.length()-1);
    case 2 :
        cmp = arg(0);
        arr = arrcopy(arg(1));
        quicksort_cmp(cmp, arr, 0, arr.length()-1);
    default :
        throw ArgCheck;
    }
    return arr;
}