/*
 *      masterslave.cpp
 *
 * This implementation of the Master-Slave pattern creates 3 different sort-algorithms
 * and gives them the same vector for sorting. The first algorithm to finish will call
 * the response method of the Master.
 * This implementation is an example for the use of the Master-Slave pattern for 
 * redundance and accelerating the computation. 
 */

#include "masterslave.h"

using namespace std;

void MyThread::run() //simply call the sort method of the slave
{
    slave->doSort();
}
void BubbleSort::doSort()
{
    int temp;
    bool sorted=true;
    do
    {
        sorted=true;
        for (uint i = 0; i < v.size()-1; ++i)
        {
            if (v.at(i)>v.at(i+1))
            {
                sorted=false;
                temp = v.at(i);
                v[i]=v[i+1];
                v[i+1]=temp;
            }
        }
    }
    while (!sorted);
    m->response("BubbleSort ");
    for ( int i = 0; i<v.size(); ++i )
    {
    //    cout << v.at(i) << " ";
    }
cout << endl;
}

void Quicksort::doSort()
{
    quicksort(0,v.size()-1);
    m->response("QuickSort ");
    for ( int i = 0; i<v.size(); ++i )
    {
      //  cout << v.at(i) << " ";
    }
cout << endl;
}

void Quicksort::quicksort(int anfang, int ende)
{
    if (anfang<ende)
    {
        int pivot =split(anfang, ende);
        quicksort(anfang,pivot-1);
        quicksort(pivot+1,ende);
    }
}

int Quicksort::split(int anfang, int ende)
{
    int i=anfang;
    int j= ende-1;
    int x = v.at(ende);
    do
    {
        while (v.at(i)<=x && i<ende)
        {
            i++;
        };
        while (v.at(j)>=x && j>anfang)
        {
            j--;
        };
        if (i<j)
        {
            int temp=v.at(i);
            v[i]=v.at(j);
            v[j]=temp;
            j--;
        }
    }
    while (i<j);
    if (v.at(i)>x)
    {
        int temp=v.at(i);
        v[i]=v.at(ende);
        v[ende]=temp;
    };
    return i;
}

void MergeSort::doSort()
{
    vector<int> vec = mergesort(v);
    m->response("MergeSort ");
    for ( int i = 0; i<vec.size(); ++i )
    {
     //   cout << vec.at(i) << " ";
    }
cout << endl;
}

vector<int> MergeSort::mergesort(vector<int> _vector)
{
    if (_vector.size()<2)
    {
        return _vector;
    }
    else
    {
        vector<int> links;
        vector<int> rechts;
	uint i=0;
        for (; i < _vector.size()/2;++i)
        {
		links.push_back(_vector.at(i));
        }
        for (; i < _vector.size();++i)
        {
            rechts.push_back(_vector.at(i));
        }
        return merge(mergesort(links), mergesort(rechts));
    }
}

vector<int> MergeSort::merge(vector<int> va, vector<int> vb)
{
    vector<int> newVector;
    vector<int>::iterator it1 = va.begin();
    vector<int>::iterator it2=vb.begin();
    for ( ; it1 != va.end() && it2 !=vb.end();)
    {
        if ((*it1)<=(*it2))
        {
            newVector.push_back(*it1);
	    it1++;
        }
        else if (*it1>*it2)
        {
            newVector.push_back(*it2);
            it2++;
        }
    }
    while (it1!=va.end())
    {
        newVector.push_back(*it1);
        it1++;
    };
    while (it2!=vb.end())
    {
        newVector.push_back(*it2);
        it2++;
    };
    return newVector;
}

/*
master method called by client
creates slaves and threads and waits till the first thread returns a result by calling the
response method of the master
note: QThreads do not wait-if one returns a result, all other threads are killed automatically
*/
void Master::sortArray(vector<int> vec) 
{
    Quicksort *qsort = new Quicksort(vec, this);
    slaves.push_back(qsort);
    BubbleSort *bsort = new BubbleSort(vec, this);
    slaves.push_back(bsort);
    MergeSort *msort = new MergeSort(vec, this);
    slaves.push_back(msort);
    vector<Slave*>::iterator it1 =slaves.begin();
    for(;it1!=slaves.end();it1++){
    MyThread* thread = new MyThread(*it1);
	thread->start(); 
    }
}
/* simple implementation, only to show which slave
 * was the fastest
 */
void Master::response(string text){
	cout <<endl<< text <<" was fastest algorithm" ;
}
int main(int argc, char** argv)
{
    vector<int> startV;
    vector<int> preSorted;
    for (int j = 0; j<10000; j++){
    	preSorted.push_back(j);
    }	
    cout <<"Startsequenz: ";
    for ( int i = 0; i < 10000; ++i )
    {
        int num = (int) rand() % 10000;
        cout << num << " ";
        startV.push_back( num );
    }

    Master *m = new Master();
    m->sortArray(startV); //quicksort should be fastest
   // m->sortArray(preSorted); //bubblesort should win
    return 0;
}
