#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;

struct train
{
	string city;
	string day;
	int time;
	int seats;
};

vector<train> trains;   // массив всех поездов
train one_train;    // один поезд, экземпляр структуры
ofstream fout;
ifstream fin;
int i;

void foo_TRAINS_fileout(vector<train>& trains)  // записывает вектор поездов в ЧИСТОВОЙ файл
{
	int size = trains.size();
	for (int i = 0; i < size; i++)
	{
		fout << "Поезд №: " << i + 1 << endl;
		fout << "\t\t" << "Город: " << trains[i].city << endl;
		fout << "\t\t" << "День недели: " << trains[i].day << endl;
		fout << "\t\t" << "Время отправления: " << trains[i].time << " часов" << endl;
		fout << "\t\t" << "Свободные места: " << trains[i].seats << endl;
	}
}

void Quick_Sort(vector<train>& trains, int begin, int end)
{
	int left, right;string x; train temp;
	left = begin;
	right = end;
	x = trains[(left + right) / 2].city;
	do {
		while (trains[left].city < x)  left++;
		while (x < trains[right].city) right--;
		if (left <= right) {
			temp = trains[left];
			trains[left] = trains[right];
			trains[right] = temp;
			left++;
			right--;
		}
	} while (left <= right);
	if (begin < right) Quick_Sort(trains, begin, right);
	if (left < end) Quick_Sort(trains, left, end);
}

int BinSearch(const vector<train> & trains, int low, int high, const string& key)
{
	while (low < high)
	{
		int mid = (low + high) / 2;
		if (trains[mid].city == key) {
			return mid;
		}

		else if (trains[mid].city < key)
			low = mid + 1;

		else {
			return mid;
		}
	}
	return -1;
}


int main()
{
	fout.open("TRAINS.txt"); // открытие TRAINS.txt для дозаписи
	fout << "";
	fout.close();

	setlocale(LC_ALL, "ru");

	while (true) { // бесконечный цикл без выхода
		cout << "--------------------------МЕНЮ------------------------------" << endl;
		cout << "1 - Чтение из файла\n2 - Просмотр\n3 - Создать и добавить\n4 - Найти поезд" << endl;
		cout << "--------------------------ИНФО------------------------------" << endl;
		int menu;
		cin >> menu;
		cout << "------------------------------------------------------------" << endl;
		switch (menu)
		{
		case 1: // добавление информации из готового файла
		{
			fin.open("trainss.txt"); // открываем готовый файл для чтения
			while (!fin.eof())
			{
				if (fin.eof()) { break; };
				fin >> one_train.city;
				fin >> one_train.day;
				fin >> one_train.time;
				fin >> one_train.seats;
				trains.push_back(one_train); // закидывает экземпляр в вектор
			}
			fin.close();
			fout.open("TRAINS.txt", ofstream::app); // открытие TRAINS.txt для дозаписи
			foo_TRAINS_fileout(trains); // кидает вектор студентов в файл TRAINS.txt
			fout.close();
			break;
		}
		case 2: // просмотр (вывод содержимого файла)
		{
			fin.open("TRAINS.txt"); // открываем основной файл для чтения
			string str;
			while (!fin.eof())
			{
				str = "";
				getline(fin, str);
				cout << str << endl;
			}
			fin.close();
			break;
		}
		case 3: // создание поезда (экземпляра структуры), дозапись нового поезда в вектор, запись нового вектора в файл
		{
			cout << "Введите данные о новом поезде:" << endl;
			cout << "Город: ";                 cin >> one_train.city;
			cout << "День недели: ";          cin >> one_train.day;           // создание экземпляра
			cout << "Время отправления: ";      cin >> one_train.time;
			cout << "Свободные места: ";      cin >> one_train.seats;
			trains.push_back(one_train);    // запись нового экземпляра в вектор
			fout.open("TRAINS.txt"); // открытие TRAINS.txt для дозаписи
			foo_TRAINS_fileout(trains); // кидает новый вектор студентов в файл TRAINS.txt
			fout.close(); // закрывает поток записи в файл students.txt
			break;
		}
		case 4:     // найти поезд
		{
			string N, k;  int t, key;
			cout << "Хочу уехать в город - ";       cin >> N;
			cout << "в день недели - ";              cin >> k;
			cout << "отправление не позднее - ";    cin >> t;
			cout << "свободных мест нужно - ";        cin >> key;
			cout << endl;

			cout << "--------------------------МЕНЮ------------------------------" << endl;
			cout << "\t1 - Линейный поиск\n\t2 - Сортировка и двоичный поиск" << endl;
			cout << "--------------------------ИНФО------------------------------" << endl;
			int men;
			cin >> men;
			cout << "------------------------------------------------------------" << endl;
			switch (men)
			{
			case 1:  // линейный поиск
			{
				int o = 0;

				for (int i = 0; i < trains.size(); i++)
				{
					if (N == trains[i].city && k == trains[i].day && t >= trains[i].time && key <= trains[i].seats) {
						cout << "Время отправления подходящего вам поезда: " << trains[i].time << " часов." << endl;
						o = 1;
					}
				}
				if (o == 0)
				{
					cout << "\nНевозможно выполнить заказ." << endl;
				}
				break;
			}
			case 2:  // сортировка и двоичный поиск///////////////////////////////////////////////////////////////
			{
				cout << "\t\t1 - Сортировка методом прямого выбора\n\t\t2 - QuickSort" << endl;
				cout << "------------------------------------------------------------" << endl;
				int pop;
				cin >> pop;
				cout << "------------------------------------------------------------" << endl;
				switch (pop)
				{
				case 1: // сортировка прямым выбором//////////////////////
				{
					int min, r; train temp;
					for (i = 0; i < trains.size() - 1; i++)
					{
						min = i;
						for (int j = i + 1; j < trains.size(); j++)
							if (trains[j].city < trains[min].city) min = j;
						temp = trains[min];
						trains[min] = trains[i];
						trains[i] = temp;
					}
					break;
				}
				case 2:
				{
					Quick_Sort(trains, 0, trains.size() - 1);
					break;
				}
				}
				int size = trains.size();
				cout << "Отсортированный массив:" << endl;
				for (int i = 0; i < size; i++)
				{
					cout << "Поезд №: " << i + 1 << endl;
					cout << "\t\t" << "Город: " << trains[i].city << endl;
					cout << "\t\t" << "День недели: " << trains[i].day << endl;
					cout << "\t\t" << "Время отправления: " << trains[i].time << " часов" << endl;
					cout << "\t\t" << "Свободные места: " << trains[i].seats << endl;
				}
				cout << "------------------------------------------------------------" << endl;
				// двоичный поиск///////////////////////////////////////////////////////////////////////////////////

				int low = BinSearch(trains, 0, trains.size(), N);
					if (key <= trains[low].seats && k == trains[low].day && t >= trains[low].time)
					{
						cout << "Время отправления подходящего вам поезда: " << trains[low].time << " часов." << endl;
						break;
					}
					cout << "\nНевозможно выполнить заказ." << endl;
					break;
			}
			}

		}
		}
	}
	return 0;
}