#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <time.h>

void quicksort (int *A, int len);

#define MIN_LENGTH 4

int DEBUG;

typedef struct
{
  int *array;
  int left;
  int right;
  int tid;
} thread_data_t;

int number_of_threads;
pthread_mutex_t lock_number_of_threads;

int
my_comp (const void *larg, const void *rarg)
{
  int l = *(int *) larg;
  int r = *(int *) rarg;
  if (l < r)
    {
      return -1;
    }
  else if (l == r)
    {
      return 0;
    }
  return 1;
}

void
merge (int *data, int left, int right, int tid)
{
  if (DEBUG)
    {
      printf ("[%d] Merging %d to %d\n", tid, left, right);
    }
  int ctr = 0;
  int i = left;
  int mid = left + ((right - left) / 2);
  int j = mid + 1;
  int *c = (int *) malloc ((right - left + 1) * sizeof (int));
  while (i <= mid && j <= right)
    {
      if (data[i] <= data[j])
	{
	  c[ctr++] = data[i++];
	}
      else
	{
	  c[ctr++] = data[j++];
	}
    }
  if (i == mid + 1)
    {
      while (j <= right)
	{
	  c[ctr++] = data[j++];
	}
    }
  else
    {
      while (i <= mid)
	{
	  c[ctr++] = data[i++];
	}
    }
  i = left;
  ctr = 0;
  while (i <= right)
    {
      data[i++] = c[ctr++];
    }
  free (c);
  return;
}

void *
merge_sort_threaded (void *arg)
{
  thread_data_t *data = (thread_data_t *) arg;
  int l = data->left;
  int r = data->right;
  int t = data->tid;
  if (r - l + 1 <= MIN_LENGTH)
    {
      if (DEBUG)
	{
	  printf ("[%d] Calling qsort(%d, %d).\n", t, l, r);
	}
      qsort (data->array + l, r - l + 1, sizeof (int), my_comp);
    }
  else
    {
      int m = l + ((r - l) / 2);
      thread_data_t data_0;
      data_0.left = l;
      data_0.right = m;
      data_0.array = data->array;
      pthread_mutex_lock (&lock_number_of_threads);
      data_0.tid = number_of_threads++;
      pthread_mutex_unlock (&lock_number_of_threads);
      pthread_t thread0;
			       NULL,
			       merge_sort_threaded,
			       &data_0);
      if (rc)
	{
	  if (DEBUG)
	    {
		      data_0.tid);
	    }
	  qsort (data->array + l, m - l + 1, sizeof (int), my_comp);
	}
      thread_data_t data_1;
      data_1.left = m + 1;
      data_1.right = r;
      data_1.array = data->array;
      pthread_mutex_lock (&lock_number_of_threads);
      data_1.tid = number_of_threads++;
      pthread_mutex_unlock (&lock_number_of_threads);
      pthread_t thread1;
      if (rc)
	{
	  if (DEBUG)
	    {
		      data_1.tid);
	    }
	  qsort (data->array + m + 1, r - m, sizeof (int), my_comp);
	}
	{
	  pthread_join (thread0, NULL);
	}
	{
	  pthread_join (thread1, NULL);
	}
      merge (data->array, l, r, t);
    }
  pthread_exit (NULL);
  return NULL;
}

void
merge_sort (int *array, int start, int finish)
{
  thread_data_t data;
  data.array = array;
  data.left = start;
  data.right = finish;

  number_of_threads = 0;
  pthread_mutex_init (&lock_number_of_threads, NULL);
  data.tid = 0;
  pthread_t thread;
			   NULL,
			   merge_sort_threaded,
			   &data);
  if (rc)
    {
      if (DEBUG)
	{
	}
      qsort (array + start, finish - start + 1, sizeof (int), my_comp);
    }
  pthread_join (thread, NULL);
  return;
}




int
max (int *a, int n, int i, int j, int k)
{
  int m = i;
  if (j < n && a[j] > a[m])
    {
      m = j;
    }
  if (k < n && a[k] > a[m])
    {
      m = k;
    }
  return m;
}

void
downheap (int *a, int n, int i)
{
  while (1)
    {
      int j = max (a, n, i, 2 * i + 1, 2 * i + 2);
      if (j == i)
	{
	  break;
	}
      int t = a[i];
      a[i] = a[j];
      a[j] = t;
      i = j;
    }
}

void
heapsort (int *a, int n)
{
  int i;
  for (i = (n - 2) / 2; i >= 0; i--)
    {
      downheap (a, n, i);
    }
  for (i = 0; i < n; i++)
    {
      int t = a[n - i - 1];
      a[n - i - 1] = a[0];
      a[0] = t;
      downheap (a, n - i - 1, 0);
    }
}

void
quicksort (int *A, int len)
{
  if (len < 2)
    return;

  int pivot = A[len / 2];

  int i, j;
  for (i = 0, j = len - 1;; i++, j--)
    {
      while (A[i] < pivot)
	i++;
      while (A[j] > pivot)
	j--;

      if (i >= j)
	break;

      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }

  quicksort (A, i);
  quicksort (A + i, len - i);
}




