#include <iostream>

using namespace std;

struct Osoba
{
    string imie;
    string nazwisko;
    Osoba* nastepna;
    Osoba()
    {
        nastepna = nullptr;
    }
};

ostream& operator<<(ostream& os, const Osoba osoba)
{
    os << osoba.imie << ' ' << osoba.nazwisko;
    return os;
}

struct Lista
{
    Osoba* pierwsza;
    void dodaj_osobe(string, string);
    Lista()
    {
        pierwsza = nullptr;
    }
    void sortuj_malejaco();
    void usun_osobe(unsigned);
};

void Lista::dodaj_osobe(string name, string surname)
{
    Osoba* nowa = new Osoba;
    nowa->imie = name;
    nowa->nazwisko = surname;
    nowa->nastepna = nullptr;

    // sprawdzamy czy dana osoba jest pierwszą na liście
    if(pierwsza == nullptr)
    {
        pierwsza = nowa;
    }
    else
    {
        Osoba* temp = pierwsza;
        while(temp->nastepna != nullptr)
            temp = temp->nastepna;
        temp->nastepna = nowa;
    }
}

void Lista::usun_osobe(unsigned nr)
{
    if(nr == 0)
    {
        Osoba* temp = pierwsza;
        pierwsza = pierwsza->nastepna;
        delete temp;
        return;
    }

    Osoba* temp = pierwsza;
    Osoba* poprzednia;
    while(nr > 0)
    {
        poprzednia = temp;
        temp = temp->nastepna;
        --nr;
    }
    poprzednia->nastepna = temp->nastepna;
    delete temp;
}

void Lista::sortuj_malejaco()
{
    Lista* temp;
    temp->pierwsza = nullptr;
    Osoba* najwieksza;
    Osoba* szukana;
    unsigned nr, nr_najw;

    while(pierwsza != nullptr)
    {
        nr = 0;
        nr_najw = 0;
        najwieksza = pierwsza;
        szukana = pierwsza;

        while(szukana->nastepna != nullptr)
        {
            szukana = szukana->nastepna;
            ++nr;
            if(szukana->nazwisko > najwieksza->nazwisko)
            {
                nr_najw = nr;
                najwieksza = szukana;
            }
        }
        temp->dodaj_osobe(najwieksza->imie, najwieksza->nazwisko);
        usun_osobe(nr_najw);
    }
    pierwsza = temp->pierwsza;
}

int main()
{
    Lista* lista = new Lista;

    lista->dodaj_osobe("Andrzej", "A");
    lista->dodaj_osobe("Beata", "B");
    lista->dodaj_osobe("Cecylia", "C");
    lista->dodaj_osobe("Dominik", "D");

    // wyświetlenie listy:
    Osoba* temp = lista->pierwsza;

    while(temp != nullptr)
    {
        cout << *temp << endl;
        temp = temp->nastepna;
    }

    lista->usun_osobe(2);
    cout << endl;
    lista->sortuj_malejaco();

    temp = lista->pierwsza;

    while(temp != nullptr)
    {
        cout << *temp << endl;
        temp = temp->nastepna;
    }

    cout << endl;
    lista->dodaj_osobe("Zenon", "Z");
    lista->sortuj_malejaco();
    temp = lista->pierwsza;

    while(temp != nullptr)
    {
        cout << *temp << endl;
        temp = temp->nastepna;
    }


    delete lista;
    return 0;
}