#include <iostream>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <cstddef>
#include <vector>

/*************************************************************
 * PARTITIONING AN ARRAY INTO DECADES
 *
 * Given an array of numbers in [0, 100], rearrange its
 * entries into ten consecutive partitions:
 *
 *   [0, 10), [10, 20), ..., [80, 90), [90, 100].
 *
 * The order of entries within a partition does not matter.
 * Store the boundaries in bounds[0] through bounds[10],
 * so that partition idx occupies the half-open interval
 *
 *   [bounds[idx], bounds[idx + 1]).
 *
 * In particular, bounds[0] == 0 and bounds[10] == capacity.
 * An empty partition has equal starting and ending bounds.
 *
 * Implement decade_partition() using one of three approaches:
 *
 * 1. Scan the original array once for each decade, copying
 *    matching entries into a temporary array.
 *
 * 2. Avoid the temporary array by swapping matching entries
 *    into the next available position of each partition.
 *
 * 3. Count the entries in each decade, convert the counts
 *    into starting positions, and distribute the entries
 *    into a temporary array in a single pass.
 *
 * Start with the first approach. The later approaches
 * reduce either the auxiliary storage or the number of scans.
 *************************************************************/

// Function declarations
void decade_partition( double            array[],
                       std::size_t       bounds[11],
                       std::size_t const capacity );
std::size_t to_index( double const x );
int main();

// Function definitions
int main() {
    std::size_t const N{ 30 };
    double data[N]{
        39.5718, 19.3139,  2.2424, 80.0187, 42.7552,
        84.2622, 41.2286, 99.6417, 38.6408, 69.4607,
        77.3013, 73.0616, 10.6507, 39.6412, 94.4913,
        21.0936, 75.0072, 45.4744, 73.6602, 32.9844,
        61.5732, 84.7018, 47.1077, 99.9999, 39.2554,
        83.6404, 47.4259, 22.4085,  7.8606, 72.0683
    };

    std::size_t bounds[11]{};
    decade_partition( data, bounds, N );

    // These checks are useful once you have implemented
    // decade_partition(). They deliberately fail for the
    // unfinished skeleton below.
    assert( bounds[0] == 0 );
    assert( bounds[10] == N );

    std::cout << "The order within each partition doesn't matter."
              << std::endl;

    for ( std::size_t idx{ 0 }; idx < 10; ++idx ) {
        assert( bounds[idx] <= bounds[idx + 1] );
        assert( bounds[idx + 1] <= N );

        for ( std::size_t k{ bounds[idx] };
              k < bounds[idx + 1]; ++k ) {
            assert( to_index( data[k] ) == idx );
            std::cout << data[k] << " ";
        }

        std::cout << std::endl;
    }

    return 0;
}

void decade_partition( double            array[],
                       std::size_t       bounds[11],
                       std::size_t const capacity ) {
    assert( array != nullptr || capacity == 0 );
    assert( bounds != nullptr );

    for ( std::size_t idx{ 0 }; idx <= 10; ++idx ) {
        bounds[idx] = 0;
    }

    // Enter your implementation here.
    // Set bounds[10] to capacity when you are finished.
}

// Return the decade to which x belongs.
// The value 100.0 belongs to decade 9.
std::size_t to_index( double const x ) {
    assert( std::isfinite( x ) );
    assert( 0.0 <= x && x <= 100.0 );

    if ( x == 100.0 ) {
        return 9;
    }

    return static_cast<std::size_t>( std::floor( x/10.0 ) );
}

/*************************************************************
 * HINTS
 *
 * APPROACH 1: COPY INTO A NEW ARRAY
 *
 * Keep a variable next_index, initially zero. For each
 * decade idx, first record bounds[idx] = next_index.
 * Scan the entire original array and copy each entry in
 * decade idx to partition[next_index], incrementing
 * next_index after each copy.
 *
 * After processing all ten decades, what must next_index
 * equal? Copy the temporary array back to the original.
 *
 * APPROACH 2: SWAP IN PLACE
 *
 * Use the same outer loop over the decades, but instead
 * of copying into a temporary array, swap a matching
 * entry into array[next_index].
 *
 * IMPORTANT: Begin the inner scan at next_index, not zero.
 * Everything before next_index is already in its final
 * partition and must not be disturbed.
 *
 * Why can the entry displaced by the swap be ignored for
 * the current decade? What happens when k == next_index?
 *
 * APPROACH 3: COUNT, THEN DISTRIBUTE
 *
 * Count how many entries belong to each decade.
 * Convert these counts into cumulative starting positions:
 *
 *   counts:  {2, 3, 0, 1, ...}
 *   bounds:  {0, 2, 5, 5, 6, ...}
 *
 * Copy bounds[0] through bounds[9] into a separate
 * next_index array. For each original entry x, calculate
 * idx = to_index(x), then place x at
 * partition[next_index[idx]] and increment that index.
 *
 * Keeping bounds separate from next_index means the
 * original boundaries do not need to be reconstructed.
 *************************************************************/

