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

// ROTATING AN ARRAY USING THREE REVERSALS
//
// A rotation rearranges the entries of an array
// without changing their relative order within
// the two portions being exchanged.
//
// Suppose we have an array and three indices
//
//     m <= n <= n2.
//
// A left rotation of the interval [m, n2)
// by n - m positions transforms
//
//     ar[m], ..., ar[n - 1], ar[n], ..., ar[n2 - 1]
//
// into
//
//     ar[n], ..., ar[n2 - 1], ar[m], ..., ar[n - 1].
//
// For example, given
//
//     0  1  2  3  4  5  6  7  8  9  10  11
//
// rotating the interval [3, 9) left by four
// positions produces
//
//     0  1  2  7  8  3  4  5  6  9  10  11.
//
// Equivalently, this is a right rotation
// of the interval [3, 9) by two positions.
//
// In this exercise, our functions will
// perform RIGHT rotations.
//
// One approach is to store some entries
// in a temporary array, move the remaining
// entries, and then copy the stored entries
// back into the array.
//
// However, there is a simpler approach
// that requires no additional array.
//
// First, write a function reverse_array()
// that reverses the entries in a given
// half-open interval [m, n).
//
// Then, use three calls to reverse_array()
// to implement a right rotation.
//
// If the interval has length L and we
// want to rotate right by r positions,
// first calculate
//
//     r = r % L.
//
// Next, reverse the following intervals:
//
//     [m, n - r)
//     [n - r, n)
//     [m, n)
//
// This algorithm uses constant additional
// memory and runs in linear time.

// Function declarations
int main();

void reverse_array(
    double             array[],
    std::size_t const  m,
    std::size_t const  n
);

void swap_array_entries(
    double             array[],
    std::size_t const  m,
    std::size_t const  n
);

void rotate_array(
    double             array[],
    std::size_t const  capacity,
    std::size_t const  rotation
);

void rotate_array(
    double             array[],
    std::size_t const  m,
    std::size_t const  n,
    std::size_t const  rotation
);

void print_array(
    double       const array[],
    std::size_t  const capacity
);

// Function definitions
int main() {
    double array[]{
         0,  1,  2,  3,  4,  5,  6,
         7,  8,  9, 10, 11, 12, 13
    };

    std::size_t const capacity{
        sizeof( array )/sizeof( array[0] )
    };

    print_array( array, capacity );

    // Rotate the entire array right by four.
    // The original array[10] moves to array[0].
    std::cout << "Rotate so that array[10] appears "
              << "at array[0]:" << std::endl;

    rotate_array( array, capacity, 4 );
    print_array( array, capacity );

    assert( array[0] == 10 );
    assert( array[4] == 0 );

    // Undo the rotation.
    std::cout << "Undo the rotation:" << std::endl;

    rotate_array( array, capacity, capacity - 4 );
    print_array( array, capacity );

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        assert( array[k] == static_cast<double>( k ) );
    }

    // Rotate only the interval [3, 9).
    // The original array[7] moves to array[3].
    std::cout << "Rotate so that array[7] appears "
              << "at array[3] up to array[8]:"
              << std::endl;

    rotate_array( array, 3, 9, 2 );
    print_array( array, capacity );

    assert( array[3] == 7 );
    assert( array[4] == 8 );

    // Undo the subarray rotation.
    rotate_array( array, 3, 9, 4 );
    print_array( array, capacity );

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        assert( array[k] == static_cast<double>( k ) );
    }

    // Test an empty interval.
    rotate_array( array, 3, 3, 5 );

    // Test a rotation by zero.
    rotate_array( array, capacity, 0 );

    // Test an empty array.
    rotate_array( nullptr, 0, 5 );

    // Test a rotation greater than the capacity.
    rotate_array( array, capacity, 2*capacity );

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        assert( array[k] == static_cast<double>( k ) );
    }

    return 0;
}

// Reverse the entries in the half-open
// interval [m, n).
//
// Preconditions:
//     m <= n
//     array is valid for the specified interval.
//
// For example, reversing [3, 10) in
//
//     0  1  2  3  4  5  6  7  8  9  10  11
//
// produces
//
//     0  1  2  9  8  7  6  5  4  3  10  11.
//
// An empty interval or an interval containing
// one entry requires no changes.

void reverse_array(
    double             array[],
    std::size_t const  m,
    std::size_t const  n
) {
    assert( m <= n );
    assert( array != nullptr || m == n );

    if ( n - m <= 1 ) {
        return;
    }

    std::size_t first{ m };
    std::size_t second{ n - 1 };

    while ( first < second ) {
        swap_array_entries( array, first, second );

        ++first;
        --second;
    }
}

// Exchange two entries in an array.

void swap_array_entries(
    double             array[],
    std::size_t const  m,
    std::size_t const  n
) {
    assert( array != nullptr );

    double const tmp{ array[m] };

    array[m] = array[n];
    array[n] = tmp;
}

// Rotate the entire array right by the
// specified number of positions.
//
// A rotation equal to or greater than
// the capacity is reduced modulo capacity.
//
// An empty array requires no changes.

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

    if ( capacity == 0 ) {
        return;
    }

    std::size_t const r{ rotation % capacity };

    if ( r == 0 ) {
        return;
    }

    reverse_array( array, 0, capacity - r );
    reverse_array( array, capacity - r, capacity );
    reverse_array( array, 0, capacity );
}

// Rotate the entries in the half-open
// interval [m, n) right by the specified
// number of positions.
//
// Entries outside this interval are unchanged.
//
// Preconditions:
//     m <= n
//     array is valid for the specified interval.

void rotate_array(
    double             array[],
    std::size_t const  m,
    std::size_t const  n,
    std::size_t const  rotation
) {
    assert( m <= n );
    assert( array != nullptr || m == n );

    std::size_t const capacity{ n - m };

    if ( capacity == 0 ) {
        return;
    }

    std::size_t const r{ rotation % capacity };

    if ( r == 0 ) {
        return;
    }

    reverse_array( array, m, n - r );
    reverse_array( array, n - r, n );
    reverse_array( array, m, n );
}

// Print an array as a comma-separated list.

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

    std::cout << "{";

    if ( capacity != 0 ) {
        std::cout << array[0];

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

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