/********************************************************************
  Author:        Dana Vrajitoru, IUSB, CS
  Class:         B424 B524 Parallel Programming
  File name:     process.cc
  Last updated:  November 2020
  Description:   A program that generates an ideal playlist. 
                 Functions for the master and worker processes.
*********************************************************************/

#include <iostream>
using namespace std;
#include <mpi.h>
#include "process.h"

// Creates a custom MPI data type to be able to send and receive the
// struct Song and commits it so that we can use it.
void create_data_type(MPI_Datatype &dt_song)
{
    int          blocklengths[6] = {1, 1, 1, 1, 1, 1};
    MPI_Datatype types[6] = {MPI_INT, MPI_INT, MPI_INT, MPI_INT, 
                             MPI_FLOAT, MPI_FLOAT};
    MPI_Aint     offsets[6];

    offsets[0] = offsetof(Song, title1);
    offsets[1] = offsetof(Song, title2);
    offsets[2] = offsetof(Song, title3);
    offsets[3] = offsetof(Song, title4);
    offsets[4] = offsetof(Song, att1);
    offsets[5] = offsetof(Song, att2);

    MPI_Type_create_struct(6, blocklengths, offsets, types, &dt_song);
    MPI_Type_commit(&dt_song);
}

// Master function. Generates the songs, send the information to the
// workers, generates its own subset of permutations and finds the
// optimal one, then collects the results from the workers.
void Master(int nr_proc)
{
    MPI_Datatype mpi_song;
    int nr_songs;
    Song *songs;
    int *perm, *min_shuffle;
    float min_dist = -1;
    
    create_data_type(mpi_song);

    nr_songs = nr_proc;
    songs = new Song[nr_songs];
    perm = new int[nr_songs];
    min_shuffle = new int[nr_songs];
    generate_songs(songs, nr_songs);

    MPI_Bcast(&nr_songs, 1, MPI_INT, 0, MPI_COMM_WORLD);
    MPI_Bcast(songs, nr_songs, mpi_song, 0, MPI_COMM_WORLD);

    first_permutation(perm, nr_songs, 0);
    cout << "Original list of songs: ";
    output_songs(perm, songs, nr_songs);
    // Comment this out after you compute the minimum permutation
    // properly and receive it from all the workers or leave it as an
    // initialization for this permutation.
    first_permutation(min_shuffle, nr_songs, 0);

    // move this after collect results
    output_permutation(min_shuffle, nr_songs);

    // showing how next permutation works
    //next_permutation(min_shuffle, nr_songs);
    //output_permutation(min_shuffle, nr_songs);

    min_dist = generate_permutations(perm, min_shuffle, songs, nr_songs);
    collect_results(min_shuffle, min_dist, nr_songs, nr_proc);
    output_songs(min_shuffle, songs, nr_songs);

    // free the data type once we're done using it. 
    MPI_Type_free(&mpi_song);
}

// Worker function. It should first call the function creating the data
// structure that can be used to receive data of type Song. Then it
// should receive the number of songs and the array of songs from the
// master. Then it should generate the initial permutation based on
// the id. Then it should call the function generate_permutations in a
// similar way to the master. At the end it should send the minimal
// shuffle to the master.
void Worker(int id) 
{
    // To be implemented by the student
}

// Function generating the next permutation in lexicographic order.
void next_permutation(int a[], int n) 
{
    int i, j, k, m;
    for (k = n-2; k >= 0; k--) 
        if (a[k] < a[k+1]) 
            break;
    if (k >= 0) {
        for (m = n-1; a[m] < a[k]; m--);
        swap(a[k], a[m]);
    }
    for(i = k+1, j = n-1; i < j; i++, j--)
        swap(a[i], a[j]);
}

// Generates the initial permutation in the subgroup given by id.
void first_permutation(int a[], int n, int id) 
{
    int i;
    for (i = 0; i < n; i++)
        a[i] = i;
    int temp = a[id];
    for (i = id-1; i >= 0; i--)
        a[i+1] = a[i];
    a[0] = temp;
}

// Generates the last permutation, meaning an array sorted backwards.
void last_permutation(int a[], int n) 
{
    int i;
    for (i = 0; i < n; i++)
        a[i] = n-i-1;
}

// Copies the array b into the array a.
void copy_array(int a[], int b[], int n)
{
    for (int i = 0; i < n; i++)
        a[i] = b[i];
}

// Outputs the array.
void output_permutation(int a[], int n)
{
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
    cout << endl;
}

// Outputs the given shuffle as a list of songs
void output_songs(int shuffle[], Song *songs, int nr_songs)
{
    cout << "Here is the shuffle:" << endl;
    for (int i = 0; i < nr_songs; i++) 
        output_song(songs[shuffle[i]]);
}

// Generate all the permutations allocated to this process. The
// function should evaluate the distance in the starting permutation
// and store it in a local variable. Then it should generate new
// permutations until the first element (a[0]) has changed. For each
// of them, it should compare the sum of the distances between songs
// to the stored one, and if the new one is smaller, copy the
// permutation into the mina array. At the end it should also return
// the minimal distance.
float generate_permutations(int a[], int mina[], Song *songs, int n)
{
  // To be implemented by the student
}

// This function should receive the minimum permutation and the
// distance from each worker and compute the minimum of shuffle of all
// the received ones. A local array will be needed to receive the
// permutations.
void collect_results(int min_shuffle[], float &min_distance, int nr_songs, 
                     int nr_proc)
{
  // To be implemented by the student
}

// Computes the distance between songs in a playlist
float distance_songs(int *playlist, Song *songs, int nr_songs)
{
    // To be implemented by the student
    return 0;
}