#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <io.h>
#include<iomanip>

using namespace std;
FILE* fl;


struct train_to_brest   //struct
{
    int time_to;
    char place_to[50];
    int available_places;
}train,*tr;

int  menu_list_1();   // menu list 1
int  menu_list_2();   // menu list 2

void creating_f();  // 1.create new file
void filling_f();   // 2.filling FILE
void reading_f();   // 3.file reading
void conclusion_screen();  // 4.conclusion_screen
void conclusion_file();    // 5.conclusion_file


//second part of programm
void taking_elements();   //6. taking elements from file
void sort_shell(train_to_brest*, int);   //6.sorting by shell
void quick_sort_bez_reqursii(train_to_brest* a, int n);   //7.quick sort
void search(train_to_brest *, int );   //8.serach element

int menu_for_search_and_sort(train_to_brest *,int );

int search_by_dv(train_to_brest*,int ,int );
int search_by_lin(train_to_brest*,int, int);


int main()
{
    while (true)
    {
        switch (menu_list_1())
        {
        case 1: creating_f(); break;
        case 2: filling_f(); break;
        case 3: reading_f(); break;
        case 4: conclusion_screen(); break;
        case 5: conclusion_file(); break;
        case 6: taking_elements(); break; //taking elements for different searches and sorting
                                        //functions for search and sort lie in this function !
        case 7: return 0;
        default: cout<<"Choose correct!" << endl;
        }

    }
}

int menu_list_1()
{
    cout << "Choose: " << endl;
    cout << "1.create new file" << endl;
    cout << "2.filling FILE" << endl;
    cout << "3.file reading" << endl;
    cout << "4.conclusion_screen" << endl;
    cout << "5.conclusion_file" << endl;
    cout << "6.taking_elements" << endl;

    cout << "7.exit" << endl;
    int k; cin >> k;
    return k;
}

void creating_f()  //creatin file
{

    if ((fl = fopen("struct.dat", "wb")) == NULL)
    {
        cout << "file didn't create" << endl;
    }
    else cout << "file created GOOD"<<endl;
    fclose(fl);
}

void filling_f()  //filling file
{
    if ((fl = fopen("struct.dat", "rb+")) == NULL)
    {
        cout << "file didn't write" << endl;
    }
    else cout << "file write GOOD";

    char ch[10];
    int count = 0;
    do
    {
        cout << "Enter time_to: " << endl; cin >> train.time_to;
        cout << "Enter Place_to: " << endl; cin >> train.place_to;
        cout << "Enter available_places: " << endl; cin >> train.available_places;

        fwrite(&train, sizeof(train_to_brest), 1, fl); //writing

        cout << "Do u want to continue? Yes / No " << endl;
        cin >> ch;
    } while (strcmp(ch, "yes") == 0);

    fclose(fl);
}

void reading_f()
{

    if ((fl = fopen("struct.dat", "rb+")) == NULL)
    {
        cout << "file didn't read" << endl;
    }
    else cout << "file readed GOOD" << endl;

    int n = 0;

    n = _filelength(_fileno(fl)) / sizeof(train_to_brest);

    rewind(fl);

    for(int i=0; i<n ; i++)
    {
        cout << "--------------------------------------------------"<<endl;
        fread(&train, sizeof(train_to_brest), 1, fl);
        cout << "PLace_to: " << train.place_to << endl;
        cout << "Time_to: " << train.time_to << endl;
        cout << "Available places: " << train.available_places << endl;
        cout << "--------------------------------------------------" << endl;
    }
    fclose(fl);
}

void conclusion_screen()  // screen
{
    if ((fl = fopen("struct.dat", "rb+")) == NULL)
    {
        cout << "file didn't read" << endl;
    }
    else cout << "file readed GOOD" << endl;
    rewind(fl);

    int n = 0;

    n = _filelength(_fileno(fl)) / sizeof(train_to_brest);

    rewind(fl);
    fread(&train, sizeof(train_to_brest), 1, fl);
    int min = train.available_places;

    int count;
    cout << endl << "Conclusion on SCREEN:" << endl;
    cout << "Trains to brest: available_places from MIN to MAX" << endl;
    train_to_brest k, k_i;
    int count_mesto = 0;
    bool p;
    for (int i = 0; i < n; i++)
    {
        p = false;
        fseek(fl, sizeof(train_to_brest) * i, 0);
        fread(&train, sizeof(train_to_brest), 1, fl);

        k_i=train;
        count = i;

        if (strcmp(train.place_to, "brest") == 0)
        {
            min = train.available_places;

            while (fread(&train, sizeof(train_to_brest), 1, fl) == 1)
            {
                count++;
                if (train.available_places < min && (strcmp(train.place_to, "brest") == 0))
                {
                    p=true;
                    min = train.available_places;
                    count_mesto = count;
                }
            }
            if (p == true)
            {
                fseek(fl, sizeof(train_to_brest) * count_mesto, 0);
                fread(&train, sizeof(train_to_brest), 1, fl);
                fseek(fl, sizeof(train_to_brest) * count_mesto, 0);
                k = train;

                fwrite(&k_i, sizeof(train_to_brest), 1, fl);

                fseek(fl, sizeof(train_to_brest) * i, 0);
                fwrite(&k, sizeof(train_to_brest), 1, fl);
            }
        }
    }
    rewind(fl);
    cout << endl << endl;
    while (fread(&train, sizeof(train_to_brest), 1, fl) == 1)
    {
        if (strcmp(train.place_to, "brest") == 0)
        {
            cout << "--------------------------------------------------" << endl;
            cout << "PLace_to: " << train.place_to << endl;
            cout << "Time_to: " << train.time_to << endl;
            cout << "Available places: " << train.available_places << endl;
            cout << "--------------------------------------------------" << endl;
        }
    }
    fclose(fl);
    cout << endl;

}

