#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct Prepod {
	const char* name;
	const char* surname;
	const char* pupil;
	const char* subject;

	Prepod(const char* n, const char* surn, const char* pup, const char* subj)
	{
		name = n;
		surname = surn;
		pupil = pup;
		subject = subj;
	}
};

struct Link {
	Link* prev;
	Link* next;
	Prepod* teacher;

	Link(Prepod* prep, Link* pr = nullptr, Link* next = nullptr)
	{
		this->prev = pr;
		this->next = next;
		this->teacher = prep;
	}
};

vector<const char*> sorting(vector<const char*> names);

void findPupil(Link* curr, const char* pupil)
{
	while (curr->prev != NULL)
	{
		curr = curr->prev;
	}

	vector<const char*> name;

	while (curr != NULL)
	{
		if (curr->teacher->pupil == pupil)
		{
			name.push_back(curr->teacher->surname);
		}
		curr = curr->next;
	}

	sorting(name);

	for (auto i : name)
		cout << i << "\t";
	cout << endl;
}

vector<const char*> sorting(vector<const char*> names)
{
	const char* temp;
	for (int i = 0; i < names.size()-1; i++)
	{
		if (names[i] > names[i + 1])
		{
			temp = names[i + 1];
			names[i + 1] = names[i];
			names[i] = temp;
		}
	}

	return names;
}

void findSubj(Link* curr, const char* name, const char* surname)
{
	while (curr->prev != NULL)
	{
		curr = curr->prev;
	}

	while (curr != NULL)
	{
		if (curr->teacher->name == name && curr->teacher->surname == surname)
		{
			cout << curr->teacher->subject << endl;
		}
		curr = curr->next;
	}
}

Link* add(Link* current, Link* follow)
{
	current->next = follow;
	follow->prev = current;
	follow->next = nullptr;

	return follow;
}

void print(Link* curr)
{
	cout << "Name: " << curr->teacher->name << endl;
	cout << "Surname: " << curr->teacher->surname << endl;
	cout << "Pupil: " << curr->teacher->pupil << endl;
	cout << "Subject: " << curr->teacher->subject << endl;
}

int main()
{
	Link* teachers = new Link(new Prepod("Alexey", "Zykov", "Physics", "Labs"), nullptr);
	teachers = add(teachers, new Link(new Prepod("Irina", "Ryzkova", "Math", "linear algebra")));
	teachers = add(teachers, new Link(new Prepod("Irina", "Ryzkova", "Math", "mathematical analysis")));
	teachers = add(teachers, new Link(new Prepod("Natalia", "Garinova", "Physics", "Electricity")));
	teachers = add(teachers, new Link(new Prepod("Igor", "Spiridonov", "Physics", "Labs")));

	//findSubj(teachers, "Irina", "Ryzkova");
	findPupil(teachers, "Physics");
	return 0;
}