Your are to implement the Dynamic Hashing Algorithm, as discussed in class
and posted in the course notes on the web using appropriate C++ classes. 

You are to structure your main program to accept and interpret file input
with the following format:

You will need to write your program to first accept the power of 2 (from
the input file, on the first line) that will be used for the hash function
mod value.  Be sure to return an error to the user if they do not enter a
power of 2 and then halt execution of (exit) the program.  Return the
error to the output
file.  The next line on the input file will be the bucket size to be used
for each bucket.

Listed below are the possibilities for the different categories of
commands that will follow the above 2 lines: 

I      Integer_Key             To "insert" the integer to the appropriate
       Dynamic Hash structure bucket appropriately. 

D      Integer_Key             To "delete" the integer from its Dynamic
       Hash structure bucket appropriately.
 
S      Integer_Key             To "search" for the integer key.  For a
       successful search a pointer to the bucket that contains that
       contains the key will be returned.   For an unsuccessful search, a
       NULL pointer will be returned. 

P      To print out the contents of each bucket in the tree, by following
       an inorder traversal.   Print out the pseudokey for each
       bucket prior to printing out the contents of the bucket.  The first
       pseudokey to be printed will be all zeros, and then go from there
       with your inorder traversal steps. 

You will, of course, need to write a hash function, and you will need to
create a Dynamic_Hash class that has at least the following member
functions: 
     
     Constructor 
     Destructor 
     Insert 
     Delete 
     Search 
     Print 

Note:  You will also need to implement "chaining to overflow buckets" as
discussed in class and shown in the course notes.
Output: Send your output for this program to a file.  For inserts, it is
an error to insert a duplicate value in the Hash structure, be sure to
notify the user of such an attempt.  Tell the user if an operation is
successful, as well.

Be sure to give appropriate "error" messages back to the user of your
program, via the output file.  For e.g., if asked to delete a value from
the Hash structure that is not found in the structure, you should reply
that the value was not foundand so could not be deleted.  For the Search
operation, as well as returning the appropriate pointer as described
above, if the item being sought is found, print out a message that says
you found it and what its value is.  On the other hand, if the item is not
found, print out a message to that effect.

Also Note: You are responsible to write a program that deals with *all
cases*.  That is, your program should not only *work good on some input
files*, itneed to work on *all possible* input files.  This means it is
not your TAs responsibility to give you an input file that allows your
program to work.  It is your responsibility to write code that cannot be
broken by any input file and so will work in all cases.  This will be the
case for every program you write for this course.

A sample file follows that adheres to the input file format:

8

5

I  46

I 55

I 88

P

S 46

S 99

I 99

D 50

S 200

I 200

D 55

P

I 120

I 200

I 300

I 400

I 500

S 300

P

D 600

D 500

Program Source Code

//      File name: Bucket.h
//	Programmer: Abid Akbar
//	********************************************************************************
//  CLASS NAME: Bucket
//  Purpose: 
//  To construct a bucket.
//  Description: 
//  It is to construct a bucket. Bucket size is obtained dynamically from
//  the user. Item_ptr is a pointer which points to an array of data inserted in the bucket.
//  Sign_ptr is a pointer which points to an array of true/false values. A true value in any
//  slot of an array indicates that the slot is not empty and vice versa. Next_Bucket is a pointer which 
//  points to the next bucket, in case of overflow buckets. If no overflow bucket then it will 
//  be null 
//  ***********************************************************************************
//	CONSTRUCTOR for the Bucket Class
//  struct Bucket
//  {
//  int *Item_ptr;
//  bool *Sign_ptr;
//  Bucket *Next_Bucket;
//  };

#ifndef BUCKET_H
#define BUCKET_H

struct Bucket
{
int *Item_ptr;
bool *Sign_ptr;
Bucket *Next_Bucket;

Bucket(int);
};

#endif                




//  FILE: Bucket.cpp
//  Class Implemented: Bucket
#include <stdlib.h>
#include "Bucket.h"


               Bucket::Bucket(int Bucket_Size)
               {
               int i;
			   
			   Item_ptr = new int[Bucket_Size];
			   Sign_ptr = new bool[Bucket_Size];
               for (i=0;i<Bucket_Size;i++)
			   {
                 Item_ptr[i]=0;
                 Sign_ptr[i]=false;
               }
               Next_Bucket = NULL;
               }                           


