// -------------------------------------------------------------
// Algoritmos e Estruturas de Dados 2024/2025 - LEIC (FCUP/FEUP)
// http://www.dcc.fc.up.pt/~pribeiro/aulas/aed2425/
// -------------------------------------------------------------
// A simple lightweight implemetation of hash tables
// (using open addressing, a.k.a. closed hashing)
// Last update: 08/12/2024
// -------------------------------------------------------------

#ifndef _HASHTABLEOA_H_
#define _HASHTABLEOA_H_

#include <iostream>
#include <iomanip>
#include <vector>
#include <functional>

template <class KeyType> class HashTableOA {
  enum EntryType {EMPTY, ACTIVE, DELETED}; // Type of table entry
  struct HashEntry {                       // One table entry
    EntryType state;
    KeyType key;
  };
  
  int size;                                      // Size of the hash table
  int numberActive;                              // Number of active table entries (with keys)
  int numberDeleted;                             // Number of deleted table entries
  std::vector<HashEntry> table;                  // The hash table itself
  std::function<unsigned(const KeyType &)> hash; // Hash function: key -> unsigned

public:
  // Constructor: receives the table size n and the hash function h
  HashTableOA(int n, std::function<unsigned(const KeyType&)> h) :
    size(n), numberActive(0), numberDeleted(0), table(n), hash(h) {
    for (int i=0; i<size; i++) table[i].state = EMPTY;
  }
  
  // Show contents of hash table (to check if implementation is correct)
  void showContents() {
    std::cout << "Size: " << size << " | Nr Active: " << numberActive
              << " | Nr Deleted: " << numberDeleted << " | Load Factor: "
              << std::fixed << std::setprecision(3)
              << (double)(numberActive + numberDeleted) / size << std::endl;
    std::cout << "Table:";
    for (int i=0; i<size; i++) {
      if (table[i].state == EMPTY) std::cout << " {}";
      else if (table[i].state == DELETED) std::cout << " DEL";
      else std::cout << " " << table[i].key;
    }
    std::cout << std::endl;
  }
  
  // ---------------------------------------------------------
  // TODO: functions to implement in this exercise
  // ---------------------------------------------------------

  
  // Does it contain key k?
  bool contains(const KeyType & k) {
    // TO DO
    
  }
  
  // Insert key k (true if successful)
  bool insert(const KeyType & k) {
    // TO DO
    
  }

  // Remove key k (true if successful)
  bool remove(const KeyType & k) {
    // TO DO
        
  }
};

#endif