Biographical guide

#include <iostream>
#include <time.h>
#include <conio.h>

using namespace std;

//кількість клієнтів хеш-таблиці
#define CLIENTS_COUNT   10

//розмір хеш таблиці
#define HASHTABLE_SIZE  10

//початок адреси клієнта (потрібно для ідентифікації адреси)
#define ADDRESS_IND     '$'

//повідомлення при відсутності запису у хеш-таблиці
#define NO_RECORD       "None"

//типи даних
#define PHONE_TYPE      string
#define SURNAME_TYPE    string
#define DATA_TYPE       string

//з'єднання між клієнтами
const int connections[CLIENTS_COUNT][3] = {
    {9, 1, -1}, //з'єднання першого клієнта
    {0, 2, -1}, //з'єднання другого клієнта
    {1, 3, -1}, //з'єднання i-го клієнта
    {2, 4, -1},
    {3, 5, -1},
    {4, 6, -1},
    {5, 7, -1},
    {6, 8, -1},
    {7, 9, -1},
    {8, 0, -1}
};

//структура елемента звичайної хеш-таблиці
template <typename keyType, typename dataType> struct HashTableNode {
    keyType key; //ключ
    dataType data; //значення
    HashTableNode* next = NULL;  //адреса на наступний елемент

    HashTableNode(keyType _key, dataType _data) : key(_key), data(_data) {}
};

//клас звичайної хеш-таблиці
template <typename keyType, typename dataType> class HashTable {
    private:
        //хеш-таблиця
        HashTableNode<keyType, dataType>* hashTable[HASHTABLE_SIZE];

        //кількість записів у хеш-таблиці
        int recordsCount;

        //хеш-функція
        int hash(keyType key) {
            int sum = 0;

            for (int i = 0; i < key.length(); i++)
                sum += key[i];

            return sum % HASHTABLE_SIZE;
        }

    public:
        HashTable() {
            recordsCount = 0;

            for (int i = 0; i < HASHTABLE_SIZE; i++)
                hashTable[i] = NULL;
        }

        //функція занесення інформації у хеш-таблицю
        void push(keyType key, dataType data) {
            recordsCount++;

            //визначаємо індекс у хеш-таблиці через хеш-функцію
            int hashIndex = hash(key);

            HashTableNode<keyType, dataType>* newHashNode = new HashTableNode<keyType, dataType>(key, data);

            HashTableNode<keyType, dataType>* hashNode = hashTable[hashIndex];

            //шукаємо останній елемент у комірці хеш-таблиці
            if (hashNode == NULL) {
                hashTable[hashIndex] = newHashNode;
            } else {
                while (hashNode->next) {
                    hashNode = hashNode->next;
                }
                //додаємо у кінець комірки новий елемент
                hashNode->next = newHashNode;
            }
        }

        //функція для отримання даних за ключем
        dataType get(keyType key) {
            //визначаємо індекс у хеш-таблиці через хеш-функцію
            int hashIndex = hash(key);

            HashTableNode<keyType, dataType>* hashNode = hashTable[hashIndex];

            //знаходимо елемент хеш-таблиці, доки не знайшли елемент з заданим ключем
            while (hashNode) {
                if (hashNode->key == key) {
                    //повертаємо знайдене значення
                    return hashNode->data;
                }
                hashNode = hashNode->next;
            }
            return NO_RECORD;
        }

        //функція для видалення елемента з хеш-таблиці
        void pop(keyType key) {
            //визначаємо індекс у хеш-таблиці через хеш-функцію
            int hashIndex = hash(key);

            HashTableNode<keyType, dataType>* hashNode = hashTable[hashIndex];
            HashTableNode<keyType, dataType>* preHashNode;

            //продовжуємо пошуки, доки не знайшли елемент із заданим ключем
            while (hashNode) {
                //якщо знайшли елемент , то видаляємо його
                if (hashNode->key == key) {
                    recordsCount--;
                    if (hashNode->next == NULL) {
                        if (hashTable[hashIndex]->key == key) {
                            hashTable[hashIndex] = NULL;
                        } else {
                            (*preHashNode).next = NULL;
                        }
                    } else {
                        *hashNode = *hashNode->next;
                    }
                    return;
                }
                preHashNode = hashNode;
                hashNode = hashNode->next;
            }
        }

        //функція для знаходження кількості записів у хеш-таблиці
        int getRecordsCount() {return recordsCount;}

        //функція для отримання усіх ключів хеш-таблицю
        keyType* getKeys() {
            //якщо немає записів, то повертаємо NULL
            if (recordsCount == 0) return NULL;

            keyType* keys = new keyType[recordsCount];
            HashTableNode<keyType, dataType>* hashNode;

            //рухаємось по усім коміркам хеш-таблиці
            for (int i = 0, k = 0; i < HASHTABLE_SIZE; i++) {
                hashNode = hashTable[i];

                //доки не дійшли до кінця комірки
                while (hashNode != NULL) {
                    //записуємо ключі у масив
                    keys[k++] = hashNode->key;
                    hashNode = hashNode->next;
                }
            }
            return keys;
        }
};

