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

// Strictly increasing arrays
//
// An array is sorted in nondecreasing order if
// each entry is greater than or equal to the
// previous entry.
//
// For example:
//
//     {1.0, 2.0, 2.0, 4.0}
//
// is sorted in nondecreasing order.
//
// An array is sorted in strictly increasing order
// if each entry is greater than the previous entry.
//
// For example:
//
//     {1.0, 2.0, 3.0, 4.0}
//
// is strictly increasing, whereas
//
//     {1.0, 2.0, 2.0, 4.0}
//
// is not.
//
// Update the is_sorted(...) function to take a third
// argument, strictly_increasing.
//
// If strictly_increasing is false, equal adjacent
// entries are permitted.
//
// If strictly_increasing is true, every entry after
// the first must be strictly greater than its
// predecessor.
//
// The function should return:
//
//   - capacity if the array satisfies the requested
//     ordering;
//
//   - otherwise, the first index at which the
//     requested ordering is violated.
//
// Give strictly_increasing a default value of false
// so that
//
//     is_sorted( array, capacity )
//
// continues to check whether the array is sorted in
// nondecreasing order.
//
// Test your function.

// Function declarations
std::size_t is_sorted(
    double      const array[],
    std::size_t const capacity,
    bool        const strictly_increasing = false
);

int main();

// Function definitions
int main() {
    std::cout << "Starting testing"
              << std::endl;

    double data1[2]{
        6.0, 6.0
    };

    // Equal adjacent entries are permitted if
    // strict ordering is not required.

    assert( is_sorted( data1, 2, false ) == 2 );

    // If strict ordering is required, the second
    // entry violates the required ordering.

    assert( is_sorted( data1, 2, true ) == 1 );

    double data2[5]{
        1.0, 2.0, 3.0, 4.0, 5.0
    };

    assert( is_sorted( data2, 5, false ) == 5 );
    assert( is_sorted( data2, 5, true ) == 5 );

    double data3[5]{
        1.0, 2.0, 2.0, 4.0, 5.0
    };

    assert( is_sorted( data3, 5, false ) == 5 );
    assert( is_sorted( data3, 5, true ) == 2 );

    double data4[5]{
        1.0, 2.0, 4.0, 3.0, 5.0
    };

    assert( is_sorted( data4, 5, false ) == 3 );
    assert( is_sorted( data4, 5, true ) == 3 );

    // Arrays containing zero or one entry satisfy
    // both definitions.

    assert( is_sorted( nullptr, 0, false ) == 0 );
    assert( is_sorted( nullptr, 0, true ) == 0 );

    double data5[1]{
        42.0
    };

    assert( is_sorted( data5, 1, false ) == 1 );
    assert( is_sorted( data5, 1, true ) == 1 );

    // The default argument is false.

    assert( is_sorted( data1, 2 ) == 2 );

    std::cout << "Finished testing"
              << std::endl;

    return 0;
}

// Your implementation:

std::size_t is_sorted(
    double      const array[],
    std::size_t const capacity,
    bool        const strictly_increasing
) {
    // Your implementation here
}




















































// Here is one possible solution.
//
// This implementation checks the Boolean flag
// during each iteration of the loop.

/*
std::size_t is_sorted(
    double      const array[],
    std::size_t const capacity,
    bool        const strictly_increasing
) {
    for ( std::size_t k{ 1 };
          k < capacity;
          ++k ) {
        if ( array[k] < array[k - 1] ) {
            return k;
        } else if ( strictly_increasing
                 && (array[k] == array[k - 1]) ) {
            return k;
        }
    }

    return capacity;
}
*/

// We could also combine the two conditions:
//
//     if ( (array[k] < array[k - 1])
//       || (strictly_increasing
//           && (array[k] == array[k - 1])) ) {
//         return k;
//     }
//
// The first form may be easier to read because it
// separates the two reasons the ordering may fail:
//
//   1. The next entry is smaller.
//
//   2. The entries are equal when strict ordering
//      has been requested.
//
//
//
// Here is another solution.
//
// This implementation checks the Boolean flag only
// once and then selects the appropriate loop.

