// parallel sort.cpp : definisce il punto di ingresso dell'applicazione console.
//

#include "stdafx.h"

template <class B,class T >
B  Add(T a, T b) //C++ function template sample
{
	
	return  a+b ;
}
template <class T>
void stampa (T i) {
  cout << " " << i;
}

void aspetta(){	char cc;
cout << endl << " inserisci un carattere per proseguire " << endl;
	cin >> cc;}

int _tmain(int argc, _TCHAR* argv[])
{
	
	{  // Primo esempio di uso dei template
	float a,b,c;
	
	a=0.3;
	b=1.8;
	c=Add<double>((int)a,(int)b);
	cout << Add<float,int>(a,b)<< " " ; //Risultato float, argomenti int
	cout<< Add<int,float>(a,b) <<" " ; // Risultato int somma float.
	cout<< " c= " << c << endl; // Risultato float somma float
	//cout << Add(a,b) << endl;
	//aspetta();
	//return 0;
	}
	
	{
	vector<int> a,b,c;

	for(unsigned int i=0;i<11;i+=2) a.push_back(i);
	for(unsigned int i=1;i<11;i+=2) a.push_back(i);
	for(unsigned int i=0;i<a.size();i++) cout<< a[i]<< " ";
	cout << endl << " Size: "<< a.size() << endl ;
	//aspetta();
	cout<<a.empty()<<endl;
	a.clear(); // Svuota a ;
	cout<<a.empty()<< " Svuotato  "<<a.capacity()<<endl;
	for(unsigned int i=0;i<11;i+=2) a.push_back(i);
	for( int i=11;i>0;i-=2) b.push_back(i);
	
	for(unsigned int i=0;i<a.size();i++) cout<< a[i]<< " ";
	cout << endl << "Vettore B: " ;
    for_each (b.begin(), b.end(), stampa<int>);

	cout << endl ;
	//aspetta();
	c.resize(2*a.size());
	sort(b.begin(),b.end());
	for_each (b.begin(), b.end(), stampa<int>);
	cout << endl ;
	merge(a.begin(),a.end(),b.begin(),b.end(),c.begin());
	for_each (c.begin(), c.end(), stampa<int>);
		cout << endl ;
//aspetta();
//	return 0;
	}
	vector<int> a,b,c;
	a.clear();
	b.clear();
	c.clear();
#define PROB_SIZE 120000000
	for(unsigned int i=0;i<PROB_SIZE;i++) b.push_back(rand() % 100 + 1);	
	
	double start_t=omp_get_wtime();
	sort(b.begin(),b.end());
	double end_t=omp_get_wtime();
	cout << " Tempo Scalare : "<< end_t-start_t <<endl;
	a.clear();
	for(unsigned int i=0;i<PROB_SIZE;i++) a.push_back(rand() % 100 + 1);	
c.resize(a.size());
//	for_each (a.begin(), a.begin()+12, stampa<int>);
	cout << endl;
start_t=omp_get_wtime();
int NPROCS=omp_get_num_procs();

omp_set_num_threads(4); // OCCHIO così comè questo programma funziona con solo con 4 threads
vector<vector<int>::iterator> start(NPROCS),end(NPROCS);
#pragma omp parallel 
{
int NTH=omp_get_num_threads();
int asize=a.size()/NTH;
int TID=omp_get_thread_num();

start[TID]=a.begin()+(TID*asize);
end[TID]=a.begin()+((TID+1)*asize);

sort(start[TID],end[TID]);

/*
#pragma omp critical 
cout << " Sort Eseguito : "<< TID<< endl;
{

for_each (start[TID], end[TID], stampa<int>);
cout<<endl;
}*/
#pragma omp barrier
if (TID%(NTH/2)==0)
{
	merge(start[TID],end[TID],start[TID+1],end[TID+1],c.begin()+asize*TID);
}
}
int asize=a.size()/2;
vector<int>::iterator source_start=c.begin(),source_start2=c.begin()+asize;
merge(source_start,source_start2,source_start2,c.end(),a.begin());
end_t=omp_get_wtime();
cout << "Tempo parallelo: "<< end_t-start_t << endl;
for_each (a.begin(), a.begin()+12, stampa<int>);
/*
#pragma omp sections
	{
		
#pragma omp section
		sort(a.begin(),a.begin()+asize);

#pragma omp section
		sort(a.begin()+asize+1,a.end());
	}
merge(a.begin(),a.begin()+asize,a.begin()+asize+1,a.end(),c.begin());
for_each (c.begin(), c.begin()+10, stampa<int>);*/
//for_each (a.begin(), a.begin()+12, stampa<int>);
aspetta();
return 0;

}