/*
   Searching program with hashing method.
*/

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

#define MAXSTUDENTS 50   /*  Constants */
#define HASH_SIZE 61

int hash( long int key, int n ){
  return( (int) ( key % (int)(n*1.4)) ) ;
}

main()
{
  /*  Declaration Statements  */
  char names[HASH_SIZE][25], temp_name[25];
  long int id[HASH_SIZE], key, temp_id;
  int i, n, hash_index, cont, counter, probe_worked, yes_no;

  printf("Zeroing all elements of the array\n\n");
  for( i=0;  i < (HASH_SIZE); i++)
     id[i] = 0;

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

  printf("Enter students' names and ID #'s\n");
  printf("in this format ->Name:Doe,John[ENTER] (no spaces)\n");
  printf("               ->ID:9421234[ENTER]\n");

  /*  The following is along loop that carries out the hashing
       algorithm as each student is added to the list. */

  for( i=0; i<n; i++){
     printf("Student #%d:",i+1);
     printf("Name:");
     scanf("%s",temp_name);
     printf("ID:");
     scanf("%ld",&temp_id);

    hash_index = hash( temp_id,n );
 /*  This hash is legal! */

  /* Now, this is the part where we will check for collisions, and take
     appropriate action. */

    if( id[ hash_index ] == 0 ) {
       id[hash_index] = temp_id;
       strcpy( names[hash_index], temp_name );
       }
    else {         /* What to do if we had a collision */
       probe_worked = 0;
       do{
         /*  Check the next slot */
        hash_index++;

         /*  If we're at the end of the list, go back to beginning */
        if( hash_index >= HASH_SIZE)
          hash_index = 0;

         /*  If the next slot was empty, fill it, and get out of loop */
        if( id[ hash_index ] == 0 ){
          id[hash_index] = temp_id;
          strcpy( names[hash_index], temp_name );

       probe_worked = 1;  /*  A flag to exit the linear probing loop */
          }   /* end if */

     }while( probe_worked == 0 ); /* end of linear probing loop */

     } /* endif - this was the if that checked for a collision */

  }  /* end of outer loop that prompts user for names and id#'s */

/* This part of the program lets the user search the list
   using the hashing function */

 do {
   /* Keep on looking up names until user wants to quit */

  printf("Enter search key\n\n ID# :");
  scanf("%ld",&key);

  printf("\n  **SEARCHING**\n");

    hash_index = hash( key, n );

  /* Now, we will check for collisions, and take appropriate action. */

    if( id[ hash_index ] == key ) {
       strcpy( temp_name, names[hash_index] );
       }
    else {        /* What to do if we had a collision when storing */
                 /* the ID # that the user is requesting */

       /* Initialize a counter to make sure that we don't
          keep probing the whole list over and over again. */
       counter = 0;
       i = 0;
       do{
        counter++;
         /*  Check the next slot  */
        hash_index++;

         /*  If we're at the end of the list, go back to beginning */
 if( hash_index >= HASH_SIZE )
          hash_index = 0;

         /* If the next slot was the key, get name and get out of loop*/
        if( id[ hash_index ] == key ){
          strcpy( temp_name, names[hash_index] );

          i=1;  /*  This is a flag to exit the linear probing loop */
          }   /* end if */

        }while( i==0 && counter <= HASH_SIZE); /*end of linear probe*/

     } /* endif - this was the "if"that checked for a collision */

  cont = 0;
  if(counter > n){
    printf("Search key not found - check spelling\n");
    printf("Try again (1 for yes/0 for no)? ");
    scanf("%d",&yes_no);
    }
  else {
    printf("  **FOUND**\n");
    printf("ID#:%ld  Name:%s\n\n", key, temp_name);
    printf("Look up another student (1 for yes/0 for no)? ");
    scanf("%d",&yes_no);
    } /* End of if{} statement */

 }while(yes_no == 1);

}
/*  End of Hash.c program  */