//	File Name: Hash.h
//	Programmer: Abid Akbar
//	Section: csci 151-02
//	******************************************************************************************
//	Class Name: Hash
//	Purpose:
//	It is to define and implement various functions which shall be use to Insert, Delete,
//	Print, Search various entries.
//	Description:
//	Hash class includes all those functions which we will be using in our program for carrying out
//	different operations. 
//	********************************************************************************************
// FILE: Hash.h
// Class Provided: Hash.h
//
// CONSTRUCTOR for the Hash Class
// Hash (int Bucket_Size)
//
// Destructor for Hash Class
// ~Hash()
//
// Node* Traverse(Node* Cur_ptr, int Key)
//
// Void Insert(int Key, Node* Cur_ptr)
//
// Bucket* Search(int Key, Node* Cur_ptr)
//
// Void Delete(int Key, Node* Cur_ptr)
//
// Void Print(Node* Cur_ptr)
//                                          
// int* HashConvert (int Key, int ModVal, int Power)
//
#ifndef HASH_H
#define HASH_H
#include<stdlib.h>
#include<iostream.h>
#include "Node.h"
#include "Bucket.h"
#include <fstream.h>

class Hash 
{
  private:
  int Bucket_Size;
  int ModVal;
  int Power;
  Node * root_ptr;

  public:
	  ofstream outfile;
  // Constructor
  Hash (int Bucket_Size, int ModVal, int Power);
  // Destructor
  ~Hash();
  //Member Functions
  Node* Traverse(int Key);
  void Insert(int Key);
  Bucket* Search(int Key);     
  Bucket* Search2(int Key);
  void Delete(int Key);
  void Print();
  void Print2(Node * ptr);
  int* HashConvert(int Key);
  int Depth(int Key);
  void ItemDeletion(int Number, Bucket * Bucket_ptr);
  Node* Parent(int Key);

};
#endif                                          
 

//FILE: Hash.cpp
//Class Implemented: Hash
#include "Hash.h"

//	*********************************************************************************************
//	Function: Constructor
//	Purpose: To construct a node and a bucket. middle pointer of node points to the bucket.
//	FUNCTIONAL DESCRIPTION: It constructs one node and one bucket.
//	OPERATIONAL DESCRIPTION: A bucket is constructed having bucket size equal to the size peovided by the user
//	A node is also constructed, middle pointer of the node points to the bucket.
//	ModVal and Power are also passed to the function.
//	Pre-Condition: Bucket size must be provided by the user.
//	Post-Condition: A Bucket and a node is constructed.
//	********************************************************************************************


Hash::Hash(int bucket_size, int modval, int power)
{
  Bucket_Size = bucket_size;
  ModVal = modval;
  Power = power;
  root_ptr = new Node;
  root_ptr->left = NULL;
  root_ptr->right= NULL;
  root_ptr->middle = new Bucket(bucket_size);
}

//	*************************************************************************************************
//	Function: Destructor
//	Purpose: To de-allocate the memory.
//	Post-Condition: It de-allocates the memory
//	*************************************************************************************************

Hash::~Hash()
{
}

//	**************************************************************************************************
//	Function: HashConvert
//	Purpose: To convert the given number, after getting its Mod, to a binary array of length eqaul to Power.
//	Functional Description: It converts the given number to an array.
//	Operational Description: It takes the given number, get its Mod by using ModVal.IF and ELSE
//	combination is used to convert the given outcome to bit array.
//	Pre-Condition: Maximum depth(Power) of the tree must be known
//
//	**************************************************************************************************

int * Hash::HashConvert(int key)
{ 
  int i;
  int *bit_ptr = new int[Power];
  int test=(key%ModVal);
  for (i=1;i<=Power;i++)
  { 
      if (test <=0)
	  {
		  bit_ptr[Power-i]=0;
//          cout << "0";  
	  }
	  else 
	  {
          bit_ptr[Power-i]=test%2;
//         cout<<test%2;
	  }
	test=(test/2);
   }
  cout << endl;
  return bit_ptr;
}




//	******************************************************************************************************
//	Function: Insert
//	
//	Purpose: To Insert a particular number in the database
//	
//	Functional Description: It takes a given number and puts it into the tree at appropriate place.
//	
//	Operational Description: Search function is used to know that the number does not already exist. 
//	Traverse function is used to reach to the node with which the bucket, where number should be entered, is 
//	present. If there is any empty place in bucket, number is entered there. 
//	In case no empty place is found, the Depth function is used to evaluate the current depth.
//	If the current depth is equal to maximum depth, then overflow bucket is reached and number id placed
//	there, if no overflow bucket is found or is full, a new one is created and record is placed there.
//	If current depth is not equal to maximum depth, then middle pointer of node with which bucket is attached 
//	is set to NULL and two new nodes and buckets are created. Temporary bucket is created and all
//	entries of old deleted bucket are put there along with the new entry to be inserted. After creation of 
//	two new Buckets, entries of temporary bucket are re-hashed and entered into the new buckets.
//	
//	Pre-Condition: A tree must be present along with at least one node and one bucket.
//	
//	Post-Condition: Number is enterd into the bucket. It can be a newly created bucket or old bucket
//	(depends if old bucket is found empty)
//	*****************************************************************************************************


