-------filename: hash tab.cpp --------------

#include "hash_tab.h"
#include <fstream.h>
#include <string.h>
#include <stdlib.h>  //for atoi()

hash_table::hash_table(void)
{
    for(int i=0; i<79; i++)
        table[i] = new link_node(0, "", 0);  //point all nodes to null in table
}

hash_table::~hash_table()
{
    for(int i=0; i<79; i++)                //step through chains
    {
        link_node* cursor = table[i];
        link_node* temp_cursor;
        while(cursor != 0)              //search chain for nodes
        {
            temp_cursor = cursor->next;
            delete cursor;                 //delete a node
            cursor = temp_cursor;
        }
    }

}

void hash_table::add_node(char key[], int position)
{
    int hash_number = hash_key(key);              //find out what chain will hold new node
    link_node* cursor = table[hash_number]->next; //set cursor to 1st node in chain
    link_node* last_cursor = table[hash_number]; //keep track of the previous node
    link_node* new_node;
    new_node = new link_node(0, key, position);  //create new node, point it to NULL

    while(cursor != 0)            //step through each chain of nodes
    {                             //until the end of the chain is found
        last_cursor = cursor;
        cursor = cursor->next;
    }
    last_cursor->next = new_node;   // make end of chain point to the added node
}

void hash_table::remove_node(link_node* remove)
{
    int table_index = hash_key(remove->record_key); //find out what chain conatins node to be removed
	link_node* ptr=table[table_index];              //set a node pointer to point to chain
   while(ptr->next!=remove)                         //find out what node is before node to be removed
   	  ptr = ptr->next;
   ptr->next = remove->next;     //set node before node to be removed to point to node after node to be removed

    delete remove;
}

             // ------ legened to file coding ->   ~  start of chain
                                                // |  beginning of a record_key
void hash_table::save_to_file(char* file_name)  // #  beginning of file_position
{                                               // ^  end of a node
    fstream output_file(file_name, ios::out);

    for(int i=0; i<79; i++)                //step through all chains
    {
        output_file << "~";
        link_node* cursor = table[i]->next;
        while(cursor != NULL)              //visit each node in chain
        {
            output_file << "|";
            output_file << cursor->record_key << "#";     //write record_key to file
            output_file << cursor->file_position << "^";  //write file_position to file
            cursor = cursor->next;
        }
    }
}

void hash_table::load_from_file(char* file_name)
{
    fstream input_file(file_name, ios::in);
    char input_char = input_file.get();      //used to input char by char from rfile
    char input_key[20];
    char input_position[3];   //store file position when inputed form file
    int table_index = -1;

    while(input_char != EOF)        //input until EOF is reached
    {
      if(input_char == '~')          // ~ = new chain
      {
      	table_index++;                   //advance to next chain
      	input_char = input_file.get();   //get the next char in the file
      }
      else if(input_char == '|')     // | = beginning of a record field
      {
         input_char = input_file.get();
         for(; input_char!= '~'; input_char = input_file.get())
         {
            if(input_char == '|')              //not part of the record field
                input_char = input_file.get(); //so get the next char
            if(input_char == EOF)
                break;         //end of file is reached
            int i=0;
         	for(; input_char!= '#'; input_char = input_file.get())  // # = file position follows
            {
               input_key[i++] = input_char;   //store char of record field
            }
            input_key[i] = '\0';   // terminate input_key string
            i = 0;
            input_char = input_file.get();
            for(; input_char!= '^'; input_char = input_file.get())  //input until end of node is reached
            {
               input_position[i++] = input_char; //input the file position
            }
            input_position[i] = '\0';    // terminate input_position string
            add_node(input_key, atoi(input_position));  //add the node to the table
            input_char = input_file.get();    //get the next char in file
         }
      }
    }
}

link_node* hash_table::search_table(char key[])
{
    link_node* cursor = table[hash_key(key)]->next;  //set cursor to first node in chain
    while(cursor!=0)     //loop while the end of the chain is not reached
    {
         for(int i=0; ; i++)
        {
           if((cursor->record_key[i]==' ' || cursor->record_key[i]=='\0')
                    && key[i]==' ' || key[i]=='\0')
             return cursor;           //the keys match so a pointer to the node containing key is returned
           if(cursor->record_key[i] != key[i])  //if the keys to not match
             break;
        }
        cursor = cursor->next;   //advance to next node in chain
    }
    return 0;     //if key is not found return a null pointer

}

int hash_table::zero_length_nodes()
{
   int total = 0;
	for(int i=0; i<79; i++)                //step through all chains of hash table
    {
        if(table[i]->next == 0)        //check to see if chain is empty
        	total++;
    }

    return total;
}

int hash_table::hash_key(char key[])
{
    int total = 0;
    for(int i=0; key[i] != '\0' && key[i] != ' '; i++)  //sum the values of all character
    	total += key[i];                        //in the primary key

    return (total%79);         //hash into table of 79 slots
}



------- hash tab.h ----------------

#include "link_node.h"

class hash_table
{

    public:
        hash_table();
        ~hash_table();
        void add_node(char key[], int position);
        void save_to_file(char* file_name);    //save hash table to file
        void load_from_file(char* file_name);  //loads hash table from file
        int zero_length_nodes();               //returns # of empty chains in table
        void remove_node(link_node* remove);   //removes a record from table
        link_node* search_table(char key[]);   //returns pointer to first node containing key
        int hash_key(char key[]);

    private:
        link_node* table[79];   //container of hash table chains


};


------- link node.cpp -------------
#include "link_node.h"
#include <string.h>    //for strcpy()

link_node::link_node(link_node* n, const char key[], const int position)
{
    next = n;
    strcpy(record_key, key);    //copy key to the record key
    file_position = position;
}


-------- link node.h --------------
class link_node
{
    public:
        link_node* next;
        char record_key[20];
        int file_position;
        link_node(link_node*, const char key[] , const int position);

};