#include <iostream>
using namespace std;
 
#include "Hash_file.h"
 
 
 
int main(void)
{   
	Hash_Map<int> Numbers(1);
    Numbers.insert("one", 1);
 
	cout<<Numbers.find("one");
 
 
	cin.get();
	return 0;
}

#pragma once
#ifndef HASH_MAP
#define HASH_MAP
#include <string>
 
 
 
 
typedef struct Entry_t
{
  void * Object;
  Entry_t * next;
  std::string  Key;
  int position;
}Entry;
 
 
 
template<class Map>
class Hash_Map
{ 
 
 
 private :
   Entry **Primary;
   Entry **Secondary;
  int Num;
  size_t secondary_size;
 
 
  public:
  Hash_Map(const Hash_Map & Map_secondary);
  // the default SuperFastHash comes from the included header file 
  Hash_Map( int num ); 
 
  int   insert(std::string  key, Map  map);
 
  int   deletion(std::string key);
 
  bool  isFull();
 
  Map * find(std::string key);
 
  int   Secondaryinsert(std::string key, Map & map);
 
  int   Swap_Hash(int leftoff);
 
 
 
 
};
 
#endif

#include "Hash_file.h"
#include <cstring>
 
 
//using Coalesced_hashing
 
//also will use incrementing for Resize
 
 
 
template< class Map>
Hash_Map<Map>::Hash_Map( const Hash_Map & Map_secondary)
{
  Primary = Map_secondary.Primary;
 
  Secondary = Map_secondary.Secondary;
 
  Num = Map_secondary.Num;
}
 
template< class Map>
Hash_Map<Map>::Hash_Map( int num)
{
   Num = num;
 
   Primary = new Entry[num];
   int i= 0;
   while( i < Num)
   {
	   Primary[Num] = NULL;
   }
   Secondary = NULL;
 
}
 
 
 
template< class Map>
int Hash_Map<Map>::insert(std::string  key, Map  map)
{
  unsigned h = SuperFastHash(key.c_str(), strlen(key.c_str())) % Num;
 
  if(Primary[h] == NULL)
  {
	  Primary[h] = new Entry;
	  Primary[h]->Object = map;
	  Primary[h]->Key = key;
      Primary[h]->position = h;
  }
  else
  {
	  Entry * it;
	  int cursor = 0; 
 
	  while(cursor < Num && Primary[cursor] != NULL)
		  ++cursor;
	  if( cursor == Num)
		  return -1;
 
	  Primary[cursor] = new Entry;
	  Primary[cursor]->Object = map;
	  Primary[cursor]->Key = key;
      Primary[cursor]->position = cursor;
	  it = Primary[h];
 
	  while(it->next != NULL)
		  it = it->next;
 
	  it->next = Primary[cursor];
 
  }
  return 0;
 
}
 
template< class Map>
Map * Hash_Map<Map>::find(std::string key)
{
  unsigned h = SuperFastHash(key.c_str(),strlen(key.c_str())) % Num;
 
 if ( Primary[h] != NULL ) {
     Entry *it;
 
    /* Search the chain at index h */
    for ( it = Primary[h]; it != NULL; it = it->next ) {
      if ( strcmp ( key.c_str(), it->Key.c_str() ) == 0 )
        return (Map)it->Object;
    }
  }
 return NULL;
 
}
 
 
template<class Map>
int Hash_Map<Map>::deletion(std::string key)
{
  unsigned h = SuperFastHash(key.c_str(),strlen(key.c_str())) % Num;
 
 if(Primary[h] != NULL)
 { 
 
 
	 if(  strcmp ( key.c_str(), Primary[h]->Key.c_str() ) == 0)
	 {
		 delete Primary[h];
	     Primary[h] = NULL;
	 }
	 else
	 {    
		 Entry * tempt1 = Primary[h]->next;
		 Entry * tempt2 = Primary[h];
	 while( tempt1 != NULL  ) {
		 if ( strcmp ( key.c_str(), tempt1->Key.c_str() ) == 0 )
            break;
            tempt1 = tempt1->next;
			tempt2 = tempt2->next;
		 }
 
		 tempt2->next = tempt1->next;
 
		 unsigned int P =  tempt1->position;
 
		 delete Primary[P];
         Primary[P] = NULL;
	  }
    return 0;
 }
 
return -1;
 
}
 
 
 
 
template< class Map>
bool Hash_Map<Map>:: isFull()
{ 
   int cursor =0;
  while(cursor < Num && Primary[cursor] != NULL)
		  ++cursor;
  if(cursor == Num )
	  return true;
 
 
  return false;
 
}
 
template< class Map>
int Hash_Map<Map>::Secondaryinsert(std::string key, Map & map)
{
 
 if(Secondary == NULL)
 {
 
  secondary_size = Num * 1.5;
 
  Secondary = new Entry[secondary_size];
  int i;
  while( i < secondary_size )
   {
	   Secondary[ i ] = NULL; ++i;
   }
 
 }
 
   unsigned h = SuperFastHash(key.c_str(),strlen(key.c_str())) %secondary_size;
 
 
   if(Secondary[h] == NULL)
   {  Secondary[ h ] = new Entry;
      Secondary[h]->Object = map;
	  Secondary[h]->Key = key;
      Secondary[ h ]->position = h;
   }
   else
   {
     Entry * it;
	  int cursor = 0; 
 
	  while(cursor < secondary_size&& Secondary[cursor] != NULL)
		  ++cursor;
	  if( cursor == secondary_size)
		  return -1;
 
	 Secondary[cursor] = new Entry;
	 Secondary[cursor]->Object = map;
	 Secondary[cursor]->Key = key;
     Secondary[cursor]->position = cursor;
	  it = Secondary[h];
 
	  while(it->next != NULL)
		  it = it->next;
 
	  it->next = Secondary[cursor];
   }
 
return 0;
}
template< class Map>
int Hash_Map<Map>::Swap_Hash(int leftoff)
{
   int Num_of_buckets_transfer =  Num * .40;
 
   int i;
   int j;
   if( leftoff != 0 )
   for( i = leftoff, j = 0;  j < Num_of_buckets_transfer; --i, j++)
   {
	   unsigned int h;
       h = SuperFastHash(Primary[i]->Key.c_str(),strlen(Primary[i]->Key.c_str())) % secondary_size;
       if(Secondary[h] == NULL)
	   {
		Secondary[h] = new Entry;
		Secondary[h]->Key = Primary[i]->Key;
		Secondary[h]->Object = Primary[i]->Object;
        Secondary[ h ]->position = h;
	   }
	   else
	   {
         Entry * it;
	  int cursor = 0; 
 
	  while(cursor < secondary_size&& Secondary[cursor] != NULL)
		  ++cursor;
	  if( cursor == secondary_size)
		  return -1;
 
	 Secondary[cursor] = new Entry;
	 Secondary[cursor]->Key = Primary[i]->Key;
	 Secondary[cursor]->Object = Primary[i]->Object;
     Secondary[cursor]->position = cursor;
	  it = Secondary[h];
 
	  while(it->next != NULL)
		  it = it->next;
 
	  it->next = Secondary[cursor];
	  }
   }
 
   return leftoff;
}