---

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <string>

using namespace std;

// Структура для B7
struct Reise {
    string destination;   // Пункт назначения
    int flightNumber;     // Номер рейса (КЛЮЧ)
    string departTime;    // Время отправления
};

// Хеш-функция 1: i = Key % M
int hashFunc1(int key, int M) {
    return key % M;
}

// Хеш-функция 2: c = 1 + (Key % (M-2))
int hashFunc2(int key, int M) {
    return 1 + (key % (M - 2));
}

// Вставка с двойным хешированием
void sv_add(Reise reise, int m, Reise H[], int status[]) {
    int key = reise.flightNumber;
    int i = hashFunc1(key, m);
    int c = hashFunc2(key, m);
    int attempts = 0;
    
    // Поиск свободной ячейки
    while (status[i] == 1 && attempts < m) { // 1 = занято
        i = i - c;
        if (i < 0) i = i + m;
        attempts++;
    }
    
    if (status[i] != 1) {
        H[i] = reise;
        status[i] = 1; // Помечаем как занято
    }
}

// Поиск с двойным хешированием
int sv_search(int key, int m, Reise H[], int status[]) {
    int i = hashFunc1(key, m);
    int c = hashFunc2(key, m);
    int start = i;
    int attempts = 0;
    
    while (status[i] != 0 && attempts < m) { // 0 = свободно
        if (status[i] == 1 && H[i].flightNumber == key) {
            return i; // Нашли
        }
        i = i - c;
        if (i < 0) i = i + m;
        attempts++;
        if (i == start) break;
    }
    return -1; // Не нашли
}

// Генерация случайных данных
string randomDestination() {
    string destinations[] = {"Москва", "СПб", "Новосибирск", "Екатеринбург", "Казань", 
                             "Сочи", "Владивосток", "Красноярск", "Ростов", "Уфа"};
    return destinations[rand() % 10];
}

string randomTime() {
    int hour = rand() % 24;
    int minute = rand() % 60;
    return to_string(hour) + ":" + (minute < 10 ? "0" : "") + to_string(minute);
}

int randomFlightNumber() {
    return 100 + rand() % 900; // 100-999
}

// Вывод хеш-таблицы
void printHashTable(Reise H[], int status[], int m) {
    cout << "\n=== Хеш-таблица (двойное хеширование) ===" << endl;
    for (int i = 0; i < m; i++) {
        if (status[i] == 1) {
            cout << "H[" << setw(2) << i << "] -> Рейс " << H[i].flightNumber 
                 << " | " << H[i].destination << " | " << H[i].departTime << endl;
        } else {
            cout << "H[" << setw(2) << i << "] -> СВОБОДНО" << endl;
        }
    }
}

int main() {
    srand(time(NULL));
    
    // Параметры варианта B7
    const int n = 8;            // Количество элементов
    const int M = 10;           // Размер хеш-таблицы
    
    // Генерация исходного массива рейсов
    Reise reisen[n];
    cout << "=== ВАРИАНТ B7: Двойное хеширование (ключ - номер рейса) ===" << endl;
    cout << "Сгенерированный массив рейсов (" << n << " элементов):" << endl;
    cout << "----------------------------------------------------------------" << endl;
    for (int i = 0; i < n; i++) {
        reisen[i].flightNumber = randomFlightNumber();
        reisen[i].destination = randomDestination();
        reisen[i].departTime = randomTime();
        cout << "[" << i << "] Рейс " << reisen[i].flightNumber 
             << " | " << reisen[i].destination 
             << " | " << reisen[i].departTime 
             << " (hash1 = " << (reisen[i].flightNumber % M) << ")" << endl;
    }
    cout << "----------------------------------------------------------------" << endl;
    
    // Создание хеш-таблицы
    Reise H[M];
    int status[M]; // 0 - свободно, 1 - занято
    for (int i = 0; i < M; i++) {
        status[i] = 0;
    }
    
    // Заполнение хеш-таблицы
    for (int i = 0; i < n; i++) {
        sv_add(reisen[i], M, H, status);
    }
    
    // Вывод хеш-таблицы
    printHashTable(H, status, M);
    
    // === ПОИСК ПО КЛЮЧУ (номер рейса) ===
    cout << "\n=== ПОИСК РЕЙСА ===" << endl;
    int searchFlight;
    cout << "Введите номер рейса для поиска: ";
    cin >> searchFlight;
    
    int position = sv_search(searchFlight, M, H, status);
    
    if (position != -1) {
        cout << "\n✅ Рейс " << searchFlight << " НАЙДЕН!" << endl;
        cout << "Позиция в хеш-таблице: H[" << position << "]" << endl;
        cout << "\n--- ВСЕ ПОЛЯ СТРУКТУРЫ ---" << endl;
        cout << "Номер рейса:       " << H[position].flightNumber << endl;
        cout << "Пункт назначения:  " << H[position].destination << endl;
        cout << "Время отправления: " << H[position].departTime << endl;
    } else {
        cout << "\n❌ Рейс " << searchFlight << " НЕ НАЙДЕН в хеш-таблице!" << endl;
    }
    
    return 0;
}