// $RCSfile: hash.cc,v $
// $State: Exp $ 
// $Revision: 1.2 $
// $Author: roman $
// $Date: 90/07/20 03:25:00 $
#include "hash.h"
//
//  hash.cc
//
int HashTable::Hash(HashKey key, int tblsz) {
      
      return((int)(((unsigned long)key)%tblsz));

};

int HashTable::CurElmNum() {
  return(cur_nelm);
}

void HashTable::Expand(int factor) {
      register int i, j, k;
      register HashEntry* newHashTbl;
/* should be prime number ?? */
      j = nelement*factor;
      newHashTbl = new HashEntry[j];
      for(i = 0; i <= j-1; i++) {
	newHashTbl[i].id = (HashKey)nil;
      };
      for(i = 0; i <= nelement-1; i++) {
	if (HashTbl[i].id != (HashKey)nil) {
	  k = Hash(HashTbl[i].id, j);
	  while (newHashTbl[k].id != (HashKey)nil){
	    k = (++k)%j;
	  };
	  newHashTbl[k] = HashTbl[i];
	};
      };
      delete HashTbl;
      HashTbl = newHashTbl;
      nelement = j;
}
      
HashTable::HashTable() {                       // Constructor
      register int i;
/* n -> close prime number ... How ??*/
      nelement = Nelm;
      cur_nelm = 0;
      HashTbl = new HashEntry[nelement];
      for(i = 0; i <= nelement-1; i++) {
	HashTbl[i].id = (HashKey)nil;
      }
}           

HashTable::HashTable(int sz) {                       // Constructor with size
      register int i;
/* n -> close prime number ... How ??*/
      nelement = sz;
      cur_nelm = 0;
      HashTbl = new HashEntry[nelement];
      for(i = 0; i <= nelement-1; i++) {
	HashTbl[i].id = (HashKey)nil;
      }
}           

HashTable::~HashTable() {                        // Destructor
      
      delete HashTbl;
      
}

void HashTable::Enter(HashEntry* entry){
      register int position;
      position = Hash(entry->id, nelement);
      while (HashTbl[position].id != (HashKey)nil && 
                          HashTbl[position].id != entry->id) {
	position = (++position)%nelement;
      };
      if (HashTbl[position].id != entry->id)
	cur_nelm++;
      HashTbl[position] = *entry;
      if (((cur_nelm*3)/2) > nelement) {
	Expand(2);
      };

}

void HashTable::Enter(HashKey id, HashData data){
      register int position;
      position = Hash(id, nelement);
      while (HashTbl[position].id != (HashKey)nil && 
                          HashTbl[position].id != id) {
	position = (++position)%nelement;
      };
      if (HashTbl[position].id != id)
	cur_nelm++;
      HashTbl[position].id = id;
      HashTbl[position].dataptr = data;
      if (((cur_nelm*3)/2) > nelement) {
	Expand(2);
      };
}

HashData HashTable::Find(HashKey id) {
      register int position;
      register int origin;
      position = Hash(id, nelement);
      origin = position;
      while (HashTbl[position].id != id) {
	if (HashTbl[position].id == (HashKey)nil) {
	  return((HashData)nil);
	};
	position = (++position)%nelement;
	if (position == origin) {
	  return((HashData)nil);
	};
      };
      return(HashTbl[position].dataptr);

}

HashData HashTable::Delete(HashKey id) {
      register int position;
      register int origin;
      HashData dataptr;
      register int loc;
      position = Hash(id, nelement);
      origin = position;
      while (HashTbl[position].id != id &&
	     HashTbl[position].id != (HashKey)nil) {
	position = (++position)%nelement;
	if (position == origin) {
	  return((HashData)nil);
	};
      };

      if (HashTbl[position].id == (HashKey)nil) {
	return((HashData)nil);}
      else {
      HashTbl[position].id = (HashKey)nil;
      dataptr = HashTbl[position].dataptr;
      --cur_nelm;
      origin = position;
      position = (++position)%nelement;
      while (HashTbl[position].id != (HashKey)nil && position != origin) {
	loc = Hash(HashTbl[position].id, nelement);
	  while (loc != position && HashTbl[loc].id != (HashKey)nil){
	    loc = (++loc)%nelement;
	  };
	if (loc != position) {
	HashTbl[loc] = HashTbl[position];
	HashTbl[position].id = (HashKey)nil;
      };
	position = (++position)%nelement;
	};
      return(dataptr);
    }
}

HashEntry* HashTable::GetTable(int& n) {

  n = nelement;
  return (HashTbl);

}

HashEntry* HashTable::next() {
  while((itr < nelement) && (HashTbl[itr].id == (HashKey)nil))
    itr++;

  if(itr == nelement) return nil;
  return &HashTbl[itr++];
}

HashData HashTable::dnext()
{
   HashEntry* e = next();
   if(e)
     return e->dataptr;
   else
     return nil;
}