void Hash::Insert(int Key)
{

  bool Inserted=false;
  int * data_ptr = new int[Bucket_Size+1];
  Bucket * Bucket_ptr = Search2(Key);
//  cout<<"coming from insert function"<<endl;
  if (Bucket_ptr == NULL)
  {
		outfile<<"Operation I "<< Key<< " is done successfully"<<endl<<endl;
		Node * Cur_ptr=Traverse(Key);  
        int Cur_Depth = Depth(Key);   // to determine the current depth of the tree for this Key
		for (int i=0;i<Bucket_Size;i++)  // if there is any space in the first bucket Cur_ptr -> middle, insert the Key
			{ 
				if ((Cur_ptr->middle->Sign_ptr[i])==false)
					{      
						Cur_ptr->middle->Item_ptr[i]=Key;
						Cur_ptr->middle->Sign_ptr[i]=true;
						Inserted=true;
						return;
					}
			}
        
		if (Cur_Depth == Power)
        {
		    Bucket_ptr=Cur_ptr->middle;	
			while(!Inserted)
				{ 
				
					if (Bucket_ptr->Next_Bucket == NULL) // The last bucket and also no overflow buckets
						{
							Bucket_ptr->Next_Bucket = new Bucket(Bucket_Size); // make an overflow bucket and insert Key
							Bucket_ptr->Next_Bucket->Item_ptr[0] =Key;
							Bucket_ptr->Next_Bucket->Sign_ptr[0] =true; 
							Inserted = true;        
							Bucket_ptr=Bucket_ptr->Next_Bucket;
							return;
						}
					else
						{
							Bucket_ptr=Bucket_ptr->Next_Bucket; // else move to the next bucket which is an overflow bucket 
							for (i=0;i<Bucket_Size;i++)         // try to find an empty space in this bucket and insert the Key
								{ 
									if (Bucket_ptr->Sign_ptr[i]=false)
										{   
											Bucket_ptr->Item_ptr[i]=Key;
											Bucket_ptr->Sign_ptr[i]=true;
											Inserted = true;
											return;
										}
								}
						}
				}
		}
        if (Cur_Depth !=Power)
			{  
               for (i=0;i<Bucket_Size;i++)
					{
						data_ptr[i]=(Cur_ptr->middle->Item_ptr[i]); // move all entries of the bucket to a temporary bucket
					}
						data_ptr[Bucket_Size]=Key; // put Key also in the temporary bucket.
             
	                   while (Cur_Depth!=Power)
					   {
                                
								
								int left= 0;
								int right = 0;
								Cur_ptr->middle = NULL;    
								Cur_ptr->left = new Node;        // creation of new nodes and new Buckets
								Cur_ptr->right = new Node;
								Cur_ptr->left->middle = new Bucket(Bucket_Size);
								Cur_ptr->right->middle = new Bucket(Bucket_Size);
								Cur_Depth ++;

									for (i=0;i<=Bucket_Size;i++)   // inserting the values from temporary bucket to new buckets
										{
											Node * Node_ptr = Traverse(data_ptr[i]);
											
										
											if (Node_ptr == Cur_ptr->left)
												{

														if(left >= Bucket_Size)
															{
																Cur_ptr = Node_ptr;
																break;
															}
														else
															{  
					   											
																Node_ptr->middle->Item_ptr[left]=data_ptr[i];
																Node_ptr->middle->Sign_ptr[left]=true;
																left++;
															
															}
												}
				 
											if (Node_ptr == Cur_ptr->right)
												{

													if(right >= Bucket_Size)
													{
														Cur_ptr=Node_ptr;
														break;
													}
													else
													{  

												
														Node_ptr->middle->Item_ptr[right]=data_ptr[i];
														Node_ptr->middle->Sign_ptr[right]=true;
														right++;
													
													}
												}
										}
							if ((left+right)> Bucket_Size) 
							return;
					   }
											
				    if (Cur_Depth == Power) // if Current Depth becomes equal to power after many loops then make an overflow bucket to insert Key.
					{
						Bucket_ptr=Cur_ptr->middle;
						Bucket_ptr->Next_Bucket = new Bucket(Bucket_Size);
						Bucket_ptr = Bucket_ptr->Next_Bucket;
						Bucket_ptr->Item_ptr[0] =data_ptr[Bucket_Size];
						Bucket_ptr->Sign_ptr[0] =true; 
						Inserted = true;        
						return;
					}
			 }

			
		}
		else 
		{	outfile<<Key<< " is already in the database, duplication is not allowed"<<endl<<endl;}
return;
}

