#include<iostream>
#include<cstdlib>
#include<string>
#include<windows.h>
using namespace std;
const int MAX = 50;
int a_a = 0;
int*a = new int[];
struct htype
{
    string passport;
    string FIO;
    string BirthYear;
    string WhyCome;
    htype*next;
}primary[MAX];
void init()
{
    for (int i = 0; i < MAX; i++)
    {
        primary[i].passport.empty();
        primary[i].FIO.empty();
        primary[i].BirthYear.empty();
        primary[i].WhyCome.empty();
        primary[i].next = NULL;
    }
}
int hash_func(string pass)
{
    int loc = 0, h;
    for (int i = 0; i < pass.size(); i++)
    {
        loc += int(pass[i]);
    }
    h = loc%MAX;
    return h;
}
void add(string pass, string FIO, string Birth, string why)
{
    int h;
    htype *p0;
    htype *p = new htype;
    h = hash_func(pass);
    if (primary[h].passport.empty())
    {
        primary[h].passport = pass;
        primary[h].FIO = FIO;
        primary[h].BirthYear = Birth;
        primary[h].WhyCome = why;
        a_a++;
        a[a_a] = h;
        return;
    }
    else if (!primary[h].passport.empty())
    {
        p0 = primary[h].next;
        primary[h].next = p;
        p->passport = pass;
        p->FIO = FIO;
        p->BirthYear = Birth;
        p->WhyCome = why;
        p->next = p0;
        return;
    }
}
void find(string pass)
{
    int h;
    htype*p;
    h = hash_func(pass);
    if (primary[h].passport == pass)
    {
        cout << "Пасспорт: " << primary[h].passport << endl;
        cout << "ФИО: " << primary[h].FIO << endl;
        cout << "Год: " << primary[h].BirthYear << endl;
        cout << "Цель прибывания: " << primary[h].WhyCome << endl;
    }
    else
    {
        p = primary[h].next;
        while (p)
        {
            if (p->passport == pass)
            {
                cout << "Пасспорт: " << p->passport << endl;
                cout << "ФИО: " << p->FIO << endl;
                cout << "Год: " << p->BirthYear << endl;
                cout << "Цель прибывания: " << p->WhyCome << endl;
            }
            p = p->next;
        }
        cout << "Такого постояльца нет!" << endl;
    }
}
void HDel_elem(string pass)
{
    int h;
    htype*p;
    h = hash_func(pass);
    if (primary[h].passport == pass)
    {
        cout << "Пасспорт: " << primary[h].passport << endl;
        cout << "ФИО: " << primary[h].FIO << endl;
        cout << "Год: " << primary[h].BirthYear << endl;
        cout << "Цель прибывания: " << primary[h].WhyCome << endl;
        primary[h].passport.clear();
        primary[h].FIO.clear();
        primary[h].BirthYear.clear();
        primary[h].WhyCome.clear();
        primary[h].next = NULL;
        cout << "Данные удалены!" << endl;
    }
    else
    {
        p = primary[h].next;
        while (p)
        {
            if (p->passport == pass)
            {
                cout << "Пасспорт: " << p->passport << endl;
                cout << "ФИО: " << p->FIO << endl;
                cout << "Год: " << p->BirthYear << endl;
                cout << "Цель прибывания: " << p->WhyCome << endl;
                p->passport = p->passport.empty();
                p->FIO = p->FIO.empty();
                p->BirthYear = p->BirthYear.empty();
                p->WhyCome = p->WhyCome.empty();
                primary[h].next = NULL;
                cout << "Данные удалены!" << endl;
            }
            p = p->next;
        }
        cout << "Такого постояльца нет!" << endl;
    }
}
void HdelAll()
{
    for (int i = MAX - 1; i >= 0; i--)
    {
        primary[i].passport.clear();
        primary[i].FIO.clear();
        primary[i].BirthYear.clear();
        primary[i].WhyCome.clear();
        primary[i].next = NULL;
    }
}
void HShowALL()
{
    htype*p;
    cout << endl;
    for (int i = 0; i<MAX; i++)
    {
        cout << i + 1 << ") " << endl;
        cout << "Пасспорт: " << primary[i].passport << endl;
        cout << "ФИО: " << primary[i].FIO << endl;
        cout << "Год рождения: " << primary[i].BirthYear << endl;
        cout << "Причина прибывания" << primary[i].WhyCome << endl;
        p = primary[i].next;
        while (p != NULL)
        {
            cout << i + 1 << ") " << p->passport;
            cout << p->FIO;
            cout << p->BirthYear;
            cout << p->WhyCome;
            p = p->next;
        }
        cout << endl;
    }
}
struct Tree
{
    string Number;
    int Place;
    int Rooms;
    bool WC;
    string Equipments;
    Tree*Left;
    Tree*Right;
    int height;
};
int height_tree(Tree*tree)
{
    int temp;
    if (tree == NULL)
    {
        return(-1);
    }
    else
    {
        temp = tree->height;
        return temp;
    }
}
int Max(int temp1, int temp2)
{
    return ((temp1 > temp2) ? temp1 : temp2);
}
Tree srl(Tree*&tree)
{
    Tree* t2;
    t2 = tree->Left;
    tree->Left = t2->Right;
    t2->Right = tree;
    tree->height = Max(height_tree(tree->Left), height_tree(tree->Right)) + 1;
    t2->height = Max(height_tree(tree->Left), t2->height) + 1;
    return *t2;
}
Tree srr(Tree*&tree)
{
    Tree* tree2;
    tree2 = tree->Right;
    tree->Right = tree2->Left;
    tree2->Left = tree;
    tree->height = Max(height_tree(tree->Left), height_tree(tree->Right)) + 1;
    tree2->height = Max(tree->height, height_tree(tree2->Right)) + 1;
    return *tree2;
}
Tree drl(Tree*&tree)
{
    *tree->Left = srr(tree->Right);
    return srr(tree);
}
Tree drr(Tree*&tree)
{
    *tree->Right = srl(tree->Right);
    return srr(tree);
}
int temp_of(string Numb)
{
    int loc = 0;
    loc = ((Numb[1] - 48) * 100 + (Numb[2] - 48) * 10 - (Numb[3] - 48) * 1) + 6;
    return loc;
}
void add_tree(string Number, int Place, int Rooms, bool WC, string Equipments, Tree*tree)
{
    if (tree == NULL)
    {
        tree = new Tree;
        tree->Number = Number;
        tree->Place = Place;
        tree->Rooms = Rooms;
        tree->WC = WC;
        tree->Equipments = Equipments;
        tree->Left = NULL;
        tree->Right = NULL;
        tree->height = 0;
    }
    else
    {
        if (temp_of(Number) < temp_of(tree->Number))
        {
            add_tree(Number, Place, Rooms, WC, Equipments, tree->Left);
            if (height_tree(tree->Left) - height_tree(tree->Right) == 2)
            {
                if (temp_of(Number)<temp_of(tree->Number))
                {
                    *tree = srl(tree);
                }
                else
                {
                    *tree = srl(tree);
                }
            }
        }
        else if (temp_of(Number) > temp_of(tree->Number))
        {
            add_tree(Number, Place, Rooms, WC, Equipments, tree->Right);
            if (height_tree(tree->Right) - height_tree(tree->Left) == 2)
            {
                if (temp_of(Number) > temp_of(tree->Number))
                {
                    *tree = srr(tree);
                }
                else
                {
                    *tree = drr(tree);
                }
            }
        }
        else
        {
            cout << "Такой номер уже существует!" << endl;
        }
    }
}
void find_tree(string elem, Tree*&tree)
{
    if (tree == NULL)
    {
        cout << "База номеров пуста, пожалуйста добавте номер!" << endl;
    }
    else
    {
        while (elem != tree->Number)
        {
            if (elem < tree->Number)
            {
                find_tree(elem, tree->Left);
                cout << "Номер " << endl;
                cout << tree->Number << endl;
                cout << "Мест: " << endl;
                cout << tree->Place << endl;
                cout << "Rоличество комнат: " << endl;
                cout << tree->Rooms << endl;
                cout << "Наличие санузла \n 1 - есть \n 0 - нет" << endl;
                cout << tree->WC << endl;
            }
            else if (elem>tree->Number)
            {
                find_tree(elem, tree->Right);
                cout << "Номер " << endl;
                cout << tree->Number << endl;
                cout << "Мест: " << endl;
                cout << tree->Place << endl;
                cout << "Rоличество комнат: " << endl;
                cout << tree->Rooms << endl;
                cout << "Наличие санузла \n 1 - есть \n 0 - нет" << endl;
                cout << tree->WC << endl;
            }
            else
            {
                cout << "Номер " << endl;
                cout << tree->Number << endl;
                cout << "Мест: " << endl;
                cout << tree->Place << endl;
                cout << "Rоличество комнат: " << endl;
                cout << tree->Rooms << endl;
                cout << "Наличие санузла \n 1 - есть \n 0 - нет" << endl;
                cout << tree->WC << endl;
            }
        }
    }
}
void direct_by_pass(Tree*&tree)
{
    if (tree != NULL)
    {
        cout << "Номер " << endl;
        cout << tree->Number << endl;
        cout << "Мест: " << endl;
        cout << tree->Place << endl;
        cout << "Rоличество комнат: " << endl;
        cout << tree->Rooms << endl;
        cout << "Наличие санузла \n 1 - есть \n 0 - нет" << endl;
        cout << tree->WC << endl;
        direct_by_pass(tree->Left);
        direct_by_pass(tree->Right);
    }
}
void Delete_Elem_tree(string elem, Tree*&tree)
{
    Tree*del;
    if (tree == NULL)
    {
        cout << "Такого номера нет!" << endl;
    }
    else if (elem < tree->Number)
    {
        Delete_Elem_tree(elem, tree->Left);
    }
    else if (elem > tree->Number)
    {
        Delete_Elem_tree(elem, tree->Right);
    }
    else if ((tree->Left == NULL) && (tree->Right == NULL))
    {
        del = tree;
        free(del);
        tree = NULL;
        cout << "Номер удален!" << endl;
    }
    else if (tree->Left == NULL)
    {
        del = tree;
        free(tree);
        tree = tree->Right;
        cout << "Номер удален!" << endl;
    }
    else if (tree->Right == NULL)
    {
        del = tree;
        free(tree);
        tree = tree->Left;
        cout << "Номер удален!" << endl;
    }
}
void Del_All_tree(Tree*&tree)
{
    delete tree;
}
struct Check
{
    string numPas;
    string numRoom;
    string dateIn;
    string dateOut;
    Check* next;
};
struct List
{
    Check* head;
    Check* tail;
    List()
    {
        head = 0;
        tail = 0;
    }
};
List* insert(List* p[], int i, string passport, string room, string dateIn, string dateOut) // Добавление данных
{
    Check* tmp = new Check();
    tmp->numPas = passport;
    tmp->numRoom = room;
    tmp->dateIn = dateIn;
    tmp->dateOut = dateOut;
    tmp->next = 0;
    if (p[i]->head != 0)
    {
        p[i]->tail->next = tmp;
        p[i]->tail = tmp;
    }
    else p[i]->tail = p[i]->head = tmp;
    return p[i];
}
List* deleting(List* p[], string passport, int i) // Удаление элемента
{
    bool flag = 0;
    Check* tmp = p[i]->head;
    Check* tmp1 = p[i]->head;
    if (!tmp) return 0;
    if (p[i]->head->numPas == passport) // Голова
    {
        flag = 1;
        tmp = p[i]->head->next;
        delete p[i]->head;
        p[i]->head = tmp;
    }
    else if (p[i]->tail->numPas == passport) // Хвост
    {
        flag = 1;
        tmp = p[i]->head;
        while (tmp->next != p[i]->tail->next)
        {
            if (tmp->next == p[i]->tail)
            {
                delete p[i]->tail;
                p[i]->tail = tmp;
            }
            else tmp = tmp->next;
        }
    }
    else // Иные эл.
    {
        while (tmp->next != p[i]->tail->next)
        {
            if (tmp->next->numPas == passport)
            {
                flag = 1;
                tmp1 = tmp->next;
                tmp->next = tmp->next->next;
                delete tmp1;
                break;
            }
            else tmp = tmp->next;
        }
    }
    if (!flag)
        cout << "Нет такой записи" << endl;
    return p[i];
}
void deleting(List* p[]) // Удаление всего списка
{
    Check* tmp = 0;
    for (int i = 0; i < 4; i++)
    {
        tmp = p[i]->head;
        while (tmp != p[i]->tail->next)
        {
            tmp = p[i]->head;
            p[i]->head = p[i]->head->next;
            delete tmp;
        }
    }
}
int skip(string room) // Определение номера указателя
{
    if (room[0] == 'Л') return 0;
    if (room[0] == 'П') return 1;
    if (room[0] == 'О') return 2;
    if (room[0] == 'М') return 3;
    else return -1;
}

