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

//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.

int compare(const void* a, const void* b) {
   return (*(unsigned int*)a - *(unsigned int*)b);
}

unsigned int *createNumbers(unsigned int len)
{
  //array erstellen
  if(len < 2)
    return NULL;

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

  //sicherstellen dass zahlen einmalig vorkommen
  srand(time(NULL));
  for(int i = 0; i < len; i++){
    while(1){  
      unsigned int value = (rand() % (2 * len)) + 1;  
      int alreadyUsed = 0;
      for(int j = 0; j < i; j++) {
        if(arr[j] == value) {
          alreadyUsed = 1;      
          break;              
        }
      }
      if(!alreadyUsed) {
        arr[i] = value;         
        break;                   
      }
    }
  }

  //eine zahl duplizieren und irgendwo hinkopieren
  int dupIndex = rand() % len;
  int targetIndex;
  do{
    targetIndex = rand() % len;
  }while (targetIndex == dupIndex);  
  arr[targetIndex] = arr[dupIndex];

  return arr;
}

// 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 *copy = malloc(sizeof(unsigned int)*len);

  memcpy(copy, numbers, len * sizeof(unsigned int));

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

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