//	******************************************************************************************************************
//	Function: Delete
//	Purpose: To delete the given entry, if it is present, from the database.
//	Functional Description: It deletes the given entry from the database.
//	Operational Description: Entry to be deleted is first Searched in the database by using the
//	search function. It the entry is not found then message is given that entry does not exist. If 
//	entry is found then, Traverse function is used which points to the node with which the bucket 
//	or overflow bucket(s) containing the entry is attached. Depth function is used to obtain the current depth.
// 
//	Current Depth is evaluated against the Depth allowed. 
//	If entry is found in the very fist bucket, to which the pointer of traverse function is pointing,it is deleted 
//	using ItemDeletion function.After its deletion, if both companion buckets have no 
//	overflow buckets then both buckets are evaluated to ckeck the number of entries. If number of entries
//	are  less than or equal to bucket size, then both buckets are deleted and nodes within which they are attached
//	are also deleted. A temporary bucket is created and all entries are entered into it. A new bucket is 
//	created which is attached to the parent node of deleted nodes.
//	
//	If entry is found in an over flow bucket, then it is deleted and the very last entry of the the last overflow 
//	bucket is moved to that place. In case the entry deleted is the entry of the last bucket and it is the only entry
//	then the bucket is deleted.
//	PRE-CONDITION: A Hash tree is already constructed and having at least one node and one Bucket. 
//	POST-CONDITION: If the entry is found in any bucket, it is deleted and replaced with the last entry of the bucket and 
//	in case of overflow buckets, it is replaced by the last entry of the last bucket. Buckets can coalsce if condition 
//	permits.
//  ********************************************************************************************************************      


