#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>
#include "numbers.h"
#include "bintree.h"

unsigned int seed = 0;

unsigned int *numbers;

// TODO: getDuplicate und createNumbers implementieren
/*  *   * Erzeugen eines Arrays mit der vom Nutzer eingegebenen Anzahl an Zufallszahlen.
 * Sicherstellen, dass beim Befüllen keine Duplikate entstehen.
 * Duplizieren eines zufälligen Eintrags im Array.
 * in `getDuplicate()`: Sortieren des Arrays und Erkennen der doppelten Zahl durch Vergleich benachbarter Elemente. */

// Returns len random numbers between 1 and 2x len in random order which are all different, except for two entries.
// Returns NULL on errors. Use your implementation of the binary search tree to check for possible duplicates while
// creating random numbers.

unsigned int setSeed(unsigned int seed_test)
{
  seed = seed_test;
  return seed;
}

void create_unique_random_numbers(unsigned int len, unsigned int numbers[])
{
  for (unsigned int i = 0; i < len; i++)
  {
    unsigned int same = 0;

    do
    {
      unsigned int value = 0;
      value = (rand() % (len * 2) + 1);

      same = 0;

      for (unsigned int j = 0; j < i; j++)
      {
        if (numbers[j] == value)
        {
          same = 1;
          break;
        }
      }

      if (same == 0)
      {
        numbers[i] = value;
      }

    } while (same == 1);
  }
}

unsigned int *createNumbers(unsigned int len)
{

  if (len <= 2)
  {
    return numbers;
  }

  if (seed == 0)
  {
    srand(time(NULL));
  }
  else
  {
    srand(seed);
  }

  numbers = malloc(sizeof(unsigned int) * len);

  if (numbers != NULL)
  {
    create_unique_random_numbers(len, numbers);

    unsigned int i = 0;
    unsigned int j = 0;

    do
    {
      i = 0;
      j = 0;

      i = rand() % len;
      j = rand() % len;

    } while (i == j || i == j + 1 || i == j - 1);

    numbers[i] = numbers[j];
  }

  return numbers;
}

/*
void sortnumbers(unsigned int numbers[], unsigned int len) //-> qsort
{
  for (unsigned int j = 0; j < len - 1; j++)
  {
    for (unsigned int i = 0; i < len - 1 - j; i++)
    {
      unsigned int temp = 0;
      if (numbers[i] > numbers[i + 1])
      {
        temp = numbers[i];
        numbers[i] = numbers[i + 1];
        numbers[i + 1] = temp;
      }
    }
  }
}
*/

int compare(const void *arg1, const void *arg2)
{
  unsigned int a = *(const unsigned int *)arg1;
  unsigned int b = *(const unsigned int *)arg2;

  return ((a > b) - (a < b));
}

// Returns only the only number in numbers which is present twice. Returns zero on errors.
unsigned int getDuplicate(const unsigned int numbers[], unsigned int len)
{
  if (len <= 2)
  {
    return 0;
  }

  unsigned int *copynumbers = malloc(sizeof(unsigned int) * len);

  if (copynumbers == NULL)
  {
    return 0;
  }

  for (unsigned int i = 0; i < len; i++)
  {
    copynumbers[i] = numbers[i];
  }

  qsort(copynumbers, len, sizeof(unsigned int), compare);

  // sortnumbers(copynumbers, len);

  for (unsigned i = 0; i < len - 1; i++)
  {
    if (copynumbers[i] == copynumbers[i + 1])
    {
      unsigned int a = copynumbers[i];
      free(copynumbers);
      return a;
    }
  }

  free(copynumbers);

  return 0;
}