#include <cstddef>
#include <iostream>

// Function declarations
std::size_t select_unique(
    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[4]{
        5, 5, 5, 5
    };

    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 = select_unique( nullptr, 0 );
    print_array( nullptr, result );
    std::cout << std::endl;

    print_array( array1, 4 );
    result = select_unique( array1, 4 );
    print_array( array1, result );
    std::cout << std::endl;

    print_array( array2, 12 );
    result = select_unique( array2, 12 );
    print_array( array2, result );
    std::cout << std::endl;

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

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

    return 0;
}

// Write a function that selects all the unique
// 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 unique
// entries.
//
// For example, given the array
//
//     {8, 0, 7, 1, 2, 9, 0, 7, 5, 1}
//
// this function should place
//
//     8, 0, 7, 1, 2, 9, 5
//
// in the first seven entries and return 7.
//
// The values in the remaining entries do not
// matter. All that matters is that the first seven
// entries contain the seven unique values.
//
// This implementation should preserve the order in
// which the unique values first occur.

std::size_t select_unique(
    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 one entry at a time.
// For each entry, compare it with the values already
// determined to be unique. If it has not yet appeared,
// copy it into the second array.
//
// Once you have examined the entire original array,
// copy the unique values back into the original array
// and return the number of unique entries.
//
// This works, but it requires additional memory.
//
// You might imagine declaring the temporary array as
//
//     int unique_array[capacity];
//
// but this is not a standard C++ built-in array because
// capacity is not known at compile time.
//
// Can you instead store the unique entries directly at
// the front of the original array?




































// You may be able to apply the same idea from the
// previous problem.
//
// Keep the unique values found so far in the first
// count entries of the array.
//
// For example, suppose the original array is
//
//      3  8  3  5  8  2  5  1
//
// Initially, no unique values have been selected:
//
//     count == 0
//
// The first value, 3, has not appeared before, so keep it:
//
//      3  8  3  5  8  2  5  1
//      ^
//     count == 1
//
// The next value, 8, is different from all previously
// selected values, so keep it:
//
//      3  8  3  5  8  2  5  1
//      ^--^
//     count == 2
//
// The next value is another 3. Since 3 is already among
// the first count entries, skip it.
//
// The next value, 5, has not yet appeared, so copy it
// into position count:
//
//      3  8  5  5  8  2  5  1
//      ^-----^
//     count == 3
//
// Continuing in this way eventually gives
//
//      3  8  5  2  1  ...
//
// and the function returns 5.
//
// Notice that when array[k] is copied, it is only ever
// copied to array[count], where count <= k. Therefore,
// no entry that has not yet been examined is overwritten.




































// One solution:

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

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        bool unique{ true };

        for ( std::size_t i{ 0 }; i < count; ++i ) {
            if ( array[k] == array[i] ) {
                unique = false;
                break;
            }
        }

        if ( unique ) {
            array[count] = array[k];
            ++count;
        }
    }

    return count;
}
*/