void Hash::Delete(int Key)
{
	int countright=0;
	int countleft=0;
	int Number;
	int number4;
	int * temp_ptr = new int[Bucket_Size];
	int i=0;
	bool foundnumber = false;
	bool found=false;
	int countfalse=0;
	Bucket * Bucket_ptr_temp;
	Bucket * Bucket_ptr = Search2(Key);

	
	if (Bucket_ptr == NULL)
	{	
		outfile<<Key<< " not in the database nothing to delete"<<endl<<endl;
		return;
	}
	else
	{	
		outfile<<"Operation D "<<Key <<" is done successfully"<<endl<<endl;
		int Cur_Depth = Depth(Key);
		Node * Cur_ptr = Traverse (Key);
		Node * Parent_ptr = Parent (Key);
		
		if (Cur_Depth == Power)	
		{
			if (Parent_ptr->left == Cur_ptr)
				Bucket_ptr = Parent_ptr->left->middle;
			if (Parent_ptr->right== Cur_ptr)
				Bucket_ptr = Parent_ptr->right->middle;
			if (Bucket_ptr->Next_Bucket == NULL)
			{ 
				for (i=0;i<Bucket_Size;i++)
				{
					if (Bucket_ptr->Item_ptr[i]==Key)
					{
						Number = i ;
						
						break;
					}
				}
				ItemDeletion(Number, Bucket_ptr); // Use of ItemDeletion function to delete the Key
				
				for (i=0;i<Bucket_Size;i++)
				{
					if ((Parent_ptr ->left->middle->Sign_ptr[i]) == true)
						countleft++;
					if ((Parent_ptr ->right->middle->Sign_ptr[i]) == true)
						countright++;
				}

				if ((Parent_ptr ->left->middle->Next_Bucket==NULL) && (Parent_ptr ->right->middle->Next_Bucket==NULL) && ((countleft + countright) <= Bucket_Size))  // condition to determine that collapse of two buckets is possible or not
				{	
					for (i=0;i<countleft;i++) // collapse is possible and therefore destroy the two buckets and two nodes, move all entries to temporary bucket
					{
						temp_ptr[i]= (Parent_ptr ->left->middle->Item_ptr[i]);
					}
					for (i=countleft;i<(countleft+countright);i++)
					{
						temp_ptr[i] = (Parent_ptr ->right->middle->Item_ptr[i]);
					}

					Parent_ptr ->left = NULL;
					Parent_ptr ->right = NULL;
					Parent_ptr->middle = new Bucket(Bucket_Size);

					for (i=0;i<Bucket_Size;i++)
					{
						Parent_ptr->middle->Item_ptr[i]=temp_ptr[i]; // put entries from temporary bucket to new bucket
						Parent_ptr->middle->Sign_ptr[i]=true;
						return;
					}
				}
			}

			else  
			{
				while(Bucket_ptr!=NULL)  // loop until reaches to the bucket containing the Key.
				{
					
					for (i=0;i<Bucket_Size;i++)
					{
						if (Bucket_ptr->Item_ptr[i]==Key)
						{
							Number=i;
							found=true;
							break;
						}
					}
				
				if (found == true)
				   break;
				
				else
				Bucket_ptr=Bucket_ptr->Next_Bucket;
				}
				
				if (Bucket_ptr->Next_Bucket == NULL) //last bucket of the linked list
				{
						ItemDeletion(Number, Bucket_ptr);
						for (i=0;i<Bucket_Size;i++)
						{
							if (Bucket_ptr->Sign_ptr[i]==false)
								countfalse++;
						}
						if(countfalse==Bucket_Size)
						{
							Bucket_ptr=NULL;
							return;
						}
				}


				else // not the last bucket of the linked list		
				{	
					Bucket_ptr_temp = Bucket_ptr; // make a temporary pointer pointing to the bucket containing the Key
					while (Bucket_ptr->Next_Bucket!=NULL) // loop to reach the last bucket
					{
						Bucket_ptr= Bucket_ptr->Next_Bucket;
					}
					for (i=0;i<Bucket_Size;i++)  // find last entry of last bucket and put it in the place of Key in bucket pointed by temporary pointers
					{
						if ((Bucket_ptr->Sign_ptr[i])=false)
						{
							number4=i-1;
						    foundnumber=true;
							break;
						}
					}
					if (foundnumber == true)
					{
						if (number4 == 0) // if this is the case then Bucket_ptr = NULL, so last bucket is deleted, after moving the value out of it
						{
						Bucket_ptr_temp->Item_ptr[Number]=Bucket_ptr->Item_ptr[number4];
						Bucket_ptr_temp->Sign_ptr[Number]=true;
						Bucket_ptr->Sign_ptr[number4]=false;
						Bucket_ptr->Item_ptr[number4] = 0;
						Bucket_ptr = NULL;
						return;
						}
						else
						{
						Bucket_ptr_temp->Item_ptr[Number]=Bucket_ptr->Item_ptr[number4];
						Bucket_ptr_temp->Sign_ptr[Number]=true;
						Bucket_ptr->Sign_ptr[number4]=false;
						Bucket_ptr->Item_ptr[number4] = 0;
						return;
						}
					}
					else
					{
						number4=(Bucket_Size-1); // if bucket is full, therefore we have to move last value of the bucket
						if (number4 == 0) // if Bucket_Size == 1
						{
							Bucket_ptr_temp->Item_ptr[Number]=Bucket_ptr->Item_ptr[number4];
							Bucket_ptr_temp->Sign_ptr[Number]=true;
							Bucket_ptr->Sign_ptr[number4]=false;
							Bucket_ptr->Item_ptr[number4] = 0;
							Bucket_ptr =NULL;						
							return;
						}
						else
							Bucket_ptr_temp->Item_ptr[Number]=Bucket_ptr->Item_ptr[number4];
							Bucket_ptr_temp->Sign_ptr[Number]=true;
							Bucket_ptr->Sign_ptr[number4]=false;
							Bucket_ptr->Item_ptr[number4] = 0;
							return;
						
					}
				}
		
			}
		}
		if (Cur_Depth != Power)
		{
			Bucket_ptr = Cur_ptr ->middle;
			
			if (Cur_Depth == 0) // only one bucket in the tree
			{
				for (i=0;i<Bucket_Size;i++)
				{
					if (Bucket_ptr->Item_ptr[i]==Key)
					{
						Number=i;
						break;
					}
				}
			ItemDeletion(Number, Bucket_ptr);
			return;
			}
			
			if ((Parent_ptr ->left == Cur_ptr) || (Parent_ptr -> right == Cur_ptr)) // move further to find the bucket containing the Key using Parent_ptr
			{
				for (i=0;i<Bucket_Size;i++)
				{
					if (Bucket_ptr->Item_ptr[i] == Key)
					{
						Number = i;
						break;
					}

				}
			ItemDeletion(Number, Bucket_ptr);
			}
			
			if ((Parent_ptr->left->middle !=NULL) && (Parent_ptr->right->middle !=NULL)) // checking for the possibility of collapsing the two companion buckets
			{
				for (i=0;i<Bucket_Size;i++) 
				{
					if(Parent_ptr->left->middle->Sign_ptr[i]==true)
						countleft++;
					if(Parent_ptr->right->middle->Sign_ptr[i]==true)
						countright++;
				}

				if((countleft+countright)<=Bucket_Size)
				{
					for(i=0;i<countleft;i++) // moving values from old buckets to temporary bucket
					{
						temp_ptr[i]=(Parent_ptr->left->middle->Item_ptr[i]);
					}
					for (i=countleft;i<(countleft+countright);i++)
					{
						temp_ptr[i]=(Parent_ptr->right->middle->Item_ptr[i]);
					}
					
					Parent_ptr ->left = NULL; // destroying buckets and nodes
					Parent_ptr ->right = NULL;
					Parent_ptr->middle = new Bucket(Bucket_Size);

						for (i=0;i<Bucket_Size;i++) // putting values from temprary bucekt to new bucket
						{
							Parent_ptr->middle->Item_ptr[i]=temp_ptr[i];
							Parent_ptr->middle->Sign_ptr[i]=true;
						}

				}
			}
		}
	}
	return;
}


