Datastrukturer_Algoritmer/Hashing/hash.cpp

//##################################################################
//	PROGRAMMERINGSUPPGIFT 3
// DATASTRUKTURER OCH ALGORITMER
// HASH TABELL
//==================================================================
//	HASH.HPP
//	Filen innehåller hashfunktionerna
//		Christian Ohlsson
//		Ingela Johansson
//		Anna-Maria Haglund
//		Karlstad 981007
//==================================================================

#include "header.hpp"
//##################################################################
//Function: hashClass()
//Task: constuctorn
//Calls: nothing
//==================================================================
hashClass::hashClass()
{
  prime();
  PRIMENUMBER=0;
  ARRAYSIZE = DEFAULTSIZE;
  hashPtr = new hashNode[ARRAYSIZE];
  for(int i=0; i<ARRAYSIZE ; i++) {
    strcpy(hashPtr[i].name, "");
    strcpy(hashPtr[i].number, "");
    hashPtr[i].exist = FALSE;
  }
}
//##################################################################
//Function: ~hashclass
//Task: destructorn
//Calls: nothing
//==================================================================
hashClass::~hashClass(){ delete hashPtr; }
//##################################################################
//Function: getSize()
//Task: returnerar storleken på hashtabellen
//Calls: nothing
//==================================================================
int hashClass::getSize(){ return ARRAYSIZE; }
//##################################################################
//Function: nextPrime()
//Task: returnerar nästa primtal
//Calls: nothing
//==================================================================
int hashClass::nextPrime()
{
  PRIMENUMBER++;
  return primeArray[DEFAULTPRIMENUMBER+PRIMENUMBER];
}
//##################################################################
//Function: prime()
//Task: lägger in primtalen i en array
//Calls: isPrime()
//==================================================================
void hashClass::prime()
{
  int i = 1, num=FIRSTPRIME;
  primeArray[0] = STARTPRIME;
  
  while(i<PRIMEARRAYSIZE) {
    if(isPrime(num, i, primeArray)) {
      primeArray[i] = num;
      i++;
    }
    num = (num+PRIMESTEP);
  }
}
//##################################################################
//Function: isPrime()
//Task: kollar om ett tal är ett primtal
//Calls: nothing
//=================================================================

