/************************************************************/
// System includes

#include <iostream>
#include <stdio.h>
#include <locale.h>
#include <cstdlib>
#include <vector>
#include <string>
#include <random>
#include <algorithm>
#include <queue>
#include <array>

/************************************************************/
// Local includes

#include "Timer.hpp"
/************************************************************/
// Using declarations

using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::string;
using std::minstd_rand;
using std::swap;
using std::sort;
using std::queue;
using std::array;

/************************************************************/
// Function prototypes/global vars/typedefs

void
printIntro (size_t& numElem, int& digits);

void
printOutro (vector<int>& A, vector<int>& Acopy);

void
populateVector (vector<int>& A, size_t& numElem, int& digits);

void
radixSort (vector<int>& A, int& digitPos);

/*size_t
insertionSort (vector<int>& v);*/

/************************************************************/

int
main (int argc, char* argv[])
{
    vector<int> A;
    size_t numElem;
    int digits;
    int digitPos;

    Timer<> timer;
    Timer<> timer2;
    timer.start();
    printIntro (numElem, digits);
    populateVector (A, numElem, digits);
    vector<int> Acopy(A);
    cout << "\nAcopy: ";
    for (int val: Acopy)
    {
        cout << val << " | ";
    }
    timer2.start();
    sort (Acopy.begin(), Acopy.end());
    timer2.stop();
    cout << "\nSorted Acopy: ";
    for (int val: Acopy)
    {
        cout << val << " | ";
    }
    cout << endl;
    digitPos = 1;
    radixSort (A, digitPos);
    digitPos = 10;
    radixSort (A, digitPos);
    timer.stop();

    printOutro (A, Acopy);

    cout << "Radix time:     " << timer.getElapsedMs() << " ms" <<  endl;
    cout << "std::sort time: " << timer2.getElapsedMs() << " ms" <<  endl;


    return EXIT_SUCCESS;
}

/************************************************************/

void
printIntro (size_t& numElem, int& digits)
{
   cout << "N ==> ";
   cin >> numElem;
   numElem = numElem;


   cout << "d ==> ";
   cin >> digits;
   digits = digits;

   cout << endl;
}

/************************************************************/

void
printOutro (vector<int>& A, vector<int>& Acopy)
{
     if (A == Acopy)
    {
        cout << "success\n";
    }
    else
    {
        cout << "fail\n";
    }
}

/************************************************************/

// Takes the given inputs from the user, to fill vector 'v'.
// Then calls the selected sort using the filled vector.
void
populateVector (vector<int>& A, size_t& numElem, int& digits)
{
    minstd_rand gen;
    gen.seed(0);
    std::uniform_int_distribution<int> dist(0, pow(10, digits));
    //fill(A.begin(), A.end(), dist(gen));
    do {
        A.push_back(dist(gen));
    } while (A.size() != numElem) ;
    cout << endl;


}

/************************************************************/

// Takes the vector created by the users.
// Then runs the sort using an array of 10 queues.
void
radixSort (vector<int>& A, int& digitPos)
{
    int position;
    queue<int> holder[10];
    for(int val: A)
    {
        if(digitPos == 1)
            position = val % 10;

        if (digitPos == 10)
            position = (val / 10) % 10;

        holder[position].push(val);
        cout << "pushed: " << val << " onto queue\n";
    }

    int n = 0;
    cout << "A: ";
    for(int val: A)
    {
        cout << val << " | ";
    }
    cout << endl;
    A.clear();

    while(!holder[0].empty())
    {
        A.push_back(holder[0].front());
        cout << "pushed: " << holder[0].front() << endl;
        holder[0].pop();
        ++n;
    }
    while(!holder[1].empty())
    {
        A.push_back(holder[1].front());
        cout << "pushed: " << holder[1].front() << endl;
        holder[1].pop();
        ++n;
    }
    while(!holder[2].empty())
    {
        A.push_back(holder[2].front());
        cout << "pushed: " << holder[2].front() << endl;
        holder[2].pop();
        ++n;
    }
    while(!holder[3].empty())
    {
        A.push_back(holder[3].front());
        cout << "pushed: " << holder[3].front() << endl;
        holder[3].pop();
        ++n;
    }
    while(!holder[4].empty())
    {
        A.push_back(holder[4].front());
        cout << "pushed: " << holder[4].front() << endl;
        holder[4].pop();
        ++n;
    }
    while(!holder[5].empty())
    {
        A.push_back(holder[5].front());
        cout << "pushed: " << holder[5].front() << endl;
        holder[5].pop();
        ++n;
    }
    while(!holder[6].empty())
    {
        A.push_back(holder[6].front());
        cout << "pushed: " << holder[6].front() << endl;
        holder[6].pop();
        ++n;
    }
    while(!holder[7].empty())
    {
        A.push_back(holder[7].front());
        cout << "pushed: " << holder[7].front() << endl;
        holder[7].pop();
        ++n;
    }
    while(!holder[8].empty())
    {
        A.push_back(holder[8].front());
        cout << "pushed: " << holder[8].front() << endl;
        holder[8].pop();
        ++n;
    }
    while(!holder[9].empty())
    {
        A.push_back(holder[9].front());
        cout << "pushed: " << holder[9].front() << endl;
        holder[9].pop();
        ++n;
    }


    for (int val: A)
    {
        cout << val << " | ";
    }
    cout << endl;
}

/************************************************************/
/************************************************************/