//	******************************************************************************************************
//	function: Search
//
//	Purpose: To search the given number
//
//	Functional Description: The function searches the provided number in the database.
//
//	Operational Description: The function first make use of Traverse function to reach to the node
//	within which the bucket having the number of should have the number is attached. The function then searches 
//	each entry of the bucket matching with the given number. If bukcet is having overflow buckets then those are
//	also checked. If no matching entry is found, NULL is returned.
//
//	Pre-Condition: A bucket and node must be created.
//
//	Post-Condition: If search is successful, then Bucket_ptr pointing to the bucket containing the record is
//	returned and if not successful, then NULL is returned.
//	*********************************************************************************************************
Bucket* Hash::Search(int Key)
{
  bool Found = false;
  Node * Cur_ptr = Traverse (Key);
  Bucket * Bucket_ptr;
  Bucket_ptr=Cur_ptr-> middle;
	while (!Found)
	{ 
    	   for (int i=0;i<Bucket_Size;i++)
    	   {    
    			if (Bucket_ptr->Item_ptr[i]==Key)
				{
					Found = true;
					break;
				}
           }
		if (Found==true)
		{
			outfile<<Key <<" is found in the database"<<endl;
			break;
		}
		else
		{
			Bucket_ptr = Bucket_ptr->Next_Bucket;
			if (Bucket_ptr== NULL)
			{
				outfile <<Key<<" is not in the database"<<endl;
				Bucket_ptr = NULL;
				break;
			}
		}
	}
return  Bucket_ptr;
}

//	*************************************************************************************************************
//	Function name: Traverse
//
//	Purpose: To traverse the tree and reach to the node within which is attached the bucket containing the desired
//	number or should contain the number.
//
//	Functional Description: To traverse the tree and reach the destination node.
//
//	Operational Description: HashConvert function is used to obtain the bit array corresponding to the number. 
//	Bit array is used to traverse the tree(if bit array entry is 0, move left or else). Traversal continues until 
//	pointer hits the node containing the bucket where the number should be persent.
//
//	Pre-Condition: Constructor is used to construct a tree with at least one node and one bucket.
//
//	Post-Condition: Pointer points to the node with which the bucket containg of should be containing the record is attached.
//	************************************************************************************************************************

Node* Hash::Traverse (int key)
{
int * bit_ptr=HashConvert(key);
Node * Cur_ptr = root_ptr;
int index=0;
int depth=0;
while(Cur_ptr -> middle ==NULL)
   {
    if (bit_ptr[index] == 0)
      Cur_ptr = Cur_ptr->left;
    else
      Cur_ptr = Cur_ptr->right;
   index++;
   depth++;
   }
return Cur_ptr;
}


//	************************************************************************************************************
//	Function name: Print
//	
//	Purpose: To print the content of the database.
//
//	Functional Description: It prints the contents of the tree.
//
//	Operational Description: It make use of inorder traversal to print the contents of the node.
//	Pre-Condition: A tree must be present.
//	Post-Condition: Contents of the tree are printed.
//
//	************************************************************************************************************
void Hash::Print()
{
	Print2(root_ptr);
}

void Hash::Print2(Node * Node_ptr)
{

	if ( Node_ptr ->middle!=NULL)
	{
			
		int index = 0;
//		int Cur_Depth = Depth(Node_ptr->middle->Item_ptr[index]);
//		int * bit_ptr = HashConvert2(Node_ptr->middle ->Item_ptr[index], Cur_Depth);
		while (Node_ptr->middle!=NULL)
		{
				for (int i=0;i<Bucket_Size;i++)
				{
					if(Node_ptr->middle->Sign_ptr[i]==true)
						outfile<<"The contents of the Bucket are: ";
						outfile<<Node_ptr->middle->Item_ptr[i]<<endl;
				}
				Node_ptr->middle=(Node_ptr->middle->Next_Bucket);
		}
	}
	else
	{
		Print2(Node_ptr ->left);
		Print2(Node_ptr ->right);
	}
}


//	*******************************************************************************************************
//	Function: Depth
//	Purpose: To determine the current depth of the tree for a particular entry.
//	FUNCTIONAL DESCRIPTION: It determines the current depth of the tree, against the given number.
//	OPERATIONAL DESCRIPTION: HashConvert function is used to change the given number to bit array. Bit array
//	is used to traverse the tree (i.e. if value in array is one, go left or else). Traversal 
//  terminates as the pointer hits the node with which the bucket containing the target number 
//	is attached. Number of traversal are recorded which gives the current depth for a particular entry.
//	PRE-CONDITION: A tree is constructed with at least one node and one bucket. 
//	POST-CONDITION: Current Depth is found using HashConvert function.
//	******************************************************************************************************* 

