/*Implementare una hash map con concatenamento*/
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;

class Nodo
{
private:
    int ID;
    string data;
    Nodo *p_prev, *p_next;
public:
    Nodo(string x, int y) { ID = y; data = x; p_prev = nullptr; p_next = nullptr; }
    ~Nodo(){}

    void setPrev(Nodo *x) { p_prev = x; }
    void setNext(Nodo *x) { p_next = x; }

    int getID() { return ID; }
    string getString() { return data; }
    Nodo* getPrev() { return p_prev; }
    Nodo* getNext() { return p_next; }
};

class ListaBid
{
private:
    Nodo *testa, *coda;
public:
    ListaBid() { testa = nullptr; coda = nullptr; }
    ~ListaBid(){}

    bool Empity() { if (testa != nullptr)return false; else return true; }

    Nodo* Search(int val);
    void Delete(int val);
    void Insert(Nodo *x);

    void visualizza_ListaBid();
};
Nodo* ListaBid::Search(int val)
{
    Nodo *tmp = testa;
    while (tmp != nullptr)
    {
        if (tmp->getID() == val)
            return tmp;

        tmp = tmp->getNext();
    }
    return nullptr;
}
void ListaBid::Delete(int val)
{
    Nodo *tmp = Search(val);
    if (tmp != nullptr)
    {
        if (tmp->getNext() != nullptr)
            tmp->getNext()->setPrev(tmp->getPrev());
        else
            coda = tmp->getPrev();

        if (tmp->getPrev() != nullptr)
            tmp->getPrev()->setNext(tmp->getNext());
        else
            testa = tmp->getNext();

        delete tmp;
    }
}
void ListaBid::Insert(Nodo *x)
{
    if (Search(x->getID()) == nullptr)
    {
        x->setNext(testa);
        x->setPrev(nullptr);
        testa = x;
        if (coda == nullptr)
            coda = x;
    }
}
void ListaBid::visualizza_ListaBid()
{
    Nodo *tmp = testa;
    if (tmp != nullptr)
    {
        while (tmp != nullptr)
        {
            cout << tmp->getString() << ' ';
            tmp = tmp->getNext();
        }
    }
}

class HashTable
{
private:
    vector<ListaBid*>Table;
    int HashFunction(int val);///Metodo della moltiplicazione
    int getVal(string s);///Calcola la chiave di una stringa con sistema posizionale pesato in base 27
public:
    HashTable(int size) { Table.resize(size, nullptr); }
    ~HashTable(){}

    bool Search(string s);
    void Insert(string s);
    void Delete(string s);

    void visualizza_Hash();
};
int HashTable::getVal(string s)
{
    int val = 0;
    for (int i = 0; i < s.size(); i++)
        val += int((s[i] - 'a' + 1)*pow(27.00, double(s.size() - i - 1)));
    return val;
}
int HashTable::HashFunction(int val)
{
    return fmod(double(val)*(sqrt(5.00) - 1.00) / 2.00, 1.00)*double(Table.size());
}
void HashTable::Insert(string s)
{
    int val, i;

    val = getVal(s);
    i = HashFunction(val);

    if (Table[i] == nullptr)
        Table[i] = new ListaBid;

    Table[i]->Insert(new Nodo(s, val));
}
void HashTable::Delete(string s)
{
    int val, i;

    val = getVal(s);
    i = HashFunction(val);

    if (Table[i] != nullptr)
    {
        Table[i]->Delete(val);
        if (Table[i]->Empity())
        {
            delete Table[i];
            Table[i] = nullptr;
        }
    }
}
bool HashTable::Search(string s)
{
    int val, i;

    val = getVal(s);
    i = HashFunction(val);

    if (Table[i] != nullptr)
    {
        if (Table[i]->Search(val) != nullptr)
            return true;
    }
    return false;
}
void HashTable::visualizza_Hash()
{
    for (int i = 0; i < Table.size(); i++)
    {
        cout << Table[i] << " -> ";
        if (Table[i] != nullptr)
        {
            Table[i]->visualizza_ListaBid();
        }
        cout << endl;
    }
}


int main()
{
    HashTable tabella(4);

    vector<string>A = { "a","b","c","d","e","f","g","h","i","l","m","n","o","p","q","r","s","t" };

    for (int i = 0; i < A.size(); i++)
        tabella.Insert(A[i]);

    tabella.visualizza_Hash(); cout << endl;

    tabella.Delete("a");

    tabella.visualizza_Hash(); cout << endl;

    return 0;
}