#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <tuple>
#include <algorithm>
#include <string>//подключение необходимых библиотек
using namespace std;// открытие простравнтсва имен

using Graphic = set<std::pair<string, string>>;//предстваление графика

struct Conformity {//представление соотношения
	set<string> X;
	set<string> Y;
	Graphic G;
};

void FillGraphic(Graphic& g, int n) {//заполняет график значениями, введенными с клавиатуры
	for (int i = 0; i < n; i++) {
		string first, second;
		cin >> first >> second;//Принимает значение элемента
		g.insert({ first,second });//создает и записывает кортеж в график
	}
}

Graphic Union(const Graphic& first, const Graphic& second) {//операция объединения
	Graphic result;//создаем пустой график С
	for (const auto& x : first) {//берем эдементы графика А
		result.insert(x);//записываем элементы графика А в график С
	}
	for (const auto& y : first) {//берем  элемент графика А
		for (const auto& x : second) {//берем  элемент графика В
			if (x != y) {//сравниваем выбранные элементы графика А и с выбранным элемнтом графика В
				result.insert(x);//если не равен(если равен, то идем в пункт 2), то добавляем в график С, если равен, то переходим в пункт 1 и берем следующий элемент А
			}
		}
	}
	return result;
}

set<string> Union(const set<string>& first, const set<string>& second) {//операция объединения
	set<string> result;//создаем пустое множество С
	for (const auto& x : first) {//берем эдементы множества А
		result.insert(x);//записываем элементы множестав А в множество С
	}
	for (const auto& y : first) {//1
		for (const auto& x : second) {//2
			if (x != y) {//сравниваем первый элемент множества А с элементом множества В
				result.insert(x);//если не равен(если равен, то идем в пункт 2), то добавляем в множество С, если равен, то переходим в пункт 1 и берем следующий элемент А
			}
		}
	}
	return result;
}


Conformity Union(const Conformity& first, const Conformity& second) {
	return { Union(first.X,second.X),Union(first.Y,second.Y),Union(first.G,second.G) };//используем операции объединения для множеств и графика
}


set<string> Intersection(const set<string>& first, const set<string>& second) {//операция пересечения
	set<string> result;//создаем пустое множество
	for (const auto& item_first : first) {//1
		for (const auto& item_second : second) {//2
			if (item_first == item_second) {//сравниваем первый элемент множества А с элементом множества В
				result.insert(item_first);//если равен(если не равен, то идем в пункт 2), то добавляем в множество С, переходим в пункт 1 и берем следующий элемент А
			}
		}
	}
	return result;
}

Graphic Intersection(const Graphic& first, const Graphic& second) {//операция пересечения
	Graphic result;//создаем пустой график
	for (const auto& item_first : first) {//берем  элемент графика А
		for (const auto& item_second : second) {//берем  элемент графика В
			if (item_first == item_second) {//сравниваем выбранный элемент множества А с выбранным элементом множества В
				result.insert(item_first);//если равен(если не равен, то идем в пункт 2), то добавляем в множество С, переходим в пункт 1 и берем следующий элемент А
			}
		}
	}
	return result;
}

Conformity Intersection(const Conformity& first, const Conformity& second) {
	return { Intersection(first.X,second.X),Intersection(first.Y,second.Y),Intersection(first.G,second.G) };//используем операции пересечения для множеств и графика
}

Graphic Difference(const Graphic& first, const Graphic& second) {// Операция разности
	Graphic result;//создаем пустой график С
	for (const auto& item_first : first) {// Берем элемент графика А
		auto it = find(second.begin(), second.end(), item_first);//Берем элемент графика В и сравниваем с элементом графика А
		if (it == second.end()) {//Если данного эл-та нету в графкие В, то записываем его в график С
			result.insert(item_first);
		}
	}
	return result;
}

set<string> Difference(const set<string>& first, const set<string>& second) {// Операция разности
	set<string> result;//создаем пустое множество
	for (const auto& item_first : first) {// Берем элемент мн-ва А
		auto it = std::find(second.begin(), second.end(), item_first);//Берем элемент мн-ва В и сравниваем с элементом мн-ва А
		if (it == second.end()) {//Если данного эл-та нету в мн-ве С, то записываем его
			result.insert(item_first);
		}
	}
	return result;
}

Conformity Difference(const Conformity& first, const Conformity& second) {
	return { Difference(first.X,second.X),Difference(first.Y,second.Y),Difference(first.G,second.G) };//используем операции разности для множеств и графика
}


