//********************************************************************
// authors - David Samaan, Melinda Davis, Irinca Oros                *
// purpose - hashing using chaining                                  *
// A millisecond is used to time each of these operations.           *
// A probe count is also given for each of these operations.         *
// A probe is counted every time the key value is compared to a      * 
// hashtable position.                                               *
//********************************************************************
#include <iostream.h>
#include <stddef.h>
#include <fstream.h>
#include <stdlib.h>
#include <time.h>
#include <sys/timeb.h>

struct chainnode
{
	 int item;
	 chainnode* next;
};
//******************* Prototypes ****************************
void hash_table_insert ( int*, int );
void init_hashtable ( );
void deleteitem ( int*, int );
long mstimer();

//******************* Variables *****************************
chainnode* hashtable [75];
typedef int boolean;
boolean success;
const int arraysize = 150;
const int partialsize = 50;
int probe;

//******************************************************************
void hash_table_insert ( int* array, int array_size )
// purpose - places items in array[array_size] to a hashtable, for each
// called by - main
// calls - nothing
// pre - hashtable is initialized, pointers point to NULL
// post - hashtable filled, last link pointers point to NULL and
//        array is unchanged
{
	chainnode* temp;
	int key;

    probe = 0;

	for ( int index = 0; index < array_size; index++ )
	{
		key = array [index]  % 75;
		// create a new node
		temp = new chainnode;

		success = boolean ( temp != NULL );
		if ( success )
		{
        	probe++;
			temp -> item = array[index];
			temp -> next = hashtable [ key ];
			hashtable [ key ] = temp;
		} // end if
		else cout <<"prog error1 " ;
	} // end for
    cout<<"Number of probes to insert "<<array_size<<" items: "<< probe
		<<endl <<endl;
} // end hashtable insert

//******************************************************************
void deleteitem ( int* array, int array_size )
// purpose - removes items found in an array from hashtable, for each
//			 comparison the variable "probe" is incremented
// called by - main
// calls - nothing
// pre - hashtable is initialized, last link pointers point to NULL
// post - hashtable with fewer items, last link pointers point to NULL and
{	int key,value,index;
	chainnode* tempptr;
	chainnode* delptr;

	for ( index = 0; index < array_size; index++ )
	{
		key = array[index] % 75; // hash function
		value = array [index];   // value that will be deleted
		tempptr = hashtable [ key ]; //

		if (tempptr->item == value) //if item is first item in table
		{
			probe++;
			delptr = tempptr;
			hashtable[key] = hashtable[key] -> next;
			delete delptr;
		} // end if

		else if (tempptr == NULL)
		{
			probe++;
		}

		else
		{
			probe = probe + 2; // for if and else if statements above
			while ( tempptr->item != value && tempptr != NULL )
			{
				probe++;
				delptr = tempptr;
				tempptr = tempptr -> next;
			} // end while
			delptr-> next = tempptr -> next;
			delete tempptr;
		} // end else
	} // end for
}// end delete


//******************************************************************
void init_hashtable ( )
//purpose-
//called by-main
//calls nothing
//pre-hashtable is defined and empty
//post-hashtable first pointers point to NULL;
{
	// Initialize each ptr to NULL
	for ( int i = 0; i < 75 ; i++ )
	{
		hashtable [ i ] = NULL;
	}
} // end init_hashtable


//******************************************************************
long mstimer ( )
//purpose-returns bios time in milliseconds
//called by main
//calls nothing
{
	struct timeb f;
	ftime(&f);
	return f.time%86400*1000+f.millitm;
}	// end mstimer