#include <math.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define TRUE 1
#define FALSE 0

int *array_ptr;
pthread_barrier_t barrier;

typedef struct {
  int thread_id;
  int *arr;
  int size;
  int n_threads;
} thread_args;

void generateArray(int *array, int size) {
  for (int i = 0; i < size; ++i) {
    array[i] = rand() % 1000;
  }
}

int verify(int *array, int size) {
  for (int i = 0; i < size - 1; ++i) {
    if (array[i] > array[i + 1]) {
      return FALSE;
    }
  }
  return TRUE;
}

void printArray(int *arr, int n) {
  for (int i = 0; i < n; ++i) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

void *parallel_bubble_sort(void *arg) {
  thread_args *args = (thread_args *)arg;
  int tid = args->thread_id;
  int *arr = args->arr;
  int n = args->size;
  int n_threads = args->n_threads;

  for (int step = 0; step < n; ++step) {
    int start = (step % 2 == 0) ? 0 : 1;
    for (int i = start + 2 * tid; i < n - 1; i += 2 * n_threads) {
      if (arr[i] > arr[i + 1]) {
        int tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
      }
    }
    pthread_barrier_wait(&barrier);
  }

  return NULL;
}

// Argument parsing utility
int get_named_arg(int argc, char *argv[], const char *name) {
  for (int i = 1; i < argc - 1; ++i) {
    if (strcmp(argv[i], name) == 0) {
      return atoi(argv[i + 1]);
    }
  }
  return -1;
}

int main(int argc, char *argv[]) {
  int power = get_named_arg(argc, argv, "--size");
  int n_threads = get_named_arg(argc, argv, "--threads");

  if (power < 1 || n_threads < 1) {
    fprintf(stderr, "Usage: %s --threads <num> --size <log10(size)>\n",
            argv[0]);
    return EXIT_FAILURE;
  }

  int n = (int)pow(10, power);

  array_ptr = (int *)malloc(n * sizeof(int));
  if (!array_ptr) {
    perror("malloc");
    return EXIT_FAILURE;
  }

  pthread_t *threads = malloc(n_threads * sizeof(pthread_t));
  thread_args *args = malloc(n_threads * sizeof(thread_args));
  if (!threads || !args) {
    perror("malloc");
    return EXIT_FAILURE;
  }

  generateArray(array_ptr, n);
  pthread_barrier_init(&barrier, NULL, n_threads);

  for (int i = 0; i < n_threads; ++i) {
    args[i].thread_id = i;
    args[i].arr = array_ptr;
    args[i].size = n;
    args[i].n_threads = n_threads;
    pthread_create(&threads[i], NULL, parallel_bubble_sort, &args[i]);
  }

  for (int i = 0; i < n_threads; ++i) {
    pthread_join(threads[i], NULL);
  }

  pthread_barrier_destroy(&barrier);

  // Uncomment to see result
  // printArray(array_ptr, n);

  /*
  if (verify(array_ptr, n))
    printf("\nArray is sorted.\n");
  else
    printf("\nArray is NOT sorted.\n");
  */

  free(array_ptr);
  free(threads);
  free(args);

  return 0;
}