#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

/**
 * Compares the ints (given as pointers to them) and returns whether 
 * the first is smaller than , equal to, or greater than the second.
 *
 * @param s1 a pointer to an int, non-NULL
 * @param s2 a pointer to an int, non-NULL
 * @return a negative number of the first int is smaller than the second,
 * zero if they are equal, and a positive number if the first is larger
 */
int compare_ints(const void *s1, const void *s2);

/**
 * Compares two strings (given as pointers to pointers to their first
 * characters and returns whether)
 * the first is smaller than , equal to, or greater than the second.
 *
 * @param s1 a pointer to a pointer to a null-terminated char array, non-NULL
 * @param s2 a pointer to a pointer to a null-terminated char array, non-NULL
 * @return a negative number of the first string comes before the second,
 * zero if they are equal, and a positive number if the first comes after
 */
int compare_strings(const void *s1, const void *s2);

/**
 * Searches the given array using the given comparison function, returning
 * whether it was found and either the location where the item was found or
 * the index where it would be inserted.
 *
 * This function is polymorphic -- it will work with any type.
 * Because it works with any type, it accepts the array as a void *
 * so we can pass any pointer to it whether it is a pointer to the
 * first element of an array of ints, the pointer to the first element
 * of an array of struct points, or whatever.  Like most functions that
 * work with arrays, it needs to know how many elements are in the array.
 * In order to do the pointer arithmetic, it needs to know how many bytes
 * each element occupies.
 *
 * @param array a pointer, non-NULL
 * @param key a pointer, non-NULL
 * @param index a pointer to an int to store the index at which the key
 * was found or should be inserted (or -1 if an error); non-NULL
 * @param item_count a non-negative integer
 * @param item_size a positive integer
 * @param compare a pointer to a comparison function
 * @return true if the key was found, false otherwise
 */
bool binary_search(const void *array, const void *key, int *index, int item_count, int item_size, int (*compare)(const void *, const void *));

int main(int argc, char **argv)
{
  // copy command line arguments into an array, converting to ints as we go
  // we con't check for numeric input and we don't check order
  int input_b[argc - 1];
  for (int i = 1; i < argc; i++)
    {
      input_b[i - 1] = atoi(argv[i]);
    }

  // min and max to search for are just before and just after inputs
  int min, max;
  if (argc == 1)
    {
      min = max = 0;
    }
  else
    {
      min = input_b[0] - 1;
      max = input_b[argc - 2] + 1;
    }

  // search for every int between min and max and output result
  for (int i = min; i <= max; i++)
    {
      int index;
      if (binary_search(input_b, &i, &index, argc - 1, sizeof(int), compare_ints))
	{
	  printf("%d: found at %d\n", i, index);
	}
      else if (index == -1)
	{
	  printf("%d: error searching\n", i);
	}
      else
	{
	  printf("%d: not found; insert at %d\n", i, index);
	}
    }

  // now search some strings
  char *route[] = {"ACY", "BOS", "CMH", "DAY", "EUG", "FAT", "GRR"};
  char *keys[] = {"ABE", "BWI", "DEN", "FAR", "GYY"};
  for (int i = 0; i < sizeof(route) / sizeof(char *); i++)
    {
      printf("%s ", route[i]);
    }
  printf("\n");
  
  for (int i = 0; i < sizeof(keys) / sizeof(char *); i++)
    {
      int index;
      if (binary_search(route, keys + i, &index, sizeof(route) / sizeof(char *), sizeof(char *), compare_strings))
	{
	  printf("%s: found at %d\n", keys[i], index);
	}
      else if (index == -1)
	{
	  printf("%s: error searching\n", keys[i]);
	}
      else
	{
	  printf("%s: not found; insert at %d\n", keys[i], index);
	}
    }
}

bool binary_search(const void *a, const void *key, int *index, int item_count, int item_size, int (*compare)(const void *, const void *))
{
  if (a == NULL || key == NULL || index == NULL || item_count < 0 || item_size <= 0)
    {
      if (index != NULL)
	{
	  *index = -1;
	}
      return false;
    }

  const char *arr = a;

  int start = 0;
  int end = item_count - 1;
  while (start <= end)
    {
      int mid = (start + end) / 2;
      int result = compare(key, arr + mid * item_size);
      if (result == 0)
	{
	  *index = mid;
	  return true;
	}
      else if (result < 0)
	{
	  end = mid - 1;
	}
      else
	{
	  start = mid + 1;
	}
    }

  *index = start;
  return false;
}

	   
int compare_ints(const void *s1, const void *s2)
{
  const int *i1 = s1;
  const int *i2 = s2;

  return *i1 - *i2;
}

int compare_strings(const void *s1, const void *s2)
{
  const char * const *i1 = s1;
  const char * const *i2 = s2;

  return strcmp(*i1, *i2);
}