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

/************************************************************
 * INCLUSIVE AND EXCLUSIVE SCANS
 *
 * Previously, we implemented reduce(), which combines
 * the entries of an array into a single result.
 *
 * For example, reducing
 *
 *     {2, 3, 4, 5}
 *
 * with an initial value of zero and addition produces
 *
 *     (((0 + 2) + 3) + 4) + 5 = 14.
 *
 * Sometimes, however, we want to retain every
 * intermediate result rather than just the final one.
 *
 * This operation is called a scan.
 *
 * There are two types of scans:
 *
 * 1. INCLUSIVE SCAN
 *
 *    An inclusive scan includes the current array
 *    entry when calculating the result stored at
 *    that position.
 *
 *    For example, starting with
 *
 *        {2, 3, 4, 5}
 *
 *    and using addition with an initial value of
 *    zero produces
 *
 *        {2, 5, 9, 14}.
 *
 *    Each entry is the sum of all the original
 *    entries up to and including that position.
 *
 * 2. EXCLUSIVE SCAN
 *
 *    An exclusive scan excludes the current array
 *    entry when calculating the result stored at
 *    that position.
 *
 *    Starting with the same array and initial
 *    value produces
 *
 *        {0, 2, 5, 9}.
 *
 *    The first entry is the initial value.
 *    Each subsequent entry is the accumulated
 *    result of the preceding original entries.
 *
 * Both scans use an accumulator: a function
 * that accepts two doubles and returns a double.
 *
 * The scans modify the array in place, so no
 * additional array is required.
 *
 * They operate on the half-open interval
 * [begin, end), leaving all other entries
 * unchanged.
 *
 * These implementations process entries
 * strictly from left to right.
 ************************************************************/

// Function declarations
int main();

void inclusive_scan(
    double                              array[],
    std::size_t                   const begin,
    std::size_t                   const end,
    double                        const initial_value,
    std::function<double(double, double)> const accumulator
);

void exclusive_scan(
    double                              array[],
    std::size_t                   const begin,
    std::size_t                   const end,
    double                        const initial_value,
    std::function<double(double, double)> const accumulator
);

double sum(
    double const x,
    double const y
);