//клас розподіленої хеш-таблиці
template <typename keyType, typename dataType> class DHashTable {
    private:
        //клієнти хеш таблиці
        HashTable<keyType, dataType> clients[CLIENTS_COUNT];

    public:
        //функція для занесення даних у хеш-таблицю клієнта з адресою clientId
        void push(int clientId, keyType key, dataType data) {
            //якщо дані не були занесені, то заносимо
            if (clients[clientId].get(key) == NO_RECORD) {
                clients[clientId].push(key, data);

                int i = 0;

                //заносимо дані до всіх приєднаних клієнтів і вказуємо адресу даних як адресу даного клієнта
                while (connections[clientId][i] != -1) {
                    int newClientId = connections[clientId][i++];
                    dataType newData = ADDRESS_IND + to_string(clientId);

                    push(newClientId, key, newData);
                }
            }
        }

        //фукнція для отримання даних із хеш-таблиці клієнта з адресою clientId
        dataType get(int clientId, keyType key) {
            //отримуємо дані
            dataType data = clients[clientId].get(key);

            //якщо отримані дані це адреса, то знаходимо дані вже за новою адресою
            if (data[0] == ADDRESS_IND) {
                int newClientId = 0;

                //перетворюємо адресу із string в int
                for (int i = data.length() - 1, s = 1; i > 0; i--, s *= 10) {
                    newClientId += (data[i] - '0') * s;
                }
                //знаходимо дані за новою адресою
                return get(newClientId, key);
            }
            //якщо дані виявились не адресою, то повертаємо їх і припиняємо пошук
            return data;
        }

        //функція для видалення запису із хеш-таблиці клієнта із адресою clientId
        void pop(int clientId, keyType key) {
            //якщо такий запис існує
            if (clients[clientId].get(key) != NO_RECORD) {
                //видаляємо його
                clients[clientId].pop(key);

                int i = 0;

                //повідомляємо всім з'єднаним клієнтам про видалення даних
                while (connections[clientId][i] != -1) {
                    int newClientId = connections[clientId][i++];

                    pop(newClientId, key);
                }
            }
        }

        //функція для отримання всіх ключів у розподіленій хеш-таблиці
        keyType* getKeys() {return clients[0].getKeys();}

        //функція для отримання кількості записів у розподіленій хеш-таблиці
        int getRecordsCount() {return clients[0].getRecordsCount();}
};

int main() {
    srand(time(NULL));

    DHashTable<PHONE_TYPE, SURNAME_TYPE> surnameTable;
    DHashTable<SURNAME_TYPE, DATA_TYPE> dataTable;

    while (1) {
        int clientId = rand() % CLIENTS_COUNT;

        system("CLS");

        cout << "###Biographical guide###" << endl << endl;

        cout << "Records in guide: " << dataTable.getRecordsCount() << endl << endl;

        if (dataTable.getRecordsCount()) {
            cout << "Records:" << endl;

            SURNAME_TYPE* surnames = dataTable.getKeys();
            PHONE_TYPE* phones = surnameTable.getKeys();

            for (int i = 0; i < dataTable.getRecordsCount(); i++) {
                PHONE_TYPE phone;

                for (int j = 0; j < dataTable.getRecordsCount(); j++)
                    if (surnameTable.get(clientId, phones[j]) == surnames[i])
                        phone = phones[j];

                cout << surnames[i] << " : " << phone << endl;
            }
            cout << endl;
        }

        cout << "Commands:" << endl;
        cout << "Add new record -> add" << endl;
        cout << "Remove record -> pop" << endl;
        cout << "Find record -> get" << endl << endl;

        string command, key;
        PHONE_TYPE phone;
        SURNAME_TYPE surname;
        DATA_TYPE data;

        cout << "Enter command: ";
        cin >> command;

        if (command == "add") {
            cout << endl << "Enter surname: " << endl;;
            cin >> surname;

            cout << endl << "Enter phone: " << endl;;
            cin >> phone;

            cout << endl << "Enter info about person: " << endl;
            cin.ignore();
            getline(cin, data);

            surnameTable.push(clientId, phone, surname);
            dataTable.push(clientId, surname, data);

        } else if (command == "pop") {
            cout << endl << "Enter surname or phone: " << endl;;
            cin >> key;

            if (surnameTable.get(clientId, key) != NO_RECORD) {
                dataTable.pop(clientId, surnameTable.get(clientId, key));
                surnameTable.pop(clientId, key);
            } else if (dataTable.get(clientId, key) != NO_RECORD) {
                PHONE_TYPE phone;
                PHONE_TYPE* phones = surnameTable.getKeys();

                for (int j = 0; j < dataTable.getRecordsCount(); j++)
                    if (surnameTable.get(clientId, phones[j]) == key)
                        phone = phones[j];

                surnameTable.pop(clientId, phone);
                dataTable.pop(clientId, key);
            }

        } else if (command == "get") {
            cout << endl << "Enter surname or phone: " << endl;;
            cin >> key;

            if (surnameTable.get(clientId, key) != NO_RECORD) {
                cout << endl << "Surname:" << endl;
                cout << surnameTable.get(clientId, key) << endl;
                cout << endl << "Info:" << endl;
                cout << dataTable.get(clientId, surnameTable.get(clientId, key)) << endl;
            } else if (dataTable.get(clientId, key) != NO_RECORD) {
                cout << endl << "Phone:" << endl;

                PHONE_TYPE phone;
                PHONE_TYPE* phones = surnameTable.getKeys();

                for (int j = 0; j < dataTable.getRecordsCount(); j++)
                    if (surnameTable.get(clientId, phones[j]) == key)
                        phone = phones[j];

                cout << phone << endl;
                cout << endl << "Info:" << endl;
                cout << dataTable.get(clientId, key) << endl;
            }
        } else {
            cout << endl << "Error!" << endl;
        }
        cout << endl << "Press key to continue" << endl;
        _getch();
    }

    return 0;
}