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

/************************************************************
 * INNER PRODUCT
 *
 * Previously, we implemented transform_reduce(), which
 * transforms each entry of an array before combining
 * the transformed values into a single result.
 *
 * An inner product extends this idea to two arrays.
 *
 * Consider the arrays
 *
 *     array1 = {2, 3, 4}
 *     array2 = {5, 6, 7}
 *
 * The usual inner product multiplies corresponding
 * entries and adds the products:
 *
 *     2*5 + 3*6 + 4*7 = 56.
 *
 * We can generalize this calculation by allowing
 * the caller to supply two operations:
 *
 *   1. pair_operation:
 *
 *      Combines two corresponding array entries.
 *      For the usual inner product, this is
 *      multiplication.
 *
 *   2. accumulator:
 *
 *      Combines the running result with the value
 *      returned by pair_operation.
 *      For the usual inner product, this is addition.
 *
 * We also supply an initial value.
 *
 * The generalized algorithm is:
 *
 *   1. Initialize result to initial_value.
 *   2. For each corresponding pair of entries:
 *        a. Apply pair_operation to the two entries.
 *        b. Combine its result with result using
 *           accumulator.
 *   3. Return result.
 *
 * The first array is read over [begin1, end1).
 * The second array is read starting at begin2.
 *
 * Both arrays must contain enough entries for
 * these ranges to be valid.
 *
 * Neither array is modified.
 *
 * This implementation processes entries strictly
 * from left to right, as does std::inner_product.
 ************************************************************/

// Function declarations

int main();

double inner_product(
    double const                         array1[],
    std::size_t const                    begin1,
    std::size_t const                    end1,
    double const                         array2[],
    std::size_t const                    begin2,
    double const                         initial_value,
    std::function<double(double, double)> const accumulator,
    std::function<double(double, double)> const pair_operation
);

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

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

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

double abs_val(
    double const x
);

double absolute_difference(
    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 capacity{ 10 };

    double vector1[capacity]{
         6.73, -0.52, -5.52, -8.43,  4.41,
         1.19,  5.19, -1.40,  2.55, -9.02
    };

    double vector2[capacity]{
         7.35,  7.34,  9.34, -0.06,  1.12,
        -2.73, -9.77,  4.71,  2.20, -9.28
    };

    std::cout << "First vector:  ";
    print( vector1, 0, capacity );

    std::cout << "Second vector: ";
    print( vector2, 0, capacity );

    // The usual inner product multiplies
    // corresponding entries and adds the products.
    std::cout << "The inner product is "
              << inner_product(
                     vector1, 0, capacity,
                     vector2, 0,
                     0.0,
                     sum,
                     product
                 )
              << std::endl;

    // The same algorithm can calculate the
    // sum of the absolute differences between
    // corresponding entries.
    std::cout << "The sum of absolute differences is "
              << inner_product(
                     vector1, 0, capacity,
                     vector2, 0,
                     0.0,
                     sum,
                     absolute_difference
                 )
              << std::endl;

    // Or find the largest absolute difference.
    std::cout << "The maximum absolute difference is "
              << inner_product(
                     vector1, 0, capacity,
                     vector2, 0,
                     0.0,
                     max,
                     absolute_difference
                 )
              << std::endl;

    /********************************************************
     * Tests
     *
     * Use small arrays with results that can be
     * calculated by hand.
     ********************************************************/

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

    // 2*5 + 3*6 + 4*7 = 56.
    assert(
        inner_product(
            test1, 0, 3,
            test2, 0,
            0.0,
            sum,
            product
        ) == 56.0
    );

    // The initial value is included once.
    assert(
        inner_product(
            test1, 0, 3,
            test2, 0,
            10.0,
            sum,
            product
        ) == 66.0
    );

    // |2 - 5| + |3 - 6| + |4 - 7| = 9.
    assert(
        inner_product(
            test1, 0, 3,
            test2, 0,
            0.0,
            sum,
            absolute_difference
        ) == 9.0
    );

    // The largest absolute difference is 3.
    assert(
        inner_product(
            test1, 0, 3,
            test2, 0,
            0.0,
            max,
            absolute_difference
        ) == 3.0
    );

    // Test a partial interval.
    //
    // Pair test1[1], test1[2] with
    // test2[0], test2[1]:
    //
    //     3*5 + 4*6 = 39.
    assert(
        inner_product(
            test1, 1, 3,
            test2, 0,
            0.0,
            sum,
            product
        ) == 39.0
    );

    // An empty interval returns the
    // initial value.
    assert(
        inner_product(
            test1, 2, 2,
            test2, 0,
            42.0,
            sum,
            product
        ) == 42.0
    );

    // Both arrays may be null if the
    // interval is empty.
    assert(
        inner_product(
            nullptr, 0, 0,
            nullptr, 0,
            42.0,
            sum,
            product
        ) == 42.0
    );

    // Verify that neither input array
    // was modified.
    assert( test1[0] == 2.0 );
    assert( test1[1] == 3.0 );
    assert( test1[2] == 4.0 );

    assert( test2[0] == 5.0 );
    assert( test2[1] == 6.0 );
    assert( test2[2] == 7.0 );

    return 0;
}

/************************************************************
 * INNER PRODUCT
 *
 * Combine corresponding entries of two arrays,
 * and accumulate the resulting values.
 *
 * If the first interval contains n entries,
 * calculate
 *
 *     result = initial_value;
 *
 *     for each k from 0 to n - 1:
 *
 *         value = pair_operation(
 *             array1[begin1 + k],
 *             array2[begin2 + k]
 *         );
 *
 *         result = accumulator(result, value);
 *
 * Return the final result.
 *
 * If begin1 == end1, return initial_value.
 *
 * Preconditions:
 *     begin1 <= end1
 *     Both array ranges are valid.
 *     Both operations contain callable objects.
 *
 * The function cannot verify the actual capacities
 * of the arrays, so the caller must ensure that
 * the second array has at least end1 - begin1
 * entries starting at begin2.
 ************************************************************/

double inner_product(
    double const                         array1[],
    std::size_t const                    begin1,
    std::size_t const                    end1,
    double const                         array2[],
    std::size_t const                    begin2,
    double const                         initial_value,
    std::function<double(double, double)> const accumulator,
    std::function<double(double, double)> const pair_operation
) {
    assert( begin1 <= end1 );
    assert( array1 != nullptr || begin1 == end1 );
    assert( array2 != nullptr || begin1 == end1 );
    assert( static_cast<bool>( accumulator ) );
    assert( static_cast<bool>( pair_operation ) );

    double result{ initial_value };

    std::size_t k2{ begin2 };

    for (
        std::size_t k1{ begin1 };
        k1 < end1;
        ++k1, ++k2
    ) {
        double const value{
            pair_operation( array1[k1], array2[k2] )
        };

        result = accumulator( result, value );
    }

    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 larger of two values.
 ************************************************************/

double max(
    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 absolute difference between x and y.
 ************************************************************/

double absolute_difference(
    double const x,
    double const y
) {
    return abs_val( 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;
}