#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <boost/thread/thread.hpp>
#include <iomanip>

using namespace std;

unsigned int tab_size;

//======= NAGLOWKI ============

int DEBUG = 0;
const int maxw = 100;
const int minw = 0;
int * tab;
int * temptab;
int * tab2;
int pocz1=0, sr1=0, kon1=tab_size-1;
bool useboost = 1;

void prepare();
void wypisz(int* tablica);
void clear_temp();

inline void merge(int pocz, int sr, int kon);
inline void mergesort(int pocz, int kon);
void odpalanie_watkow();


inline void bmerge(int pocz, int sr, int kon);
inline void bmergesort(int pocz, int kon);
void wat1();
void wat2();
boost::thread w1;
boost::thread w2;

//=============================

int main(){
time_t czas1, czas2;
cout<<"DEBUG MODE [0/1/2]: "<<endl;
cin >> DEBUG;
cout<<"Rozmiar tablicy: "<<endl;
cin >> tab_size;
tab = new int[tab_size];
temptab = new int[tab_size];
tab2 = new int[tab_size];

prepare();

if(DEBUG == 1){
cout<<"Tablica przed posortowaniem: "<<endl;
wypisz(tab);
}

//=========== wersja sekwencyjna
czas1 = clock();
mergesort(0, tab_size-1);
czas2 = clock();
double czas = double(czas2-czas1)/CLOCKS_PER_SEC;
cout<<"Czas sortowania tablicy sekwencyjnie: "<<setprecision(6)<<czas<<" s."<<endl;
//==============================

if(DEBUG == 1){
cout<<"Tablica posortowana: "<<endl;
wypisz(tab);
}





if(DEBUG == 1 || DEBUG == 2){
cout<<"Tablica przed posortowaniem: "<<endl;
wypisz(tab2);
}

//=========== wersja watkowa
czas1 = clock();
//bmergesort(0, tab_size-1);
odpalanie_watkow();
czas2 = clock();
czas = double(czas2-czas1)/CLOCKS_PER_SEC;
cout<<"Czas sortowania tablicy w 2 watkach: "<<czas<<" s."<<endl;
//==============================

if(DEBUG == 1 || DEBUG == 2){
cout<<"Tablica posortowana: "<<endl;
wypisz(tab2);
}


delete tab;
delete temptab;
delete tab2;
}


void prepare(){

srand((unsigned int)time(NULL));
//zapelnianie tablicy losowymi liczbami z pewnego zakresu
for (unsigned int i=0; i<tab_size; i++){
tab[i] = rand()%(maxw-minw+1)+minw;
tab2[i] = tab[i];
}
}

void wypisz(int* tablica){

for (unsigned int i=0; i<tab_size; i++){
cout<<tablica[i]<<", ";
}
cout<<endl<<endl;
}

void merge(int pocz, int sr, int kon)
{
  int i,j,q;
  for (i=pocz; i<=kon; i++) temptab[i]=tab[i];  // Skopiowanie danych do tablicy pomocniczej
  i=pocz; j=sr+1; q=pocz;                 
  while (i<=sr && j<=kon) {
    if (temptab[i]<temptab[j])
        tab[q++]=temptab[i++];
    else
        tab[q++]=temptab[j++];
  }
  while (i<=sr) tab[q++]=temptab[i++];
}


void mergesort(int pocz, int kon)
{
  int sr;
  if (pocz<kon) {
    sr=(pocz+kon)/2;
    mergesort(pocz, sr);    // Dzielenie lewej czesci
    mergesort(sr+1, kon);   // Dzielenie prawej czesci
    merge(pocz, sr, kon);   // laczenie czesci lewej i prawej
  }
}


//========================================
//   FUNKCJE DOTYCZACE WATKOW
//========================================

void bmerge(int pocz, int sr, int kon)
{
  int i,j,q;
  for (i=pocz; i<=kon; i++) temptab[i]=tab2[i];  // Skopiowanie danych do tablicy pomocniczej
  i=pocz; j=sr+1; q=pocz;                 
  while (i<=sr && j<=kon) {
    if (temptab[i]<temptab[j])
        tab2[q++]=temptab[i++];
    else
        tab2[q++]=temptab[j++];
  }
  while (i<=sr) tab2[q++]=temptab[i++];
}


void bmergesort(int pocz, int kon)
{
  if (pocz<kon) {
	int sr=(pocz+kon)/2;
	bmergesort(pocz, sr);    // Dzielenie lewej czesci
	bmergesort(sr+1, kon);   // Dzielenie prawej czesci
	bmerge(pocz, sr, kon);   // laczenie czesci lewej i prawej
	}


}    
void odpalanie_watkow() {
  
    sr1 = (tab_size-1)/2;
    pocz1 = 0;
	kon1 = tab_size-1;
	boost::thread w1(&wat1);
	boost::thread w2(&wat2);

    bmerge(pocz1, sr1, kon1); 
    w1.join();
    w2.join();
 }    
  


void wat1(){
bmergesort(pocz1, sr1);
}

void wat2(){
bmergesort(sr1+1, kon1); 
}