par.cpp

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

#include <thread>
#include "utimer.cpp"

using namespace std;

#define vk vector
#define pb push_back

typedef vk<int> vi;
typedef pair<int, int> pii;
typedef vk<pii> vii;

const int ARG_COUNT = 3;
const int MINN = -1e5;
const int MAXX = 1e5 + 10;


/// mt19937 random number generator
int rand_generator(int mn, int mx) {
    thread_local random_device rd;
    thread_local mt19937 rng(rd());
    thread_local uniform_int_distribution<int> uid;
    return uid(rng, decltype(uid)::param_type {mn,mx});
}

/// generate random vector
vi rand_vec(int N, int nw) {
    vk<thread> threads(nw);	// threads vector
    vi randArr(N);	// to save generated rand values for each thread
    int chunk = N / nw;

    // utimer *timer_rand = new utimer("Generate Rand Vec");
    for (int th = 0; th < nw; th++) {
        // thread (function, parameters)
        threads[th] = thread([&](const int si, const int ei) {
            // loop over all items
            for (int i = si; i < ei; i++)
                randArr[i] = rand_generator(MINN, MAXX);
        },
        th * chunk,
        th == (nw - 1) ? N : (th + 1) * chunk);
    }

    for_each(threads.begin(), threads.end(), [](thread & th) {
        th.join();
    });
    // timer_rand->~utimer();

    return randArr;
}

/// print vector
void print_vec(vi &vec) {
    cout << "\n";
    for (auto x: vec)
        cout << x << "\t";
    cout << "\n\n";
}

/// make ranges for threads
vii make_ranges(int N, int nw, int nt) {
    // number taks, number workers, type number - [0 - even, 1 - odd]
    vi idxList;
    for(int i = 0; i < N; i++)
        if(i%2 == nt)   idxList.pb(i);
    
    int sz = int(idxList.size());
    int chunk = sz / nw;
    int mod = sz % nw;

    int idx = 0;
    vii retList(nw);
    for(int th = 0; th < nw; th++) {
        int st = idx;
        int ei = idx + chunk - 1 + (mod-- > 0);
        retList[th] = make_pair(idxList[st], idxList[ei]);
        idx = ei + 1;
    }
    return retList;
}

/// Odd-Even Sort
void OddEvenSort(vi &Arr, int nw) {
    //
    int N = Arr.size();
    vi startIndex = {0, 1};	// 0 - Even, 1 - Odd
    // Even Index starts from 0, Odd Index starts from 1.
    // Both will increase by 2 in each step.

    vk<thread> threads(nw);	// threads vector

    vii ranges_even = make_ranges(N, nw, 0);
    vii ranges_odd = make_ranges(N, nw, 1);

    utimer *timer = new utimer("Parallel Code");
    while (!is_sorted(Arr.begin(), Arr.end())) {
        for (int th = 0; th < nw; th++) {
            threads[th] = thread([&](const int si, const int ei) {
                // loop over all items
                for (int i = si; i <= ei; i += 2) {
                    if (Arr[i] > Arr[i + 1])
                        swap(Arr[i], Arr[i + 1]);
                }
            }, ranges_even[th].first, ranges_even[th].second);
        }
        for_each(threads.begin(), threads.end(), [](thread & th) {
            th.join();
        });
        for (int th = 0; th < nw; th++) {
            threads[th] = thread([&](const int si, const int ei) {
                // loop over all items
                for (int i = si; i <= ei; i += 2) {
                    if (Arr[i] > Arr[i + 1])
                        swap(Arr[i], Arr[i + 1]);
                }
            }, ranges_odd[th].first, ranges_odd[th].second);
        }
        for_each(threads.begin(), threads.end(), [](thread & th) {
            th.join();
        });
    }
    timer->~utimer();
}

int main(int argc, char *argv[]) {
    // read inputs
    if (argc != ARG_COUNT) {
        cout << "Input Error. Number of argument is wrong..\n";
        exit(0);
    }

    int N = atoi(argv[1]);
    int nw = atoi(argv[2]);

    // input validation
    if (N < 1 || nw == 0) {
        cout << "Invalid Input..\n";
        exit(0);
    }

    // genereate random vector
    vi Arr = rand_vec(N, nw);
    // print_vec(Arr);

    // Run OddEvenSort
    OddEvenSort(Arr, nw);

    // Print Sorted Vector
    // print_vec(Arr);

    return 0;
}