#include<iostream>
#include<cstring>
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(){
        if(next!=NULL){
            delete next;
        }
    }
};
template<typename T>
class HashTable{
    node<T>** table; //pointer to an array of pointers
    int current_size;
    int table_size;

    int hashfn(string key){
        int idx = 0;
        int p=1;
        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;
        table = new node<T>*[table_size];
        //initialize new table buckets with null
        //now oldtable has data and new table is null
        for(int i=0;i<table_size;i++){
            table[i] = NULL;
        }
        current_size = 0;
        //shift data from old table to new table
        for(int i=0;i<oldTableSize;i++){
            node<T>*temp = oldTable[i];

            while(temp!=NULL){
                insert(temp->key,temp->value);
                temp = temp->next;
            }
            //delete this entire row from oldtable
            if(oldTable[i]!=NULL){
                delete oldTable[i];
            }

        }
        delete [] oldTable;
    }
public:
    HashTable(int ts = 7){
        table_size = ts;
        table = new node<T>*[table_size];
        current_size = 0;
        for(int i=0;i<table_size;i++){
            table[i] = NULL;
        }
    }

    void insert(string key , T value){
        int idx = hashfn(key);
        node<T>*n = new node<T>(key,value);
        //insert at head  of linkedlist with id=idx
        n->next = table[idx];
        table[idx]=n;
        current_size++;

        //rehash
        float load_factor = current_size/(1.0*table_size);
        if(load_factor>0.7){
            rehash();
        }
    }
    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=temp->next;
           }
            cout<<endl;
        }
    }

    T* Search(string key){
        int idx = hashfn(key);
        node<T>*temp = table[idx];
        while(temp!=NULL){
            if(temp->key == key){
                return &temp->value;
            }
            temp = temp->next;
        }
        return NULL;
    }

    void Erase(string key){
        int idx = hashfn(key);
        node<T>*temp = table[idx];
         node<T>*prev = NULL;
        
           
       
        while(temp->next!=NULL){
            if(temp->next->key == key){
                prev = temp;
                prev->next = temp->next->next;
                delete temp->next;
            }
            temp = temp->next;
        }
        return;
    }
};

int main(){
    HashTable<int>price_menu;
    price_menu.insert("burger",120);
    price_menu.insert("pepsi",80);
    price_menu.insert("burgerpizza",90);
    price_menu.insert("noodles",150);
    price_menu.insert("coke",50);
    price_menu.print();
    int *price = price_menu.Search("noodles");
    if(price!=NULL){
        cout<<"found "<<*price;
    }
    else{
        cout<<"not found";
    }
    price_menu.Erase("noodles");
    price_menu.print();
return 0;}