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

/************************************************************
 * ADJACENT DIFFERENCE
 *
 * Previously, we implemented scans, which calculate
 * successive accumulated results.
 *
 * The adjacent_difference() function performs a
 * different operation: it combines each entry
 * with the preceding entry.
 *
 * For example, consider the array
 *
 *     {3, 8, 6, 10}
 *
 * Using subtraction produces
 *
 *     {3, 5, -2, 4}.
 *
 * The first entry is copied unchanged. Each
 * subsequent entry is the difference between
 * two consecutive original entries:
 *
 *     8 - 3  =  5
 *     6 - 8  = -2
 *    10 - 6  =  4
 *
 * We can generalize this algorithm by allowing
 * the caller to supply a binary operation.
 *
 * For example, using addition produces
 *
 *     {3, 11, 14, 16}.
 *
 * The function reads the entries in the
 * half-open interval [begin1, end1) and
 * writes the results into the second array,
 * starting at begin2.
 *
 * The first result is always a copy of
 * the first input entry.
 *
 * This implementation also supports two
 * particular overlapping arrangements:
 *
 *   1. Input and output start at the same entry.
 *
 *   2. Output starts one position after input.
 *
 * The second arrangement allows us to generate
 * the Fibonacci sequence using addition.
 *
 * Other partially overlapping ranges are
 * not supported.
 ************************************************************/

// Function declarations

int main();

void adjacent_difference(
    double                       array1[],
    std::size_t            const begin1,
    std::size_t            const end1,
    double                       array2[],
    std::size_t            const begin2,
    std::function<double(double, double)> const operation
);

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

double sum(
    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{ 20 };

    double vector[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( vector, 0, capacity );

    // Calculate adjacent differences in place.
    //
    // The input and output ranges begin
    // at the same position.
    adjacent_difference(
        vector, 0, capacity,
        vector, 0,
        difference
    );

    std::cout << "Adjacent differences:" << std::endl;
    print( vector, 0, capacity );

    std::cout << std::endl;

    /********************************************************
     * Generating the Fibonacci sequence
     *
     * Initially, every entry is one.
     *
     * We process [0, capacity - 1), but write
     * the results starting at index 1.
     *
     * The first output is a copy of fib[0].
     *
     * Subsequently, the operation adds the
     * current input entry to the previous
     * input entry.
     *
     * Because the output starts one position
     * after the input, previously calculated
     * Fibonacci numbers become the input
     * entries used by later iterations.
     *
     * This deliberately uses overlapping
     * input and output ranges.
     ********************************************************/

    double fib[capacity]{
        1.0, 1.0, 1.0, 1.0, 1.0,
        1.0, 1.0, 1.0, 1.0, 1.0,
        1.0, 1.0, 1.0, 1.0, 1.0,
        1.0, 1.0, 1.0, 1.0, 1.0
    };

    std::cout << "Initial Fibonacci array:"
              << std::endl;
    print( fib, 0, capacity );

    adjacent_difference(
        fib, 0, capacity - 1,
        fib, 1,
        sum
    );

    std::cout << "Fibonacci numbers:"
              << std::endl;
    print( fib, 0, capacity );

    // Verify the first few Fibonacci numbers.
    assert( fib[0] == 1.0 );
    assert( fib[1] == 1.0 );
    assert( fib[2] == 2.0 );
    assert( fib[3] == 3.0 );
    assert( fib[4] == 5.0 );
    assert( fib[5] == 8.0 );
    assert( fib[19] == 6765.0 );

    /********************************************************
     * Additional tests
     ********************************************************/

    // Separate input and output arrays.
    double input[]{ 3.0, 8.0, 6.0, 10.0 };
    double output[4]{};

    adjacent_difference(
        input, 0, 4,
        output, 0,
        difference
    );

    assert( output[0] == 3.0 );
    assert( output[1] == 5.0 );
    assert( output[2] == -2.0 );
    assert( output[3] == 4.0 );

    // The input array is unchanged.
    assert( input[0] == 3.0 );
    assert( input[1] == 8.0 );
    assert( input[2] == 6.0 );
    assert( input[3] == 10.0 );

    // Addition with separate arrays combines
    // consecutive original entries.
    adjacent_difference(
        input, 0, 4,
        output, 0,
        sum
    );

    assert( output[0] == 3.0 );
    assert( output[1] == 11.0 );
    assert( output[2] == 14.0 );
    assert( output[3] == 16.0 );

    // Test an interval containing one entry.
    double single[]{ 42.0 };

    adjacent_difference(
        single, 0, 1,
        single, 0,
        difference
    );

    assert( single[0] == 42.0 );

    // An empty interval writes nothing.
    adjacent_difference(
        input, 2, 2,
        output, 0,
        difference
    );

    // Empty arrays are valid for an
    // empty input interval.
    adjacent_difference(
        nullptr, 0, 0,
        nullptr, 0,
        difference
    );

    return 0;
}

/************************************************************
 * ADJACENT DIFFERENCE
 *
 * Read the entries in [begin1, end1) and
 * write the results starting at begin2.
 *
 * If the input interval is empty, do nothing.
 *
 * Otherwise, copy the first input entry
 * into the first output position.
 *
 * For each subsequent entry:
 *
 *     1. Save the current input value.
 *
 *     2. Apply the operation to the current
 *        input value and the preceding
 *        input value.
 *
 *     3. Store the result in the output array.
 *
 *     4. Update the preceding input value.
 *
 * Saving the current input value before
 * writing the result permits in-place
 * operation.
 *
 * It also permits the special overlapping
 * arrangement used in the Fibonacci example,
 * in which output begins one position
 * after input.
 *
 * Preconditions:
 *     begin1 <= end1
 *     Both array ranges are valid.
 *     The operation contains a callable object.
 *     The input and output ranges are disjoint,
 *       begin at the same position, or overlap
 *       with output starting exactly one
 *       position after input.
 ************************************************************/

void adjacent_difference(
    double                       array1[],
    std::size_t            const begin1,
    std::size_t            const end1,
    double                       array2[],
    std::size_t            const begin2,
    std::function<double(double, double)> const operation
) {
    assert( begin1 <= end1 );
    assert( array1 != nullptr || begin1 == end1 );
    assert( array2 != nullptr || begin1 == end1 );
    assert( static_cast<bool>( operation ) );

    if ( begin1 == end1 ) {
        return;
    }

    // Save the first original input value.
    double previous{ array1[begin1] };

    // The first output is always a copy
    // of the first input entry.
    array2[begin2] = previous;

    std::size_t k2{ begin2 + 1 };

    for (
        std::size_t k1{ begin1 + 1 };
        k1 < end1;
        ++k1, ++k2
    ) {
        // Save the current input value
        // before overwriting any entry.
        double const current{ array1[k1] };

        // Combine the current input value
        // with the preceding input value.
        array2[k2] = operation(
            current,
            previous
        );

        // This becomes the preceding input
        // value for the next iteration.
        previous = current;
    }
}

/************************************************************
 * Return the difference x - y.
 *
 * The order of the arguments matters:
 *
 *     current - previous
 ************************************************************/

double difference(
    double const x,
    double const y
) {
    return x - y;
}

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

double sum(
    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;
}