#include <cstddef>
#include <iostream>

// Function declarations
std::size_t select_non_negative(
    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 array1[1]{   5 };
    int array2[1]{ -15 };

    int array3[10]{
         28, -6, 30, -1,  13,
         20, 11,  0, -21, -31
    };

    int array4[20]{
         35, -1, -22,  11,  -8,  10,  -8, -35, -10, 11,
         -5, 36, -49, -24,   8,  -1,  23,   8,  23, 24
    };

    std::size_t result{};

    print_array( nullptr, 0 );
    result = select_non_negative( nullptr, 0 );
    print_array( nullptr, result );
    std::cout << std::endl;

    print_array( array1, 1 );
    result = select_non_negative( array1, 1 );
    print_array( array1, result );
    std::cout << std::endl;

    print_array( array2, 1 );
    result = select_non_negative( array2, 1 );
    print_array( array2, result );
    std::cout << std::endl;

    print_array( array3, 10 );
    result = select_non_negative( array3, 10 );
    print_array( array3, result );
    std::cout << std::endl;

    print_array( array4, 20 );
    result = select_non_negative( array4, 20 );
    print_array( array4, result );

    return 0;
}

// Write a function that selects all the non-negative
// entries in the array and moves them to the front of
// the array, overwriting what may already be there.
//
// The value returned is the number of non-negative
// entries.
//
// Definition: A positive integer is greater than zero,
//             so 1, 2, 3, ..., while a negative integer
//             is less than zero, so -1, -2, -3, ... .
//             The non-negative integers are those that
//             are not negative, so 0, 1, 2, 3, ... .
//
// For example, given the array
//
//     {-8, 0, -7, 1, -2, -9, 10, -7, -5, 1}
//
// this function should place 0, 1, 10, and 1 in the
// first four entries and return 4.
//
// The values in the remaining entries do not matter.
// All that matters is that the first four entries
// contain the four non-negative values.

std::size_t select_non_negative(
    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 a second array.
//
// Go through the original array and copy each non-negative
// entry into the second array. Once you are finished, copy
// those selected values back into the original array.
//
// This works, but it requires additional memory.
//
// You might imagine something like:
//
//     int non_negative_array[capacity];
//
// but this is not a standard C++ built-in array because
// capacity is not known at compile time.
//
// Can you instead perform the selection directly in the
// original array?




































// Notice that once you examine array[k], if that entry is
// non-negative, it only ever needs to be moved to an index
// less than or equal to k.
//
// Keep track of how many non-negative entries have already
// been found. That count is also the index where the next
// non-negative entry should be copied.
//
// For example:
//
//         -3  0 -5 -4 10 -6  9  8 -5
//
// Skip -3 and copy 0 to position 0:
//
//          0  0 -5 -4 10 -6  9  8 -5
//
// Skip -5 and -4 and copy 10 to position 1:
//
//          0 10 -5 -4 10 -6  9  8 -5
//
// Skip -6 and copy 9 and 8 to positions 2 and 3:
//
//          0 10  9  8 10 -6  9  8 -5
//
// The value 4 is returned.
//
// We do not care what remains in the last five entries.
// All that matters is that the first four entries contain
// the four non-negative values.
//
// Notice also that the selected entries remain in the same
// relative order in which they occurred in the original
// array.




































// One solution:

/*
std::size_t select_non_negative(
    int               array[],
    std::size_t const capacity
) {
    std::size_t count{ 0 };

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        if ( array[k] >= 0 ) {
            array[count] = array[k];
            ++count;
        }
    }

    return count;
}
*/