Graphic SymmetryDifference(const Graphic& first, const Graphic& second) {//Операция Симметрической разности
	Graphic result(Difference(first, second)); //записываем в график С разность между графиками А и В
	for (const auto& x : Difference(second, first)) {  //Берем элемент разности между графиками В и А
		result.insert(x);//записываем в график С
	}
	return result;
}


set<string> SymmetryDifference(const set<string>& first, const set<string>& second) {//Операция Симм. разности
	set<string> result(Difference(first, second)); //записываем во мн-во С разность между мн-вами А и В
	for (const auto& x : Difference(second, first)) {          // записываем во мн-во С разность между мн-вами В и А
		result.insert(x);
	}
	return result;
}

Conformity SymmetryDifference(const Conformity& first, const Conformity& second) {
	return { SymmetryDifference(first.X,second.X),SymmetryDifference(first.Y,second.Y),SymmetryDifference(first.G,second.G) };//используем
	//операции симметрической разности для множеств и графика
}

Graphic Inversion(const Graphic& graphic) {
	Graphic result;//создаем пустой график С
	for (const auto& [first, second] : graphic) {//берем элемент графика А
		result.insert({ second,first });//записываем инверсированный кортеж элемента из графика А в график С
	}
	return result;
}

Conformity Inversion(const Conformity& first) {
	return { first.Y,first.X,Inversion(first.G) };//используем операцию инверсии для графика
}

Graphic Composition(const Graphic& first_graphic, const Graphic& second_graphic) {
	Graphic result;//создаем пустой график С
	for (const auto& [first, second] : first_graphic) {//берем элемент графика А
		for (const auto& [first_of_sec, second_of_sec] : second_graphic) {
			if (second == first_of_sec) {
				result.insert({ first,second_of_sec });
			}
		}
	}
	return result;
}

Conformity Composition(const Conformity& first, const Conformity& second) {
	return { first.X,second.Y, Composition(first.G,second.G) };//используем операцию композиция для графика
}

std::ostream& operator<<(std::ostream& out, const set<std::pair<string, string>>& s) {
	out << "{";
	if (s.size() == 0) {
		out << "}";
		return out;
	}
	for (auto it = s.begin(); it != s.end(); it++) {

		if (it != prev(s.end())) {
			out << "<" << it->first << ", " << it->second << ">, ";
		}
		else {
			out << "<" << it->first << ", " << it->second << ">}";
		}
	}
	return out;
}

void Menu() {//выбор операции
	cout << "1 - Операция объединения" << std::endl << "2 - Операция пересечения" << std::endl
		<< "3 - Операция разности" << std::endl
		<< "4 - Операция симметрической разности" << std::endl
		<< "5 - Операция инверсии" << std::endl
		<< "6 - Операция композиции" << std::endl
		<< "7 - Операция образа (Соответствие Г1)" << std::endl
		<< "8 - Операция прообраза (Соответствие Г1)" << std::endl
		<< "9 - Операция продолжения (Соответствие Г1)" << std::endl
		<< "10 - Oперация сужения (Соответствие Г1)" << endl
		<< "0 - выйти из программы" << std::endl;
}

void FillSet(set<string>& s, int n) {//заполняет множество значениями, введенными с клавиатуры
	for (int i = 0; i < n; i++) {//
		string temp;
		cin >> temp;//Принимает значение элемента
		s.insert(temp);//записывает значение
	}
}

set<std::pair<string, string>> Cartesian(const set<string>& first, const set<string>& second) {//Операция Декартова произведения
	set<std::pair<string, string>> result;//создаем пустое множество
	for (const auto& first_it : first) {//Берем последовательно элементы множества А
		for (const auto& second_it : second) {//Берем последовательно элементы множества А
			result.insert(std::make_pair(first_it, second_it));//создаем кортеж <A,B>
		}
	}
	return result;

}

set<string> ImageOperation(const Conformity& conf ) {//операция образа
	int size;
	cout << "Введите мощность множества А\n";
	cin >> size;//вводим мощность
	set<string> A;
	cout << "Введите элементы множества А\n";
	set<string> result;
	FillSet(A, size);//заполняем эдементы
	for (const auto& element : A ) {//берем элемент множества А
		auto it = find_if(conf.G.begin(), conf.G.end(), [element](pair<string, string> p) {
			return p.first == element; }//если элемент множества А равен выбранному первому элементу компоненты графика
		);
		if (it != conf.G.end()) {
			result.insert(it->second);//добавляем  множество
		}
	}
	return result;
}

