#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include "Int.h"
#include "..\compare.h"

#include "hashdict.h"

template <class Key, class Elem, class KEComp, class EEComp>
bool hashdict<Key, Elem, KEComp, EEComp>::
hashSearch(const Key& K, Elem& e) const {
    int home= h(K);            // home 保存K的基地址
    int i=0;    
    int pos = home;           // 探查序列的初始位置
    while(!EEComp::eq(EMPTY, HT[pos])){
	  if (KEComp::eq(K, HT[pos])) {  // 發(fā)現(xiàn)目標(biāo)
          e = HT[pos];
         return true;
	  }
      i++;
	  pos = (home + p(K, i)) % M;
  }
   return false;    
}







// 將數(shù)據(jù)元素e插入到散列表 HT
template <class Key, class Elem, class KEComp, class EEComp>
bool hashdict<Key, Elem, KEComp, EEComp>::hashInsert(const Elem &e)
  {
    int  home= h(getkey(e));        // home記錄基位置
    int  i=0, insplace;    
    bool tomb_pos=false;
    int  pos = home;                // 探查序列的初始位置
    while(!EEComp::eq(EMPTY, HT[pos])){
      if(EEComp::eq(e, HT[pos]))
		  return false;//不允許重復(fù)關(guān)鍵碼
	  if(EEComp::eq(TOMB, HT[pos])&& !tomb_pos )  {
          insplace=pos;                 //記錄第一個(gè)墓碑的位置   
          tomb_pos=true;
		}  
	  i++;
	  pos = (home + p(getkey(e), i)) % M;
  }
     if (!tomb_pos) 
		 insplace=pos;      //如果沒有墓碑，插入空位置
     HT[insplace]=e;                  //插入e
     return true;
}


// 刪除算法：在檢索函數(shù)的基礎(chǔ)上進(jìn)行了修改。
// 若檢索失敗，則無(wú)值可刪；檢索成功則將其設(shè)為墓碑。
template <class Key, class Elem, class KEComp, class EEComp>
Elem hashdict<Key,Elem,KEComp,EEComp>::hashDelete(const Key& K)
{
    int home= h(K);// home記錄基位置
    int i=0;    
    int pos = home;        // 探查序列的初始位置
    while(!EEComp::eq(EMPTY, HT[pos])){
	   if (KEComp::eq(K, HT[pos])){
		   temp = HT[pos];
          HT[pos] = TOMB; //設(shè)置墓碑
          return temp;    //返回目標(biāo)
		}
	   i++;
	   pos = (home + p(K, i)) % M;
	}
    return EMPTY; 
}





  int getkey(Int* e) 
  {
	  return e->key(); 
  }
    char* getkey(char* e) 
	{ 
		return e; 
	}


   int Intkey(Int& e)
   { 
	   return e.key(); 
   }
   char* charkey(char*& e)
   { 
	   return e; 
   }

void main(int argc, char** argv) {
   hashdict<int, Int*, intIntsCompare, IntsIntsCompare> dict(100, new Int(-1),new Int(-2));
  Int* val;

  dict.hashInsert(new Int(10));
  if (dict.hashSearch(10, val))
    cout << "發(fā)現(xiàn)值 " << val << " 匹配關(guān)鍵碼10\n";
  else
    cout << "沒有發(fā)現(xiàn)匹配關(guān)鍵碼10的元素\n";

}