#include<iostream>
using namespace std;
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

struct Lista // struktura reprezentujaca pojedyncza wizytowke
{
string napis;
Lista *nastepny; // wskaznik na nastepny element na liscie

Lista() // konstruktor - wywolywany przy tworzeniu obiektu
{
// wczytujemy dane
cout << "Podaj napis: ";
cin >> napis;

nastepny = NULL;
}

void wypisz()
    {
        cout << napis << endl;
    }
};

void dodaj_napis(Lista **korzen)
{
Lista *nowa = new Lista; // utworzenie nowej wizytowki
Lista *pomoc = (*korzen), *pomoc1 = NULL; // wskazniki pomocnicze posluza do poruszania sie po liscie

while (pomoc != NULL && (pomoc->napis).compare(nowa->napis) == -1) // dopoki nie wyszlismy za liste i nazwisko na liscie jest przed nowym nazwiskiem poruszamy sie dalej
{
pomoc1 = pomoc; // pomoc1 zawsze wskazuje poprzednika pomoc
pomoc = pomoc->nastepny;
}

if (pomoc != NULL && (pomoc->napis).compare(nowa->napis) == 0) // wizytowka z podanym nazwiskiem juz istanieje
{
cout << "napis " << nowa->napis << " juz istanieje na liscie\n";
delete nowa; // usuniecie obiektu
}
else if ((*korzen) == NULL || (pomoc == (*korzen) && (pomoc->napis).compare(nowa->napis) == 1)) // nowy element bedzie korzeniem listy
{
nowa->nastepny = (*korzen);
(*korzen) = nowa;
}
else // dodajemy wizytowke w srodku lub na koncu listy
{
pomoc1->nastepny = nowa;
nowa->nastepny = pomoc;
}
}

void skasuj_liste(Lista **korzen){
    Lista *pomoc = *korzen, *pomoc1 = pomoc->nastepny;
    while(pomoc != NULL){
        pomoc1 = pomoc->nastepny;
        free(pomoc);
        pomoc = pomoc->nastepny;
    }
    *korzen = NULL;
}

void wyszukaj_napis(Lista *korzen, string a)
{
while(korzen != NULL && (korzen->napis).compare(a) != 0) // dopoki nie znajdziemy wizytowki z podanym nazwiskiem lub nie przeszukamy calego wizytownika
korzen = korzen->nastepny;

if (korzen == NULL)
cout << "Nie ma napisu " << a << endl;
else
korzen->wypisz();
}

void wypisz_wizytownik(Lista *korzen)
{
cout << "Zawartosc listy:\n";

while(korzen != NULL)
{
korzen->wypisz(); // wypisanie wizytowki
korzen = korzen->nastepny; // przejscie na kolejny element
}
}

bool usun_napis(Lista **korzen, string a)
{
if ((*korzen) == NULL) // lista jest pusta
return false;
Lista *pomoc = (*korzen), *pomoc1 = NULL; // wskazniki pomocnicze posluza do poruszania sie po liscie

while(pomoc != NULL && (pomoc->napis).compare(a) != 0) // dopoki nie znajdziemy wizytowki z podanym nazwiskiem lub nie przeszukamy calego wizytownika
{
pomoc1 = pomoc;
pomoc = pomoc->nastepny;
}

if (pomoc == NULL) // wyszlismy za liste - nie ma takiego nazwiska na liscie
return false;
else if (pomoc == (*korzen)) // usuwamy koniec
{
(*korzen) = (*korzen)->nastepny;
delete pomoc;
}
else // usuwamy z srodka lub konca listy
{
pomoc1->nastepny = pomoc->nastepny;
delete pomoc;
}
return true;
}

int main()
{
char instrukcja;
string napis;
Lista *korzen = NULL; // korzen listy - wskaznik na pierwszy element
cout << "MENU - mozliwe operacje na wizytowniku\n"
<< "d - dodanie wizytowki\n"
<< "s - wyszukanie wizytowki\n"
<< "w - wypisanie wszystkich wizytowek\n"
<< "u - usuniecie wizytowki\n"
<< "Ctrl+Z - koniec programu\n";

while (cin >> instrukcja)
{
switch (instrukcja)
{
case 'd':
dodaj_napis(&korzen);
break;
case 's':
cout << "Podaj napis: ";
cin >> napis;
wyszukaj_napis(korzen, napis);
break;
case 'w':
wypisz_wizytownik(korzen);
break;
case 'u':
cout << "Podaj napis: ";
cin >> napis;
if (!usun_napis(&korzen, napis))
cout << "Nie odnaleziono wizytowki z podanym nazwiskiem" << endl;
else
cout << "Wizytowka z podanym nazwiskiem zostala usunieta" << endl;
break;
case 'b':
    skasuj_liste(&korzen);break;
default:
cout << "Musisz wybrac jedna z opcji: d - dodawanie, s - wyszukiwanie, w - wypisanie zawartosci lub u - usuwanie\n";
break;
}
}

return 0;
}