int main()
{
    system("cls");
    SetConsoleOutputCP(1251);
    SetConsoleCP(1251);
    int choose = -1;
    string pass, FIO, Why, Birth;
    cout << "1-Добавить гостя" << endl;
    cout << "2-Удалить гостя" << endl;
    cout << "3-Показать всех гостей" << endl;
    cout << "4-Найти гостя" << endl;
    cout << "5-Удалить всех гостей" << endl;
    cout << "6-Поиск гостя по ФИО" << endl;
    init();
    cin >> choose;
    switch (choose)
    {
    case 1:
        system("cls");
        cout << "Введите номер пасспорта" << endl;
        cin >> pass;
        cout << "Введите ФИО" << endl;
        cin >> FIO;
        cout << "Введите год рождения" << endl;
        cin >> Birth;
        cout << "Введите цель прибывания" << endl;
        cin >> Why;
        add(pass, FIO, Birth, Why);
        break;
    case 2:
        system("cls");
        cout << "Введите номер паспорта для поиска" << endl;
        cin >> pass;
        HDel_elem(pass);
        system("pause");
        break;
    case 3:
        system("cls");
        HShowALL();
        system("pause");
        break;
    case 4:
        system("cls");
        cout << "Введите номер паспорта для поиска" << endl;
        cin >> pass;
        find(pass);
        system("pause");
        break;
    case 5:
        system("cls");
        HdelAll();
        cout << "Все данные были удалены!" << endl;
        system("pause");
        break;
    }
    return main();
}