9.2

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

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <chrono>
#include <numeric>
#include <windows.h>
#include <algorithm>
#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 TableWith2H {
    struct HNPrecord {
        UI cadastral_number;
        string adress;
    };
    vector<HNPrecord> storage;
    vector<HNPrecord>::iterator it;
    vector<string> rand_adresses;
    vector<bool> erastophen_res;
    UI prime;
 //   size_t curr_size;
    size_t inline _1hash(UI value) {
        return value % storage.size();
    }
    size_t inline _2hash(UI value) {
        return prime - (value % prime);
    }
public:
    TableWith2H() {
        fill_adresses();
    }
    TableWith2H(size_t size) {
        fill_adresses();
        storage.resize(size);
        find_prime();
    }
    TableWith2H(UI cadastral_number, string adress) {
        storage.push_back(convert_2_HNPrecord(cadastral_number, adress));
        fill_adresses();
    }
    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();
    }
    vector<bool> fill_erastrophen(int n) {
        vector<bool> prime(n + 1, true);
        prime[0] = prime[1] = false;
        for (int i = 2; i * i <= n; ++i)
            if (prime[i])
                for (int j = i * i; j <= n; j += i)
                    prime[j] = false;
        return prime;
    }
    UI find_prime() {
        if (erastophen_res.empty()) erastophen_res = fill_erastrophen(1'000'000);
        for (int i = storage.size() - 1; i >= 2; i--)
            if (erastophen_res[i]) { prime = i; return i; }
        return 0;
    }
    void keyboard_init(size_t size) {
        storage.clear();
        //        curr_size = 0;
        storage.resize(size, convert_2_HNPrecord(1, ""));
        find_prime();
        for (int i = 0; i < storage.size(); i++) {
            UI key;
            string t_s;
            cout << "Введите кадастровый номер: ";
            cin >> key;
            cout << "Введите адрес: ";
            cin.ignore();
            getline(cin, t_s);
            insert(key,t_s);
        }
    }
    void insert(UI cadastral_number, string adress) {
        HNPrecord h = convert_2_HNPrecord(cadastral_number, adress);
        if (h.cadastral_number == 0 || h.cadastral_number == 1) {
            cerr << "0 и 1 не подходят под описание ключа и являются удаленными либо подготовленными к инициализации элементами\n";
            return;
        }
        else if (!get(cadastral_number).empty()) {
            cerr << ("Такой ключ уже есть в таблице\n");
            return;
        }
        int index = _1hash(h.cadastral_number);
        while (storage[index].cadastral_number != 1) {
            if (storage[index].cadastral_number==0)
                break;
            index = (index + _2hash(h.cadastral_number)) % storage.size();
        }
        storage[index] = h;
        //curr_size++;
    }
    string get(UI key) {
        int index = _1hash(key);
        if (storage[index].cadastral_number == key)
                return storage[index].adress;
        index = (index + _2hash(key)) % storage.size();
        if (storage[index].cadastral_number == key)
                return storage[index].adress;
        return string();
    }
    /*bool inline isFull() {
        return (curr_size == storage.size());
    }*/
    void rand_init(size_t size) {
        storage.clear();
//        curr_size = 0;
        storage.resize(size,convert_2_HNPrecord(1,""));
        find_prime();
        vector<UI> t_vec(size);
        iota(t_vec.begin(), t_vec.end(), 1000000);
        random_shuffle(t_vec.begin(), t_vec.end());
        for (int i = 0; i < storage.size(); i++)
            insert(t_vec[i], rand_adresses[rand() % rand_adresses.size()]);
        t_vec.clear();
    }
    void print_table() {
        for (int i = 0; i < storage.size(); i++) {
            cout << "Key: " << storage[i].cadastral_number << " adress:" << storage[i].adress << '\n';
        }
    }
    HNPrecord convert_2_HNPrecord(UI cadastral_number, string adress) {
        return HNPrecord{ cadastral_number , adress };
    }
};

int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    srand(time(NULL));
    TableWith2H 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) Поиск\n";
        cout << "4) Вывести таблицу\n";
        cout << "0) Выход\n";
        cout << "Ваш выбор: ";
        cin >> answer1;
        system("cls");
        cout << "Лабораторная работа №8 ИКБО-33-21 Резван М.Б. Вариант 21" << endl << endl;
        switch (answer1)
        {
        case 1:
            cout << "Введите размер таблицы: ";
            cin >> answer1;
            s.start_countdown();
            t.rand_init(answer1);
            cout << "Время работы: " << s.get_milliseconds() << '\n';
            system("pause");

            break;
        case 2:
            cout << "Введите размер таблицы: ";
            cin >> answer1;
            t.keyboard_init(answer1);
        system("pause");
        break;

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

}


///////

    //size_t _1hash(UI key)
    //{
    //    return (key % storage.size());
    //}
    //size_t _2hash(UI key)
    //{
    //    return (prime - (key % prime));
    //}
    //bool isFull() {
    //    return ()
    //}
    //void insertHash(int key)

    //{

    //    // если хеш-таблица заполнена

    //    if (isFull())

    //        return;



    //    // получить индекс из первого хэша

    //    int index = hash1(key);



    //    // если происходит столкновение

    //    if (hashTable[index] != -1)

    //    {

    //        // получаем index2 из второго хэша

    //        int index2 = hash2(key);

    //        int i = 1;

    //        while (1)

    //        {

    //            // получить новый индекс

    //            int newIndex = (index + i * index2) %

    //                TABLE_SIZE;



    //            // если нет столкновения, сохраняем

    //            // ключ

    //            if (hashTable[newIndex] == -1)

    //            {

    //                hashTable[newIndex] = key;

    //                break;

    //            }

    //            i++;

    //        }

    //    }



    //    // если не происходит столкновения

    //    else

    //        hashTable[index] = key;

    //    curr_size++;

    //}




// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.


// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.