/*

A hash table is a data structure using a list of nodes which are pairings of a key and a value.
It has been implemented with a Node struct and HashTable class which has functions for
inserting and deleting nodes along with getting the value of a node by specifying its key. It
also a function for printing the entire hash table.


*/



// Maximum size of the hash table
#define TABLE_SIZE 10

// Node structure for the linked list used in separate chaining
struct Node {
  String key;
  int value;
  Node* next;
};

// Hash Table class
class HashTable {
  private:
    Node* table[TABLE_SIZE];

    // Hash function to calculate index for a key
    int hashFunction(String key) {
      int hash = 0;
      for (int i = 0; i < key.length(); i++) {
        hash = (hash + key[i]) % TABLE_SIZE;
      }
      return hash;
    }

  public:
    // Constructor to initialize the hash table
    HashTable() {
      for (int i = 0; i < TABLE_SIZE; i++) {
        table[i] = NULL;
      }
    }

    // Insert key-value pair into the hash table
    void insert(String key, int value) {
      int index = hashFunction(key);
      Node* newNode = new Node();
      newNode->key = key;
      newNode->value = value;
      newNode->next = NULL;

      // Insert into the linked list at the calculated index
      if (table[index] == NULL) {
        table[index] = newNode;
      } else {
        Node* temp = table[index];
        while (temp->next != NULL) {
          temp = temp->next;
        }
        temp->next = newNode;
      }
    }

    // Retrieve value by key
    int get(String key) {
      int index = hashFunction(key);
      Node* temp = table[index];

      // Search through the linked list at the given index
      while (temp != NULL) {
        if (temp->key == key) {
          return temp->value;
        }
        temp = temp->next;
      }

      // If key not found, return -1
      return -1;
    }

    // Remove key-value pair from the hash table
    void remove(String key) {
      int index = hashFunction(key);
      Node* temp = table[index];
      Node* prev = NULL;

      while (temp != NULL && temp->key != key) {
        prev = temp;
        temp = temp->next;
      }

      // If key was found
      if (temp != NULL) {
        if (prev == NULL) {
          // The node to be removed is the head of the list
          table[index] = temp->next;
        } else {
          prev->next = temp->next;
        }
        delete temp;
      }
    }

    // Print the hash table
    void printTable() {
      for (int i = 0; i < TABLE_SIZE; i++) {
        Serial.print("Index ");
        Serial.print(i);
        Serial.print(": ");
        Node* temp = table[i];
        while (temp != NULL) {
          Serial.print("[");
          Serial.print(temp->key);
          Serial.print(", ");
          Serial.print(temp->value);
          Serial.print("] -> ");
          temp = temp->next;
        }
        Serial.println("NULL");
      }
    }
};

HashTable hashTable;

void setup() {
  // Start the Serial communication
  Serial.begin(9600);

  // Insert key-value pairs into the hash table
  hashTable.insert("apple", 10);
  hashTable.insert("banana", 20);
  hashTable.insert("orange", 30);
  hashTable.insert("grape", 40);
  hashTable.insert("melon", 50);

  // Print the hash table
  Serial.println("Initial Hash Table:");
  hashTable.printTable();

  // Retrieve a value
  Serial.print("Value for 'apple': ");
  Serial.println(hashTable.get("apple"));

  // Remove a key-value pair
  hashTable.remove("banana");
  Serial.println("Hash Table after removing 'banana':");
  hashTable.printTable();
}

void loop() {
  // Nothing to do here
}