#include <iostream>
#include <cstddef>
#include <cassert>
#include <algorithm>

// In this exercise, we will exchange blocks of entries between
// two arrays. The first block starts at array1[n1], and the
// second starts at array2[n2]. Each block contains m entries.
//
// The function swap(...) exchanges the two blocks while
// preserving the order of the entries within each block.
//
// The function unordered_swap(...) exchanges the same blocks,
// but the entries within each block need not retain their
// original order. Can you accomplish this using just one
// temporary double and a single loop?
//
// Assume that the arrays are distinct and that both blocks
// lie entirely within their respective arrays. The caller
// is responsible for ensuring these preconditions.
//
// For example, suppose the blocks are
//     array1: 10.2 10.3 10.4
//     array2: 20.4 20.5 20.6
//
// After swap(...), the blocks must be
//     array1: 20.4 20.5 20.6
//     array2: 10.2 10.3 10.4
//
// After unordered_swap(...), each block must contain the
// entries originally in the other block, but their order
// may differ. All entries outside the two blocks must remain
// unchanged.

// Function declarations
int main();
void swap( double            array1[],
           std::size_t const n1,
           double            array2[],
           std::size_t const n2,
           std::size_t const m );
void unordered_swap( double            array1[],
                     std::size_t const n1,
                     double            array2[],
                     std::size_t const n2,
                     std::size_t const m );
void print_array( double const      array[],
                  std::size_t const capacity );

// Function definitions
int main() {
    std::size_t const cap1{ 12 };
    std::size_t const cap2{ 18 };

    double data1[cap1]{ 10.0, 10.1, 10.2, 10.3, 10.4, 10.5,
                        10.6, 10.7, 10.8, 10.9, 11.0, 11.1 };
    double data2[cap2]{ 20.0, 20.1, 20.2, 20.3, 20.4, 20.5,
                        20.6, 20.7, 20.8, 20.9, 21.0, 21.1,
                        21.2, 21.3, 21.4, 21.5, 21.6, 21.7 };

    std::cout << "First array:" << std::endl;
    print_array( data1, cap1 );
    std::cout << "Second array:" << std::endl;
    print_array( data2, cap2 );
    std::cout << std::endl;

    assert( 2 + 5 <= cap1 );
    assert( 4 + 5 <= cap2 );
    std::cout << "Calling swap( data1, 2, data2, 4, 5 )"
              << std::endl;
    swap( data1, 2, data2, 4, 5 );

    // The five entries originally at data1[2] through
    // data1[6] have been exchanged, in order, with those
    // originally at data2[4] through data2[8].
    assert( data1[2] == 20.4 );
    assert( data1[6] == 20.8 );
    assert( data2[4] == 10.2 );
    assert( data2[8] == 10.6 );

    std::cout << "First array:" << std::endl;
    print_array( data1, cap1 );
    std::cout << "Second array:" << std::endl;
    print_array( data2, cap2 );
    std::cout << std::endl;

    assert( 8 + 3 <= cap1 );
    assert( 12 + 3 <= cap2 );
    std::cout << "Calling unordered_swap( data1, 8, data2, 12, 3 )"
              << std::endl;
    unordered_swap( data1, 8, data2, 12, 3 );

    // The order within either exchanged block does not matter.
    // These assertions check membership without assuming order.
    double const expected1[]{ 21.2, 21.3, 21.4 };
    double const expected2[]{ 10.8, 10.9, 11.0 };
    assert( std::is_permutation( data1 + 8, data1 + 11, expected1 ) );
    assert( std::is_permutation( data2 + 12, data2 + 15, expected2 ) );

    std::cout << "First array:" << std::endl;
    print_array( data1, cap1 );
    std::cout << "Second array:" << std::endl;
    print_array( data2, cap2 );
    std::cout << std::endl;

    return 0;
}

// Swap the blocks while preserving the order of their entries.
void swap( double            array1[],
           std::size_t const n1,
           double            array2[],
           std::size_t const n2,
           std::size_t const m ) {
    assert( array1 != nullptr );
    assert( array2 != nullptr );

    for ( std::size_t k{ 0 }; k < m; ++k ) {
        double const tmp{ array1[n1 + k] };
        array1[n1 + k] = array2[n2 + k];
        array2[n2 + k] = tmp;
    }
}

// Swap the blocks without preserving the order of their entries.
// Use only one temporary double. Do not allocate another array.
void unordered_swap( double            array1[],
                     std::size_t const n1,
                     double            array2[],
                     std::size_t const n2,
                     std::size_t const m ) {
    assert( array1 != nullptr );
    assert( array2 != nullptr );

    // Enter your implementation here.
}

void print_array( double const      array[],
                  std::size_t const capacity ) {
    assert( array != nullptr || capacity == 0 );

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        std::cout << " " << array[k];
    }

    std::cout << std::endl;
}


// HINTS
//
// 1. Begin by handling m == 0. In that case, there is
//    nothing to exchange.
//
// 2. Save array1[n1] in a temporary variable. This is
//    the only entry that must be held aside.
//
// 3. For each k from 0 to m - 2, move an entry from
//    array2[n2 + k] into array1[n1 + k]. The vacated
//    position in array2 can then receive the *next*
//    entry from array1.
//
// 4. After the loop, two positions remain to be filled.
//    Put the final entry from array2 into array1, and
//    put the saved entry from array1 into array2.
//
// 5. Trace the algorithm on paper with m == 1, m == 2,
//    and m == 3. Why does the loop stop at m - 1?
//    What goes wrong if you try to use m - 1 when m == 0?


// SOLUTION
// Uncomment this implementation and remove or comment out
// the incomplete unordered_swap(...) definition above.
/*
void unordered_swap( double            array1[],
                     std::size_t const n1,
                     double            array2[],
                     std::size_t const n2,
                     std::size_t const m ) {
    assert( array1 != nullptr );
    assert( array2 != nullptr );

    if ( m == 0 ) {
        return;
    }

    double const tmp{ array1[n1] };

    for ( std::size_t k{ 0 }; k < m - 1; ++k ) {
        array1[n1 + k] = array2[n2 + k];
        array2[n2 + k] = array1[n1 + k + 1];
    }

    // Fill the last two positions.
    array1[n1 + m - 1] = array2[n2 + m - 1];
    array2[n2 + m - 1] = tmp;
}
*/