#include "pch.h"

#include <iostream>
#include <algorithm>
#include<stdlib.h>
#include <time.h>
#include <mpi.h>
#include <cmath>

#define MASTER 0
using namespace std;
void bubblesort(int *v, int n);
int *merge(int* v1, int n1, int* v2, int n2);

int main(int argc, char **argv) {
	//zainicjalizuj środowisko MPI,
	MPI_Init(&argc, &argv);
	//przypisz zmiennej n ilosc elementow sortowanej tablicy
	int n = 10;
	//zadeklaruj wskaźnik służący do odwoływania się do tablicy liczb całkowitych
	int *a = new int[n];
	int rank, size, length;
	int kawalki;
	int *data = NULL;
	int buforN;
	int *bufor = NULL;
	int *kawalki_wys = NULL;
	char hostname[MPI_MAX_PROCESSOR_NAME];
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	MPI_Get_processor_name(hostname, &length);
	//jesli nr procesu = 0 (master)
	if (rank == MASTER) {
		srand(time(NULL));
		//dzielenie tablicy rownomiernie na czesci pomiedzy procesy
		kawalki = n / size;
		if (n%size != 0) {//jzaokraglenie do gory reszty z dzielenia
			kawalki++;
		}
		cout << "Kawalki: " << kawalki << endl;

		data = new int[size * kawalki];
		cout << "Tablica wyjsciowa " << endl;

		for (int i = 0; i < n; i++) {
			data[i] = rand() % 1000;
			cout << data[i] << endl;
		}
		//wypełnianie reszty ostatniego kawałka zerami
		for (int i = n; i < size*kawalki; i++) {
			data[i] = 0;
		}
	}

	MPI_Barrier(MPI_COMM_WORLD);//jak wszystkie procesy zakoncza swoje dzialanie dopiero mozna ruszyc dalej
	double timestart = MPI_Wtime();

	MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

	kawalki = n / size;
	if (n%size != 0) {
		kawalki++;
	}
	bufor = new int[kawalki];

	MPI_Scatter(data, kawalki, MPI_INT, bufor, kawalki, MPI_INT, 0, MPI_COMM_WORLD);
	delete[] data;
	data = NULL;

	if (size - 1 != rank) {
		buforN = kawalki;
	}
	else {
		buforN = n - kawalki * rank;
	}

	bubblesort(bufor, buforN);
	// w tym momencie KAŻDY PROCES POSIADA POSORTOWANY SWÓJ KAWAŁEK TABLICY
	int krok;
	int s_wys;
	for (krok = 1; krok < size; krok = krok * 2) { //tu wejdzie 1 3 5
		if ((rank % (2 * krok)) != 0) {
			MPI_Send(bufor, buforN, MPI_INT, rank - krok, 0, MPI_COMM_WORLD);
			break;
		}
		if (rank + krok < size) {
			if (n >= kawalki * (rank + 2 * krok)) { //czy to dziala i dlczego czy id+krok
				s_wys = kawalki * krok;
			}
			else {
				s_wys = n - (kawalki*(rank + krok));
			}
			kawalki_wys = new int[s_wys];
			MPI_Status status;
			MPI_Recv(kawalki_wys, s_wys, MPI_INT, rank + krok, 0, MPI_COMM_WORLD, &status);
			data = merge(bufor, buforN, kawalki_wys, s_wys);
			delete[] bufor;
			delete[] kawalki_wys;
			bufor = data;
			buforN = buforN + s_wys;
		}
	}

	if (rank == MASTER) {
		cout << "\nTablica posortowana o wielkosci " << buforN << endl;
		for (int i = 0; i < buforN; i++) {
			cout << bufor[i] << endl;
		}
		cout << "\nLiczba procesow: " << size << endl;
		cout << "Czas: " << MPI_Wtime() - timestart << endl;
	}

	MPI_Finalize();
	return 0;
}

void bubblesort(int *v, int n) {
	for (int i = n - 2; i >= 0; i--)
		for (int j = 0; j <= i; j++)
			if (v[j] > v[j + 1]) {
				swap(v[j], v[j + 1]);
			}
}

int* merge(int* v1, int n1, int* v2, int n2) {
	int *merged = new int[n1 + n2];

	int i = 0;
	int j = 0;
	int k;

	for (k = 0; k < n1 + n2; k++) {
		if (i >= n1) {
			merged[k] = v2[j];
			j++;
		}
		else if (j >= n2) {
			merged[k] = v2[i];
			i++;
		}
		else if (v1[i] < v2[j]) {
			merged[k] = v1[i];
			i++;
		}
		else {
			merged[k] = v2[j];
			j++;
		}
	}

	return merged;
}