HW4_hash_table_open_adressing

#include <iostream>
#include <vector>
#include <string>

struct HashTableCell
{
    std::string str;
    int state = 0;
};

class HashTable
{
public:
    HashTable();
    HashTable(size_t base, size_t startCapacity);
    bool Add(const std::string &value);
    bool Find(const std::string &value);
    bool Delete(const std::string &value);
private:
    std::vector <HashTableCell> hash_table;
    size_t hash_base;
    size_t size;
    bool isNull(size_t index) const;
    bool isDeleted(size_t index) const;
    size_t hash(const std::string &value, int hash_base);
    size_t linear_step(const std::string &value, size_t iter) { return (hash(value, hash_base) + iter + 1) % hash_table.size(); }
    size_t double_step(const std::string &value, size_t iter) { return (hash(value, hash_base) + iter * hash(value, 5)) % hash_table.size(); }
    size_t quadratic_step(size_t key, size_t iter);
    void rehash();
};

HashTable::HashTable(size_t base, size_t startCapacity) : hash_table(startCapacity),
hash_base(base), size(0)
{}

void HashTable::rehash()
{
    auto old_data(std::move(hash_table));
    size_t old_size = size;
    hash_table.clear();
    hash_table.resize(old_data.size() * 2);
    size = 0;
    for (auto& i : old_data)
        if (1 == i.state)
            Add(i.str);
}

size_t HashTable::quadratic_step(size_t key, size_t iter)
{
    return (key + iter + 1) % hash_table.size();
}

size_t HashTable::hash(const std::string& value, int hash_base)
{
    size_t ans = 1;
    for (size_t i = 0; i < value.size(); i++)
        ans = (static_cast<size_t>(value[i]) + ans) * hash_base;
    return ans;
}

bool HashTable::isNull(size_t index) const
{
    return hash_table[index].state == 0;
}

bool HashTable::isDeleted(size_t index) const
{
    return hash_table[index].state == -1;
}

bool HashTable::Add(const std::string& value)
{
    if (Find(value))
        return false;
    size_t key = hash(value, hash_base) % hash_table.size();
    for (size_t i = 0; i < hash_table.size(); i++)
    {
        if (isNull(key) || isDeleted(key))
        {
            hash_table[key].str = value;
            hash_table[key].state = 1;
            size++;
            if (2 * size >= hash_table.size())
                rehash();
            return true;
        }
        key = quadratic_step(key, i);
    }
    return false;
}

bool HashTable::Find(const std::string& value)
{
    size_t key = hash(value, hash_base) % hash_table.size();
    for (size_t i = 0; i < hash_table.size(); i++)
    {
        if (isNull(key))
            return false;
        if (hash_table[key].str == value)
            return true;
        key = quadratic_step(key, i);
    }
    return false;
}

bool HashTable::Delete(const std::string& value)
{
    if (!Find(value))
        return false;
    size_t key = hash(value, hash_base) % hash_table.size();
    for (size_t i = 0; i < hash_table.size(); i++)
    {
        if (isNull(key))
            return false;
        if (hash_table[key].str == value)
        {
            hash_table[key].state = -1;
            hash_table[key].str = "";
            size--;
            return true;
        }
        key = quadratic_step(key, i);
    }
    return false;
}

void result(bool res)
{
    if (res)
        std::cout << "OK\n";
    else
        std::cout << "FAIL\n";
}

int main()
{
    size_t N = 8;
    HashTable h(3, N);
    char operation;
    std::string str;
    while (std::cin)
    {
        std::cin >> operation >> str;
        if (operation == '+')
            result(h.Add(str));
        else if (operation == '-')
            result(h.Delete(str));
        else
            result(h.Find(str));
    }
    return 0;
}