Vikram Menon

/*
 * Hashtable template, with collision resolution by chaining
 * Input text file must hold comma separated values.
 * Eg-
 * name1, num1
 * name2, num2
 */

#include <iostream>
#include <fstream>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#define LEN 8               // length of the hash (bytes)
#define NAME 30             // length of string to store a name
#define BUF 200             // length of buffer to read from text file
#define LIM 1000            // number of available pointers

using namespace std;

void hash(char*, char*, int);       // reduce the string to a hash
int  key(char *h);          // reduce the hash to a numeric key

void string2Name(char*, char*);
int  string2Num(char*);

/*
 * Node of the hashtable.
 * Must include the public fields:
 * name (char[NAME])
 * next (node*)
 */
class node
{
    int marks;

public:
    char name[NAME];
    node *next;         // link to next node in chain

    void input(char *nm, int mk)        // parameterised input
    {
        strcpy(name,nm);
        marks = mk;
        next = NULL;
    }

    void output()               // display contents of node
    {
        cout<<"\nName: ";
        puts(name);
        cout<<"Marks: "<<marks<<"\n";
    }
};

/*
 * Hashtable template. Eg-
 * htable<node> myHT;
 *
 * NOTE:
 * Use 'new' to create nodes and call add_node() to enter it into the hashtable.
 * Calling del_node() on a node automatically deletes it.
 */
template <class T>          // Hashtable template
class htable
{
    T *arr[LIM];

public:
    htable()                        // constructor
    {
        for(int i=0; i < LIM; i++)
            arr[i] = NULL;
    }

    void add_node(T *in)                    // add an entry
    {
        char h[LEN + 1];
        hash(in->name, h, LEN);
        int n = key(h)%LIM;
        if(arr[n] == NULL)
            arr[n] = in;
        else
        {
            T *p = arr[n];
            while(p->next != NULL && strcmp(p->name,in->name))  // chaining the node
                p = p->next;
            if(!strcmp(p->name,in->name))
            {
                cout<<"\nDuplicate entry!\n";
                return;
            }
            p->next = in;
        }
    }

    T *find_node(char *nam)                 // search an entry
    {
        char h[LEN + 1];
        hash(nam, h, LEN);
        int n = key(h)%LIM;
        T *p;
        for(p = arr[n]; p != NULL && strcmp(p->name,nam); p = p->next);
        if(p)
        {
            cout<<"\nThe entry was found!\n";
            p->output();
            return p;
        }
        else
        {
            cout<<"\nEntry not found!\n";
            return NULL;
        }
    }

    void del_node(char *nam)                // delete an entry
    {
        char h[LEN + 1];
        hash(nam, h, LEN);
        int n = key(h)%LIM;
        T *t = NULL, *p;
        for(p = arr[n]; p != NULL && strcmp(p->name,nam);)
        {
            t = p;
            p = p->next;
        }
        if(p)
        {
            p->output();
            if(t)
                t->next = p->next;
            else
                arr[n] = NULL;
            delete p;
            cout<<"\nThe entry was deleted!\n";
        }
        else
            cout<<"\nEntry not found!\n";
    }

    void display()                      // show all entries
    {
        T *p;
        for(int i=0; i < LIM; i++)
        {
            p = arr[i];
            while(p != NULL)            // traverse the chain
            {
                p->output();
                p = p->next;
            }
        }
    }

    void feed_data(char **s, int num)       // input from string array
    {
        T *np;
        char nm[NAME];
        int mk;
        for(int i=0;i<num;i++)
        {
            np = new T;
            string2Name(s[i], nm);
            mk = string2Num(s[i]);
            np->input(nm, mk);
            add_node(np);
        }
    }
};

/* Returns: void
 *
 * Function to reduce a string to a hash of the requested length.
 * Hash only contains the letters: a-z
 * (hval must be at least LEN + 1 bytes)
 */
void hash(char *str, char *hval, int Max)   // generate the hash
{
    int i, j = 0, k, l = strlen(str), m;
    long temp;
    for(i=0; i < Max; i++)
        hval[i] = 'a';
    hval[Max] = '\0';
    for(i=0; i < l; i++)
    {
        if(str[i] > 64 && str[i] < 91)
            str[i] += 32;
        if(str[i] < 97 || str[i] > 122)
            continue;
        k = j + str[i] - 97;
        for(; j <= k; j++)              // alter values from position j to k
        {
            m = j%Max;
            temp = hval[m] + (i + 1)*(m + 1)*str[i];
            if(temp >= 123)
                temp = 97 + (temp - 123)%26;
            hval[m] = temp;
        }
        j %= Max;
    }
}

/* Returns: int
 * key value of the hash
 *
 * Function to reduce the hash to a numeric key
 */
int key(char *h)    // reduce hash to key
{
    int ret = 0;
    for(int i=0; i < LEN; i++)
        ret += (h[i] - 97)*(1 + LEN/(i+1));
    return ret;
}

/* Returns: void
 *
 * Function to retrieve the name at the start of a string
 * (nam must be exactly NAME bytes)
 */
void string2Name(char *str, char *nam)  // get name from string
{
    int l = strlen(str);
    for(int i=0; i < l; i++)
    {
        if(str[i] != ',')               // name and marks are comma separated
            nam[i] = str[i];
        else
        {
            nam[i] = '\0';
            break;
        }
    }
}

/* Returns: int
 * integer at the end of the string
 *
 * Function to retrieve the number at the end of the string
 * (Negative integers allowed)
 */
int string2Num(char *str)           // get integer from string
{
    int res = 0, l = strlen(str);
    for(int i=l-1; i >= 0; i--)
    {
        if(str[i]=='-')             // negative integer
            res *= -1;
        if(str[i] > 47 && str[i] < 58)
            res += (str[i] - 48)*pow(10, l-i-1);
        else break;
    }
    return res;
}

int filereader(char **s)            //Read lines from a file to array of strings
{
    fstream f;
    char fname[NAME];
    cout<<"\nEnter name of text file (without .txt): ";
    cin>>fname;
    f.open(fname,ios::in);
    if(f.fail())
    {
        cout<<"\nERROR: Could not open file!\n";
        exit(0);
    }
    int num = 0;
    while(f.good())                 // read file contents to string array
    {
        s[num] = new char[BUF];
        f.getline(s[num], BUF);
        num++;
    }
    f.close();
    return num;
}

int main()                  // build and use htable<node>
{
    char str[NAME], **s;
    node *np;
    htable<node> ht;
    int c;
    do                          // program loop
    {
        cout<<"\n\nHASHTABLE PROGRAM:\n\n1. Add new entry\n2. Find an entry\n"
            <<"3. Delete an entry\n4. Add from file\n5. Display all contents\n";
        cin>>c;
        switch(c)
        {
            case 1:             // add a new entry
            {
                np = new node;
                cout<<"\nEnter name (no spaces): ";
                cin>>str;
                cout<<"Enter marks: ";
                cin>>c;
                np->input(str, c);
                ht.add_node(np);
                break;
            }
            case 2:             // search for an entry
            {
                cout<<"\nEnter the name to search: ";
                cin>>str;
                ht.find_node(str);
                break;
            }
            case 3:             // delete an entry
            {
                cout<<"\nEnter the name to delete: ";
                cin>>str;
                ht.del_node(str);
                break;
            }
            case 4:             // read comma separated data from file
            {
                c = filereader(s);
                ht.feed_data(s, c);
                break;
            }
            case 5: ht.display();   // display entire hashtable
            default:;
        }
        cout<<"\nDo you want to continue? (0/1)";
        cin>>c;
    }while(c != 0);
}