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

/************************************************************
 * REDUCING AN ARRAY
 *
 * Suppose we want to calculate the sum of the entries
 * in an array. We could initialize a variable to zero
 * and then add each array entry to that variable.
 *
 * Similarly, to calculate the product, we could
 * initialize a variable to one and multiply it by
 * each successive array entry.
 *
 * These two algorithms have exactly the same structure.
 * Only the initial value and the operation change.
 *
 * We can generalize both algorithms using a function
 * called reduce().
 *
 * A reduction starts with an initial value and
 * repeatedly combines the current result with the
 * next array entry.
 *
 * The operation is supplied as a function argument.
 * It accepts two doubles and returns a double:
 *
 *     std::function<double(double, double)>
 *
 * For example, if the array contains
 *
 *     {2, 3, 4}
 *
 * then reducing it with an initial value of zero
 * and the sum operation calculates
 *
 *     ((0 + 2) + 3) + 4 = 9.
 *
 * Reducing the same array with an initial value
 * of one and the product operation calculates
 *
 *     ((1 * 2) * 3) * 4 = 24.
 *
 * The function processes the half-open interval
 * [begin, end), including begin but excluding end.
 *
 * This implementation processes the entries in
 * order, from left to right. It is therefore
 * closer to std::accumulate than std::reduce.
 ************************************************************/

// Function declarations
int main();

double reduce(
    double                       const 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
);

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

double max(
    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 << "Array entries: ";
    print( data, 0, data_capacity );

    std::cout << "The sum of all entries is "
              << reduce(
                     data,
                     0,
                     data_capacity,
                     0.0,
                     sum
                 )
              << std::endl;

    std::cout << "The product of all entries is "
              << reduce(
                     data,
                     0,
                     data_capacity,
                     1.0,
                     product
                 )
              << std::endl;

    std::cout << "The maximum of all entries is "
              << reduce(
                     data,
                     0,
                     data_capacity,
                     -std::numeric_limits<double>::infinity(),
                     max
                 )
              << std::endl;

    std::cout << "The minimum of all entries is "
              << reduce(
                     data,
                     0,
                     data_capacity,
                     std::numeric_limits<double>::infinity(),
                     min
                 )
              << std::endl;

    // A reduction over an empty interval
    // returns the initial value.
    assert(
        reduce( data, 5, 5, 42.0, sum ) == 42.0
    );

    // Simple tests with exact integer values.
    double test[]{ 2.0, 3.0, 4.0 };

    assert( reduce( test, 0, 3, 0.0, sum ) == 9.0 );
    assert( reduce( test, 0, 3, 1.0, product ) == 24.0 );
    assert( reduce( test, 0, 3, -100.0, max ) == 4.0 );
    assert( reduce( test, 0, 3, 100.0, min ) == 2.0 );

    // Reductions can also be performed
    // on only part of an array.
    assert( reduce( test, 1, 3, 0.0, sum ) == 7.0 );

    return 0;
}

/************************************************************
 * Reduce the entries in the interval [begin, end).
 *
 * Start with the initial value.
 *
 * For each array entry, call the accumulator with
 * the current result and the next array entry.
 *
 * Store the returned value as the new result.
 *
 * After processing all entries, return the result.
 *
 * For an array a[] and an initial value x0,
 * the calculation is
 *
 *     accumulator(
 *         accumulator(
 *             ...
 *             accumulator(
 *                 accumulator(x0, a[begin]),
 *                 a[begin + 1]
 *             ),
 *             ...
 *         ),
 *         a[end - 1]
 *     ).
 *
 * If begin == end, return the initial value.
 *
 * Preconditions:
 *     begin <= end
 *     The array is valid for [begin, end).
 *     The accumulator contains a callable object.
 ************************************************************/

double reduce(
    double                       const 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] );
    }

    return result;
}

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

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

double min(
    double const x,
    double const y
) {
    if ( x <= y ) {
        return x;
    } else {
        return y;
    }
}

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

double max(
    double const x,
    double const y
) {
    if ( x >= y ) {
        return x;
    } else {
        return y;
    }
}

/************************************************************
 * Print the entries in [begin, end)
 * as a comma-separated list enclosed in braces.
 ************************************************************/

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