#include <iostream>
using namespace std;

/*
    ============================================================
    LINEAR PROBING
    ============================================================
*/

class LinearProbingHashTable {
private:
    int* table;
    int tableSize;
    int count;
    const int EMPTY = -1;

    int hashFunction(int key) {
        return key % tableSize;
    }

public:
    LinearProbingHashTable(int size) {
        tableSize = size;
        count = 0;
        table = new int[tableSize];

        for (int i = 0; i < tableSize; i++) {
            table[i] = EMPTY;
        }
    }

    ~LinearProbingHashTable() {
        delete[] table;
    }

    bool insert(int key) {
        if (count == tableSize) {
            return false;
        }

        int h = hashFunction(key);

        while (table[h] != EMPTY) {
            h = (h + 1) % tableSize;
        }

        table[h] = key;
        count++;
        return true;
    }

    bool search(int key) {
        int h = hashFunction(key);
        int start = h;

        while (true) {
            if (table[h] == EMPTY) {
                return false;
            }

            if (table[h] == key) {
                return true;
            }

            h = (h + 1) % tableSize;

            if (h == start) {
                return false;
            }
        }
    }

    void print() {
        cout << "Linear Probing:\n";

        for (int i = 0; i < tableSize; i++) {
            cout << "[" << i << "] ";

            if (table[i] == EMPTY) {
                cout << "EMPTY";
            } else {
                cout << table[i];
            }

            cout << endl;
        }
    }
};

/*
    ============================================================
    QUADRATIC PROBING
    ============================================================
*/

class QuadraticProbingHashTable {
private:
    int* table;
    int tableSize;
    int count;
    const int EMPTY = -1;

    int hashFunction(int key) {
        return key % tableSize;
    }

public:
    QuadraticProbingHashTable(int size) {
        tableSize = size;
        count = 0;
        table = new int[tableSize];

        for (int i = 0; i < tableSize; i++) {
            table[i] = EMPTY;
        }
    }

    ~QuadraticProbingHashTable() {
        delete[] table;
    }

    bool insert(int key) {
        if (count == tableSize) {
            return false;
        }

        int h = hashFunction(key);

        for (int attempt = 0; attempt < tableSize; attempt++) {
            int index = (h + attempt * attempt) % tableSize;

            if (table[index] == EMPTY) {
                table[index] = key;
                count++;
                return true;
            }
        }

        return false;
    }

    bool search(int key) {
        int h = hashFunction(key);

        for (int attempt = 0; attempt < tableSize; attempt++) {
            int index = (h + attempt * attempt) % tableSize;

            if (table[index] == EMPTY) {
                return false;
            }

            if (table[index] == key) {
                return true;
            }
        }

        return false;
    }

    void print() {
        cout << "Quadratic Probing:\n";

        for (int i = 0; i < tableSize; i++) {
            cout << "[" << i << "] ";

            if (table[i] == EMPTY) {
                cout << "EMPTY";
            } else {
                cout << table[i];
            }

            cout << endl;
        }
    }
};

/*
    ============================================================
    DOUBLE HASHING
    ============================================================
*/

class DoubleHashingHashTable {
private:
    int* table;
    int tableSize;
    int count;
    int R;
    const int EMPTY = -1;

    int hash1(int key) {
        return key % tableSize;
    }

    int hash2(int key) {
        return R - (key % R);
    }

public:
    DoubleHashingHashTable(int size, int primeLessThanSize) {
        tableSize = size;
        R = primeLessThanSize;
        count = 0;
        table = new int[tableSize];

        for (int i = 0; i < tableSize; i++) {
            table[i] = EMPTY;
        }
    }

    ~DoubleHashingHashTable() {
        delete[] table;
    }

    bool insert(int key) {
        if (count == tableSize) {
            return false;
        }

        int h1 = hash1(key);
        int h2 = hash2(key);

        for (int attempt = 0; attempt < tableSize; attempt++) {
            int index = (h1 + attempt * h2) % tableSize;

            if (table[index] == EMPTY) {
                table[index] = key;
                count++;
                return true;
            }
        }

        return false;
    }

    bool search(int key) {
        int h1 = hash1(key);
        int h2 = hash2(key);

        for (int attempt = 0; attempt < tableSize; attempt++) {
            int index = (h1 + attempt * h2) % tableSize;

            if (table[index] == EMPTY) {
                return false;
            }

            if (table[index] == key) {
                return true;
            }
        }

        return false;
    }