void conclusion_file()
{
    if ((fl = fopen("struct.dat", "rb+")) == NULL)
    {
        cout << "file didn't read" << endl;
    }
    else cout << "file readed GOOD" << endl;
    rewind(fl);
    int n = 0;

    n = _filelength(_fileno(fl)) / sizeof(train_to_brest);

    rewind(fl);

    fread(&train, sizeof(train_to_brest), 1, fl);
    int min = train.available_places;

    int count;
    cout << endl << "Conclusion on SCREEN:" << endl;
    cout << "Trains to brest: available_places from MIN to MAX" << endl;
    train_to_brest k, k_i;
    int count_mesto = 0;
    bool p;
    for (int i = 0; i < n; i++)
    {
        p = false;
        fseek(fl, sizeof(train_to_brest) * i, 0);
        fread(&train, sizeof(train_to_brest), 1, fl);

        k_i = train;
        count = i;

        if (strcmp(train.place_to, "brest") == 0)
        {
            min = train.available_places;

            while (fread(&train, sizeof(train_to_brest), 1, fl) == 1)
            {
                count++;
                if (train.available_places < min && (strcmp(train.place_to, "brest") == 0))
                {
                    p = true;
                    min = train.available_places;
                    count_mesto = count;
                }
            }
            if (p == true)
            {
                fseek(fl, sizeof(train_to_brest) * count_mesto, 0);
                fread(&train, sizeof(train_to_brest), 1, fl);
                fseek(fl, sizeof(train_to_brest) * count_mesto, 0);
                k = train;

                fwrite(&k_i, sizeof(train_to_brest), 1, fl);

                fseek(fl, sizeof(train_to_brest) * i, 0);
                fwrite(&k, sizeof(train_to_brest), 1, fl);
            }
        }
    }
    rewind(fl);
    cout << endl << endl;
    count = 0;

    for (int i = 0; i < n; i++)
    {
        fread(&train, sizeof(train_to_brest), 1, fl);

        if (strcmp(train.place_to, "brest") == 0)
        {
            cout << "--------------------------------------------------" << endl;
            cout << "PLace_to: " << train.place_to << endl;
            cout << "Time_to: " << train.time_to << endl;
            cout << "Available places: " << train.available_places << endl << endl;
            cout << "--------------------------------------------------" << endl;

            fseek(fl, 0, 2);
            fwrite(&train, sizeof(train_to_brest), 1, fl);
            fseek(fl, sizeof(train_to_brest) * (i + 1), 0);
        }
    }
        fclose(fl);
        cout << endl;
}


//SECOND PART OF PROGRAMM



void taking_elements()  //6. taking elements from file and creating arrays of structures
{
    if ((fl = fopen("struct.dat", "rb+")) == NULL)
    {
        cout << "file didn't read" << endl;
    }
    else cout << "file readed GOOD" << endl;
    rewind(fl);
    int n = 0;

    n = _filelength(_fileno(fl)) / sizeof(train_to_brest);

    train_to_brest *mass = new train_to_brest[n];
    int i = 0;

    rewind(fl);

    while (fread(&train, sizeof(train_to_brest), 1, fl) == 1)
    {
        mass[i] = train;
        i++;
    }
    cout << endl << endl;

    menu_for_search_and_sort(mass,n);
}




int menu_for_search_and_sort(train_to_brest *mass,int n)
{
    while (true)
    {
        switch (menu_list_2())
        {
        case 1: search(mass,n); break;
        case 2: sort_shell(mass,n); break;
        case 3: quick_sort_bez_reqursii(mass,n); break;

        case 4: return 0;
        default: cout << "Choose correct!" << endl;
        }

    }
}

