/////////////////////////////////////////////////////////////////////////
//  Sohail Hirani                                                      //
//  Linear Probing, Double hash and Seperate Chaining C source codes   //
//  sohail_ah @ yahoo.com                                              //
/////////////////////////////////////////////////////////////////////////

//Define type longnode with long int data field and next pointer
struct longnode {
	long int data;
	struct longnode *next;
};

typedef struct longnode longnode;


//Linear probing insertion function.
//Will return 1 when succesful and 0 on error
int LPInsert(
			 long key, 
			 long LPTable[], 
			 long size, 
			 long & probes	// Make this a reference cause the varibale needs to change in main program 
){

	long i = key % size;
	while( LPTable[i] != -1) {
		i = (++i) % size;
		if(i == (key % size))  // Completed a cycle isn't any space left
			break;
		probes++;
	}
	probes++;
	if( LPTable[i] == -1) {
		LPTable[i] = key;
		return 1;
	}else
		return 0;
}




//Double hashing insertion function.
//Will return 1 when succesful and 0 on error
int DHInsert(
			 long key, 
			 long DHTable[], 
			 long size, 
			 long DHValue,
			 long & probes	// Make this a reference cause the varibale needs to change in main program 
){

	long i = key % size;
	long j = key % DHValue;
	j = j < 1 ? 1 : j;

	while( DHTable[i] != -1 ) {
		i = (i + j) % size;
		if(i == (key % size))  // Completed a cycle aint any space left
			break;
		probes++;
	}
	probes++;
	if( DHTable[i] == -1) {
		DHTable[i] = key;
		return 1;
	}else
		return 0;
}


//Separate Chaning insertion function.
//Will return 1 always (well not always 
// in case memory is full it will return 0)
int SCInsert(
			 long key, 
			 longnode* SCTable[], 
			 long size, 
			 long & probes	// Make this a reference cause the varibale needs to change in main program 
){

	long i = key % size;
	longnode *dataNode = NULL;

	dataNode = new longnode[1];
	if( dataNode == NULL )
		return 0;
	dataNode->data = key;
	dataNode->next = SCTable[i];
	SCTable[i] = dataNode;
	probes++;
	return 1;

}


//Linear probing find function.
//Will return true when succesful and false otherwise
bool LPFind(
			 long key, 
			 long LPTable[], 
			 long size, 
			 long & probes	// Make this a reference cause the varibale needs to change in main program 
){

	long i = key % size;
	while( (LPTable[i] != -1) && (LPTable[i] != key)) {
		i = (++i) % size;
		if(i == (key % size))  // Completed a cycle key isn't there
			break;
		probes++;
	}
	probes++;
	if( LPTable[i] == key) 
		return true;
	else
		return false;
}




//Double hashing find function.
//Will return true when succesful and false otherwise
bool DHFind(
			 long key, 
			 long DHTable[], 
			 long size, 
			 long DHValue,
			 long & probes	// Make this a reference cause the varibale needs to change in main program 
){

	long i = key % size;
	long j = key % DHValue;
	j = j < 1 ? 1 : j;		// in case j==0  we could have bad results

	while( (DHTable[i] != -1) && (DHTable[i] != key) ) {
		i = (i + j) % size;
		if(i == (key % size))  // Completed a cycle key isn't there
			break;
		probes++;
	}
	probes++;
	if( DHTable[i] == key) 
		return true;
	else
		return false;
}


//Separate Chaning find function.
//Will return true when succesful and false otherwise
bool SCFind(
			 long key, 
			 longnode* SCTable[], 
			 long size, 
			 long & probes	// Make this a reference cause the varibale needs to change in main program 
){
	long i = key % size;
	longnode *node = SCTable[i];

	probes++;		// Cause atleast one test is done even if location in table is null
	while(node) { // i.e., while( node != NULL )
		if(node->data == key) {
			return true;
		}
		probes++;
		node = node->next;
	}
	return false;
}

// Deletes the nodes in the link list
void clear( longnode* start ) { 
	longnode *node = start;
	longnode *next = start;
	while( node ) {
		next = node->next;
		delete[] node;
		node = next;
	}
}

// Deletes all lists from SCTable
void deletenodes(
				 longnode* SCTable[], 
				 long size
){
	long i;
	for( i = 0 ; i < size; i++ ) {
		clear(SCTable[i]);
	}
}