#include <cstddef>
#include <iostream>

// Reverse engineering an undocumented function
//
// You are asked to investigate a bug, and you
// come across the following undocumented function
// that is called.
//
// Determine what the function does.
//
// In particular:
//
// 1. What do the variables 'a' and 'b' represent?
//
// 2. Why are they initialized to 1 and 2?
//
// 3. What does each of the possible return values
//
//        0, 1, 2, and 3
//
//    mean?
//
// 4. Why does the function sometimes return 0
//    before examining the entire array?
//
// 5. What is the purpose of the bitwise OR
//    operator | in
//
//        return a | b;
//
// Once you understand the function, add appropriate
// documentation.
//
// You should test the function on arrays that are:
//
//   - strictly increasing,
//   - strictly decreasing,
//   - constant,
//   - nondecreasing with repeated values,
//   - nonincreasing with repeated values, and
//   - neither nondecreasing nor nonincreasing.
//
// Also consider arrays containing zero or one entry.

// Function declarations
int main();

unsigned int is_sorted(
    double      const array[],
    std::size_t const capacity
);

// Function definitions
int main() {
    std::size_t const N{ 2 };

    double array[N]{
        1.25, 1.25
    };

    std::cout << is_sorted( array, N )
              << std::endl;

    return 0;
}

unsigned int is_sorted(
    double      const array[],
    std::size_t const capacity
) {
    unsigned int a{ 1 };
    unsigned int b{ 2 };

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

            if ( b == 0 ) {
                return 0;
            }
        }

        if ( array[k - 1] > array[k] ) {
            b = 0;

            if ( a == 0 ) {
                return 0;
            }
        }
    }

    return a | b;
}
















































