#include <iostream>
#include <functional>
#include <cassert>
#include <cstddef>

/************************************************************
 * PARTITIONING AN ARRAY
 *
 * Previously, we used predicates to count entries
 * satisfying a particular condition.
 *
 * We can also use a predicate to rearrange an array
 * so that all entries satisfying the condition
 * appear before those that do not.
 *
 * This operation is called partitioning.
 *
 * For example, suppose we have the array
 *
 *     {3, -2, 5, -7, -1, 4}
 *
 * and the predicate is_negative(), which returns
 * true if its argument is less than zero.
 *
 * After partitioning, one possible result is
 *
 *     {-1, -2, -7, 5, 3, 4}.
 *
 * The negative entries appear first, followed
 * by the nonnegative entries.
 *
 * The relative order of entries within either
 * group is not necessarily preserved.
 *
 * The function returns the partition index:
 * the index of the first entry in the second
 * group.
 *
 * For the example above, the partition index
 * is 3.
 *
 * The function operates on the half-open
 * interval [begin, end).
 *
 * Entries outside this interval are unchanged.
 *
 * If every entry satisfies the predicate,
 * the function returns end.
 *
 * If no entries satisfy the predicate,
 * the function returns begin.
 *
 * If the interval is empty, it returns begin.
 *
 * The algorithm runs in linear time and
 * requires only constant additional memory.
 ************************************************************/

// Function declarations
int main();

std::size_t partition(
    double                       array[],
    std::size_t            const begin,
    std::size_t            const end,
    std::function<bool(double)> const predicate
);

void swap_array_entries(
    double             array[],
    std::size_t  const m,
    std::size_t  const n
);

bool is_negative(
    double const x
);

void print(
    double       const array[],
    std::size_t  const begin,
    std::size_t  const end
);

// Function definitions
int main() {
    std::size_t const data_capacity{ 20 };

    double data[data_capacity]{
         6.73, -0.52, -5.52, -8.43,  4.41,
         1.19,  5.19, -1.40,  2.55, -9.02,
         7.35,  7.34,  9.34, -0.06,  1.12,
        -2.73,  9.77,  4.71,  2.20,  9.28
    };

    std::cout << "Original array:" << std::endl;
    print( data, 0, data_capacity );

    std::size_t const partition_index{
        partition(
            data,
            0,
            data_capacity,
            is_negative
        )
    };

    std::cout << "Partitioned array:" << std::endl;
    print( data, 0, data_capacity );

    std::cout << "Number of negative entries: "
              << partition_index
              << std::endl;

    std::cout << "Negative entries: ";
    print( data, 0, partition_index );

    std::cout << "Nonnegative entries: ";
    print( data, partition_index, data_capacity );

    // Verify that the partition is correct.
    assert( partition_index == 7 );

    for (
        std::size_t k{ 0 };
        k < partition_index;
        ++k
    ) {
        assert( is_negative( data[k] ) );
    }

    for (
        std::size_t k{ partition_index };
        k < data_capacity;
        ++k
    ) {
        assert( !is_negative( data[k] ) );
    }

    // Test an array in which every entry
    // satisfies the predicate.
    double all_negative[]{ -1.0, -2.0, -3.0 };

    assert(
        partition( all_negative, 0, 3, is_negative )
        == 3
    );

    // Test an array in which no entry
    // satisfies the predicate.
    double all_positive[]{ 1.0, 2.0, 3.0 };

    assert(
        partition( all_positive, 0, 3, is_negative )
        == 0
    );

    // Test an empty interval.
    assert(
        partition( data, 5, 5, is_negative )
        == 5
    );

    // Test an empty array.
    assert(
        partition( nullptr, 0, 0, is_negative )
        == 0
    );

    // Test partitioning only part of an array.
    double test[]{ 100.0, 2.0, -3.0, 4.0, -5.0, 200.0 };

    std::size_t const middle{
        partition( test, 1, 5, is_negative )
    };

    assert( middle == 3 );

    // Entries outside [1, 5) are unchanged.
    assert( test[0] == 100.0 );
    assert( test[5] == 200.0 );

    for ( std::size_t k{ 1 }; k < middle; ++k ) {
        assert( is_negative( test[k] ) );
    }

    for ( std::size_t k{ middle }; k < 5; ++k ) {
        assert( !is_negative( test[k] ) );
    }

    return 0;
}

/************************************************************
 * Partition the entries in [begin, end).
 *
 * Rearrange the entries so that those satisfying
 * the predicate appear first, followed by those
 * that do not.
 *
 * Return the index separating the two groups.
 *
 * We maintain two indices:
 *
 *     left  starts at begin.
 *     right starts at end.
 *
 * The right index is initially one past the
 * last entry in the interval.
 *
 * Move left forward past entries that already
 * satisfy the predicate.
 *
 * Move right backward past entries that do not
 * satisfy the predicate.
 *
 * If the indices have not met, the entries
 * at left and right are in the wrong groups.
 * Swap them and continue.
 *
 * Using right as an exclusive endpoint avoids
 * decrementing an unsigned index below zero.
 *
 * Preconditions:
 *     begin <= end
 *     The array is valid for [begin, end).
 *     The predicate contains a callable object.
 *
 * The predicate should return the same result
 * each time it is called with the same value.
 ************************************************************/

std::size_t partition(
    double                       array[],
    std::size_t            const begin,
    std::size_t            const end,
    std::function<bool(double)> const predicate
) {
    assert( begin <= end );
    assert( array != nullptr || begin == end );
    assert( static_cast<bool>( predicate ) );

    std::size_t left{ begin };
    std::size_t right{ end };

    while ( left < right ) {
        // Skip entries that are already
        // in the correct left-hand group.
        while (
            left < right
            && predicate( array[left] )
        ) {
            ++left;
        }

        // Skip entries that are already
        // in the correct right-hand group.
        while (
            left < right
            && !predicate( array[right - 1] )
        ) {
            --right;
        }

        // If the indices have not met,
        // both entries are in the wrong groups.
        if ( left < right ) {
            swap_array_entries(
                array,
                left,
                right - 1
            );

            ++left;
            --right;
        }
    }

    return left;
}

/************************************************************
 * Exchange two entries in an array.
 *
 * Preconditions:
 *     array is valid at both indices.
 ************************************************************/

void swap_array_entries(
    double             array[],
    std::size_t  const m,
    std::size_t  const n
) {
    assert( array != nullptr );

    double const tmp{ array[m] };

    array[m] = array[n];
    array[n] = tmp;
}

/************************************************************
 * Return true if x is strictly negative.
 *
 *      ==|====|====o----|----|----|----|--
 *       -3   -2   -1    0    1    2    3
 *
 * Zero is not negative.
 ************************************************************/

bool is_negative(
    double const x
) {
    return x < 0.0;
}

/************************************************************
 * Print the entries in [begin, end)
 * as a comma-separated list enclosed in braces.
 *
 * An empty interval is printed as {}.
 ************************************************************/

void print(
    double       const array[],
    std::size_t  const begin,
    std::size_t  const end
) {
    assert( begin <= end );
    assert( array != nullptr || begin == end );

    std::cout << "{";

    if ( begin < end ) {
        std::cout << array[begin];

        for (
            std::size_t k{ begin + 1 };
            k < end;
            ++k
        ) {
            std::cout << ", " << array[k];
        }
    }

    std::cout << "}" << std::endl;
}