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

    typedef struct
    {
       char reg_num[12];
       char fname[20];
       char lname[20];
       float gpa;
       char gender;
       int age;
    }StudentInfo;

    float calcGpa();

    /*QUICKSORT*/

    typedef struct ListNode
    {        /* typical node to be sorted */
        struct ListNode *nextEntry;
        struct ListNode *prevEntry;
        StudentInfo data;
    }ListNode;

    /* This is the global pointer variable to be used in the above functions */
    ListNode *studentDB = NULL;

    #define compLT(a_,b_) strcmp((a_)->fname, (b_)->fname)
    #define compGT(a_,b_) strcmp((b_)->fname, (a_)->fname)

    ListNode *partition(ListNode *lb, ListNode *rb)
    {
        StudentInfo t, pivot;
        ListNode *i, *j;
        int done;           /* record if pointers cross (means we're done!) */

       /********************************************************
        * partition list [lb..rb], and return pointer to pivot *
        ********************************************************/

        /* select a pivot */
        pivot = lb->data;
        done = 0;

        /* scan from both ends, swapping when needed */
        /* care must be taken not to address outside [lb..rb] with pointers */
        i = lb; j = rb;
        while(1) {
            while (compGT(&(j->data), &pivot)) {
                j = j->prevEntry;
                if (i == j) done = 1;
            }
            if (done) return j;
            while (compLT(&(i->data), &pivot)) {
                i = i->nextEntry;
                if (i == j) done = 1;
            }
            if (done) return j;

            /* swap i, j */
            t = i->data;
            i->data = j->data;
            j->data = t;

            /* examine next element */
            j = j->prevEntry;
            if (i == j) done = 1;
            i = i->nextEntry;
            if (i == j) done = 1;
        }
    }

    void quickSort(ListNode *lb, ListNode *rb) {
        ListNode *m;

       /************************
        *  sort list [lb..rb]  *
        ************************/

        if (lb == rb) return;

        m = partition(lb, rb);

        if (m != lb) quickSort(lb, m);              /* sort left side */
        if (m != rb) quickSort(m->nextEntry, rb);        /* sort right side */
    }


    /* Function to add a student to the database */
    void addStudentRecord()
    {
      ListNode *newStudent = (ListNode *)calloc(1, sizeof(ListNode));

      /* Verify that a new student structure was allocated */
      if (newStudent != NULL)
      {
         char buf[20];

         /* Now assign some values to the structure */

         printf("Registration number (Integers only): ");
         fgets(newStudent->data.reg_num, sizeof(newStudent->data.reg_num)/sizeof(*newStudent->data.reg_num), stdin);
         if (newStudent->data.reg_num[strlen(newStudent->data.reg_num) - 1] == '\n')
            newStudent->data.reg_num[strlen(newStudent->data.reg_num) - 1] = '\0';
         else
             getchar();         /* get rid of trailing return */

         printf("First Name: ");
         fgets(newStudent->data.fname, sizeof(newStudent->data.fname)/sizeof(*newStudent->data.fname), stdin);
         if (newStudent->data.fname[strlen(newStudent->data.fname) - 1] == '\n')
            newStudent->data.fname[strlen(newStudent->data.fname) - 1] = '\0';
         else
             getchar();         /* get rid of trailing return */

         printf("Last Name: ");
         fgets(newStudent->data.lname, sizeof(newStudent->data.lname)/sizeof(*newStudent->data.lname), stdin);
         if (newStudent->data.lname[strlen(newStudent->data.lname) - 1] == '\n')
            newStudent->data.lname[strlen(newStudent->data.lname) - 1] = '\0';
         else
             getchar();         /* get rid of trailing return */

         printf("Gender (Please enter either the letter M or F): ");
         newStudent->data.gender = toupper(fgetc(stdin));
         getchar();         /* get rid of trailing return */

         newStudent->data.gpa = calcGpa();

         printf("Age: ");
         fgets(buf, sizeof(buf)/sizeof(*buf), stdin);
         if (buf[strlen(buf) - 1] == '\n')
            buf[strlen(buf) - 1] = '\0';
         else
             getchar();
         newStudent->data.age = atoi(buf);

         ListNode *tmpPtr = studentDB;
         ListNode *prevPtr = studentDB;


    /* Get to end of student list */
         while (tmpPtr != NULL)
         {
            prevPtr = tmpPtr;
            tmpPtr = tmpPtr->nextEntry;
         }

         /* Is this the first entry? */
         if (prevPtr == NULL)
            studentDB = newStudent;
         else
         {
             /* Add the new student after the last student */
             prevPtr->nextEntry = newStudent;
             /* Ensure we have a way to get from the current student to the previous student */
             newStudent->prevEntry = prevPtr;
         }
      }  /* End of check if new student record was able to be created */
      else
          printf("\nNot enough memory to add a student to the database!\n\n");
    }    /* addStudentRecord() */

    /* Function to add a student to the database */
    void addStudentRecordFromStruct(StudentInfo *stud)
    {
      ListNode *newStudent = (ListNode *)calloc(1, sizeof(ListNode));

      /* Verify that a new student structure was allocated */
      if (newStudent != NULL)
      {
         /* Now assign some values to the structure */
         strcpy(newStudent->data.reg_num, stud->reg_num);
         strcpy(newStudent->data.fname, stud->fname);
         strcpy(newStudent->data.lname, stud->lname);
         newStudent->data.gpa = stud->gpa;
         newStudent->data.gender = stud->gender;
         newStudent->data.age = stud->age;

         ListNode *tmpPtr = studentDB;
         ListNode *prevPtr = studentDB;

    /* Get to end of student list */
         while (tmpPtr != NULL)
         {
            prevPtr = tmpPtr;
            tmpPtr = tmpPtr->nextEntry;
         }

         /* Is this the first entry? */
         if (prevPtr == NULL)
            studentDB = newStudent;
         else
         {
             /* Add the new student after the last student */
             prevPtr->nextEntry = newStudent;
             /* Ensure we have a way to get from the current student to the previous student */
             newStudent->prevEntry = prevPtr;
         }
      }  /* End of check if new student record was able to be created */
      else
          printf("\nNot enough memory to add a student to the database!\n\n");
    }    /* addStudentRecord() */

    void TryGetString(char* p, size_t size)
    {  /* read a string, if the string is not empty, copy it to p, otherwice, keep what was in p */
       char* buf = (char*)malloc(size);
       fgets(buf, size, stdin);

       if(strlen(buf)) /* Not empty */
       {
          if(buf[strlen(buf) - 1] == '\n')
             buf[strlen(buf) - 1] = 0;
          strcpy(p, buf);
       }
       free(buf);
    }


    /* Function to update a student in the database */
    void updateStudentRecord()
    {
       if (studentDB == NULL)
          printf("\nThere are no students in the database. Add at least one student before attempting this operation.\n\n");
       else
       {
          char regid[12];
          printf("Enter the registration id for the student to update: ");
          fgets(regid, sizeof(regid)/sizeof(*regid), stdin);

          /* Make sure they typed a last name */
          if (strlen(regid) > 0)
          {
             /* Remove the newline from the string to check for */
             if (regid[strlen(regid) - 1] == '\n')
                regid[strlen(regid) - 1] = '\0';

             ListNode *tmpPtr = studentDB;

             /* Loop through the student list
    */
             while (tmpPtr != NULL)
             {
                /* See if we found a match on the last name */
                if(strcmp(tmpPtr->data.reg_num, regid) == 0)
                {
                   char buf[20];
                   printf("Enter Reg Number of the student that you want to update AGAIN: ");
                   TryGetString(tmpPtr->data.reg_num, sizeof(tmpPtr->data.reg_num));
                   printf("New first name: ");
                   TryGetString(tmpPtr->data.fname, sizeof(tmpPtr->data.fname));
                   printf("New last name: ");
                   TryGetString(tmpPtr->data.lname, sizeof(tmpPtr->data.lname));
                   tmpPtr->data.gpa = calcGpa();
                   printf("New Age: ");
                   sprintf(buf, "%d", tmpPtr->data.age);
                   TryGetString(buf, sizeof(buf));
                   tmpPtr->data.age = atoi(buf);
                   /* Students are not allowed to change their gender... */
                   return;
                }
                tmpPtr = tmpPtr->nextEntry;
             }
          }
       }
       printf("No such student\n");
    }/* updateStudentRecord() */


    /* Function to delete a student from the database */
    void deleteStudentRecord()
    {
       /* See if there are any students */
       if (studentDB == NULL)
          printf("\nThere are no students in the database. Add at least one student before attempting this operation.\n\n");
       else
       {
          char regid[12];
          char last_name[20];
          char first_name[20];
          printf("Enter the registration id for the student to delete: ");
          fgets(regid, sizeof(regid)/sizeof(*regid), stdin);

          /* Make sure they typed a last name */
          if (strlen(regid) > 0)
          {
             /* Remove the newline from the string to check for */
             if (regid[strlen(regid) - 1] == '\n')
                regid[strlen(regid) - 1] = '\0';


        ListNode *tmpPtr = studentDB;
             int bDeleted = 0;

             /* Loop through the student list */
             while (tmpPtr != NULL)
             {
                /* See if we found a match on the last name */
                if (strcmp(tmpPtr->data.reg_num, regid) == 0)
                {
                   /* Get a copy of the first/last name */
                   strcpy(first_name, tmpPtr->data.fname);
                   strcpy(last_name, tmpPtr->data.lname);



                   /* Repoint the previous entry's nextEntry to the one for the item we will be

    deleting */
                   if (tmpPtr->prevEntry != NULL)
                      tmpPtr->prevEntry->nextEntry = tmpPtr->nextEntry;
                   /* Repoint the next entry's prevEntry to the one for the item we will be deleting

    */
                   if (tmpPtr->nextEntry != NULL)
                      tmpPtr->nextEntry->prevEntry =
    tmpPtr->prevEntry;

                   printf("\nStudent '%s, %s' (%s) has been deleted from the database.\n\n",

    last_name, first_name, regid);



                   /* see if we need to repoint the studentDB */
                   if (tmpPtr == studentDB)
                      studentDB = tmpPtr->nextEntry;

                   /* Deallocate the memory */
                   free(tmpPtr);

                   /* Exit loop early */
                   tmpPtr = NULL;

                   /* We have deleted the item */
                   bDeleted = 1;
                }
                else
                    tmpPtr = tmpPtr->nextEntry;  /* Get to next entry if we need to */
             }
             /* See if we didn't find an entry */
             if (bDeleted == 0)
                printf("\nStudent with the last name '%s' was not found!\n\n", last_name);
          }
          else
             printf("\nYou must specify a last name to perform this operation.\n\n");
       }
    }    /* deleteStudentRecord() */

    /* Function to calculate a student's GPA in the database */
    float calcGpa()
    {
       char buf[32];
       float res = 0;
       int n;

       printf("please type the letters of the all the grades obtained and then press enter: ");
       fgets(buf, sizeof(buf), stdin);
       if(buf[strlen(buf) - 1] == '\n')
           buf[strlen(buf) - 1] = 0;
       else
           getchar();         /* get rid of trailing return */

       for(n = 0; buf[n]; n++)
       {
          switch(buf[n])
          {
          case 'A':
          case 'a':
             res += 4;
             break;
          case 'B':
          case 'b':
             res += 3;
             break;
          case 'C':
          case 'c':
             res += 2;
             break;
          case 'D':
          case 'd':
             res += 1;
             break;
          case 'F':
          case 'f':
             res += 0;

       break;
          default: /* Invalid grade... */
             return -1;
          }
       }
       return res/n;
    }    /* calcGpa() */

    /* Function to calculate the average student's age in the database */
    void CalcAvgAge()
    {
      ListNode *tmpPtr = studentDB;
      int totalAge = 0;
      int studentCount = 0;
      float avg = 0.0;



      /* Loop through all entries, getting a tally of the ages */
      while (tmpPtr != NULL)
      {
         studentCount++;
         totalAge += tmpPtr->data.age;
         tmpPtr = tmpPtr->nextEntry;
      }

      /* Only calculate if there is at least 1 student */
      if (studentCount > 0)
         avg = (float)totalAge/(float)studentCount;
      printf("\nThe average age is: %0.2f, and there are %d students\n\n", avg, studentCount);
    }    /* CalcAvgAge() */

    /* Function to search for a student in the database */
    void search()
    {
       /* See if there are any students */
       if
    (studentDB != NULL)
       {
          char reg_num[12];
          printf("Enter the Registration Number of the student to find: ");
          fgets(reg_num, sizeof(reg_num)/sizeof(*reg_num), stdin);



          /* Make sure they typed a last name */
          if (strlen(reg_num) > 0)
          {
             /* Remove the newline from the string to check for */
             if (reg_num[strlen(reg_num) - 1] == '\n')
                reg_num[strlen(reg_num) - 1] = '\0';

             ListNode *tmpPtr = studentDB;
             int bFound = 0;

             /* Loop through the student list */
             while (tmpPtr != NULL)
             {
                /* See if we found a match on the last name */
                if (strcmp(tmpPtr->data.reg_num, reg_num) == 0)
                {
                  printf("\nFound student: %s, %s (%s)\n", tmpPtr->data.lname, tmpPtr->data.fname, tmpPtr->data.reg_num);
                  printf("Age: %d\tGPA: %0.2f\n\n", tmpPtr->data.age, tmpPtr->data.gpa);
                  /* Terminate the loop prematurely */
                  tmpPtr = NULL;
                  bFound = 1;
                }
                else
                    tmpPtr = tmpPtr->nextEntry;
             }
             /* Display message if we never found an entry */
             if (bFound == 0)
                printf("\nNo students exist with that Registration Number '%s'.\n\n", reg_num);
          }
       }
       else
           printf("\nThere are currently no students in the database to search for.\n\n");
    }    /* search() */

    /* Function to list all students in the database */
    void list()
    {
      if (studentDB != NULL)
      {
         ListNode *tmpPtr = studentDB;
         while (tmpPtr != NULL)
         {
            printf("\nStudent: %s, %s (%s)\n", tmpPtr->data.lname, tmpPtr->data.fname, tmpPtr->data.reg_num);
            printf("Gender: %c\tAge: %d\tGPA: %0.2f\n", tmpPtr->data.gender, tmpPtr->data.age, tmpPtr->data.gpa);
            tmpPtr = tmpPtr->nextEntry;
         }
      }
      else
          printf("\nThere are no students listed at this time.\n\n");
    }    /* list() */

    int main(int argc, char *argv[])
    {
       StudentInfo students[5];

       strcpy(students[0].reg_num,"0707151111");
       strcpy(students[0].fname,"Malisa");
       strcpy(students[0].lname,"Singh");

       students[0].gpa=1.0;
       students[0].age=19;
       students[0].gender='f';

       strcpy(students[1].reg_num,"0707152222");
       strcpy(students[1].fname,"Jeff");
       strcpy(students[1].lname,"Hardy");
       students[1].gpa=2.0;
       students[1].age=29;
       students[1].gender='m';

       strcpy(students[2].reg_num,"0707153333");
       strcpy(students[2].fname,"Sean");
       strcpy(students[2].lname,"Paul");

       students[2].gpa=2.1;
       students[2].age=23;
       students[2].gender='m';

       strcpy(students[3].reg_num,"0707154444");
       strcpy(students[3].fname,"Rickardo");
       strcpy(students[3].lname,"Jermin");

       students[3].gpa=3.6;
       students[3].age=20;
       students[3].gender='m';

       strcpy(students[4].reg_num,"0707155555");
       strcpy(students[4].fname,"Raymond");
       strcpy(students[4].lname,"Mark");
       students[4].gpa=1.7;
       students[4].age=28;
       students[4].gender='m';
       addStudentRecordFromStruct(&students[0]);
       addStudentRecordFromStruct(&students[1]);
       addStudentRecordFromStruct(&students[2]);
       addStudentRecordFromStruct(&students[3]);
       addStudentRecordFromStruct(&students[4]);
       int a = 0;


       while(1)
       {
          printf("\n\t+-------------------------------------------------------------+");
          printf("\n\t|                                                             |");
          printf("\n\t|     Select an Option:                                       |");
          printf("\n\t|                                                             |");
          printf("\n\t|  1. Add Student Record and Calculate the GPA of that student|");
          printf("\n\t|                                                             |");
          printf("\n\t|  2. Update Student Record                                   |");
          printf("\n\t|                                                             |");
          printf("\n\t|  3. Delete Student Record                                   |");
          printf("\n\t|                                                             |");
          printf("\n\t|  4. Calculate average age of the class                      |");
          printf("\n\t|                                                             |");
          printf("\n\t|  5. Search                                                  |");
          printf("\n\t|                                                             |");
          printf("\n\t|  6. List                                                    |");
          printf("\n\t|                                                             |");
          printf("\n\t|  7. Sort                                                    |");
          printf("\n\t|                                                             |");
          printf("\n\t|  8. Student Count                                                    |");
          printf("\n\t|                                                             |");
          printf("\n\t|  9. Exit                                                    |");
          printf("\n\t+-------------------------------------------------------------+");
          printf("\n\n Please enter the number beside your choice : ");

          scanf("%d", &a);
          getchar();
          switch(a)
          {
          case 1:
          addStudentRecord();
          break;
          case 2:
          updateStudentRecord();
          break;
          case 3:
          deleteStudentRecord();
          break;
          case 4:
          CalcAvgAge();
          break;
          case 5:
          search();
          break;
          case 6:
          list();
          break;
          case 7:
          quickSort(studentDB, studentDB->prevEntry);
          break;
          case 8:
          printf("Number of students: %d\n", getStudentCount()); // BKB, must print the result
          break;
          case 9:
          printf("Bye Cruel World");
          exit(0);
          break;
          default:
          printf("\nInvalid Option\n\n");
          break;
          }
       }
       return 0;
    }
     /* function used to count the number of students in the DB */

    int getStudentCount()
    {
       int count = 0;
       struct student *tmpPtr = studentDB;
    /* Loop through entire student list */
       while (tmpPtr != NULL)
       {
          count++;
          tmpPtr = tmpPtr->nextEntry;
       }
       return count; // BKB must return the number
    }

    /*

       Define the compare function for the qsort() function to call.

       This function is used to compare 2 of the values, it should return the following:

          -1 (or below) to indicate that a < b

          0 if they are equal

          1 (or more) to indicate that a > b

    */

    int compare(const void * a, const void * b)
    {
       int result = 0;   // Assume they are equal

       // struct student *left = static_cast <struct student *>(a);  BKB static_cast is a C++ thing,
       // struct student *right = static_cast <struct student *>(b); BKB in C you just do:
       struct student *left = (struct student *)a;
       struct student *right = (struct student *)b;
       // Compare registration numbers
       result = strcmp(left->reg_num, right->reg_num);
       // See if we should continue
       if (result == 0)
       {
          // Compare last names
          result = strcmp(left->lname, right->lname);
       }
       // See if we should continue
       if (result == 0)
       {
          // Compare first names
          result = strcmp(left->fname, right->fname);
       }
       return result;
    }   // end of compare()