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

typedef struct Golfer {
   char fName[80];
   char lName[80];
   int handicap;
} Golfer;

typedef struct ListNode {
   Golfer data;
   struct ListNode *next;
} ListNode;

void insertInOrder(ListNode **golfers, ListNode *golfer);

ListNode * findBestGolfer(ListNode *golfers);

//returns the head of the list
ListNode * deleteGolfer(ListNode *golfers, ListNode *golfer);

void printRoster(ListNode *golfers);

void printBackward(ListNode *golfers);

//void sortByHandicap(Golfer golfers[], int numGolfers);

int main() {
   printf("Hello World!\n");
  

   Golfer g;
   strcpy(g.fName,"Roger");
   strcpy(g.lName,"Priebe");
   g.handicap = 17;

   printf("%s, %s - %d\n",g.lName, g.fName, g.handicap);

   ListNode *head = NULL;
   ListNode *tail = NULL;

   FILE *fptr;
   fptr = fopen("golfers.dat", "r");

   int numGolfers = 0;

   if (fptr == NULL) {
       printf("Cannot open file!\n");
       exit(0);
   }
   else {
       printf("found it!\n");

    }

    char fName[80];
    char lName[80];
    int handicap;

    while (fscanf(fptr, "%s %s %d", fName, lName, &handicap) != EOF) {
        ListNode *temp = (ListNode *) malloc(sizeof(ListNode));
        strcpy(temp->data.fName, fName);
        strcpy(temp->data.lName, lName);
        temp->data.handicap = handicap;
        temp->next = NULL;

        insertInOrder(&head, temp);
/*
        //O(n) insert at end
        if (head == NULL) {
            head = temp;
        } 
        else {
            ListNode *p = head;
            while (p->next != NULL) {
                p = p->next;
            }
            
            p->next = temp;
        } 

        //O(1) insert at end
        if (head == NULL) {  //first item
            head = temp;
            tail = temp;
        }
        else {
            tail->next = temp;
            tail = temp;
        }          
 */       
    }
    
    printBackward(head);
    printf("------------------------\n");
    printRoster(head);

    ListNode *bestGolfer = findBestGolfer(head);
    printf("The best golfer is %s\n", bestGolfer->data.fName);

    head = deleteGolfer(head, bestGolfer);

    //sortByHandicap(golfers, numGolfers);

    printRoster(head);
    printf("=================\n");
    head = deleteGolfer(head, head);
    printRoster(head);

    printf("--------------------------\n");
    //WARNING MEMORY LEAD
    head = NULL;
    head = deleteGolfer(head, bestGolfer);
    printRoster(head);
   
}

void printBackward(ListNode *golfers) {
   if (golfers != NULL) {
      printBackward(golfers->next);
      printf("%s, %s - %d\n", golfers->data.lName, golfers->data.fName, golfers->data.handicap);
   }
}


void insertInOrder(ListNode **golfers, ListNode *golfer) {
   ListNode *p = *golfers;
   ListNode *prev = NULL;

   if (p == NULL) {
      *golfers = golfer;
   }
   else {
      while ((p != NULL) && (p->data.handicap < golfer->data.handicap)) {
          prev = p;
          p = p->next;
      }

      if (prev == NULL) {  //insert at head
          golfer->next = *golfers;
          *golfers = golfer;
      }
      else { 
          prev->next = golfer;
          golfer->next = p; 
      }
   }
}




ListNode * deleteGolfer(ListNode *golfers, ListNode *g) {
   ListNode *p = golfers;
   ListNode *prev = NULL;

   if (golfers == NULL) {
      return NULL;
   }
   else {
      while ((p != NULL) && (p != g)) {
         prev = p;
         p = p->next;
      }

      if (prev == NULL) {  //first element
         golfers = p->next;
         free(p);
      }
      else if (p != NULL) {
         prev->next = p->next;
         free(p);
      }  

      return golfers;
   }      
}




void printRoster(ListNode *golfers) {
    ListNode *p = golfers;
    while (p != NULL) {
        printf("%s, %s - %d\n", p->data.lName, p->data.fName, p->data.handicap);
        p = p->next;
  }
}  

ListNode * findBestGolfer(ListNode *golfers) {
   if (golfers == NULL) {
      return NULL;
   }
   else {
        ListNode *best = golfers;
        for (ListNode *p = golfers->next; p !=NULL; p = p->next) {
            if (p->data.handicap < best->data.handicap) {
                best = p;
            }
        }
    
       return best;
   }

}