dsadasdadasdasda

// SiAOD 9.1.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <chrono>
#include <windows.h>
#define UI unsigned int
#define byte unsigned char
using namespace std;
//Задание 1. Разработать программу поиска записи по ключу в таблице записей с применение двух алгоритмов линейного поиска
//1.    Таблица содержит записи, структура которых определена вариантом.Ключи уникальны в пределах таблицы.
//2.    Разработать функцию линейного поиска(метод грубой силы).
//3.    Разработать функцию поиска с барьером.
//4.    Провести практическую оценку времени выполнения алгоритмов на таблицах объемом 100, 1000, 10 000 записей.
//5.    Составить таблицу с указанием : времени выполнения алгоритма, его фактическую и теоретическую вычислительную сложность.
//6.    Сделать выводы об эффективности алгоритмов.
//Регистрация земельного участка в СНТ: кадастровый номер – семизначное число, адрес СНТ
//Horticultural non-profit partnerships - Садоводческие некоммерческие товарищества (СНТ)
class Stopwatch {
    chrono::steady_clock::time_point point;
    chrono::nanoseconds dim;
public:
    void start_countdown() {
        point = chrono::steady_clock::now();
    }
    double get_milliseconds() {
        dim = chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now() - point);
        return (double)dim.count() / 1'000'000;
    }
};
string utf8_to_cp1251(const char* str) {
    std::string res;
    WCHAR* ures = NULL;
    char* cres = NULL;
    int result_u = MultiByteToWideChar(CP_UTF8, 0, str, -1, 0, 0);
    if (result_u != 0)
    {
        ures = new WCHAR[result_u];
        if (MultiByteToWideChar(CP_UTF8, 0, str, -1, ures, result_u))
        {
            int result_c = WideCharToMultiByte(1251, 0, ures, -1, 0, 0, 0, 0);
            if (result_c != 0)
            {
                cres = new char[result_c];
                if (WideCharToMultiByte(1251, 0, ures, -1, cres, result_c, 0, 0))
                {
                    res = cres;
                }
            }
        }
    }

    delete[] ures;
    delete[] cres;

    return res;
}
class Table {
    struct HNPrecord {
        UI cadastral_number;
        string adress;
    };
    vector<HNPrecord> storage;
    vector<string> rand_adresses;
public:
    Table() {
        fill_adresses();
    }
    UI rand_number() {
        int s = 0;
        for (int i = 0; i < 7; i++) {
            s += (1 + rand() % 9) * pow(10, i);
        }
        return s;
    }
    Table(UI cadastral_number, string adress) {
        storage.push_back(convert_2_HNPrecord(cadastral_number, adress));
        fill_adresses();
    }
    void insert(UI cadastral_number, string adress) {
        if (!barrier_search(cadastral_number).empty()){ cerr << "Такое значение уже есть в таблице!\n"; return;}
        storage.push_back(convert_2_HNPrecord(cadastral_number, adress));
    }
    void fill_adresses() {
        fstream f("SNT.txt", ios::in);
        string t;
        while (getline(f, t)) {
            rand_adresses.push_back(utf8_to_cp1251(t.c_str()));
        }
        f.close();
    }
    void rand_init(size_t size) {
        storage.resize(size);
        for (int i = 0; i < storage.size(); i++) {
            UI t = rand_number();
            while(!barrier_search(t).empty()) t = rand_number();
            storage[i] = convert_2_HNPrecord(t, rand_adresses[rand() % rand_adresses.size()]);
            if (i == 10000) cout << "1";
            if (i == 20000) cout << "1";
            if (i == 30000) cout << "1";
            if (i == 40000) cout << "1";
            if (i == 50000) cout << "1";
            if (i == 60000) cout << "1";
            if (i == 70000) cout << "1";
        }
    }
    void print_table() {
        for (int i = 0; i < storage.size(); i++) {
            cout << "Key: " << storage[i].cadastral_number << " adress:" << storage[i].adress<<'\n';
        }
    }
    string brute_force(UI key) {
        if (storage.empty()) return string();
        for (size_t i = 0; i < storage.size(); i++)
            if (storage[i].cadastral_number == key) return storage[i].adress;
        return string();
    }
    string barrier_search(UI key) {
        if (storage.empty()) return string();
        UI last = storage[storage.size()-1].cadastral_number;
        if (key == last) return storage[storage.size() - 1].adress;
        storage[storage.size() - 1].cadastral_number = key;
        size_t i = 0;
        while (storage[i].cadastral_number != key) i++;
        storage[storage.size() - 1].cadastral_number = last;
        return (i != storage.size() - 1) ? storage[i].adress : string();
    }
    HNPrecord convert_2_HNPrecord(UI cadastral_number, string adress) {
        return HNPrecord{ cadastral_number , adress };
    }
};

int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    srand(time(NULL));
    Table t;
    Stopwatch s;
    int answer1 = 100;
    while (answer1 != 0) {
        system("cls");
        cout << "Лабораторная работа №8 ИКБО-33-21 Резван М.Б. Вариант 21" << endl << endl;
        cout << "Задание 21" << endl;
        cout << "Условия задачи 1:\n\n\n.";
        cout << "Меню\n";
        cout << "1) Заполнить таблицу рандомными (случайными) значениями\n";
        cout << "2) Заполнить таблицу с клавиатуры\n";
        cout << "3) Brute force (линейный поиск (метод грубой силы)).\n";
        cout << "4) Barrier search (поиск с барьером).\n";
        cout << "5) Вывести таблицу\n";
        cout << "0) Выход\n";
        cout << "Ваш выбор: ";
        cin >> answer1;
        system("cls");
        cout << "Лабораторная работа №8 ИКБО-33-21 Резван М.Б. Вариант 21" << endl << endl;
        switch (answer1)
        {
        case 1:
            cout << "Введите размер таблицы: ";
            cin >> answer1;
            t.rand_init(answer1);
            break;
        case 2:
        {
            UI key;
            string t_s;
            cout << "Введите кадастровый номер: ";
            cin >> key;
            cout << "Введите адрес: ";
            cin.ignore();
            getline(cin, t_s);
            t.insert(key, t_s);
        }
            break;

        case 3:
            UI key;
            cout << "Введите ключ: ";
            cin >> key;
            s.start_countdown();
            cout << "Результат поиска (брут): " << t.brute_force(key) << "\n";
            cout << "Время работы: " << s.get_milliseconds() << '\n';
            system("pause");
            break;
        case 4:
        {
            UI key;
            cout << "Введите ключ: ";
            cin >> key;
            s.start_countdown();
            cout << "Результат поиска (барьер): " << t.barrier_search(key) << "\n";
            cout << "Время работы: " << s.get_milliseconds() << '\n';
        }
            system("pause");
            break;
        case 5:
            t.print_table();
            system("pause");
            break;
        }
    }

}