/* Insert.c */
/* Example of a dynamically-allocated linked list. */

/* include files */
#include <stdio.h>
#include <string.h>

/* global structure, variables, and constants */
#define NAME_LENGTH 20

  struct county_node         /* node for linked list */
    {
     char county_name[NAME_LENGTH];
     long population;
     struct county_node *next;      /* link to next node */
    };

  struct county_node *head_ptr;      /* pointer to head of linked list */
  struct county_node *current_ptr;   /* pointer to current node */

/* function prototypes */
int get_county_data(char name[NAME_LENGTH], long *popul);
void insert_node(char name[NAME_LENGTH], long popul);
void position_insertion_point(long popul);
void make_node_new_head(struct county_node *new_rec_ptr);
void move_current_to_end();
void display_list();
void delete_list();

/* beginning of main function */
int main()
{
 char name[NAME_LENGTH];
 long popul;

 if(get_county_data(name, &popul))   /* prompt user for data for the node */
   {
     head_ptr = (struct county_node *)malloc(sizeof(struct county_node)); /* initialize list head */
     strcpy(head_ptr->county_name, name);
     head_ptr->population = popul;
     head_ptr->next = NULL;       /* initialize next node pointer to NULL */

     while(get_county_data(name, &popul))
      {
       insert_node(name, popul);
      }
     display_list();  /* display the counties and populations */
     delete_list();   /* free the memory used by the linked list */
   }
 printf("\nEND OF PROGRAM\n");
 return 0;
}

/* Function that gets data from user. */
int get_county_data(char name[NAME_LENGTH], long *popul)
 {
  int keep_data = 1;
  int temp;

  printf("Enter county name (Press Enter alone to stop): ");
  fgets(name, 20, stdin);
  name[strlen(name) - 1] = '\0'; /* delete \n */
  if(name[0] != '\0')
   {
    printf("Enter county population: ");
    scanf("%ld", popul);
    /* eliminate \n from stream */
    temp = getc(stdin);
    if( temp != '\n')
       ungetc(temp, stdin);
   }
  else
   {
    keep_data = 0;
   }
  return(keep_data);
 }

/* Function that inserts a new node into the linked list */
/* sorted by population. */
void insert_node(char name[NAME_LENGTH], long popul)
{
  struct county_node *new_rec_ptr; /* Declare temporary pointer for the new node. */
  struct county_node *before_ptr;  /* More temporary pointers. */
  struct county_node *after_ptr;

  new_rec_ptr = (struct county_node *)malloc(sizeof(struct county_node)); /* Allocate memory for a new node and */
				 /* initialize pointer to point to it. */

  strcpy(new_rec_ptr->county_name, name);  /* Initialize the new node */
  new_rec_ptr->population = popul;         /* with data. */

  if(popul > head_ptr->population)    /* If the population of the new */
   {                                  /* county is greater than that of the */
    make_node_new_head(new_rec_ptr);  /* head of the list, make new node */
   }                                  /* the head. */
  else                                /* Else, determine where the new node */
   {                                  /* should be inserted. */
    position_insertion_point(popul); /* Move current_ptr to node before */
				     /* insertion point. */
    before_ptr = current_ptr;      /* Use pointers to keep track of nodes */
    after_ptr = current_ptr->next; /* on each side of the insertion point. */

    before_ptr->next = new_rec_ptr; /* Insert node in list. */
    new_rec_ptr->next = after_ptr;
   }
}

/* Function that positions current_ptr at the node before the position */
/* where the new node should be inserted. */
void position_insertion_point(long popul)
{
 long temp_popul;
 struct county_node *temp_ptr;

 if(head_ptr->next != NULL) /* If more than one node exists, search the */
  {                         /* list for the correct insertion point. */
   current_ptr = head_ptr;
   temp_ptr = current_ptr->next;
   temp_popul = temp_ptr->population;
   /* Loop until the population of the node following current_ptr has */
   /* less population than the current node. */
   while((current_ptr->next !=NULL) && (popul < temp_popul))
    {
     current_ptr = temp_ptr;
     temp_ptr = current_ptr->next;
     temp_popul = temp_ptr->population;
    }
  }
 else  /* If only one node exists in the list, current_ptr is the same */
  {    /* as head_ptr. New node will be added to the end of the list. */
   current_ptr = head_ptr;
  }
}

/* Function that makes the node pointed to by new_rec_ptr the new */
/* head of the linked list. It handles the special case of inserting at */
/* the front of the list. */
void make_node_new_head(struct county_node *new_rec_ptr)
{
  new_rec_ptr->next = head_ptr;
  head_ptr = new_rec_ptr;
}

/* Function that moves current_ptr to end of the linked list. */
void move_current_to_end()
{
 current_ptr = head_ptr;  /* Move current_ptr to head of the list. */

 while(current_ptr->next != NULL)
  {                             /* Traverse list until NULL is reached. */
   current_ptr = current_ptr->next;
  }
}

/* Function that displays entire linked list. */
void display_list()
{
 current_ptr = head_ptr;   /* Move current_ptr to head of list. */
 printf("\nCounty                     Population\n");
 printf("-------------------        ----------\n");
 do
  {
   printf("%-25s", current_ptr->county_name);
   printf("%12ld\n", current_ptr->population);
   current_ptr = current_ptr->next; /* set current_ptr to point to next node */
  } while(current_ptr != NULL); /* loop until end of list */
}

/* Function that frees the memory used by the linked list. */
void delete_list()
{
 struct county_node *temp_ptr;  /* pointer used for temporary storage */

 current_ptr = head_ptr;  /* Move current_ptr to head of the list. */

 do    /* Traverse list until the end is reached. */
  {
   temp_ptr = current_ptr->next;   /* Set temporary pointer to point */
				   /* to the remainder of the list. */
   free( current_ptr);   /* Delete current */
   current_ptr = temp_ptr;
  } while(temp_ptr != NULL);
}