/*
 * MORE DETAILED FRAMEWORKS
 *
 * Replace the active decade_partition() with ONE of the
 * following versions when working on that approach.
 *
 * Approach 1:
 *
 * void decade_partition( double array[],
 *                        std::size_t bounds[11],
 *                        std::size_t capacity ) {
 *     std::vector<double> partition( capacity );
 *     std::size_t next_index{ 0 };
 *
 *     for ( std::size_t idx{ 0 }; idx < 10; ++idx ) {
 *         bounds[idx] = next_index;
 *
 *         for ( std::size_t k{ 0 }; k < capacity; ++k ) {
 *             if ( ... ) {
 *                 // Copy and increment next_index.
 *             }
 *         }
 *     }
 *
 *     // Set bounds[10] and copy the entries back.
 * }
 *
 * Approach 2:
 *
 *     for each decade idx:
 *         bounds[idx] = next_index;
 *         for k from next_index to capacity - 1:
 *             if to_index(array[k]) == idx:
 *                 swap array[k] and array[next_index];
 *                 increment next_index;
 *
 * Approach 3:
 *
 *     count each decade;
 *     build cumulative boundaries;
 *     initialize next_index from bounds;
 *     distribute each entry into a temporary array;
 *     copy the temporary array back.
 */

/*************************************************************
 * SOLUTIONS
 *
 * Each implementation below is complete. To try one,
 * replace the active decade_partition() above with that
 * implementation. Do not compile more than one definition
 * of decade_partition() at the same time.
 *************************************************************/

/*
// SOLUTION 1: TEN SCANS AND A TEMPORARY ARRAY
// Time: O(10 * capacity). Extra space: O(capacity).
void decade_partition( double            array[],
                       std::size_t       bounds[11],
                       std::size_t const capacity ) {
    assert( array != nullptr || capacity == 0 );
    assert( bounds != nullptr );

    std::vector<double> partition( capacity );
    std::size_t next_index{ 0 };

    for ( std::size_t idx{ 0 }; idx < 10; ++idx ) {
        bounds[idx] = next_index;

        for ( std::size_t k{ 0 }; k < capacity; ++k ) {
            if ( to_index( array[k] ) == idx ) {
                partition[next_index] = array[k];
                ++next_index;
            }
        }
    }

    assert( next_index == capacity );
    bounds[10] = capacity;

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        array[k] = partition[k];
    }
}
*/

/*
// SOLUTION 2: TEN SCANS, USING SWAPS IN PLACE
// Time: O(10 * capacity). Extra space: O(1).
void decade_partition( double            array[],
                       std::size_t       bounds[11],
                       std::size_t const capacity ) {
    assert( array != nullptr || capacity == 0 );
    assert( bounds != nullptr );

    std::size_t next_index{ 0 };

    for ( std::size_t idx{ 0 }; idx < 10; ++idx ) {
        bounds[idx] = next_index;

        for ( std::size_t k{ next_index }; k < capacity; ++k ) {
            if ( to_index( array[k] ) == idx ) {
                std::swap( array[next_index], array[k] );
                ++next_index;
            }
        }
    }

    assert( next_index == capacity );
    bounds[10] = capacity;
}
*/

/*
// SOLUTION 3: COUNTING AND CUMULATIVE BOUNDARIES
// Time: O(capacity + 10). Extra space: O(capacity).
void decade_partition( double            array[],
                       std::size_t       bounds[11],
                       std::size_t const capacity ) {
    assert( array != nullptr || capacity == 0 );
    assert( bounds != nullptr );

    std::size_t counts[10]{};

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        ++counts[to_index( array[k] )];
    }

    bounds[0] = 0;

    for ( std::size_t idx{ 0 }; idx < 10; ++idx ) {
        bounds[idx + 1] = bounds[idx] + counts[idx];
    }

    assert( bounds[10] == capacity );

    std::size_t next_index[10]{};

    for ( std::size_t idx{ 0 }; idx < 10; ++idx ) {
        next_index[idx] = bounds[idx];
    }

    std::vector<double> partition( capacity );

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        std::size_t const idx{ to_index( array[k] ) };
        assert( next_index[idx] < bounds[idx + 1] );
        partition[next_index[idx]] = array[k];
        ++next_index[idx];
    }

    for ( std::size_t idx{ 0 }; idx < 10; ++idx ) {
        assert( next_index[idx] == bounds[idx + 1] );
    }

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        array[k] = partition[k];
    }
}
*/