    void print() {
        cout << "Double Hashing:\n";

        for (int i = 0; i < tableSize; i++) {
            cout << "[" << i << "] ";

            if (table[i] == EMPTY) {
                cout << "EMPTY";
            } else {
                cout << table[i];
            }

            cout << endl;
        }
    }
};

/*
    ============================================================
    CHAINING
    ============================================================
*/

class ChainingHashTable {
private:
    struct Node {
        int key;
        Node* next;

        Node(int k) {
            key = k;
            next = nullptr;
        }
    };

    Node** table;
    int tableSize;

    int hashFunction(int key) {
        return key % tableSize;
    }

public:
    ChainingHashTable(int size) {
        tableSize = size;
        table = new Node*[tableSize];

        for (int i = 0; i < tableSize; i++) {
            table[i] = nullptr;
        }
    }

    ~ChainingHashTable() {
        for (int i = 0; i < tableSize; i++) {
            Node* current = table[i];

            while (current != nullptr) {
                Node* temp = current;
                current = current->next;
                delete temp;
            }
        }

        delete[] table;
    }

    void insert(int key) {
        int index = hashFunction(key);

        Node* newNode = new Node(key);

        if (table[index] == nullptr) {
            table[index] = newNode;
        } else {
            Node* current = table[index];

            while (current->next != nullptr) {
                current = current->next;
            }

            current->next = newNode;
        }
    }

    bool search(int key) {
        int index = hashFunction(key);

        Node* current = table[index];

        while (current != nullptr) {
            if (current->key == key) {
                return true;
            }

            current = current->next;
        }

        return false;
    }

    void print() {
        cout << "Chaining:\n";

        for (int i = 0; i < tableSize; i++) {
            cout << "[" << i << "]";

            Node* current = table[i];

            while (current != nullptr) {
                cout << " -> " << current->key;
                current = current->next;
            }

            cout << endl;
        }
    }
};

/*
    ============================================================
    MAIN
    ============================================================
*/

int main() {
    int keys[] = {55, 35, 66, 76, 59, 48, 84, 70};
    int n = 8;

    cout << "==============================\n";
    cout << "Linear Probing Example\n";
    cout << "==============================\n";

    LinearProbingHashTable linearTable(11);

    for (int i = 0; i < n; i++) {
        linearTable.insert(keys[i]);
    }

    linearTable.print();

    cout << "Search 48: " << (linearTable.search(48) ? "Found" : "Not Found") << endl;
    cout << "Search 100: " << (linearTable.search(100) ? "Found" : "Not Found") << endl;

    cout << endl;

    cout << "==============================\n";
    cout << "Quadratic Probing Example\n";
    cout << "==============================\n";

    QuadraticProbingHashTable quadraticTable(11);

    for (int i = 0; i < n; i++) {
        quadraticTable.insert(keys[i]);
    }

    quadraticTable.print();

    cout << "Search 48: " << (quadraticTable.search(48) ? "Found" : "Not Found") << endl;
    cout << "Search 100: " << (quadraticTable.search(100) ? "Found" : "Not Found") << endl;

    cout << endl;

    cout << "==============================\n";
    cout << "Double Hashing Example\n";
    cout << "==============================\n";

    DoubleHashingHashTable doubleHashTable(11, 7);

    for (int i = 0; i < n; i++) {
        doubleHashTable.insert(keys[i]);
    }

    doubleHashTable.print();

    cout << "Search 48: " << (doubleHashTable.search(48) ? "Found" : "Not Found") << endl;
    cout << "Search 100: " << (doubleHashTable.search(100) ? "Found" : "Not Found") << endl;

    cout << endl;

    cout << "==============================\n";
    cout << "Chaining Example\n";
    cout << "==============================\n";

    ChainingHashTable chainingTable(10);

    int chainingKeys[] = {10, 12, 23, 26, 32, 52, 70, 88};
    int chainingN = 8;

    for (int i = 0; i < chainingN; i++) {
        chainingTable.insert(chainingKeys[i]);
    }

    chainingTable.print();

    cout << "Search 52: " << (chainingTable.search(52) ? "Found" : "Not Found") << endl;
    cout << "Search 99: " << (chainingTable.search(99) ? "Found" : "Not Found") << endl;

    return 0;
}