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

//
// Compare the whole thing by passing 0 as end
//
// @param str String to check for palindrome
// @param end For checking a substring shorter than the end of str
//
// @return int Is a palindrome (1) or not (0)
//
char is_palindrome(char* str, long len) {
  //long len;
  long i = 0;

  // This handles comparisons of odd and even length strings
  while(len - i > 0) {
    if(str[i] != str[len])
      return 0;

    ++i;
    --len;
  }
  return 1;
}


//
// Finds the largest palindrome in a data set
//
// @param data Data chunk to search for the largest palindrome
//
void find_largest_palindromes(char* data) {
  long cursor = 0;
  int start = 0;
  int end = 0;

  int largest = 0;
  int largest_start = 0;
  int largest_end = 0;

  // Writing this here for sanity purposes
  // 0 1 2 3 4 5 6
  // r a c e c a r

  // 0 1 2 3 4 5
  // a b c c b a

  while(data[cursor] != '\0') {
    // Need to align with the center
    // Advance end one to see if this is an even numbered palindrome
    if(data[end + 1] != '\0') {
      ++end;
    }
    // If it's not an even numbered, let's see if it's odd numbered
    if(start > 0 && data[start] != data[end]) {
      --start;
    }
    // Looks like it's not either, reset and continue
    if(data[start] != data[end]) {
      ++cursor;
      start = cursor;
      end = cursor;
      continue;
    }

    // It seems we have found a palindrome, let's see how big...
    while(data[start] == data[end]) {
      if(data[end + 1] != '\0') {
        ++end;
      }
      if(start > 0) {
        --start;
      }

    }
    if(end - start - 1 > largest) {
      largest = end - start - 1;
      largest_start = start + 1;
      largest_end = end - 1;
    }

    ++cursor;
    start = cursor;
    end = cursor;
  }
  // Move start one forwards since moving it backwards resulted in a non-
  if( largest > 1) {
    printf("The largest palindrome is %d long\n", largest);
    printf("It starts at %d, and ends at %d\n", largest_start, largest_end);
    printf("%.*s\n", largest, &data[largest_start]);
  }
}


//
// Function for testing one-off strings
// Useful for debugging
//
// @param str String to test for palindromeism
//
void palstr(char* str) {
   if(is_palindrome(str, 0) == 1) {
     printf("%s \e[1mis\e[0m a palindrome!\n", str);
   } else {
     printf("%s is \e[1mnot\e[0m a palindrome.\n", str);
   }
}


//
// Ye olde' main function
//
int main(int argc, char *argv[]) {
  if(argc < 2) {
    printf("Please specify a string to check for palindrome-ism.\n");
    return 1;
  }

  struct timespec start, stop;
  FILE *f = fopen(argv[1], "r");

  // If the file can't be opened, try using the passed value as a palindrome
  // test
  if(!f) {
    palstr(argv[1]);
    return 0;
  }
  
  printf("Scanning file %s\n", argv[1]);

  // Get file length
  unsigned int flen = 0;
  while(fgetc(f) != EOF) {
    flen++;
  }

  rewind(f);

  printf("Allocating memory\n");
  // Allocate array for file contents
  char* data = malloc(flen + 1);
  unsigned int i = 0;
  char c;
  printf("Reading data to memory\n");
  while((c = fgetc(f)) != EOF) {
    data[i] = c;
    i++;
  }
  
  fclose(f);

  printf("Searching for palindromes\n");

  
  clock_gettime(CLOCK_MONOTONIC_RAW, &start);
  find_largest_palindromes(data);
  clock_gettime(CLOCK_MONOTONIC_RAW, &stop);

  free(data);

  // Calculate search time
  double timestart = start.tv_sec + (1.0e-9 * start.tv_nsec);
  double timestop = stop.tv_sec + (1.0e-9 * stop.tv_nsec);
  // Print runtime message
  printf("Palindrome search took %.5f seconds\n", timestop - timestart);

  return 0;
}