bool hashClass::isPrime(int nummer, int antal, int primeArray[PRIMEARRAYSIZE])
{
  for(int i = 0; i < antal; i++)
    if(nummer%primeArray[i] == 0)
      return FALSE;
  return TRUE;
}
//##################################################################
//Function: search()
//Task: söker efter ett namn i tabellen
//Calls: hash1() och hash2()
//==================================================================
bool hashClass::search(nameType name)
{
  int location = hash1(name);
  if(strcmp(hashPtr[location].name, name) == 0)
    return TRUE;
  else
    while(hashPtr[location].exist == TRUE) {
      location = location + hash2(hash1(name));
      if(location > ARRAYSIZE)
	location = location - ARRAYSIZE;
      if(strcmp(hashPtr[location].name, name) == 0)
	return TRUE;
    }
  return FALSE;
}
//##################################################################
//Function: getNode()
//Task: hämtar en nod ur tabellen, d.v.s. namn telefonnummer och
//		  "deleted-flaggan"
//Calls: hash1() och hash2()
//==================================================================
hashNode hashClass::getNode(nameType &oneName)
{
  int location = hash1(oneName);
  if(strcmp(hashPtr[location].name, oneName) == 0)
    return (hashPtr[location]);
  else
    do {
      location = location + hash2(hash1(oneName));
      if(location>ARRAYSIZE) {
	location = (location-ARRAYSIZE);
	if(strcmp(hashPtr[location].name, oneName) == 0)
	  return hashPtr[location];
      }
    }while(hashPtr[location].exist == FALSE);
}
//##################################################################
//Function: biggerHash()
//Task: kollar om en större tabell behövs (om 80% av positionerna
//		  är upptagna)
//Calls: checkOccupied()
//==================================================================
bool hashClass::biggerHash()
{
  float siz = INSERTFACTOR*getSize();
  int occ = checkOccupied();
  if(occ>=siz)
    return TRUE;
  return FALSE;
}
//##################################################################
//Function: newHashArray()
//Task:
//Calls: reHash()
//==================================================================
void hashClass::newHashArray()
{
  int oldSize = ARRAYSIZE;
  ARRAYSIZE = nextPrime();
  reHash(oldSize);
}
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================
bool hashClass::anotherHash()
{
  int del=0;
  float siz = DELETEFACTOR*getSize();
  for(int i=0; i<ARRAYSIZE ; i++)
    if(hashPtr[i].exist == TRUE && !hashPtr[i].name[0])
      del++;
  if(del>=siz)
    return TRUE;
  return FALSE;
}
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================
void hashClass::reHash(int oldSize)
{
  int location;
  hashNode *tempPtr = new hashNode[ARRAYSIZE];
  for(int j=0; j<oldSize ; j++) {
    strcpy(tempPtr[j].name, hashPtr[j].name);
    strcpy(tempPtr[j].number, hashPtr[j].number);
    tempPtr[j].exist = hashPtr[j].exist;
  }
  destroyHash(oldSize);
  hashPtr = new hashNode[ARRAYSIZE];
  for(int k=0; k<ARRAYSIZE ; k++) {
    strcpy(hashPtr[k].name, "");
    strcpy(hashPtr[k].number, "");
    hashPtr[k].exist = FALSE;
  }
  for(int i=0; i<oldSize ; i++)
    if(tempPtr[i].exist == TRUE && tempPtr[i].name[0]) {
      location = hash1(tempPtr[i].name);
      if(hashPtr[location].exist == FALSE)
	insert(location, tempPtr[i]);
      else
	while(hashPtr[location].exist == TRUE) {
	  location = location + hash2(hash1(tempPtr[i].name));
	  if(location > ARRAYSIZE)
	    location = location - ARRAYSIZE;
	  if(hashPtr[location].exist == FALSE)
	    insert(location, tempPtr[i]);
	}
    }
  delete tempPtr;
}
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================
int hashClass::hash1(nameType name)
{
  int sum = 0;
  for(int i=0 ; i<strlen(name) ; i++)
    sum = name[i] + sum;
  return (sum % ARRAYSIZE);
}
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================
int hashClass::hash2(int key){ return(STEPSIZE - (key % STEPSIZE)) }
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================
int hashClass::checkOccupied()
{
  int occupied = 0;
  for(int i=0 ; i<ARRAYSIZE ; i++)
    if(hashPtr[i].exist == TRUE)
      occupied++;
  return occupied;
}
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================
void hashClass::destroyHash(int oldSize)
{
  for(int i = 0; i < oldSize; i++)
    delHash(i);
}
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================
void hashClass::del(int location)
{
  strcpy(hashPtr[location].name, "");
  strcpy(hashPtr[location].number, "");
  hashPtr[location].exist = TRUE;
}
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================

void hashClass::delHash(int location)
{
  strcpy(hashPtr[location].name, "");
  strcpy(hashPtr[location].number, "");
  hashPtr[location].exist = FALSE;
}
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================
void hashClass::insert(int location, hashNode &newNode)
{
  strcpy(hashPtr[location].name, newNode.name);
  strcpy(hashPtr[location].number, newNode.number);
  hashPtr[location].exist = TRUE;
}
//##################################################################
//Function:
//Task:
//Calls:
//==================================================================
void hashClass::save(fstream &fil)
{
  int i = 0;
  while(i < ARRAYSIZE) {
    if((hashPtr[i].name[0]) && (hashPtr[i].exist == TRUE))
      fil.write((char*)& hashPtr[i],sizeof(hashPtr[i]));
    i++;
  }
}