#include "mpi.h"
#include <stdio.h>
#include <string.h>

//bestimmt den Index des Exchange-Nachbarn
int getNextEX(int me){
		return me^1; // letztes Bit invertiert
	}
	

//bestimmt den Index des Shuffle-Nachbarn
int getNextSH(int me, int size){
		int temp = me <<1;
		if(temp >= size) {
			temp = temp ^ size; // oberstes Bit abschneiden- muss ja ==1 sein!
			temp = temp ^ 1; // unterstes Bit - muss ja null sein - auf 1 setzen
		}
		return temp;
	}

int main(int argc, char *argv[]) {
  int rank;
  int size;
  int counter;
  int* a; // array fuer die ganze Liste (Start)
  int actLength ;
  MPI_Status status;
  int blockSize;
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  if (argc > 1){
        blockSize = atoi(argv[1]);}
  else{
        blockSize = 2;}
  actLength = blockSize*size;
  fprintf(stdout, "size: %d\n", size);
  a = (int*) malloc(blockSize*size*sizeof(int)); 
  // Speicher reservieren. 2: 2 Datenelemente soll jeder Prozess haben am Ende

  fprintf(stdout, "ich bin: %d\n", rank);

  if (rank ==0) {
	// a mit daten Fuellen:
	counter =0;
  	for (counter=0; counter < (blockSize *size); counter++){
		a[counter] = counter; // testdaten
  	}
  }
  
  else {
    //Alle ausser P0 empfangen
    MPI_Recv(a, actLength , MPI_INT, 
	     MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
    actLength=status.MPI_TAG;
    if (status.MPI_SOURCE!=getNextEX(rank)) {
      //Nachricht kam von Shufflepartner
      //sende 2. Haelfte an Exchangepartner
      actLength/=2;
      MPI_Send(a+(actLength) , actLength , MPI_INT, 
	       getNextEX(rank), actLength, MPI_COMM_WORLD);
    }
  }
  while (actLength>blockSize){
    //sende Shuffle
    MPI_Send (a, actLength, MPI_INT, 
	      getNextSH(rank, size), actLength, MPI_COMM_WORLD);
    if (rank%2==0){
      //empfange Shuffle
      MPI_Recv(a, actLength , MPI_INT, MPI_ANY_SOURCE, 
	       MPI_ANY_TAG, MPI_COMM_WORLD, &status);
      actLength/=2;
      //sende exchange
      MPI_Send(a+actLength , actLength , MPI_INT, 
	       getNextEX(rank), actLength, MPI_COMM_WORLD);
    }
    else {
      //empfange exchange
      actLength/=2;
      MPI_Recv(a, actLength , MPI_INT, 
	       MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
    }
  }
  fprintf(stdout, "Prozess:%d: habe meine Daten! ",rank);
  for (counter = 0; counter < blockSize;counter++){
    fprintf (stdout,"%d, ",a[counter]);}
  fprintf (stdout,"\n");
  free(a);
  MPI_Finalize();
}