partial-order/poset

/**
 * Output sensitive inplace algorithm to find the minima set of a set S of
 * elements according to some partial order.
 *
 * Uses at most 3nA comparisons where A is the cardinality of the minima set.
 *
 * For (1), at most nA comparisons are used since we compare each element of S
 * with each elements of the minima set which is of cardinality at most A
 * during the execution of the algorithm.
 *
 * For (2), for each executed loop we
 * obtain a new minimum and increase the size of the constructed minima set by
 * 1, hence there are at most A loops execution, each of which loops over at
 * most n elements. (2) uses thus at most nA comparisons.
 *
 * The running time is dominated by the comparison time and thus the complexity
 * of this algorihtm is O(nA).
 *
 * Description and context in
 * ------------------------------------------
 * More Output-Sensitive Geometric Algorithms.
 * -------------------- Kenneth L. Clarkson -
 *
 * @param {function} prec relation
 * @param {any[]} a input array
 * @param {number} i inclusive left bound of the input
 * @param {number} j non-inclusive right bound of the input
 *
 * @return {number} non-inclusive right bound of the minima set
 */
const clarkson = (prec, a, i, j) => {
    //
    // This algorithm reorganizes the input array `a` as follows
    //  - elements that are minima are put at the front of `a`
    //  - other elements are put at the back of `a`
    //
    // During the algorithm, `a` looks like this
    //
    //  ------------------------------------------------------
    // | minima set | candidate elements | discarded elements |
    //  ------------------------------------------------------
    //  i           min                dis                     j

    let min;
    let dis;
    let k;
    let inc;
    let temporary;

    min = i;
    dis = j - 1;

    // While there are candidate elements left.

    while (min <= dis) {
        // (1) Determine if the right-most candidate should be discarded because it
        // is dominated by one of the minima elements of the minima set in
        // construction.

        for (k = i; k < min && !prec(a[k], a[dis]); ++k);

        // If so, discard it.

        if (k < min) {
            --dis;
        }

        // (2) Otherwise, scan the candidates for a minimum. If at this point the
        // candidate set is not empty, at least one of its elements must be a
        // minimum. We scan the candidate list to find such a minimum.
        else {
            // Store the current minimum as the left-most candidate.

            temporary = a[dis];
            a[dis] = a[min];
            a[min] = temporary;

            // For each other candidate, right-to-left.

            for (inc = min + 1; inc <= dis; ) {
                // If the current minimum precedes the right-most candidate,
                // discard the right-most candidate.

                if (prec(a[min], a[dis])) {
                    --dis;
                }

                // Else, if the right-most candidate precedes the current
                // minimum, we can discard the current minimum and the
                // right-most candidate becomes the current minimum.
                else if (prec(a[dis], a[min])) {
                    temporary = a[dis];
                    a[dis] = a[min];
                    a[min] = temporary;
                    --dis;
                }

                // Otherwise, we save the candidate for the next round.
                else {
                    temporary = a[dis];
                    a[dis] = a[inc];
                    a[inc] = temporary;
                    ++inc;
                }
            }

            // The above loop selects a new minimum from the set of candidates
            // and places it at position `min`. We now increase the `min`
            // counter to move this minimum from the candidate list to the
            // minima set.

            ++min;
        }
    }

    // The algorithm returns the outer right bound of the minima set a[i:min].

    return min;
};

export default clarkson;