// Analysis
//
// The function determines whether an array is sorted
// in either nondecreasing or nonincreasing order.
//
// The possible return values are:
//
//     0   The array is neither nonincreasing nor
//         nondecreasing.
//
//     1   The array is nonincreasing:
//
//             array[0] >= array[1] >= ...
//
//         and at least one adjacent pair is strictly
//         decreasing.
//
//     2   The array is nondecreasing:
//
//             array[0] <= array[1] <= ...
//
//         and at least one adjacent pair is strictly
//         increasing.
//
//     3   The array is both nonincreasing and
//         nondecreasing.
//
//         This can occur only when all entries are
//         equal, or when the array has fewer than
//         two entries.
//
//
// What do 'a' and 'b' represent?
//
// Initially,
//
//     a = 1;
//     b = 2;
//
// Think of these as two possibilities that have not
// yet been ruled out.
//
//     a == 1
//
// means that the array may still be nonincreasing.
//
//     b == 2
//
// means that the array may still be nondecreasing.
//
// As the function examines adjacent pairs, it may
// discover evidence that rules out one of these
// possibilities.
//
//
// Consider:
//
//     if ( array[k - 1] < array[k] ) {
//         a = 0;
//         ...
//     }
//
// If an entry is greater than its predecessor, the
// array cannot be nonincreasing.
//
// For example:
//
//     {8.0, 6.0, 7.0}
//
// cannot be nonincreasing because
//
//     6.0 < 7.0.
//
// Consequently, 'a' is assigned 0.
//
//
// Similarly:
//
//     if ( array[k - 1] > array[k] ) {
//         b = 0;
//         ...
//     }
//
// If an entry is less than its predecessor, the
// array cannot be nondecreasing.
//
// For example:
//
//     {1.0, 4.0, 3.0}
//
// cannot be nondecreasing because
//
//     4.0 > 3.0.
//
// Consequently, 'b' is assigned 0.
//
//
// Why are equal adjacent entries ignored?
//
// If
//
//     array[k - 1] == array[k],
//
// then the pair is consistent with both nonincreasing
// and nondecreasing order.
//
// For example:
//
//     {1.0, 1.0, 2.0, 2.0}
//
// is nondecreasing, while
//
//     {3.0, 3.0, 2.0, 2.0}
//
// is nonincreasing.
//
// Thus, equality does not rule out either possibility.
//
//
// Why are there two early returns?
//
// Consider:
//
//     if ( array[k - 1] < array[k] ) {
//         a = 0;
//
//         if ( b == 0 ) {
//             return 0;
//         }
//     }
//
// The current pair has demonstrated that the array
// cannot be nonincreasing.
//
// If b is already zero, an earlier pair demonstrated
// that the array cannot be nondecreasing either.
//
// Thus:
//
//     a == 0
//     b == 0
//
// means that both possible orderings have been ruled
// out.
//
// No entries examined later can undo what has already
// been observed.
//
// Consequently, the final answer must be 0, and there
// is no reason to continue examining the array.
//
//
// The other early return handles the reverse situation:
//
//     if ( array[k - 1] > array[k] ) {
//         b = 0;
//
//         if ( a == 0 ) {
//             return 0;
//         }
//     }
//
// Here the current pair rules out nondecreasing order.
// If nonincreasing order was already ruled out, the
// function can again immediately return 0.
//
//
// Why does the function use
//
//     return a | b;
//
// ?
//
// The values 1 and 2 have different bits set:
//
//     1 = 01
//     2 = 10
//
// The bitwise OR therefore gives:
//
//     0 | 0 = 0
//     1 | 0 = 1
//     0 | 2 = 2
//     1 | 2 = 3
//
// Thus, the two variables encode two independent
// properties.
//
// If both possibilities survive, the function returns
//
//     1 | 2 == 3.
//
// If only the nonincreasing possibility survives,
// the function returns
//
//     1 | 0 == 1.
//
// If only the nondecreasing possibility survives,
// the function returns
//
//     0 | 2 == 2.
//
// If neither survives, the function returns 0.
//
//
// Examples:
//
//     {1.0, 2.0, 3.0}
//
// returns 2 because the array is nondecreasing.
//
//
//     {3.0, 2.0, 1.0}
//
// returns 1 because the array is nonincreasing.
//
//
//     {2.0, 2.0, 2.0}
//
// returns 3 because the array is both nondecreasing
// and nonincreasing.
//
//
//     {1.0, 3.0, 2.0}
//
// returns 0.
//
// The pair
//
//     1.0, 3.0
//
// rules out nonincreasing order.
//
// The pair
//
//     3.0, 2.0
//
// then rules out nondecreasing order.
//
// At this point the function can immediately return 0.
//
//
// What happens with an empty array?
//
// If capacity is zero, the loop is never entered.
//
// Thus,
//
//     a == 1
//     b == 2
//
// and the function returns
//
//     1 | 2 == 3.
//
// This makes sense. An empty array contains no pair
// of entries that violates either ordering.
//
//
// What happens with one entry?
//
// Again, there are no adjacent pairs to compare.
//
// The function returns 3.
//
// A one-element array is both nonincreasing and
// nondecreasing.
//
//
// Appropriate documentation for the function:
//
// unsigned int is_sorted( ... )
//
// @param array
//     An array of doubles to be examined.
//
// @param capacity
//     The number of entries in the array.
//
// @returns
//
//     0 if the array is neither nonincreasing nor
//       nondecreasing;
//
//     1 if the array is nonincreasing but not
//       nondecreasing;
//
//     2 if the array is nondecreasing but not
//       nonincreasing;
//
//     3 if the array is both nonincreasing and
//       nondecreasing.
//
// @algorithm
//
//     Examine each pair of adjacent entries.
//
//     If an increasing pair is encountered, the
//     possibility that the entire array is
//     nonincreasing is eliminated.
//
//     If a decreasing pair is encountered, the
//     possibility that the entire array is
//     nondecreasing is eliminated.
//
//     If both possibilities have been eliminated,
//     return 0 immediately.
//
//     Otherwise, return a bit mask indicating which
//     possibilities remain.
//
//
// Runtime analysis
//
// As with the previous is_sorted(...) function, we
// can ask how the amount of work grows as the array
// becomes larger.
//
// Let the capacity of the array be n.
//
//
// Questions:
//
// 1. What is the maximum number of adjacent pairs
//    that may have to be examined?
//
// 2. Give an example of an array for which the
//    function must examine every adjacent pair.
//
// 3. What is the smallest number of adjacent pairs
//    that must be examined before the function can
//    return 0?
//
// 4. Give an example for which the function returns
//    0 after examining only two adjacent pairs.
//
// 5. Can the function ever return 1, 2, or 3 without
//    examining every adjacent pair?
//
// 6. What is the best-case asymptotic runtime?
//
// 7. What is the worst-case asymptotic runtime?
//
//
//
// Answers:
//
// 1. An array containing n entries has n - 1
//    adjacent pairs, provided n is greater than zero.
//
//    Thus, at most n - 1 pairs must be examined.
//
//
// 2. Any array that is entirely nondecreasing,
//    entirely nonincreasing, or constant requires
//    every adjacent pair to be examined.
//
//    For example:
//
//        {1.0, 2.0, 3.0, 4.0}
//
//    requires all three adjacent pairs to be examined.
//
//
// 3. At least two adjacent pairs must be examined.
//
//    One pair must rule out one ordering, and another
//    pair must rule out the other ordering.
//
//
// 4. For example:
//
//        {1.0, 3.0, 2.0, 8.0, 9.0, 10.0}
//
//    The first comparison
//
//        1.0 < 3.0
//
//    sets a to zero.
//
//    The second comparison
//
//        3.0 > 2.0
//
//    sets b to zero.
//
//    The function can then return 0 without examining
//    the remainder of the array.
//
//
// 5. No.
//
//    To return 1, 2, or 3, the function must establish
//    that at least one ordering remains possible.
//
//    An unexamined adjacent pair could still contradict
//    that ordering.
//
//    Consequently, every adjacent pair must be examined
//    before returning 1, 2, or 3.
//
//
// 6. For sufficiently large arrays, the function can
//    return 0 after examining only two adjacent pairs.
//
//    The amount of work in this best case therefore
//    does not grow with n.
//
//    The best-case runtime is
//
//        O(1).
//
//
// 7. In the worst case, the function examines all
//    n - 1 adjacent pairs.
//
//    The amount of work therefore grows linearly
//    with the capacity of the array.
//
//    The worst-case runtime is
//
//        O(n).
//
//
// An interesting comparison with the previous
// is_sorted(...) function:
//
// The previous function could return early as soon
// as it found one decreasing adjacent pair.
//
// This function cannot necessarily return at that
// point.
//
// Finding one decreasing pair tells us only that the
// array is not nondecreasing. It may still be entirely
// nonincreasing.
//
// Similarly, finding one increasing pair tells us only
// that the array is not nonincreasing.
//
// To return 0 early, this function must find evidence
// of both:
//
//     at least one increasing adjacent pair,
//
// and
//
//     at least one decreasing adjacent pair.
//
// Despite this additional work, its worst-case
// asymptotic runtime is still O(n).
//
// This illustrates an important point about asymptotic
// runtime:
//
// Two algorithms can perform different amounts of work
// and still have the same asymptotic runtime.
//
// What matters for Big O is how the amount of work
// grows as the size of the input grows.