/*
    This program demonstrates how a very simple linked list would work.
    First, we will have the user input the initial list, which we will
    sort.  After sorting, we will initialize the links, which means
    simply that we will store information in each record about where
    the next record is.  Finally, we will demonstrate how you would
    update the list, adding new records at the end, but effectively
    inserting them into the list at the right point just by changing
    the links of the old records.
*/

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

#define MAXSTUDENTS 50

void id_swap(long int *k, long int *l)
{
  long int temp;

  temp = *k;
  *k = *l;
  *l = temp;
}

void grade_swap(int *grade1, int *grade2)
{
  int temp;

  temp = *grade1;
  *grade1 = *grade2;
  *grade2 = temp;
}

void bsort2( long int id[], int grade[], int n)
{
  int last, k, i, kk;

  printf("Sorting\n");
  last = n - 1;
  do {
    k = 0;
    for (i = 1; i <= last; i++) {
      if (id[i - 1] > id[i]) {
     id_swap(&id[i - 1], &id[i]);
     grade_swap(&grade[i - 1], &grade[i]);
        k = i;
      }
    }
    last = k;
  } while (k != 0);
}

long int linear(long int list[], long int key, int n){

/*  This is just the linear search function with no alterations */

  int i, flag;
  flag = -2;
  for( i=0; i<n; i++){
    if( list[i] == key ){
      flag = i;
      break;
    }
  }
  return(flag);
}

void print_list(long int id[], int grade[], long int next[], int first)
{
  int i, new;

  printf("first =%d\n",first);
  i = 1;
  printf("\nElement# %d ID# %ld Grade- %d\n", i, id[first], grade[first]);
  new = first;
  while(next[new] >= 0){
    i++;
    new = next[new];
    printf("Element# %d ID# %ld Grade- %d\n", i, id[new], grade[new]);
    }
}

main(){

  long int id[MAXSTUDENTS], key, temp_id, next[MAXSTUDENTS], first, last, lastrecord;
  int i, n, flag, reply, grade[MAXSTUDENTS], temp_grade;

  do{
     printf("How many students? ( <%4d) \n",MAXSTUDENTS);
     scanf("%d",&n);
     }while( n>MAXSTUDENTS );

  printf("Enter students' names and ID #'s\n");
  printf("in this format ->ID:9421234[ENTER] (no spaces)\n");
  printf("               ->Grade:49[ENTER]\n");
  for( i=0; i<n; i++){
     printf("Student #%d:\n",i+1);
     printf("ID #:");
     scanf("%ld",&id[i]);
     printf("Grade:");
     scanf("%d",&grade[i]);
     }

  /* We will sort the initial list using the improved bubble sort */

  bsort2( id, grade, n );

  /* Now, we will initialize the links  */
  /* The last record has a null link (-1) */

  for(i=0; i < (n-1); i++)
    next[i] = i+1;
  next[n-1] = -1;
  first = 0;

  print_list( id, grade, next, first );

  printf("Ready to add new records to the list.\n\n");

do{
  printf("Enter 0 for front of list, 1 for back of list : ");
  scanf("%d",&reply);

  last = linear( next, -1, MAXSTUDENTS );
  lastrecord = last;
  if(last == -2){
      printf("ERROR- could not find end of list\n\n\n");
      break;
      }

  printf("\nlast = %d\n\n",last);
  printf("Enter student's name and ID #\n");
  printf("in this format ->ID:9421234[ENTER] (no spaces)\n");
  printf("               ->Grade:49[ENTER]\n");
  printf("ID #:");
  scanf("%ld",&id[last+1]);
  printf("Grade:");
  scanf("%d",&grade[last+1]);

  printf("Reply = %d", reply);
  if(reply == 0){
     printf("Adding record to the front of the list\n");
     lastrecord = lastrecord + 1;
     next[lastrecord] = first;
     first = lastrecord;
     print_list( id, grade, next, first );
     }
 if(reply == 1){
     printf("Adding record to the back of the list\n");
     lastrecord = lastrecord + 1;
     next[lastrecord] = -1;
     next[last] = lastrecord;
     last = lastrecord;
     print_list( id, grade, next, first );
     printf("This is back end! first= %ld",first);
     }
  printf("Add another (0 for no, 1 for yes)?\n");
  scanf("%d",&reply);
  }while( reply == 1 );
}
/*  End of main program linked.c  */