#include <cstddef>
#include <iostream>

// Function declarations
std::size_t partition_even_odd(
    int               array[],
    std::size_t const capacity
);

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

int main();

// Function definitions
int main() {
    int array0[3]{
        1, 1, 1
    };

    int array1[4]{
        2, 2, 2, 2
    };

    int array2[12]{
        1, 2, 3, 1, 2, 3, 3, 2, 1, 1, 2, 3
    };

    int array3[10]{
        6, 7, 0, 5, 0, 1, 7, 7, 0, 0
    };

    int array4[20]{
        3, 8, 6, 5, 4, 9, 1, 4, 0, 1,
        5, 6, 7, 3, 4, 8, 7, 5, 7, 7
    };

    std::size_t result{};

    print_array( nullptr, 0 );
    result = partition_even_odd( nullptr, 0 );
    std::cout << result << " even values:" << std::endl;
    print_array( nullptr, 0 );
    std::cout << std::endl;

    print_array( array0, 3 );
    result = partition_even_odd( array0, 3 );
    std::cout << result << " even values:" << std::endl;
    print_array( array0, 3 );
    std::cout << std::endl;

    print_array( array1, 4 );
    result = partition_even_odd( array1, 4 );
    std::cout << result << " even values:" << std::endl;
    print_array( array1, 4 );
    std::cout << std::endl;

    print_array( array2, 12 );
    result = partition_even_odd( array2, 12 );
    std::cout << result << " even values:" << std::endl;
    print_array( array2, 12 );
    std::cout << std::endl;

    print_array( array3, 10 );
    result = partition_even_odd( array3, 10 );
    std::cout << result << " even values:" << std::endl;
    print_array( array3, 10 );
    std::cout << std::endl;

    print_array( array4, 20 );
    result = partition_even_odd( array4, 20 );
    std::cout << result << " even values:" << std::endl;
    print_array( array4, 20 );

    return 0;
}

// Write a function that moves all the even entries
// to the front of the array and all the odd entries
// to the back.
//
// The order of the even entries does not matter,
// nor does the order of the odd entries.
//
// The return value is the number of even integers.
//
// Thus, if even_count is the number of even entries,
// the even entries will occupy locations
//
//     0, 1, ..., even_count - 1
//
// and the odd entries will occupy locations
//
//     even_count, even_count + 1, ..., capacity - 1.
//
// For example, given the array
//
//     {8, 0, 7, 1, 2, 9, 0, 7, 5, 1}
//
// this function could produce an array having
//
//     0, 0, 2, 8
//
// in the first four entries, in any order, and
//
//     1, 1, 5, 7, 7, 9
//
// in the last six entries, in any order.
//
// The function would then return 4.
//
// This is more challenging than the previous two
// problems.
//
// Enjoy. :-)

std::size_t partition_even_odd(
    int               array[],
    std::size_t const capacity
) {
    return 0;
}

void print_array(
    int         const array[],
    std::size_t const capacity
) {
    if ( capacity > 0 ) {
        std::cout << array[0];

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

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


































// Your first attempt might be to create two local arrays,
// each with the given capacity.
//
// Go through the original array, copying even values into
// one array and odd values into the other. When finished,
// copy all the even values followed by all the odd values
// back into the original array.
//
// You could also imagine using only one temporary array.
// Even values could be copied starting at the front while
// odd values are copied starting at the back.
//
// For example, given
//
//      5, 4, 9, 7, 5, 9, 2, 1, 6, 0
//
// a temporary array could initially contain
//
//      ?, ?, ?, ?, ?, ?, ?, ?, ?, ?
//
// Copy 5 to the back:
//
//      ?, ?, ?, ?, ?, ?, ?, ?, ?, 5
//
// Copy 4 to the front:
//
//      4, ?, ?, ?, ?, ?, ?, ?, ?, 5
//
// Copy 9 to the back:
//
//      4, ?, ?, ?, ?, ?, ?, ?, 9, 5
//
// Copy 7 to the back:
//
//      4, ?, ?, ?, ?, ?, ?, 7, 9, 5
//
// and so on.
//
// This works, but it requires additional storage.
//
// Furthermore, an array declared as
//
//     int partitioned_array[capacity];
//
// is not a standard C++ built-in array because capacity
// is not known at compile time.
//
// Can you partition the original array without using any
// additional array?




































// To figure this out, imagine randomly laying out a
// handful of dimes and nickels:
//
//     O o O O O o o O o O O O o O o O O
//
// Pretend that 'o' is a dime and 'O' is a nickel.
//
// How could you rearrange them so that they look like
//
//     O O O O O O O O O O O o o o o o o
//
// without creating another row of coins?
//
// One possibility is to start at both ends.
//
// Starting at the front, look for an odd entry.
//
// Starting at the back, look for an even entry.
//
// If you find both, they are on the wrong sides of the
// partition, so swap them.
//
// Continue until the two searches meet.




































// One solution:
//
// Rather than storing an index of the last entry, let
// 'back' indicate one position beyond the portion of
// the array that still needs to be examined.
//
// Thus, initially:
//
//     front == 0
//     back  == capacity
//
// This avoids having to calculate capacity - 1 when
// the array is empty.

/*
std::size_t partition_even_odd(
    int               array[],
    std::size_t const capacity
) {
    std::size_t front{ 0 };
    std::size_t back{ capacity };

    while ( front < back ) {
        // Skip over even entries already at the front.
        while ( (front < back) && (array[front]%2 == 0) ) {
            ++front;
        }

        // Skip over odd entries already at the back.
        while ( (front < back) && (array[back - 1]%2 != 0) ) {
            --back;
        }

        if ( front < back ) {
            // array[front] is odd and array[back - 1]
            // is even, so swap them.
            int const tmp{ array[front] };
            array[front] = array[back - 1];
            array[back - 1] = tmp;

            ++front;
            --back;
        }
    }

    return front;
}
*/