#include <iostream>
#include <cmath>
using namespace std;

class Node
{
public:
    int data;
    Node* next;
};
class HashTable
{
public:
    Node** HT;
    HashTable();
    ~HashTable();
    void Insert(int key);
    int Hash(int key);
    int Search(int key);
};
int HashTable::Search(int key)
{
    int hldx = Hash(key);
    Node* p = HT[hldx];
    while(p)
    {
        if(p->data == key)
        {
            return p->data;
        }
        else
        {
            p = p->next;
        }
    }
    return -1;
}
int HashTable::Hash(int key)
{
    return key%10;
}
void HashTable::Insert(int key)
{
    int hldx = Hash(key);
    Node* t = new Node;
    t->data = key;
    t->next = nullptr;
    // Case No nodes in the linked list;
    if(HT[hldx] == nullptr)
    {
        HT[hldx] = t;
    }
    else
    {
        Node* p = HT[hldx];
        Node* q = HT[hldx];

        // Traverse to find Insert position
        while(p && p->data < key)
        {
            q = p;
            p = p->next;
        }
        // case Insert position first
        if(q==HT[hldx])
        {
            t->next = HT[hldx];
            HT[hldx] = t;
        }
        else
        {
            t->next = q->next;
            q->next = t;
        }
    }
}
HashTable::HashTable()
{
    HT = new Node*[10];
    for(int i =0; i<10; i++)
    {
        HT[i] = nullptr;
    }
}

HashTable::~HashTable()
{
    for(int i=0; i<10; i++)
    {
        Node* p = HT[i];
        while(HT[i])
        {
            HT[i] = HT[i]->next;
            delete p;
            p = HT[i];
        }
    }
    delete[] HT;
}
int main()
{
    int A[] = {16, 12, 25, 39, 6, 122, 5, 68, 75};
    int n = sizeof(A)/sizeof(A[0]);
    HashTable H;
    for(int i=0; i<n;i++)
    {
        H.Insert(A[i]);
    }
    cout << "Successful Search" << endl;
    int key = 6;
    int value = H.Search(key);
    cout << "Key: " << key << ", Value: " << value << endl;
    cout << "Unsuccessful Search" << endl;
    key = 95;
    value = H.Search(key);
    cout << "Key: " << key << ", Value: " << value << endl;
    return 0;
}

#include <iostream>
#define SIZE 10
using namespace std;
template <class T>
void Print(T& vec, int n, string s)
{
    cout<<s<<": ["<<flush;
    for(int i=0; i<n;i++)
    {
        cout<<vec[i]<<flush;
        if(i<n-1)
        {
            cout<<", " <<flush;
        }
    }
    cout<<"]"<<endl;
}
int Hash(int key)
{
    return key%SIZE;
}
int LinearProbe(int A[],int key)
{
    int idx = Hash(key);
    int i=0;
    while(A[idx+i]%SIZE != 0)
    {
        i++;
    }
    return (idx+i)%SIZE;
}
void Insert(int A[], int key)
{
    int idx = Hash(key);
    if(A[idx!=0])
    {
        idx = LinearProbe(A,key);
    }
    A[idx] = key;
}
int Search(int H[], int key)
{
    int idx = Hash(key);
    int i=0;
    while(H[(idx+i)%SIZE] != key)
    {
        i++;
        if(H[(idx+i)%SIZE] == 0)
            return -1;
    }
    return (idx+i)%SIZE;
}
int main()
{
    int A[] = {26, 30, 45, 23, 25, 43, 74, 19, 29};
    int n = sizeof(A)/sizeof(A[0]);
    Print(A, n, " A");
    // HASH TABLE
    int HT[10] = {0};
    for(int i=0; i<n;i++)
    {
        Insert(HT,A[i]);
    }
    Print(HT, SIZE, "HT");
    int index =Search(HT,25);
    cout << "key found at: " << index << endl;

    index = Search(HT, 35);
    cout << "key found at: " << index << endl;
    return 0;
}

#include <iostream>
#define SIZE 10
using namespace std;
template <class T>
void Print(T& vec, int n, string s)
{
    cout<<s<<": ["<<flush;
    for(int i=0; i<n;i++)
    {
        cout<<vec[i]<<flush;
        if(i<n-1)
        {
            cout<<", " <<flush;
        }
    }
    cout<<"]"<<endl;
}
int Hash(int key)
{
    return key%SIZE;
}
int QuadraticProbe(int A[],int key)
{
    int idx = Hash(key);
    int i=0;
    while(A[idx+i*i]%SIZE != 0)
    {
        i++;
    }
    return (idx+i*i)%SIZE;
}
void Insert(int A[], int key)
{
    int idx = Hash(key);
    if(A[idx!=0])
    {
        idx = QuadraticProbe(A,key);
    }
    A[idx] = key;
}
int Search(int H[], int key)
{
    int idx = Hash(key);
    int i=0;
    while(H[(idx+i*i)%SIZE] != key)
    {
        i++;
        if(H[(idx+i*i)%SIZE] == 0)
            return -1;
    }
    return (idx+i*i)%SIZE;
}
int main()
{
    int A[] = {26, 30, 45, 23, 25, 43, 74, 19, 29};
    int n = sizeof(A)/sizeof(A[0]);
    Print(A, n, " A");
    // HASH TABLE
    int HT[10] = {0};
    for(int i=0; i<n;i++)
    {
        Insert(HT,A[i]);
    }
    Print(HT, SIZE, "HT");
    int index =Search(HT,25);
    cout << "key found at: " << index << endl;

    index = Search(HT, 35);
    cout << "key found at: " << index << endl;
    return 0;
}

#include <iostream>
#define SIZE 10
#define PRIME 7
using namespace std;
template <class T>
void Print(T& vec, int n, string s)
{
    cout<<s<<": ["<<flush;
    for(int i=0; i<n;i++)
    {
        cout<<vec[i]<<flush;
        if(i<n-1)
        {
            cout<<", " <<flush;
        }
    }
    cout<<"]"<<endl;
}
int Hash(int key)
{
    return key%SIZE;
}
int PrimeHash(int key)
{
    return PRIME-(key%PRIME);
}
int DoubleHash(int A[],int key)
{
    int idx = Hash(key);
    int i=0;
    while(A[Hash(idx)+i*PrimeHash(idx)%SIZE] != 0)
    {
        i++;
    }
    return (idx+i*PrimeHash(idx)%SIZE)%SIZE;
}
void Insert(int A[], int key)
{
    int idx = Hash(key);
    if(A[idx!=0])
    {
        idx = DoubleHash(A,key);
    }
    A[idx] = key;
}
int Search(int H[], int key)
{
    int idx = Hash(key);
    int i=0;
    while(H[(Hash(idx)+i*PrimeHash(idx))%SIZE] != key)
    {
        i++;
        if(H[Hash(idx)+i*PrimeHash(idx)%SIZE] == 0)
            return -1;
    }
    return Hash(idx)+i*PrimeHash(idx)%SIZE;
}
int main()
{
    int A[] = {26, 30, 45, 23, 25, 43, 74, 19, 29};
    int n = sizeof(A)/sizeof(A[0]);
    Print(A, n, " A");
    // HASH TABLE
    int HT[10] = {0};
    for(int i=0; i<n;i++)
    {
        Insert(HT,A[i]);
    }
    Print(HT, SIZE, "HT");
    int index =Search(HT,25);
    cout << "key found at: " << index << endl;

    index = Search(HT, 35);
    cout << "key found at: " << index << endl;
    return 0;
}