int menu_list_2()
{
    cout << "Choose: " << endl;
    cout << "1.search" << endl;
    cout << "2.sort_shell" << endl;
    cout << "3.quick_sort_bez_reqursii" << endl;
    cout << "4.exit" << endl;
    int k; cin >> k;
    return k;
}





void search(train_to_brest *mass,int n)   //SEARCH ELEMENT
{
    int key;
    cout << endl << "write your KEY:"<<endl;
    cin >> key;
    int i = 0; //place of structures in massiv



        int choose;
        do
        {
            cout << "Choose variant of searching: " << endl << "1.-Lineinie s barierom " << endl << "2.-Dvoinoi" << endl;
            cin >> choose;
            switch (choose)
            {
            case 1:
                if (search_by_lin(mass, n, key) == -1)
                    cout << "Element not found!";
                break;
            case 2:
                if (search_by_dv(mass, n, key) == -1)
                    cout << "Element not found!";
                break;


            default: cout << "choose correct:" << endl << endl;
            }
        } while (choose < 1 || choose>3);

}

 int search_by_lin(train_to_brest *mass,int n,int key)  // SEARCH 1 with bar
         {

             mass[n] = train;
             mass[n].time_to = key;
             int i = 0;
             while (mass[i].time_to != key)
             {
                 i++;
             }

             if (i == n)
             {
                 return -1;
             }
             else
             {
                 cout << "This Train is going at " << key << endl;
                 cout << "It is going to " << mass[i].place_to << endl;
                 return i;
             }
         }

 int search_by_dv(train_to_brest* mass,int n, int key)
         {
             cout << "First of all you should Choose 1 of the sorting for this search:" << endl;
             cout << "1. - Sort by shell" << endl;
             cout << "2. - Quick sort" << endl;
             int k;


            do
            {
                cin >> k;
                 switch (k)
                 {
                 case 1:sort_shell(mass, n); break;
                 case 2: quick_sort_bez_reqursii(mass, n); break;
                 default: cout << "Choose correct!" << endl;

                 }
            } while (k <1 || k > 2);


             int left = 0;
             int right = n - 1;
             int medium;

             while (left < right)
             {
                 medium = (left + right) / 2;
                 if (mass[medium].time_to < key)
                 {
                     left = medium + 1;
                 }
                 else right = medium;
             }
             if (mass[left].time_to == key)
             {
                 cout << "This Train is going at " << key << endl;
                 cout << "It is going to " << mass[left].place_to << endl;
                 return left;
             }
             else return -1;

         }


 void sort_shell(train_to_brest* mass, int n)  //  сортировка по шеллу
         {
             train_to_brest tmp;

             for (int i = 0; i < n; i++)  //old array
             {
                 cout<<setw(10) << mass[i].time_to << setw(10);
             }
             cout << endl;

             for (int step = n / 2; step > 0; step /= 2)
             {
                 for (int i = step; i < n; i++)
                 {
                     for (int j = i - step; j >= 0; j -= step)
                     {
                         if (mass[j].time_to > mass[j + step].time_to)
                         {
                             tmp = mass[j];
                             mass[j] = mass[j + step];
                             mass[j + step] = tmp;
                         }
                     }
                 }
             }

             for (int i = 0; i < n; i++)  //new array by sort
             {
                 cout << setw(10) << mass[i].time_to << setw(10);
             }
             cout << endl;
         }

 void quick_sort_bez_reqursii(train_to_brest *a, int n)
 {
     for (int k = 0; k < n; k++)
     {
         cout << setw(10) << a[k].time_to << setw(10);;
     }
     cout << endl << endl;

     struct
     {
         int l;
         int r;
     } stack[20];

     int i, j, left, right, s = 0;
     int t, pivot;
     stack[s].l = 0; stack[s].r = n - 1;
     while (s != -1)
     {
         left = stack[s].l;
         right = stack[s].r;
         s--;



         while (left < right)
         {
             i = left;
             j = right;
             pivot = a[(left + right) / 2].time_to;

             while (i <= j)
             {
                 while (a[i].time_to < pivot) i++;
                 while (a[j].time_to > pivot) j--;

                 if (i <= j)
                 {
                     t = a[i].time_to;
                     a[i].time_to = a[j].time_to;
                     a[j].time_to = t;

                     i++;
                     j--;
                 }
             }
             if ((j - left) < (right - i)) // Выбор более короткой части
             {
                 if (i < right)
                 {
                     s++;
                     stack[s].l = i;
                     stack[s].r = right;
                 }
                 right = j;
             }
             else
             {
                 if (left < j)
                 {
                     s++;
                     stack[s].l = left;
                     stack[s].r = j;
                 }
                 left = i;
             }
         }
     }

     for (int k = 0; k < n; k++)
     {
         cout << setw(10) << a[k].time_to << setw(10);;
     }
     cout << endl << endl;
 }