/*Program to demostrate Linear probing in
1. Storing Students' infroamtion
2. Searching based on roll number.
Note: roll is a 6 digits nubmer ex. 136001
Created by: Dr. Ajit Kumar
Email: ajitkumar.pu@gmail.com
Date: 11-04-2019
*/
#include<stdio.h>
#include<string.h>
#include <math.h>
#define MAX 11
#define A 0.6180339887

int h(int k, int m)
{
return floor(m * (k*A - floor(k*A)));
}

struct student
{
    char name[20];
    unsigned long roll_no;
    float marks;
};
struct student arr_student[MAX];

// Linear Probing function
// taking the Array of the student structure as argument
// along with location of collision and hash table size
int linear_probing(struct student hashtable [], int loc, int m)
{
    while(loc <= m-1)
    {
        if(hashtable[loc].roll_no == 0)
        {
            return loc;
        }
        loc++;
    }
return -1;
}

int main()
{

    int recordCount=0;
    int arrayIndex=0;
    int i;
    unsigned long key_roll=0;
    int flag = 1,search_flag =1;

    while(flag == 1)
    {
    printf("Enter student roll no: ");
    scanf("%u", &key_roll);
    //hash calculation using multiplication method
    arrayIndex = h(key_roll,11);
    printf("%d \t : %d \n", key_roll, arrayIndex);

    // Checking for hash collision
    // default initial value of roll no is use senitel value
    // initial value for int in sturcutue is 0

    if (arr_student[arrayIndex].roll_no != 0)
    {
        printf("\n\nA hash collision detected\n");
        // calling linear probing function to find next free location
        arrayIndex = linear_probing(arr_student, arrayIndex, 11);
        printf("With Linear probing New location is: %d\n", arrayIndex);
        if(arrayIndex == -1)
        {
        printf("Hash Table Overflow!!\n");
        break;
        }
    }
    // using hash value to store a student record
    printf("Enter student name: ");
    scanf("%s", arr_student[arrayIndex].name);

    arr_student[arrayIndex].roll_no = key_roll;

    printf("Enter student marks: ");
    scanf("%f", &arr_student[arrayIndex].marks);

    recordCount++;

    printf("Do you want to add more entry:(Yes-> 1/No->0)");
    scanf("%d",&flag);
    }
    printf("\n");
    printf("\t\tName\tRoll no\tMarks\n");
    for(i = 0; i < MAX; i++ )
    {
        printf("\t \t %s\t%u\t%.2f\n",
        arr_student[i].name, arr_student[i].roll_no, arr_student[i].marks);
    }
    while(search_flag == 1)
    {
    printf("\n");
     // searching a student information based on hash value
    printf("Enter Roll number so show the details");
    scanf("%u", &key_roll);
    //hash calculation using multiplication method
    arrayIndex = h(key_roll,10);
    //Need to compare the stored value with the search key (roll no)
    if(arr_student[arrayIndex].roll_no == key_roll)
    {
    printf("%s\t%u\t%.2f\n",
    arr_student[arrayIndex].name, arr_student[arrayIndex].roll_no,
				 arr_student[arrayIndex].marks);
    }
    else
    {
        for(i = arrayIndex+1; i < MAX; i++ )
        {
            if (arr_student[i].roll_no == key_roll)
            {
            printf("%s\t%u\t%.2f\n",
            arr_student[i].name, arr_student[i].roll_no, arr_student[i].marks);
            break;
            }
            else
            {
                if ((arr_student[i].roll_no == 0) || (i == MAX -1 ))
                {
                printf("Record not found.\n");
                break;
                }
            }
        }
    }
    printf("Do you want search more record:(Yes-> 1/No->0)");
    scanf("%d",&search_flag);
    }
    return 0;
}