set<string> PrototypeOperation(const Conformity& conf) {//операция прообраза
	int size;
	cout << "Введите мощность множества B\n";//вводим мощность
	cin >> size;
	set<string> B;//создаем множество В
	cout << "Введите элементы множества B\n";
	set<string> result;
	FillSet(B, size);//заполняем множество
	for (const auto& element : B) {//берем элемент множества В
		auto it = find_if(conf.G.begin(), conf.G.end(), [element](pair<string, string> p) {//берем второй элемент компоненты графика
			return p.second == element; }//если элемент равен второму элементу комоненты графика
		);
		if (it != conf.G.end()) {
			result.insert(it->first);//добавляем его
		}
	}
	return result;
}


std::ostream& operator<<(std::ostream& out, const set<string>& s) {
	out << "{";
	if (s.size() == 0) {
		out << "}";
		return out;
	}
	for (auto it = s.begin(); it != s.end(); it++) {
		if (it != prev(s.end())) {
			out << *it << ", ";
		}
		else {
			out << *it << "}";
		}
	}
	return out;
}
ostream& operator<<(ostream& out, const Conformity& conf) {
	out <<"X:"<<conf.X<<endl<<"Y:"<< conf.Y<<endl<<"G:" << conf.G;
	return out;
}

bool operator==(const set<string>& lhs, const set<string>& rhs) {//проверка на равенство множеств
	if (lhs.size() != rhs.size()) {
		return false;
	}
	auto y = rhs.begin();
	for (const auto& x : lhs) {//берем каждый элемент первого и второго множества
		if (x != *y) {//если не равны
			return false;
		}
		y++;
	}
	return true;
}

bool CheckIncludeGraphic(const Graphic& lhs, const Graphic& rhs) {
	for (const auto& element : lhs) {//берем компоненту первого графика
		auto it=find(rhs.begin(), rhs.end(), element);//берем компоненту второго графика
		if (it == rhs.end()) {//если не найдено
			return false;
		}

	}
	return true;//если все компоненты первого графика были найдены во втором графике
}

bool CheckConformityes(const Conformity& lhs, const Conformity& rhs) {
	return lhs.X == rhs.X && lhs.Y == rhs.Y && CheckIncludeGraphic(lhs.G, rhs.G);
}

void Continuation(const Conformity& default_) {//операция продолжение
	Conformity conf;
	int Q_size, U_size, G_size;
	cout << "Введите мощность множества Q\n";
	cin >> Q_size;//вводим мощность множества
	cout << "Введите элементы множества Q\n";
	FillSet(conf.X, Q_size);//заполняем множество
	cout << "Введите мощность множества U\n";
	cin >> U_size;//вводим размер множества
	cout << "Введите элементы множества U\n";
	FillSet(conf.Y, U_size);//заполняем множество
	cout << "Введите мощность графика G\n";
	cin >> G_size;//вводим размер графика
	cout << "Введите кортежи графика G\n";
	FillGraphic(conf.G, G_size);//заполняем график
	cout << conf << endl;
	if (CheckConformityes(default_, conf)) {//если соответствие Г7 является продолжением Г1
		cout << "Соответствие Г7 является продолжением соответствия Г1\n";
	}
	else {//если соответствие Г7  не является продолжением Г1
		cout << "Соответствие Г7 не является продолжением соответствия Г1\n";
	}
	if (CheckConformityes(conf,default_)) {////если соответствие Г1 является продолжением Г7
		cout << "Соответствие Г1 является продолжением соответствия Г7\n";
	}
	else {//если соответствие Г1 не  является продолжение Г7
		cout << "Соответствие Г1 не является продолжением соответствия Г7\n";
	}

}

Conformity Narrowing(const Conformity& conf) {//операции сужения
	int size;
	cout << "Введите мощность множества А\n";
	cin >> size;//вводим мощность множества
	set<string> A;
	cout << "Введите элементы множества А\n";
	set<string> result;//создаем пустое множество
	FillSet(A, size);//заполняем множество
	return { conf.X,conf.Y,Intersection(conf.G,Cartesian(A,conf.Y)) };
}