int
main ()
{



  printf ("Select benchmark mode");
  printf ("\n(1) Multthread Mergesort (Using POPCNT)\n");
  printf ("(2) Singlethread Heapsort (Using BMI)\n");
  printf ("(3) Exit\n");

  int selval, mode;
  scanf ("%d", &selval);
  if (selval < 1 || selval > 3)
    {
      printf ("Invalid input.. aborting!");
      return 0;
    }
  mode = selval;
  printf ("\nSimple Heapsort benchmarking tool\n");
  printf ("\nCopyright (C) 2017  Fabian Druschke (Knogle)");
  printf
  printf
    ("\nThis is free software, and you are welcome to redistribute it \n \n \n");
	if (selval == 3)
    {
      return 1;
    }
  sleep (3);
  if (mode == 1)
    {
      int size = 100000000, loop, qrand;
      int *array;
      array = (int *) malloc (size * sizeof (int));
      if (array != NULL)
	{
	  if ((size * sizeof (int)) < 1000)
	    {
	      printf ("\n %lu Bytes allocated\n", (size * sizeof (int)));
	    }
	  else if ((size * sizeof (int)) >= 1000)
	    {
	      printf ("\n %lu Kilobytes allocated\n",
		      ((size * sizeof (int)) / 1000));
	    }
	  else if ((size * sizeof (int)) >= 1000 * 1000)
	    {
	      printf ("\n %lu Megabytes allocated\n",
		      ((size * sizeof (int)) / 1000 * 1000));
	    }
	  sleep (1);
	  printf ("\nFilling array.\n");
	  sleep (3);
	  srand ( time(NULL) );
	  for (loop = 0; loop < size; loop++)
	    {
	      qrand = rand () % 20;
	      array[loop] = qrand;
	      printf ("%d", qrand);
	    }
	}
      else
	printf ("\nKein freier Speicher vorhanden.\n");

      printf ("\nMerge Sort..\n");
      clock_t t;
      t = clock ();
      merge_sort (array, 0, size - 1);
      for (loop = 0; loop < size; loop++)
	{
	  printf ("%d", array[loop]);
	}
      if ((size * sizeof (int)) < 1000)
	{
	  printf ("\n %lu Bytes wurden freigegeben\n", (size * sizeof (int)));
	}
      else if ((size * sizeof (int)) >= 1000)
	{
	  printf ("\n %lu Kilobytes wurden freigegeben\n",
		  ((size * sizeof (int)) / 1000));
	}
      else if ((size * sizeof (int)) >= 1000 * 1000)
	{
	  printf ("\n %lu Megabytes wurden freigegeben\n",
		  ((size * sizeof (int)) / 1000 * 1000));
	}
      t = clock () - t;
      printf ("Sorting took %f seconds to finish \n", time_taken);
      double score = (sizeof (int) / time_taken);
      printf ("Your total score: %f", score * 1000);
      printf ("\nPress ENTER to exit");
      getchar ();
      pthread_mutex_destroy (&lock_number_of_threads);
      free (array);

    }
  if (mode == 2)
    {
      int size = 100000000, loop, qrand;
      int *array;
      array = (int *) malloc (size * sizeof (int));
      if (array != NULL)
	{
	  if ((size * sizeof (int)) < 1000)
	    {
	      printf ("\n %lu Bytes allocated\n", (size * sizeof (int)));
	    }
	  else if ((size * sizeof (int)) >= 1000)
	    {
	      printf ("\n %lu Kilobytes allocated\n",
		      ((size * sizeof (int)) / 1000));
	    }
	  else if ((size * sizeof (int)) >= 1000 * 1000)
	    {
	      printf ("\n %lu Megabytes allocated\n",
		      ((size * sizeof (int)) / 1000 * 1000));
	    }
	  sleep (1);
	  printf ("\nFilling array.\n");
	  sleep (3);
	  srand ( time(NULL) );
	  for (loop = 0; loop < size; loop++)
	    {
	      qrand = rand () % 20;
	      array[loop] = qrand;
	      printf ("%d", qrand);
	    }
	}
      else
	printf ("\nKein freier Speicher vorhanden.\n");
      printf ("\n\n");
      printf ("\nHeapsort..\n");
      sleep (3);
      clock_t t;
      t = clock ();
      heapsort (array, size);
      for (loop = 0; loop < size; loop++)
	{
	  printf ("%d", array[loop]);
	}
      if ((size * sizeof (int)) < 1000)
	{
	  printf ("\n %lu Bytes reallocated\n", (size * sizeof (int)));
	}
      else if ((size * sizeof (int)) >= 1000)
	{
	  printf ("\n %lu Kilobytes reallocated\n",
		  ((size * sizeof (int)) / 1000));
	}
      else if ((size * sizeof (int)) >= 1000 * 1000)
	{
	  printf ("\n %lu Megabytes reallocated\n",
		  ((size * sizeof (int)) / 1000 * 1000));
	}
      free (array);
      t = clock () - t;
      printf ("Sorting took %f seconds to finish \n", time_taken);
      double score = (sizeof (int) / time_taken);
      printf ("Your total score: %f", score * 1000);
      printf ("\nPress ENTER to exit");
      getchar();
    }

  return 0;
}