int Hash::Depth (int key)
{
int * bit_ptr=HashConvert(key);
Node * Cur_ptr = root_ptr;
int index=0;
int Cur_Depth=0;
while(Cur_ptr -> middle ==NULL)
   {
    if (bit_ptr[index] == 0)
      Cur_ptr = Cur_ptr->left;
    else
      Cur_ptr = Cur_ptr->right;
   index++;
   Cur_Depth++;
   }
return Cur_Depth;
}

//	**************************************************************************************************************
//	Function name: ItemDeletion
//
//	Purpose: To delete the particular entry of the bucket and move last entry to the deleted place.
//
//	Functional Description: Particular entry of the bucket is deleted and replaced with the last entry of the Bucket.
//
//	Operational Description: Particular entry needs to be deleted from the bucket. if it is only one entry in the bucket,
//	it is deleted and if it is the last entry in the bucket it is deleted and if it is somewhere in the middle, then it is 
//	replaced with the last entry of the bucket.
//
//	Pre-Condition: Array number of the entry to be deleted form bucket must be provided along with the pointer 
//	to that bucket.
//
//	Post Condition: Entry is deleted from the bucket.
//	******************************************************************************************************************

void Hash::ItemDeletion(int Number, Bucket * Bucket_ptr)
{
	int i;
	int number;
	if (Number == Bucket_Size-1)
	{
		Bucket_ptr->Item_ptr[Number]=0;
		Bucket_ptr->Sign_ptr[Number]=false;
	    return;
	}
	else
	{

		for (i=(Number+1);i<Bucket_Size;i++)
		{
			if (Bucket_ptr->Sign_ptr[i]==false)
			{
				number = (i-1);
			    break;
			}
		}

 		if (number == Number) 
		{ 
			Bucket_ptr->Item_ptr[Number]=0;
			Bucket_ptr->Sign_ptr[Number]=false;
			return;
		}
		else
		{
			(Bucket_ptr->Item_ptr[Number])=(Bucket_ptr->Item_ptr[number]);
			Bucket_ptr->Sign_ptr[number]=false;
			Bucket_ptr->Item_ptr[number]=0;
			return;
		}
	}
	return;
}


//	**************************************************************************************************************
//	Function name: Parent
//	
//	Purpose: To return a pointer to the parent node of pointer which points to the node with which the 
//	bucket conatining our desired entry is attached or should be attached. Parent function is useful in case of 
//	checking conditions of caolescing where we need to keep track of both of the companion nodes.
//
//	Functional Description: Points a pointer to the parent node.
//
//	Operation Description; Traverse function is first used to node with which the bucket containing the entry or should be containing
//	the entry is attached. Depth function is used to obtain the current depth of the tree for the given entry.
//
//	Pre Condition: Number must be provided for which the parent pointer needs to be found.
//
//	Post Condition: Parent pointer points to the node which is the parent node of the two nodes, at least one of 
//	which is containing or should be containing our given entry.
//	*************************************************************************************************************** 
Node* Hash::Parent(int Key)
{
	
	int i=0; 

	Node * Parent_ptr;
	Parent_ptr = root_ptr;
	
	Node * Cur_ptr = Traverse(Key);
	
	int Cur_Depth = Depth(Key);
	
	if(root_ptr==Cur_ptr)
		Parent_ptr= Cur_ptr;
	
	else
	{
		int * bit_ptr=HashConvert(Key);
		
		for (i=0;i<(Cur_Depth-1);i++)
		{	
			if (bit_ptr[i]==0)
				Parent_ptr= Parent_ptr->left;
			else
				Parent_ptr= Parent_ptr->right;
		}
	}

return Parent_ptr;
}

//	*****************************************************************************************************************
//	Function name: Search2
//  Note: This function is a copy of original Search function except that the it does not print any messages. It
//	is used in Insert and Delete functions.
//	******************************************************************************************************************


Bucket* Hash::Search2(int Key)
{
  bool Found = false;
  Node * Cur_ptr = Traverse (Key);
  Bucket * Bucket_ptr;
  Bucket_ptr=Cur_ptr-> middle;
	while (!Found)
	{ 
    	   for (int i=0;i<Bucket_Size;i++)
    	   {    
    			if (Bucket_ptr->Item_ptr[i]==Key)
				{
					Found = true;
					break;
				}
           }
		if (Found==true)
		{
			break;
		}
		else
		{
			Bucket_ptr = Bucket_ptr->Next_Bucket;
			if (Bucket_ptr== NULL)
			{
				Bucket_ptr = NULL;
				break;
			}
		}
	}
return  Bucket_ptr;
}


