#ifndef _HASH_H
#define _HASH_H

#include <vector>
#include <string>

class hashTable {

 public:

  // The constructor initializes the hash table.
  // Uses getPrime to choose a prime number at least as large as
  // the specified size for the initial size of the hash table.
  hashTable(int size = 0);

  // Inserts the specified key into the hash table.
  // Returns 0 on success,
  // 1 if key already exists in hash table,
  // 2 if rehash fails.
  int insert(const std::string &key);

  // Checks if the specified key is in the hash table.
  // If so, returns true; otherwise, returns false.
  bool contains(const std::string &key);

 private:

  // Each item in the hash table contains:
  //   key - a string representing the item's key.
  //   isOccupied - if false, this slot in the hash table is empty,
  //                and the other fields are meaningless.
  //   isDeleted - if true, this item has been lazily deleted
  //               (only meaningful if isOccupied is true).
  class hashItem {
  public:
    std::string key {""};
    bool isOccupied {false};
    bool isDeleted {false}; // this will stay false for now

    hashItem() = default;
  };

  int capacity; // The current capacity of the hash table.
  int filled; // The number of occupied slots in the table
              // (including lazily deleted items).

  std::vector<hashItem> data; // The items are stored here.

  // The hash function.
  unsigned int hash(const std::string &key);

  // Searches for an item with the specified key.
  // Returns the position if found, -1 otherwise.
  int findPos(const std::string &key);

  // The rehash function; makes the hash table bigger.
  // Returns true on success, false if memory allocation fails.
  bool rehash();

  // Returns a prime number at least as large as the specified size.
  // Uses a hardcoded sequence of selected prime numbers.
  static unsigned int getPrime(int size);
};

#endif //_HASH_H
