#include <cstddef>
#include <iostream>

// We have already discussed that an array can be sorted;
// however, an array can also be reverse sorted, from largest
// to smallest.
//
// An array where all entries are equal is both sorted and
// reverse sorted.
//
// Thus, an array could be:
//    0. neither,
//    1. only sorted,
//    2. only reverse sorted, or
//    3. both sorted and reverse sorted.

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

int main();

// Function definitions
int main() {
    int array1[1]{ 42 };

    int array2[8]{
        1, 1, 1, 1, 1, 1, 1, 1
    };

    int array3[27]{
        42, 42, 42, 42, 42, 42, 42, 42, 42,
        42, 42, 42, 42, 42, 42, 42, 42, 42,
        42, 42, 42, 42, 42, 42, 42, 42, 42
    };

    int array4[8]{
        15, 34, 40, 42, 59, 65, 69, 80
    };

    int array5[27]{
         2,  3, 17, 19, 22, 23, 29, 34, 38,
        38, 44, 46, 46, 46, 48, 50, 52, 57,
        65, 69, 73, 79, 88, 88, 93, 98, 99
    };

    int array6[8]{
        76, 75, 75, 66, 61, 48, 35, 5
    };

    int array7[27]{
        93, 92, 89, 86, 84, 83, 81, 70, 59,
        57, 56, 53, 47, 44, 41, 34, 31, 30,
        28, 27, 26, 17, 12,  7,  7,  4,  0
    };

    std::cout
        << "These are all both sorted and reverse sorted (3):"
        << std::endl;

    std::cout << is_sorted_array( nullptr, 0 ) << std::endl;
    std::cout << is_sorted_array( array1,  1 ) << std::endl;
    std::cout << is_sorted_array( array2,  8 ) << std::endl;
    std::cout << is_sorted_array( array3, 27 ) << std::endl;
    std::cout << std::endl;

    std::cout << "These are sorted (1):"
              << std::endl;

    std::cout << is_sorted_array( array4,  8 ) << std::endl;
    std::cout << is_sorted_array( array5, 27 ) << std::endl;
    std::cout << std::endl;

    std::cout << "These are reverse sorted (2):"
              << std::endl;

    std::cout << is_sorted_array( array6,  8 ) << std::endl;
    std::cout << is_sorted_array( array7, 27 ) << std::endl;
    std::cout << std::endl;

    array2[5]  =  8;
    array3[23] =  2;
    array4[6]  =  1;
    array5[17] = 12;
    array6[2]  = 98;
    array7[19] =  6;

    std::cout << "These are all neither sorted nor reverse sorted (0):"
              << std::endl;

    std::cout << is_sorted_array( array2,  8 ) << std::endl;
    std::cout << is_sorted_array( array3, 27 ) << std::endl;
    std::cout << is_sorted_array( array4,  8 ) << std::endl;
    std::cout << is_sorted_array( array5, 27 ) << std::endl;
    std::cout << is_sorted_array( array6,  8 ) << std::endl;
    std::cout << is_sorted_array( array7, 27 ) << std::endl;

    return 0;
}

// Write a function that returns:
//
//     0b00 if the array is neither sorted nor reverse sorted,
//     0b01 if the array is sorted but not reverse sorted,
//     0b10 if the array is reverse sorted but not sorted, and
//     0b11 if the array is both sorted and reverse sorted.
//
// An array with zero or one entry is both sorted and
// reverse sorted.

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




































// There are two quite different approaches to this
// problem. Have fun. :-)
//
// One approach is to compare the first and last entries
// to determine which results are possible, and then check
// whether the appropriate ordering actually holds.
//
// Another approach is to initially assume that the array
// is both sorted and reverse sorted. As you examine
// neighbouring entries, eliminate either possibility
// whenever you find evidence that it cannot be true.
//
// Remember:
//
//     array[k - 1] < array[k]
//
// means the array cannot be reverse sorted, whereas
//
//     array[k - 1] > array[k]
//
// means the array cannot be sorted.
//
// If both possibilities have been eliminated, you already
// know the answer and can return immediately.




































// The first implementation compares the first and last
// entries in the array:
//
//   1. If array[0] < array[capacity - 1], then the array
//      can only be sorted, if it is ordered at all.
//
//   2. If array[0] == array[capacity - 1], then the array
//      is both sorted and reverse sorted only if all its
//      entries are equal. Otherwise, it is neither.
//
//   3. If array[0] > array[capacity - 1], then the array
//      can only be reverse sorted, if it is ordered at all.
//
// The second implementation keeps track of both
// possibilities independently using the two bits of the
// return value.

/*
unsigned short is_sorted_array(
    int         const array[],
    std::size_t const capacity
) {
    if ( capacity <= 1 ) {
        return 0b11;
    } else if ( array[0] < array[capacity - 1] ) {
        // The array can only be sorted, if at all.

        for ( std::size_t k{ 1 }; k < capacity; ++k ) {
            if ( array[k - 1] > array[k] ) {
                return 0b00;
            }
        }

        return 0b01;
    } else if ( array[0] == array[capacity - 1] ) {
        // If all entries are equal, the array is both
        // sorted and reverse sorted. Otherwise, it is
        // neither.

        for ( std::size_t k{ 1 }; k < capacity; ++k ) {
            if ( array[k] != array[0] ) {
                return 0b00;
            }
        }

        return 0b11;
    } else {
        // The array can only be reverse sorted, if at all.

        for ( std::size_t k{ 1 }; k < capacity; ++k ) {
            if ( array[k - 1] < array[k] ) {
                return 0b00;
            }
        }

        return 0b10;
    }
}
*/


































// Here is a second solution:

/*
unsigned short is_sorted_array(
    int         const array[],
    std::size_t const capacity
) {
    unsigned short is_sorted{   0b01 };
    unsigned short is_reversed{ 0b10 };

    for ( std::size_t k{ 1 }; k < capacity; ++k ) {
        if ( array[k - 1] > array[k] ) {
            is_sorted = 0;
        } else if ( array[k - 1] < array[k] ) {
            is_reversed = 0;
        }

        if ( (is_sorted | is_reversed) == 0b00 ) {
            return 0b00;
        }
    }

    return is_sorted | is_reversed;
}
*/