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

/************************************************************
 * TRANSFORM AND REDUCE
 *
 * Previously, we implemented reduce(), which combines
 * the entries of an array into a single result.
 *
 * For example, reducing the array
 *
 *     {2, -3, 4}
 *
 * using addition and an initial value of zero
 * calculates
 *
 *     ((0 + 2) + (-3)) + 4 = 3.
 *
 * Suppose, however, that we want the sum of the
 * squares of the entries:
 *
 *     2*2 + (-3)*(-3) + 4*4 = 29.
 *
 * We could first replace every entry with its
 * square and then reduce the resulting array.
 *
 * However, we do not need to modify the array
 * or create a second array.
 *
 * Instead, we can transform each entry immediately
 * before combining it with the running result.
 *
 * This operation is called transform-reduce.
 *
 * It accepts two functions:
 *
 *   transform:
 *       Accepts one double and returns a double.
 *
 *   accumulator:
 *       Accepts two doubles and returns a double.
 *
 * The algorithm is:
 *
 *   1. Initialize the result to initial_value.
 *   2. For each entry in the array:
 *        a. Transform the entry.
 *        b. Combine the transformed entry with
 *           the current result.
 *   3. Return the final result.
 *
 * IMPORTANT:
 *
 * The initial value is not transformed.
 *
 * This implementation processes the entries
 * strictly from left to right, unlike the
 * standard library's std::transform_reduce,
 * which may combine values in a different order.
 *
 * The function operates on the half-open
 * interval [begin, end).
 ************************************************************/

// Function declarations
int main();

double transform_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,
    std::function<double(double)>         const transform
);

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

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

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

double abs_val(
    double const x
);

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

    // Add the absolute values of all entries.
    std::cout << "The sum of the absolute values is "
              << transform_reduce(
                     data,
                     0,
                     data_capacity,
                     0.0,
                     sum,
                     abs_val
                 )
              << std::endl;

    // Add the squares of all entries.
    std::cout << "The sum of the squares is "
              << transform_reduce(
                     data,
                     0,
                     data_capacity,
                     0.0,
                     sum,
                     sqr
                 )
              << std::endl;

    // Find the largest absolute value.
    //
    // Since every absolute value is nonnegative,
    // zero is a suitable initial value.
    std::cout << "The maximum absolute value is "
              << transform_reduce(
                     data,
                     0,
                     data_capacity,
                     0.0,
                     max,
                     abs_val
                 )
              << std::endl;

    // Find the smallest absolute value.
    //
    // Positive infinity is a suitable initial
    // value because every finite absolute value
    // is smaller than positive infinity.
    std::cout << "The minimum absolute value is "
              << transform_reduce(
                     data,
                     0,
                     data_capacity,
                     std::numeric_limits<double>::infinity(),
                     min,
                     abs_val
                 )
              << std::endl;

    // Tests using an array whose results
    // can easily be calculated by hand.
    double test[]{ 2.0, -3.0, 4.0 };

    assert(
        transform_reduce(
            test, 0, 3, 0.0, sum, abs_val
        ) == 9.0
    );

    assert(
        transform_reduce(
            test, 0, 3, 0.0, sum, sqr
        ) == 29.0
    );

    assert(
        transform_reduce(
            test, 0, 3, 0.0, max, abs_val
        ) == 4.0
    );

    assert(
        transform_reduce(
            test,
            0,
            3,
            std::numeric_limits<double>::infinity(),
            min,
            abs_val
        ) == 2.0
    );

    // The initial value must not be transformed.
    //
    // The correct result is
    //
    //     10 + 4 + 9 + 16 = 39,
    //
    // not 100 + 4 + 9 + 16.
    assert(
        transform_reduce(
            test, 0, 3, 10.0, sum, sqr
        ) == 39.0
    );

    // Test a reduction over only part
    // of the array.
    //
    // The absolute values of -3 and 4
    // sum to 7.
    assert(
        transform_reduce(
            test, 1, 3, 0.0, sum, abs_val
        ) == 7.0
    );

    // An empty interval returns the
    // initial value without transforming it.
    assert(
        transform_reduce(
            test, 2, 2, 10.0, sum, sqr
        ) == 10.0
    );

    assert(
        transform_reduce(
            nullptr, 0, 0, 42.0, sum, sqr
        ) == 42.0
    );

    // Verify that the input array was not modified.
    assert( test[0] == 2.0 );
    assert( test[1] == -3.0 );
    assert( test[2] == 4.0 );

    return 0;
}

/************************************************************
 * TRANSFORM-REDUCE
 *
 * Transform each entry in [begin, end) and
 * combine the transformed values into one result.
 *
 * For the original array entries
 *
 *     a[begin], a[begin + 1], ..., a[end - 1],
 *
 * calculate
 *
 *     accumulator(
 *         accumulator(
 *             ...
 *             accumulator(
 *                 initial_value,
 *                 transform(a[begin])
 *             ),
 *             transform(a[begin + 1])
 *         ),
 *         ...
 *     ).
 *
 * The initial value is not transformed.
 *
 * If begin == end, return initial_value.
 *
 * The array is not modified.
 *
 * Preconditions:
 *     begin <= end
 *     The array is valid for [begin, end).
 *     Both function arguments are callable.
 ************************************************************/

double transform_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,
    std::function<double(double)>         const transform
) {
    assert( begin <= end );
    assert( array != nullptr || begin == end );
    assert( static_cast<bool>( accumulator ) );
    assert( static_cast<bool>( transform ) );

    double result{ initial_value };

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

        result = accumulator(
            result,
            transformed_value
        );
    }

    return result;
}

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

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

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

double max(
    double const x,
    double const y
) {
    if ( x >= y ) {
        return x;
    } else {
        return 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 absolute value of x.
 ************************************************************/

double abs_val(
    double const x
) {
    if ( x >= 0.0 ) {
        return x;
    } else {
        return -x;
    }
}

/************************************************************
 * Return the square of x.
 ************************************************************/

double sqr(
    double const x
) {
    return x*x;
}

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