//	File Name: Node.h
//	Programmer: Abid Akbar
//  Section: csci 151-02
//	*************************************************************************************
//	Class Name: Node
//	Purpose:
//	To construct a node 
//	Description:
//	A node is constructed having three pointers: left, middle and right. Each pointer is 
//	initialized to NULL.
//	************************************************************************************** 
//
//  CONSTRUCTOR for the Node Class
//
//  struct Node
//  {
//  Node *left;
//  Bucket *middle;
//  Node *right;
//  };

#include "Bucket.h"
#ifndef NODE_H
#define NODE_H

struct Node
{
Node *left;
Bucket *middle;
Node *right;

Node();
};

#endif      

//  FILE: Node.cpp
//  Class Implemented: Node
#include "Node.h"
#include <stdlib.h>
        Node::Node()
        {
        Node *left = NULL;
        Bucket *middle = NULL;
        Node *right = NULL;
        }                  

//	File Name: Program.cpp
//	Programmer	Abid Akbar
//	Section		csci 151-02
//	*******************************************************************************************************
//	Assignment # 1
//	Program Name: Dynamic Hashing
//	Programmer: Abid Akbar
//	Course: Advanced Data Structures and Algorithms
//	Section: 02
//	Due Date: 10/02/99
//	*********************************************************************************************************
//	Decelopment Time: 
//	Estimate: 
//	Actual:
//	********************************************************************************************************
//	Grading Section:
//	Design:
//	Coding:
//	Debugging:
//	Documentation
//	**********************************************************************************************************
//	Functional Description:
//	It obtains first ModVal and Bucket Size from user and construct a small tree. Bucket Size must be greater
//	than one. ModVal must be a valid power of two.Mod is obtained for every 
//	entry to be inserted into the database. The mod is converted to bit array to obtain the destination of the
//	entry where it shall reside in the tree. Maximum depth of the tree is the power of two of the ModVal. After the 
//	tree reaches its maximum depth, buckets can overflow to accommodate additional entries.
//
//	Operational Description:
//	Various functions are used to obtain the desired results. Buckets overflow and coalescing are of special
//	importance. First of all a small tree is constructed with just on node and one bucket. As the bucket reaches
//	to its full capacity, then the depth of the tree is checked against the maximum depth, if it is less than 
//	maximum depth, then new nodes and buckets are created and tree is expanded and old plus new entries are 
//	rehashed as per bit array of eahc particulr entry. If the tree has reached to its maximum depth and additional
//	entries needs to be entered, then overflow buckets are used. Reverse provcedure is applied for deleting a particular
//	entry from the bucket.
//
//	List of Classes Used
//	1) Bucket Class
//	2) Node Class
//	3) Hash Class
//	***********************************************************************************************************

#include<iostream.h>
#include<fstream.h>
#include"Bucket.h"
#include"Node.h"
#include"Hash.h"
#include<string.h>

//	***********************************************************************************************************
//	This function is used to validate that ModVal provided is of power of two.
//	**********************************************************************************************************
int validate(int modval)
{
	int power = 0;
	int r;
	while (modval>1)
	{
		r=modval%2;
			if (r!=0)
			{
				cout<<"Not a valid power of 2, exiting the program"<<endl;
				exit(1);
			}
			else
			{
				modval=(modval/2);
				power++;
			}
			
	}
return power;
}
//	************************************************************************************************************
void main(int argc, char* argv[])
{
	char string[20];
	cout << "Type the input filename : ";
	cin >> string;
	cout << endl;

	ifstream infile;
	infile.open(string);

	if (!infile)
		cout << string << " could not be opened" << endl;
	else
	{
	int ModVal;
	int Bucket_Size;
	int Key;
	int Power;
	char Command[2];

	infile >> ModVal;
	infile >> Bucket_Size;
	
	if (Bucket_Size <1)
		{ 
			cout <<"Bucket_Size is less than 1, exiting the program" <<endl;
			exit(1);
		}
	
	Power = validate(ModVal);

	Hash tree(Bucket_Size, ModVal, Power);

	tree.outfile.open("chang.txt", ios::app);
	tree.outfile << "ModVal is "<< ModVal <<endl<<endl;
	tree.outfile << "Bucekt Size is "<<Bucket_Size <<endl<<endl;
	tree.outfile << "Maximum Depth of the tree is "<< Power <<endl<<endl;


	while (infile)
	{
		infile >> Command;
		if (Command[1]!='\0')
			{infile >> Command;
			Command[0] = 'Z';}
		switch(Command[0])
		{
			case 'I':
					infile >>Key;
					tree.Insert(Key);
					break;
			
			case 'D':
					infile >>Key;
					tree.Delete(Key);
					break;
			
			case 'P':
					infile >>Key;
					tree.Print();
					break;
			
			case 'S':
					infile >>Key;
					tree.Search(Key);
					break;
		
			default:
					tree.outfile <<"Invalid Command"<<endl;
		}

	}
	}
}