5c

#include <iostream>
#include <fstream>
#include <string>
#include <cmath>

class LinkedList {
public:
    class LinkedListNode {
    public:
        std::string key = "";
        std::string value = "";

        LinkedListNode* p_prev = nullptr;
        LinkedListNode* p_next = nullptr;

        LinkedListNode* p_prev_enter = nullptr;
        LinkedListNode* p_next_enter = nullptr;
    };

    void add(const std::string &key, const std::string &value, LinkedListNode *&ptr_prev);

    void removeKey(const std::string& key, LinkedListNode* &check_ptr);

    bool getValue(const std::string& key, std::string& value);

    bool getPrevValue(const std::string& key, std::string& value);

    bool getNextValue(const std::string& key, std::string& value);

    long size();

    ~LinkedList();

private:
    LinkedListNode* p_begin = nullptr;
    LinkedListNode* p_end = nullptr;
    long list_size = 0;

    LinkedListNode* findKey(const std::string& key);
};

class LinkedStringHashMap {
public:
    explicit LinkedStringHashMap(long size);

    ~LinkedStringHashMap();

    void add(const std::string& key, const std::string& value);

    bool get(const std::string& key, std::string& value);

    bool getPrev(const std::string& key, std::string& value);

    bool getNext(const std::string& key, std::string& value);

    void remove(std::string& key);

private:
    LinkedList* table = nullptr;
    long table_size;
    const double A = (sqrt(5) - 1) / 2;

    long hash(const std::string& key);

    LinkedList::LinkedListNode* prev_enter_ptr = nullptr;

};

// LinkedList class methods
LinkedList::~LinkedList() {
    LinkedListNode* p_look = p_begin;
    while (p_look != nullptr) {
        LinkedListNode* temp = p_look;
        p_look = p_look->p_next;
        delete(temp);
    }

    p_begin = nullptr;
    p_end = nullptr;
}

void LinkedList::add(const std::string &key,
                     const std::string &value,
                     LinkedList::LinkedListNode *&ptr_prev) {
    LinkedListNode* ptr_temp = findKey(key);
    if (ptr_temp != nullptr) {
        ptr_temp->value = value;
        return;
    }

    list_size++;
    auto* temp = new LinkedListNode;
    temp->value = value;
    temp->key = key;

    temp->p_prev_enter = ptr_prev;
    if (ptr_prev != nullptr)
        ptr_prev->p_next_enter = temp;

    if (p_end == nullptr) {
        p_begin = temp;
        p_end = temp;
        ptr_prev = p_end;
        return;
    }

    temp->p_prev = p_end;
    p_end->p_next = temp;
    p_end = temp;
    ptr_prev = p_end;
}

void LinkedList::removeKey(const std::string &key, LinkedList::LinkedListNode *&check_ptr) {
    LinkedListNode* ptr_temp = findKey(key);
    if (ptr_temp == nullptr)
        return;

    if (ptr_temp == check_ptr)
        check_ptr = ptr_temp->p_prev_enter;

    if (ptr_temp == p_begin)
        p_begin = ptr_temp->p_next;
    if (ptr_temp == p_end)
        p_end = ptr_temp->p_prev;

    if (ptr_temp->p_prev != nullptr)
        ptr_temp->p_prev->p_next = ptr_temp->p_next;
    if (ptr_temp->p_next != nullptr)
        ptr_temp->p_next->p_prev = ptr_temp->p_prev;

    if (ptr_temp->p_prev_enter != nullptr)
        ptr_temp->p_prev_enter->p_next_enter = ptr_temp->p_next_enter;
    if (ptr_temp->p_next_enter != nullptr)
        ptr_temp->p_next_enter->p_prev_enter = ptr_temp->p_prev_enter;

    delete(ptr_temp);
    --list_size;
}

bool LinkedList::getValue(const std::string &key, std::string &value) {
    LinkedListNode* ptr_temp = findKey(key);
    if (ptr_temp == nullptr)
        return false;

    value = ptr_temp->value;
    return true;
}

bool LinkedList::getPrevValue(const std::string &key, std::string &value) {
    LinkedListNode* ptr_temp = findKey(key);
    if (ptr_temp == nullptr || ptr_temp->p_prev_enter == nullptr)
        return false;

    value = ptr_temp->p_prev_enter->value;
    return true;
}

bool LinkedList::getNextValue(const std::string &key, std::string &value) {
    LinkedListNode* ptr_temp = findKey(key);
    if (ptr_temp == nullptr || ptr_temp->p_next_enter == nullptr)
        return false;

    value = ptr_temp->p_next_enter->value;
    return true;
}

long LinkedList::size() {
    return list_size;
}

LinkedList::LinkedListNode *LinkedList::findKey(const std::string &key) {
    if (!list_size)
        return nullptr;

    LinkedListNode *p_look = p_begin;
    while (p_look != nullptr && p_look->key != key)
        p_look = p_look->p_next;
    return p_look;
}

// LinkedStringHashMap class methods
LinkedStringHashMap::LinkedStringHashMap(long size) {
    table = new LinkedList[size];
    table_size = size;
}

LinkedStringHashMap::~LinkedStringHashMap() {
    delete[](table);
    table = nullptr;
}

long LinkedStringHashMap::hash(const std::string &key) {
    int keyVal = 0;
    for (int i = 0; i < key.length(); ++i) {
        keyVal += key[i] * (i + 1);
    }
    keyVal *= key.length() + 1;

    double int_part;
    return (long)(table_size * modf(keyVal * A, &int_part));
}

void LinkedStringHashMap::add(const std::string &key, const std::string &value) {
    table[hash(key)].add(key, value, prev_enter_ptr);
}

void LinkedStringHashMap::remove(std::string &key) {
    table[hash(key)].removeKey(key, prev_enter_ptr);
}

bool LinkedStringHashMap::get(const std::string &key, std::string &value) {
    return table[hash(key)].getValue(key, value);
}

bool LinkedStringHashMap::getPrev(const std::string &key, std::string &value) {
    return table[hash(key)].getPrevValue(key, value);
}

bool LinkedStringHashMap::getNext(const std::string &key, std::string &value) {
    return table[hash(key)].getNextValue(key, value);
}


#define IN_FILE_NAME "linkedmap.in"
#define OUT_FILE_NAME "linkedmap.out"

using std::ifstream;
using std::ofstream;
using std::string;

int main() {
    ifstream fin(IN_FILE_NAME);
    if (!fin.is_open())
        return 2;

    ofstream fout(OUT_FILE_NAME);
    if (!fout.is_open())
        return 2;

    LinkedStringHashMap linked_map(20);
    while (true) {
        string command;
        fin >> command;

        if (command.empty())
            break;

        string key;
        fin >> key;
        if (command == "put") {
            string value;
            fin >> value;
            linked_map.add(key, value);
        }
        else if (command == "get") {
            string value;
            if (linked_map.get(key, value))
                fout << value << '\n';
            else
                fout << "none\n";
        }
        else if (command == "delete") {
            linked_map.remove(key);
        }
        else if (command == "prev") {
            string value;
            if (linked_map.getPrev(key, value))
                fout << value << '\n';
            else
                fout << "none\n";
        }
        else if (command == "next") {
            string value;
            if (linked_map.getNext(key, value))
                fout << value << '\n';
            else
                fout << "none\n";
        }
    }
    return 0;
}