#include<bits/stdc++.h>
using namespace std;

template<typename T>
class Node {
public:
    string key;
    T value;
    Node<T> *next;

    Node( string key , T val ) {
        this->key = key;
        value = val;
        next = NULL;
    }

    ~Node() {
        while ( next != NULL ) {
            delete next;
        }
    }

};

template<typename T>
class Hashtable {
    Node<T>**table;
    int current_Size;
    int table_Size;

    int hashFn( string key ) {
        int idx = 0;
        int p = 1; // base 27 integer
        for ( int j = 0 ; j < key.length() ; j++ ) {
            idx = idx + ( ( key[j] * p ) % table_Size );
            idx = idx % table_Size;
            p = ( p * 27 ) % table_Size;
        }

        return idx;
    }

    void rehash() {
        Node<T>**oldTable = table;
        int oldTableSize = table_Size;
        table_Size = 2 * table_Size+3;
        current_Size = 0;
        table = new Node<T>*[table_Size];

        for ( int i = 0 ; i < table_Size ; i++ ) {
            table[i] = NULL;
        }
        current_Size = 0;
        for ( int i = 0 ; i < oldTableSize ; i++ ) {
            Node<T> *temp = oldTable[i];
            while ( temp != NULL ) {
                insert( temp->key , temp->value );
                current_Size++;
                temp = temp->next;
            }

            if ( oldTable[i] != NULL ) {
                delete oldTable[i];
            }
        }

        delete [] oldTable;
    }

public:
    Hashtable( int ts = 7 ) {
        current_Size = 0;
        table_Size = ts;
        table = new Node<T>*[table_Size]; // table pointer is a pointer containing address of a node pointer ( array of pointers )

        for ( int i = 0 ; i < table_Size ; i++ ) {
            table[i] = NULL;
        }
    }

    void print() {
        for ( int i = 0 ; i < table_Size ; i++ ) {
            cout << "Bucket " << i << " -> ";
            Node<T> *temp = table[i];
            while ( temp != NULL ) {
                cout << "( " << temp->key << " , " << temp->value << " ) -> ";
                temp = temp->next;
            }
            cout << endl;
        }

    }

    void insert( string key , T value ) {
        int idx = hashFn( key );

        Node<T> *n = new Node<T>( key , value );

        // insert the given node in the linklist present at the idx in the hashtable
        n->next = table[idx];
        table[idx] = n;
        current_Size++;

        // rehashing..
        int loadFactor = current_Size / ( 1.0 * table_Size );
        if ( loadFactor > 0.7 ) {
            rehash();
        }

    }

    /*
    T search( string key ) {

    }

    void erase( string key ) {

    }
    */

};

int main() {
    Hashtable<int> food_Menu;

    food_Menu.insert("Burger", 120);
    food_Menu.insert("Pizza", 150);
    food_Menu.insert("Coke", 20);
    food_Menu.insert("Noodles", 60);
    food_Menu.insert("Icecream", 40);

    food_Menu.print();
}