//TP 2018/2019: Zadaća 3, Zadatak 5
#include <iostream>
#include <new>
#include <string>
#include <vector>
#include <stdexcept>
#include <set>

typedef std::vector<std::set<std::string>> povratni_tip;

struct Dijete{
    std::string ime;
    Dijete *sljedeci;
};

Dijete *Kreiraj(std::vector<std::string> stringovi)
{
    Dijete *pocetak = nullptr, *prethodni; Dijete *novi;
    for(int i = 0; i < stringovi.size(); i++)
    {
        novi = new Dijete{stringovi.at(i), nullptr};
        if(!pocetak) pocetak = novi;
        else  prethodni->sljedeci = novi;

        prethodni = novi;
    }
    prethodni->sljedeci = pocetak;

    return pocetak;
}

int vrati_duzinu(std::string s)
{
	int vrati = 0;

	for(int i = 0; i < s.length(); i++)
	{
		if( (s.at(i) >= 'a' && s.at(i) <= 'z') || (s.at(i) >= 'A' && s.at(i) <= 'Z') || (s.at(i) >= '0' && s.at(i) <= '9'))
		vrati++;
	}

	return vrati;
}
povratni_tip Razvrstavanje(std::vector<std::string> vektor_stringova, int broj_timova)
{
    if( broj_timova < 1 || broj_timova > vektor_stringova.size())
    throw std::logic_error("Razvrstavanje nemoguce");

    auto pok = Kreiraj(vektor_stringova);

    int timovi = 0, broj_djece = vektor_stringova.size();
    bool logicka;

    int po_timu = broj_djece / broj_timova;
    if(broj_djece % broj_timova == 0)
    logicka = false;
    else logicka = true;

    povratni_tip vrati;
	int strpano = 1;
    while(timovi < broj_timova)
    {
    	int poslano = 0; std::set<std::string> skup;
    	while(poslano < po_timu + logicka)
    	{

    		skup.insert(pok->ime);

    		int duzina = vrati_duzinu(pok->ime);
    		// trazenje prethodnika
    		Dijete *klizni = pok->sljedeci;
    		while( klizni->sljedeci != pok)
    		{
    			klizni = klizni->sljedeci;
    		}


    		klizni->sljedeci = pok->sljedeci;
    		Dijete *brisi = pok; pok = pok->sljedeci;
    		delete brisi;
    			if( strpano == broj_djece) break;
    		for(int i = 0; i < duzina - 1 ; i++)
    		{
    			if( pok->sljedeci )
    			pok = pok->sljedeci;
    			else continue;
    		}
    		strpano++;
    		poslano++;

    	}
    	vrati.push_back(skup);
    	timovi++;

    	if( timovi == broj_djece % broj_timova) logicka = false;
    }

    return vrati;
}

void Ispisi_Skup(std::set<std::string> skup)
{
	auto it = skup.begin();

	for(int i = 0; i < skup.size(); i++)
	{
		if( i != skup.size() - 1)
		std:: cout << *it << ", ";
		else std:: cout << *it;

		it++;
	}
}

int main ()
{

	std:: cout << "Unesite broj djece: ";
	int broj_djece; std:: cin >> broj_djece;
	std:: cout << "Unesite imena djece: ";
	std::cin.ignore(1000,'\n');
	try
	{
		std::vector<std::string> vektor_stringova(broj_djece);
		for(int i = 0; i < vektor_stringova.size(); i++)
		{
			std::string unos; std::getline(std::cin, unos);
			vektor_stringova.at(i) = unos;
		}
		std:: cout << std::endl;
		std:: cout << "Unesite broj timova: ";
		int broj_timova; std:: cin >> broj_timova;

		povratni_tip pokupi = Razvrstavanje(vektor_stringova, broj_timova);

		for(int i = 0; i < pokupi.size(); i++)
		{
			std:: cout << "Tim " << i + 1 << ": "; Ispisi_Skup(pokupi.at(i)); std:: cout << std::endl;
		}
	}
	catch(std::logic_error greska)
	{
		std:: cout << "Izuzetak: " << greska.what() << std::endl;
	}

/*	auto pok = Kreiraj(stringovi);
	Dijete *pomocni;
    auto pamti = pok;

	 za brisanje cijele liste
	{
	for(int i = 0; i < stringovi.size(); i++)
	{
	    if ( i != stringovi.size() - 1)
	    {
	        pomocni = pok->sljedeci;
	        delete pok;
	        pok = pomocni;
	    }
	    else
	    {
	        delete pok;
	    }
	}
	}
	for(int i = 0; i < stringovi.size() - 1; i++)
	{

	   if( i == 1)
	   {
	       pomocni->sljedeci = pok->sljedeci;
	       Dijete *brisi = pok;
	       pok = pok->sljedeci;
	       delete brisi;

	   }
	   pomocni = pok;
	   std:: cout << pok->ime << " ";
	   pok = pok->sljedeci;

	}
	pok = pamti;
	for(int i = 0; i < stringovi.size() - 1; i++)
	{
	    if ( i != stringovi.size() - 1)
	    {
	        pomocni = pok->sljedeci;
	        delete pok;
	        pok = pomocni;
	    }
	    else
	    {
	        delete pok;
	    }
	}
	*/

	return 0;
}