double product(
    double const x,
    double const y
);

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 );

    // Calculate inclusive partial sums.
    inclusive_scan(
        data,
        0,
        data_capacity,
        0.0,
        sum
    );

    std::cout << "Inclusive partial sums:" << std::endl;
    print( data, 0, data_capacity );

    // Apply an inclusive product scan to the
    // array of partial sums.
    //
    // Notice that we are not calculating
    // partial products of the original array.
    // We are multiplying its partial sums.
    inclusive_scan(
        data,
        0,
        data_capacity,
        1.0,
        product
    );

    std::cout
        << "Inclusive partial products of the partial sums:"
        << std::endl;

    print( data, 0, data_capacity );

    // Restore the original entries in a
    // second array for the exclusive scan.
    double data2[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
    };

    exclusive_scan(
        data2,
        0,
        data_capacity,
        0.0,
        sum
    );

    std::cout << "Exclusive partial sums:"
              << std::endl;

    print( data2, 0, data_capacity );

    // Test both scans using small arrays
    // whose expected results are easy
    // to calculate by hand.
    double test1[]{ 2.0, 3.0, 4.0, 5.0 };

    inclusive_scan( test1, 0, 4, 0.0, sum );

    assert( test1[0] == 2.0 );
    assert( test1[1] == 5.0 );
    assert( test1[2] == 9.0 );
    assert( test1[3] == 14.0 );

    double test2[]{ 2.0, 3.0, 4.0, 5.0 };

    exclusive_scan( test2, 0, 4, 0.0, sum );

    assert( test2[0] == 0.0 );
    assert( test2[1] == 2.0 );
    assert( test2[2] == 5.0 );
    assert( test2[3] == 9.0 );

    // Test multiplication.
    double test3[]{ 2.0, 3.0, 4.0, 5.0 };

    inclusive_scan( test3, 0, 4, 1.0, product );

    assert( test3[0] == 2.0 );
    assert( test3[1] == 6.0 );
    assert( test3[2] == 24.0 );
    assert( test3[3] == 120.0 );

    double test4[]{ 2.0, 3.0, 4.0, 5.0 };

    exclusive_scan( test4, 0, 4, 1.0, product );

    assert( test4[0] == 1.0 );
    assert( test4[1] == 2.0 );
    assert( test4[2] == 6.0 );
    assert( test4[3] == 24.0 );

    // Test an initial value other than
    // the identity element for addition.
    double test5[]{ 2.0, 3.0, 4.0 };

    inclusive_scan( test5, 0, 3, 10.0, sum );

    assert( test5[0] == 12.0 );
    assert( test5[1] == 15.0 );
    assert( test5[2] == 19.0 );

    // Test a scan over only part of an array.
    double test6[]{ 10.0, 2.0, 3.0, 4.0, 20.0 };

    exclusive_scan( test6, 1, 4, 0.0, sum );

    assert( test6[0] == 10.0 );
    assert( test6[1] == 0.0 );
    assert( test6[2] == 2.0 );
    assert( test6[3] == 5.0 );
    assert( test6[4] == 20.0 );

    // An empty interval must leave
    // the array unchanged.
    inclusive_scan( test6, 2, 2, 0.0, sum );
    exclusive_scan( test6, 2, 2, 0.0, sum );

    // An empty array is also valid
    // when the interval is empty.
    inclusive_scan( nullptr, 0, 0, 0.0, sum );
    exclusive_scan( nullptr, 0, 0, 0.0, sum );

    return 0;
}

/************************************************************
 * INCLUSIVE SCAN
 *
 * Replace the entries in [begin, end) with
 * the successive accumulated results.
 *
 * Let the original entries be
 *
 *     a[begin], a[begin + 1], ..., a[end - 1].
 *
 * Starting with the initial value x0,
 * calculate
 *
 *     result = x0.
 *
 * For each entry:
 *
 *     result = accumulator(result, array[k]);
 *     array[k] = result;
 *
 * Thus, the current entry contributes to
 * the value stored at that same position.
 *
 * If begin == end, no entries are modified.
 *
 * Preconditions:
 *     begin <= end
 *     The array is valid for [begin, end).
 *     The accumulator contains a callable object.
 ************************************************************/

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

    double result{ initial_value };

    for (
        std::size_t k{ begin };
        k < end;
        ++k
    ) {
        result = accumulator( result, array[k] );
        array[k] = result;
    }
}

/************************************************************
 * EXCLUSIVE SCAN
 *
 * Replace the entries in [begin, end) with
 * the accumulated results of all preceding
 * original entries.
 *
 * Starting with the initial value x0,
 * calculate
 *
 *     result = x0.
 *
 * For each entry:
 *
 *     1. Save the current original entry.
 *     2. Replace the entry with result.
 *     3. Update result using the saved entry.
 *
 * The current original entry must be saved
 * before it is overwritten.
 *
 * If begin == end, no entries are modified.
 *
 * Preconditions:
 *     begin <= end
 *     The array is valid for [begin, end).
 *     The accumulator contains a callable object.
 ************************************************************/

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

    double result{ initial_value };

    for (
        std::size_t k{ begin };
        k < end;
        ++k
    ) {
        double const current{ array[k] };

        array[k] = result;

        result = accumulator( result, current );
    }
}

/************************************************************
 * Return the sum of two values.
 ************************************************************/

double sum(
    double const x,
    double const y
) {
    return x + y;
}

/************************************************************
 * Return the product of two values.
 ************************************************************/

double product(
    double const x,
    double const y
) {
    return x*y;
}

/************************************************************
 * 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;
}