hashmaps

// Basically I'm creating an array on the stack for the table
// If we don't use chaining, it'll just be an array of integers/strings
// else, we have to use an array of integer/string vectors.

// If strings are used for hashing, then you will need to replace
// all of the int hashTable[] with string hashTable[] and
// use vs hashTable[] instead of vi hashTable[]

// There's actually a good amount of the overhead code that
// needs to be changed if your exam uses strings instead of
// integers to hash, but all of the individual functions are coorect

// Also I suggest writing everything on your own just in case and
// for more practice. I just used random variables for the things that are defined;
// those will most likely be given on the test

// One last thing, I used log base 2/10 of the size to get the r value
// for the mid square hashing functions. They might give us that value on the test,
// but just in case I have it calculated.

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

#define vi vector<int>
#define vs vector<string>
#define SIZE 100 // Given size
#define INITIAL_MULT_VALUE 20 // Given if multiplicative string hashing
#define MULTIPLIER 5 // Given if multiplicative string hashing
#define ADLER_MOD 65521 // Given if adler32 hashing
#define QUAD_PROBE_C1 4 // Given if quadratic probing
#define QUAD_PROBE_C2 5 // Given if quadratic probing

// Hashing functions
int hashItem(int key);
int hashItem(int string);
int moduloHash(int key);
int midSquare10Hash(int key);
int midSquare2Hash(int key);
int multiStringHash(string key);
int adler32Hash(string key);

// Insertion functions
bool insert(int(&hashTable)[SIZE], int item);
bool insert(vi(&hashTable)[SIZE], int item);
bool chainingInsert(vi(&hashTable)[SIZE], int item);
bool linearProbingInsert(int(&hashTable)[SIZE], int item);
bool quadraticProbingInsert(int(&hashTable)[SIZE], int item);
bool doubleHashingInsert(int(&hashTable)[SIZE], int item);

// Searching functions
// Deletion function if param "toDelete" is set to true
// Change param "query" to a string if using multiplicative string or adler32 hashing methods
bool search(int(&hashTable)[SIZE], int query, bool toDelete);
bool search(vi(&hashTable)[SIZE], int query, bool toDelete);
bool chainingSearch(vi(&hashTable)[SIZE], int query, bool toDelete);
bool linearProbingSearch(int(&hashTable)[SIZE], int query, bool toDelete);
bool quadraticProbingSearch(int(&hashTable)[SIZE], int query, bool toDelete);
bool doubleHashingSearch(int(&hashTable)[SIZE], int query, bool toDelete);

// Printing functions
void output(int(&hashTable)[SIZE]);
void output(vi(&hashTable)[SIZE]);

int main() {
    int hashTable[SIZE]; // If not using chaining
    for (int i = 0; i < SIZE; i++) hashTable[i] = -1; // If not using chaining

    // vi hashTable[SIZE]; // If using chaining

    // Main loop
    int choice = 0;
    while (choice != 5) {
        cout << "Hash Tables - Pick an option" << endl;
        cout << "1. Insert element" << endl;
        cout << "2. Search for an element" << endl;
        cout << "3. Delete an element" << endl;
        cout << "4. Output all elements" << endl;
        cout << "5. Exit" << endl;

        choice = 0;
        while (choice < 1 || choice > 5) {
            cout << "Enter an option (1-5): ";
            cin >> choice;
        }
        cout << endl;

        int q; // Change to string if using multiplicative string or adler32 hashing

        if (choice == 1) {
            int item;
            cout << "Enter the item you want to insert: ";
            cin >> item;
            cout << (insert(hashTable, item) ? "Sucessfully added " + to_string(item) : "Could not insert item into hash table") << endl << endl;
        }
        else if (choice == 2) {
            cout << "Enter key to search for: ";
            cin >> q;
            cout << (search(hashTable, q, false) ? "Item found" : "Item not found") << endl << endl;
        }
        else if (choice == 3) {
            cout << "Enter key to delete: ";
            cin >> q;
            cout << (search(hashTable, q, true) ? "Item deleted" : "Item not found") << endl << endl;
        }
        else if (choice == 4) output(hashTable);
    }
    return 0;
}

// -------------------------------------- General functions --------------------------------------

int hashItem(int key) {
    // Call a hashing function
    return moduloHash(key);
    // return midSquare10Hash(key);
    // return midSquare2Hash(key);
}

int hashItem(string key) {
    // These hashing functions have string keys
    return multiStringHash(key);
    // return adler32Hash(key);
}

bool insert(int(&hashTable)[SIZE], int item) {
    // return linearProbingInsert(hashTable, item);
    // return quadraticProbingInsert(hashTable, item);
    return doubleHashingInsert(hashTable, item);
}

bool insert(vi(&hashTable)[SIZE], int item) {
    // Chaining requires a vector<vector<int>>
    return chainingInsert(hashTable, item);
}

bool search(int(&hashTable)[SIZE], int query, bool toDelete) {
    // return linearProbingSearch(hashTable, query, toDelete);
    // return quadraticProbingSearch(hashTable, query, toDelete);
    return doubleHashingSearch(hashTable, query, toDelete);
}

bool search(vi(&hashTable)[SIZE], int query, bool toDelete) {
    // Chaining requires a vector<vector<int>>
    return chainingSearch(hashTable, query, toDelete);
}

