#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

class ItemT {
    public:
        ItemT() = default;
        ItemT(int keyValue, char value) : item{value}, key{keyValue} {};
        ItemT(const ItemT & other): item{other.item}, key{other.key} { };

        char Data(void) const {
           return item;
        }

        int Key(void) const {
            return key;
        }

        bool operator <(const ItemT  & other) const {
           return key < other.key;
        }

        bool operator >(const ItemT  & other) const {
           return key > other.key;
        }

    private:
       char item{'X'};
       int key{0};
};

using ItemLT = vector<ItemT>;

ostream & operator << (ostream  & s, const ItemT & data) ;
void PrintItems(const ItemLT & ary);
ItemLT CountSort(const ItemLT & ary);

int main() {
     ItemLT ary;

     srand(time(nullptr));
     char letter{'a'};

     for(int i = 0; i < 20; ++i) {
         ItemT newItem(rand()%10 + 5,  letter++);
         ary.push_back(newItem);
     }

     PrintItems(ary);
     cout << endl;

     ItemLT sorted = CountSort(ary);

     cout << endl;
     PrintItems(sorted);

}

ostream & operator << (ostream  & s, const ItemT & data) {
    s  << setw(2) << data.Key() << ":" << data.Data();
    return s;
}

void PrintItems(const ItemLT & ary){
    int items{0};
    for(auto i: ary) {
        cout << i;
        if (items >= 9) {
           cout << endl;
           items = -1;
        }  else {
           cout << ", "; }

        ++items;
    }
    cout << endl;
}

ItemLT CountSort(const ItemLT & ary){
    ItemLT result(ary.size());

    auto big = *max_element(begin(ary), end(ary));
    auto small = *min_element(begin(ary), end(ary));

    cout << "Big = " << big << endl;
    cout << "Small = " << small << endl;
    cout << "The difference is " << big.Key()-small.Key() << endl;

    vector<int> counts(big.Key() - small.Key()+ 1);

    for(size_t i =0; i < ary.size(); ++i) {
       size_t pos =  ary[i].Key() - small.Key();
       ++counts[pos];
    }

    cout << "The count table:  " << endl;
    for(size_t i = 0; i < counts.size(); ++i) {
       cout <<"\t" << i + small.Key()  << " " << counts[i] << endl;
    }

    for(size_t i = 1; i < counts.size(); ++i) {
       counts[i] += counts[i-1];
    }

    cout << "The count table:  " << endl;
    for(size_t i = 0; i < counts.size(); ++i) {
       cout <<"\t" << i + small.Key()  << " " << counts[i] << endl;
    }

    for(int i = ary.size()-1; i >= 0; --i) {
       int pos = ary[i].Key() - small.Key() ;
       result[counts[pos]-1] = ary[i];
       --counts[pos];
    }

    return result;
}