/*
std::size_t is_sorted(
    double      const array[],
    std::size_t const capacity,
    bool        const strictly_increasing
) {
    if ( strictly_increasing ) {
        for ( std::size_t k{ 1 };
              k < capacity;
              ++k ) {
            if ( array[k] <= array[k - 1] ) {
                return k;
            }
        }
    } else {
        for ( std::size_t k{ 1 };
              k < capacity;
              ++k ) {
            if ( array[k] < array[k - 1] ) {
                return k;
            }
        }
    }

    return capacity;
}
*/

// Notice the difference between the comparisons.
//
// For nondecreasing order, a violation occurs when
//
//     array[k] < array[k - 1].
//
// Equality is permitted.
//
// For strictly increasing order, a violation occurs
// when
//
//     array[k] <= array[k - 1].
//
// Equality is now a violation.
//
//
//
// Runtime analysis
//
// The two implementations look different.
//
// In the first implementation, the expression
//
//     strictly_increasing
//
// may be examined during every iteration.
//
// In the second implementation, the expression
//
//     strictly_increasing
//
// is examined only once, before either loop begins.
//
// Does this mean that the second implementation has
// a better asymptotic runtime?
//
//
// Questions:
//
// 1. Suppose the array contains n entries and satisfies
//    the requested ordering. How many adjacent pairs
//    must be examined?
//
// 2. In the first implementation, how many times might
//    strictly_increasing be examined?
//
// 3. In the second implementation, how many times is
//    strictly_increasing examined?
//
// 4. Does this difference change the worst-case
//    asymptotic runtime?
//
// 5. What is the best-case runtime for an array with
//    at least two entries?
//
// 6. What is the worst-case runtime?
//
// 7. If one implementation performs fewer operations,
//    can it still have the same asymptotic runtime as
//    another implementation?
//
//
//
// Answers:
//
// 1. An array containing n entries has n - 1 adjacent
//    pairs.
//
//    If the array satisfies the requested ordering,
//    every adjacent pair must be examined.
//
//
// 2. In the first implementation, strictly_increasing
//    may be examined during each of the n - 1
//    iterations.
//
//    Note that because && uses short-circuit
//    evaluation, it is examined only if
//
//        array[k] == array[k - 1]
//
//    is relevant to the test as written above.
//
//    Nevertheless, in an array containing many equal
//    adjacent entries, the flag may be checked many
//    times.
//
//
// 3. In the second implementation, strictly_increasing
//    is examined only once.
//
//    After that decision has been made, the appropriate
//    loop is executed.
//
//
// 4. No.
//
//    The first implementation may perform some
//    additional constant amount of work during each
//    iteration, but both implementations examine at
//    most n - 1 adjacent pairs.
//
//    Consequently, the amount of work in both
//    implementations grows linearly with n.
//
//    Both therefore have worst-case runtime
//
//        O(n).
//
//
// 5. If the first adjacent pair violates the requested
//    ordering, the function returns after examining
//    only one pair.
//
//    For arrays containing at least two entries, the
//    best-case runtime is therefore
//
//        O(1).
//
//
// 6. If the array satisfies the requested ordering,
//    or if the first violation occurs at the final
//    pair, all n - 1 adjacent pairs must be examined.
//
//    The worst-case runtime is therefore
//
//        O(n).
//
//
// 7. Yes.
//
//    Suppose one implementation requires approximately
//
//        2n
//
//    operations while another requires approximately
//
//        4n.
//
//    The second implementation performs approximately
//    twice as much work, but both amounts of work grow
//    in direct proportion to n.
//
//    Both therefore have linear runtime:
//
//        O(n).
//
//
// This illustrates an important feature of asymptotic
// analysis:
//
// Big O notation does not attempt to count every
// individual operation.
//
// Instead, it describes how the amount of work grows
// as the size of the input grows.
//
// Thus, checking the flag once rather than during the
// loop may make one implementation somewhat more
// efficient, but it does not change the fact that
// both algorithms have linear worst-case runtime.
//
//
//
// One final question:
//
// Suppose an array contains one million entries.
//
// If it satisfies the requested ordering, either
// implementation must examine 999999 adjacent pairs.
//
// Could any algorithm determine that an arbitrary
// array is sorted without, in the worst case,
// examining every adjacent pair?
//
// Consider what could happen if even one pair were
// never examined.