// -------------------------------------- Hashing functions --------------------------------------

int moduloHash(int key) {
    return key % SIZE;
}

int midSquare10Hash(int key) {
    int r = (int)ceil(log10(SIZE));
    string s = to_string(key * key);
    int right = (s.length() - r) / 2;
    s.erase(s.length() - right, right);
    int left = s.size() - r;
    s.erase(0, left);
    return stoi(s) % SIZE;
}

int midSquare2Hash(int key) {
    int r = (int)ceil(log2(SIZE));
    key *= key;
    int lower = (32 - r) / 2;
    int bits = key >> lower;
    bits = bits & (0xFFFFFFFF >> (32 - r));
    return bits % SIZE;
}

int multiStringHash(string key) {
    long long out = INITIAL_MULT_VALUE;
    for (auto& s : key) {
        out = (out * MULTIPLIER) + s;
    }
    return out % SIZE;
}

int adler32Hash(string key) {
    int a = 1;
    int b = 0;
    for (auto& s : key) {
        a = (a + s) % ADLER_MOD;
        b = (b + a) % ADLER_MOD;
    }
    return ((b << 16) | a) % SIZE;
}

// -------------------------------------- Insertion functions --------------------------------------

bool chainingInsert(vi(&hashTable)[SIZE], int item) {
    if (!chainingSearch(hashTable, item, false)) return false;
    hashTable[hashItem(item)].push_back(item);
    return true;
}

bool linearProbingInsert(int(&hashTable)[SIZE], int item) {
    if (linearProbingSearch(hashTable, item, false)) return false;
    int bucket = hashItem(item);
    int count = 0;
    while (count < SIZE) {
        if (hashTable[bucket] == -1) {
            hashTable[bucket] = item;
            return true;
        }
        bucket = (bucket + 1) % SIZE;
        count++;
    }
    return false;
}

bool quadraticProbingInsert(int(&hashTable)[SIZE], int item) {
    if (quadraticProbingSearch(hashTable, item, false)) return false;
    int count = 0;
    int i = 0;
    int initialHash = hashItem(item);
    int bucket = initialHash;
    while (count < SIZE) {
        if (hashTable[bucket] == -1) {
            hashTable[bucket] = item;
            return true;
        }
        i++;
        bucket = (initialHash + QUAD_PROBE_C1 * i + QUAD_PROBE_C2 * i * i) % SIZE;
        count++;
    }
    return false;
}

bool doubleHashingInsert(int(&hashTable)[SIZE], int item) {
    if (doubleHashingSearch(hashTable, item, false)) return false;
    int hash1 = moduloHash(item); // These can be any 2 hashing functions
    int hash2 = midSquare2Hash(item);
    int count = 0;
    int i = 0;
    int bucket;
    while (count < SIZE) {
        bucket = (hash1 + hash2 * i) % SIZE;
        if (hashTable[bucket] == -1) {
            hashTable[bucket] = item;
            return true;
        }
        i++;
        count++;
    }
    return false;
}

// -------------------------------------- Search and delete functions --------------------------------------

bool chainingSearch(vi(&hashTable)[SIZE], int query, bool toDelete) {
    auto& list = hashTable[hashItem(query)];
    for (int i = 0; i < list.size(); i++) {
        if (list[i] == query) {
            if (toDelete) list.erase(list.begin() + i);
            return true;
        }
    }
    return false;
}

bool linearProbingSearch(int(&hashTable)[SIZE], int query, bool toDelete) {
    int bucket = hashItem(query);
    int count = 0;
    while (count < SIZE) {
        if (hashTable[bucket] == query) {
            if (toDelete) hashTable[bucket] = -1;
            return true;
        }
        bucket = (bucket + 1) % SIZE;
        count++;
    }
    return false;
}

bool quadraticProbingSearch(int(&hashTable)[SIZE], int query, bool toDelete) {
    int count = 0;
    int i = 0;
    int initialHash = hashItem(query);
    int bucket = initialHash;
    while (count < SIZE) {
        if (hashTable[bucket] == query) {
            if (toDelete) hashTable[bucket] = -1;
            return true;
        }
        i++;
        bucket = (initialHash + QUAD_PROBE_C1 * i + QUAD_PROBE_C2 * i * i) % SIZE;
        count++;
    }
    return false;
}

bool doubleHashingSearch(int(&hashTable)[SIZE], int query, bool toDelete) {
    int hash1 = moduloHash(query); // These can be any 2 hashing functions
    int hash2 = midSquare2Hash(query);
    int count = 0;
    int i = 0;
    int bucket;
    while (count < SIZE) {
        bucket = (hash1 + hash2 * i) % SIZE;
        if (hashTable[bucket] == query) {
            if (toDelete) hashTable[bucket] = -1;
            return true;
        }
        i++;
        count++;
    }
    return false;
}

// -------------------------------------- Output functions --------------------------------------

void output(int(&hashTable)[SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        if (hashTable[i] != -1) {
            cout << i << ": " << hashTable[i] << endl;
        }
    }
    cout << endl;
}

void output(vi(&hashTable)[SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (auto& item : hashTable[i]) {
            cout << i << ": " << item << endl;
        }
    }
    cout << endl;
}