Hashtable.cpp

#include "Hashtable.h"
#include <math.h>

int Hashtable::hash(int v) const{
  return v % capacity();
}
//Hashtable() \Constructs and empty hash table with a default capacity of 17 and a default load factor threshold of .65
Hashtable::Hashtable()
{
  htableCapacity = 17;
  loadFactor = 0.65;
  htable = new int[htableCapacity]();
  count = 0;
}
//Hashtable(int size)\Constructs and empty hash table with the given capacity and a default load factor threshold of .65
Hashtable::Hashtable(int capacity)
{
  htableCapacity = capacity;
  loadFactor = 0.65;
  htable = new int[htableCapacity]();
  count = 0;
}
//Hashtable(int, double)\Constructs and empty hash table with the given capacity and load factor threshold values
Hashtable::Hashtable(int capacity, double threshold)
{
  htableCapacity = capacity;
  loadFactor = threshold;
  htable = new int[capacity]();
  count = 0;
}
//Hashtable(const Hashtable& other)\creates a deep-copy of the given hashtable
Hashtable::Hashtable(const Hashtable& other)
{
  if (!empty()) {
    delete[] htable;
    count = 0;
  }

  htableCapacity = other.capacity();
  loadFactor = other.loadFactor;
  htable = new int[other.capacity()]();
  for (int i = 0; i < htableCapacity; i++) {
    if (other.htable[i] != 0) {
      htable[i] = other.htable[i];
      count++;
    }
  }
}
//Hashtable& operator=(const Hashtable& other)\replaces the current hashtable with a deep-copy of the given hash table
Hashtable& Hashtable::operator=(const Hashtable& other)
{
  if (!empty()) {
    delete[] htable;
  }
  count = 0;
  htableCapacity = other.capacity();
  loadFactor = other.loadFactor;
  htable = new int[other.capacity()]();
  for (int i = 0; i < htableCapacity; i++) {
    if (other.htable[i] != 0) {
      htable[i] = other.htable[i];
      count++;
    }
  }
  return *this;
}
//~Hashtable()\cleans up all allocated memory of the hashtable
Hashtable::~Hashtable()
{
  delete[] htable;
}
//int size() const\retunrs the number of items currently in the hashtable
int Hashtable::size() const
{
  return count;
}
// double the size of the array if too small. ensure hashing is updated
void Hashtable::resize() {
  int* currTable = htable;
  int currCapacity = capacity();

  // the tests expect this growth rate
  htableCapacity = nextPrime(currCapacity*2);
  htable = new int[htableCapacity]();
  count = 0; // debugging this line not being here took me all day to solve :)
  for (int i = 0; i < currCapacity; i++) {
    if (currTable[i] != 0) {
      insert(currTable[i]);
    }
  }
  delete[] currTable;
}

// int capacity() const\\returns the capacity of the hashtable (i.e. the size of the array)
int Hashtable::capacity() const
{
  return htableCapacity;
}
//double getLoadFactorThreshold() const\\returns the load factor threshold used to determine when to resize the hashtable.
double Hashtable::getLoadFactorThreshold() const
{
  return loadFactor;
}
//bool empty() const\\returns true if the table is empty or false otherwise
bool Hashtable::empty() const
{
  return count == 0;
}
//void insert(const int)\\Inserts the given value into the hashtable.  Automatically resizes the table as necessary.
void Hashtable::insert(int value)
{
  //check load factor with the new item
  if (size()+1 > getLoadFactorThreshold()*capacity()) {
    resize();
  }
  int H = hash(value);
  int N = capacity();
  for (int i = 0; i < N; i++) {
    //H + 0*i + 1*i^2
    int index = (H + i*i) % N;
    if (htable[index] <= 0) {
      htable[index] = value;
      count++;
      return;
    }
    }
  }
//Removes the given value from the hashtable.  If the value is not present it takes no action and throws no errors.
void Hashtable::remove(int value)
{
  if (empty()) {
    return;
  }
  int H = hash(value);
  int N = capacity();

  for (int i = 0; i < N; i++) {
    //H + 0*i + 1*i^2
    int index = (H + i*i) % N;
    if (htable[index] != 0) {
      if (htable[index] == value){
        htable[index] = -1;
        count--;
        return;
      }
    }
    else {
      return;
    }
  }
}
//Returns true if the given value is contained in the hashtable or false if the value is not in the hashtable.
bool Hashtable::contains(int value) const{
  int H = hash(value);
  int N = capacity();
  for (int i = 0; i < N; i++) {
    //H + 0*i + 1*i^2
    int index = (H + i*i) % N;
    if (htable[index] == value) {
      return true;
    }
    if (htable[index] == 0) {
      return false;
    }
  }
  return false;
}
//Returns the index of the given value.  If the value is not in the hashtable, returns -1.
int Hashtable::indexOf(int value) const {
  int H = hash(value);
  int N = capacity();
  int index = H;

  for (int i = 0; i < N; i++) {
    //H + 0*i + 1*i^2
    int index = (H + i*i) % N;
    if (htable[index] == 0) {
      return -1;
    }
    if (htable[index] == value){
      return index;
    }
  }
  return -1;
}
//Removes all values from the hashtable, resetting it to an empty state
void Hashtable::clear()
{
  for (int i = 0; i < capacity(); i++) {
    htable[i] = 0;
  }
  count = 0;
}
//Returns true if the value is a prime number
bool Hashtable::isPrime(int n) {
  //Returns true if the value is a prime number. One way to implement this method is to check if the number is divisible by 2-sqrt(n).
  //If it is then it is not prime.  If it is not then it is prime.  2 and 3 must be tested separately.
  if (n <= 1) {
    return false;
  }
  if (n == 2 || n == 3) {
    return true;
  }
  if (n % 2 == 0) {
    return false;
  }
  // check remaining ods
  for (int i = 3; i <= sqrt(n); i+=2) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
//Returns the next prime number greater than or equal to n.
int Hashtable::nextPrime(int n){
  n++;
  //Returns the next prime number greater than or equal to n.
  //One way to implement this method is to test if n is prime and then repeatedly increment n and test again if it is prime.
  while (!isPrime(n)) {
    n++;
  }
  return n;
}