int main() {
	setlocale(LC_ALL, "ru");
	Conformity first, second;//создаем пустые соответсвия А и В
	int X_size, Y_size, F_size, W_size, Z_size, P_size;
	cout << "Введите мощность множества X\n";
	cin >> X_size;
	cout << "Введите элементы множества X\n";
	FillSet(first.X, X_size);
	cout << "Введите мощность множества Y\n";
	cin >> Y_size;
	cout << "Введите элементы множества Y\n";
	FillSet(first.Y, Y_size);
	cout << "Введите мощность графика G\n";
	cin >> F_size;
	cout << "Введите кортежи графика G\n";
	FillGraphic(first.G, F_size);
	cout <<"X:" <<first.X<<endl<<"Y:"<<first.Y<<"G:"<<first.G<<endl;

	cout << "Введите мощность множества W\n";
	cin >> W_size;
	cout << "Введите элементы множества W\n";
	FillSet(second.X, W_size);
	cout << "Введите мощность множества Z\n";
	cin >> Z_size;
	cout << "Введите элементы множества Z\n";
	FillSet(second.Y, Z_size);
	cout << "Введите мощность графика P\n";
	cin >> P_size;
	cout << "Введите кортежи графика P\n";
	FillGraphic(second.G, P_size);
	cout <<"W:" <<second.X<<endl<<"Z:"<<second.Y<<endl<<"P:"<<second.G<<endl;

	while (true) {
		Menu();//Перечисление всех операций
		cout << "Введите номер команды\n";
		int number;
		cin >> number;
		switch (number)//Выбор операции
		{
		case 1: {//операция объединения
			cout << "Объединение:\n" << Union(first, second) << std::endl;
			break;
		}
		case 2: {//операция пересечения
			cout << "Пересечение:\n" << Intersection(first, second) << std::endl;
			break;
		}
		case 3: {//операция разности
			int k;
			cout << "Введите номер операции\n1. Операция разности между соответствиями Г1 и Г2\n2. Операция разности между соответствиями Г2 и Г1\n";
			cin >> k;
			switch (k)//Выбор операций
			{
			case 1: {
				cout <<" 1 - Операция разности между соответствиями Г1 и Г2:\n" << Difference(first, second) << std::endl;
				break;
			}
			case 2: {
				cout <<"2 - Операция разности между соответствиями Г2 и Г1:\n" << Difference(second, first) << std::endl;
				break;
			}
			default:
				break;
			}

			break;
		}
		case 4: {//операция симметрической разности
			cout << "Симметрическая разность:\n" << SymmetryDifference(first, second) << std::endl;
			break;
		}

		case 5: {//операция инверсия
			int k;
			cout << "Введите номер операции\n1 - Инверсия графика Г1\n2 - Инверсия графика Г2\n";
			cin >> k;
			switch (k)
			{
			case 1: {
				cout << "Инверсия соответствия Г1:\n" << "Y:"<<Inversion(first).X<<endl<<"X:"<< Inversion(first).Y<<endl<<"G:"<< Inversion(first).G << std::endl;
				break;
			}
			case 2: {
				cout << "Инверсия соответствия Г2:\n" << "Z:" << Inversion(second).X <<endl<< "W:" << Inversion(second).Y <<endl <<"P:" << Inversion(second).G << std::endl;
				break;
			}
			default:
				break;
			}

			break;
		}
		case 6: {//операция композиция
			int k;
			cout << "Введите номер операции\n1 - Композиция соответствий Г1 и Г2 (Г1*Г2)\n2 - Композиция соответствий Г2 и Г1 (Г2*Г1)\n";
			cin >> k;
			switch (k)
			{
			case 1: {
				cout << "Композиция соответствий Г1 и Г2 (Г1 * Г2):\n "<< Composition(first, second) << std::endl;
				break;
			}
			case 2: {
				cout << "Композиция соответствий Г2 и Г1 (Г2 * Г1):\n " << Composition(second, first) << std::endl;
				break;
			}
			default:
				break;
			}
			break;

		}
		case 7: {//образ
			cout << ImageOperation(first)<<endl;
			break;
		}
		case 8: {//прообраз
			cout <<PrototypeOperation(first)<<endl;
			break;
		}
		case 9: {//продолжение
			Continuation(first);
			break;
		}
		case 10: {//сужение
			cout << Narrowing(first)<<endl;
			break;
		}
		case 0: {//операция выхода
			return 0;
		}
		default: {
			cout << "Вы ввели неправильную команду\n";
			break;
		}
		}
	}
}