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

/***************************************************
 * Counting and finding entries in an array
 *
 * Write three functions:
 *
 *   count(...) returns the number of times a given
 *   integer appears in an array.
 *
 *   first(...) returns the index of the first
 *   occurrence of the integer.
 *
 *   last(...) returns the index of the last
 *   occurrence of the integer.
 *
 * If the integer does not appear in the array,
 * first(...) and last(...) should both return the
 * capacity of the array.
 ***************************************************/

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

std::size_t first(
    int const n,
    int const array[],
    std::size_t const capacity
);

std::size_t last(
    int const n,
    int const array[],
    std::size_t const capacity
);

int main();

// Function definitions
int main() {
    int array0[20]{
         6,  8,  4, 11,  4,  5,  3,  5,  4,  8,
         9, 11,  8,  0,  3,  6,  8,  8,  7,  4
    };

    for ( int n{ 0 }; n <= 12; ++n ) {
        std::cout << n << ":\t";

        std::size_t const count_of_n{
            count( n, array0, 20 )
        };

        if ( count_of_n == 0 ) {
            std::cout << "none found" << std::endl;

            // Both first(...) and last(...) should
            // return capacity if n is not found.
            assert( first( n, array0, 20 ) == 20 );
            assert(  last( n, array0, 20 ) == 20 );
        } else if ( count_of_n == 1 ) {
            std::cout << "one found at "
                      << first( n, array0, 20 )
                      << std::endl;

            // If n appears only once, its first and
            // last occurrences must have the same
            // index.
            assert(
                first( n, array0, 20 )
                ==
                last( n, array0, 20 )
            );
        } else {
            std::cout << count_of_n
                      << " found between "
                      << first( n, array0, 20 )
                      << " and "
                      << last( n, array0, 20 )
                      << std::endl;
        }
    }

    return 0;
}

/***************************************************
 * count
 *
 * Return the number of times n appears in the
 * array.
 ***************************************************/
std::size_t count(
    int const n,
    int const array[],
    std::size_t const capacity
) {
    return 0;
}

/***************************************************
 * first
 *
 * Return the index of the first occurrence of n.
 * If n is not found, return capacity.
 ***************************************************/
std::size_t first(
    int const n,
    int const array[],
    std::size_t const capacity
) {
    return capacity;
}

/***************************************************
 * last
 *
 * Return the index of the last occurrence of n.
 * If n is not found, return capacity.
 ***************************************************/
std::size_t last(
    int const n,
    int const array[],
    std::size_t const capacity
) {
    return capacity;
}


































// Hints:
//
// The function count(...) requires a local variable
// storing the current count. Step through the array
// with a for loop. Each time an entry equal to n is
// found, increment the count.
//
//
// The function first(...) also requires a for loop
// that steps through the array. As soon as an entry
// equal to n is found, return its index.
//
// If the loop finishes without finding n, return
// capacity.
//
//
// The function last(...) can be implemented in at
// least two different ways.
//
// One approach is to walk forward through the array
// and remember the index of every occurrence found.
// The final index remembered must be the last
// occurrence.
//
// Another approach is to walk backward through the
// array. Then the first occurrence you find is the
// last occurrence in the array.
//
// Try to find both implementations.































// One solution:

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

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

    return n_count;
}

std::size_t first(
    int const n,
    int const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        if ( array[k] == n ) {
            return k;
        }
    }

    return capacity;
}

std::size_t last(
    int const n,
    int const array[],
    std::size_t const capacity
) {
    std::size_t index{ capacity };

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

    return index;
}
*/


































// An alternative implementation of last(...):
//
// We can instead walk backward through the array.
// The first matching entry encountered is therefore
// the last occurrence of n in the array.
//
// Notice the condition
//
//     k-- > 0
//
// rather than
//
//     k >= 0.
//
// Because std::size_t is an unsigned integer type,
// k can never be less than zero.

/*
std::size_t last(
    int const n,
    int const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ capacity }; k-- > 0; ) {
        if ( array[k] == n ) {
            return k;
        }
    }

    return capacity;
}
*/