#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define __USE_BSD
#include <string.h>

#include "global.h"
#include "darray.h"
#include "sorting.h"

// Can be redefined if Value_Type changes
int compare(Value_Type a, Value_Type b){
  return strcmp(a,b);
}


struct darray* initialize_set (int size)
{

  struct darray* arr = malloc(sizeof(struct darray));
  check(arr);
  arr->cells = (Value_Type*) (malloc(sizeof(Value_Type)*size));
  check(arr->cells);
  arr->capacity = size;
  arr->size = 0;
  arr->sorted = false;
  arr->resizes = 0;
  return arr;
}

void tidy(struct darray* arr)
{
  if(arr){
    // free memory created by strdup
    for(unsigned i=0; i<arr->size;i++){ free(arr->cells[i]); }
    // free array and struct
    free(arr->cells);
    free(arr);
  }
}

int size(struct darray* arr){ return arr->size; }

struct darray* insert (Value_Type value, struct darray* arr)
{
  // If we have reached capacity, double size and copy
  if(arr->size >= arr->capacity){
    struct darray* new_arr = initialize_set(arr->capacity*2);
    for(unsigned int i=0;i<arr->size;i++){
      new_arr->cells[i] = arr->cells[i];
    }
    new_arr->size = arr->size;
    new_arr->resizes = arr->resizes+1;
    free(arr->cells);
    free(arr);
    arr = new_arr;
  }

  arr->cells[arr->size] = strdup(value);
  arr->size++;

  // changing the array means it may no longer be sorted
  arr->sorted = false;

  return arr;
}

bool find (Value_Type value, struct darray* arr)
{
  if(mode == LINEAR_SEARCH){
    unsigned int i = 0;
    bool Found = false;
    // loop over every element in the darray
    // untill the value is found or is hits the end
    while((i<arr->size) && (!Found)) {
      if(compare(value, arr->cells[i]) == 0){ Found = true; }
      i++;
    }
    return Found;
  }
  else{ // Binary Search
    if(!arr->sorted){
      if(verbose > 2){
        printf("Dynamic Array not sorted, sorting...\n");
      }
      sort(arr,mode);
      if(verbose > 2){
        printf("Dynamic Array sorted\n");
      }
      arr->sorted = true;
    }
  // call the binary search function
  return binarySearch(value, arr, 0, arr->size-1);
  }
}

bool binarySearch (Value_Type value, struct darray* arr, int low, int high)
{
  int mid = ((high+low)/2);
  //printf("LOW: %d\nMID: %d\nHIGH: %d\n", low, mid, high); // delete
  // if low is greater than high, then the element hasnt been found
  if (low>high){ return false; }
  // if the value is less than the middle value,
  // binary seach the lower half of the darray
  else if (compare(value, arr->cells[mid]) < 0) {
    return binarySearch(value, arr, low, mid-1);
  }
  // if the value is greater than the middle value,
  // binary seach the upper half of the darray
  else if (compare(value, arr->cells[mid]) > 0) {
    return binarySearch(value, arr, mid+1, high);
  }
  // this mean that value is equal to the middle value
  else { return true; }
}

// You can make any changes you want to this function
void print_set (struct darray* arr)
{
  printf("DArray:\n");
  for(unsigned i=0;i<arr->size;i++){
    printf("\t%s\n",arr->cells[i]);
  }
}

// You can make any changes you want to this function
void print_stats (struct darray* arr)
{
  printf("Dynamic array of capacity %d contains %d elements\n",arr->capacity,arr->size);
  printf("Dynamic array was resized %d times\n",arr->resizes);
}