//listanomi.cpp: lista ordinata di nomi

#include <iostream>
#include <string>
using namespace std;

// struttura per i nodi della lista
struct Nodo {
	string nome;
	Nodo*succ;
   };

   Nodo*testa;   // puntatore alla testa della lista

 // prototipi delle funzioni
 void Inizializza();
 bool ListaVuota();
 void Inserisci();
 void Elimina();
 void Visualizza();
 void SvuotaLista();
 void PresentaMenu();

 // funzione principale
 int main()
{
	int scelta;    //scelta nel menu

	Inizializza();
	do{
		do{
		   PresentaMenu();
		   cout<< " Inserisci la tua scelta ";
		   cin>> scelta;
	   }while (scelta<1 || scelta>5);
	   switch(scelta) {
		   case 1:
		       Inserisci();
		       break;
		   case 2 :
		       Elimina();
		       break;
		   case 3:
		       Visualizza();
		       break;
		   case 4:
		       SvuotaLista();
		       break;
		   }
	   }while (scelta != 5);
	   SvuotaLista();

	   return 0;
   }

   // Inizializzazione della lista
   void Inizializza()
   {
	   testa = NULL;
   }// Inizializza

   //controllo se lista è vuota
   bool ListaVuota()
   {
	   //restituisce false se non vuota
	   //            true se vuota
	   if (testa == NULL) return true;

	   return false;
   } // ListaVuota

   // inserimento di un nodo nella lista
   void Inserisci()
   {
	   string NomeInp;   // nome da inserire
	   Nodo*nuovo;       // puntatore ad un nuovo nodo
	   Nodo*temp;        // puntatori per confronti
	   Nodo*prec;

	   cout<< " Nome da inserire: ";
	   cin>> NomeInp;
	   nuovo= new Nodo;  // alloca la memoria per il nuovo nodo
	   nuovo -> nome = NomeInp;
	   nuovo -> succ = NULL;
	   if (ListaVuota()) testa = nuovo;
	   else{
		   if (testa -> nome >= nuovo -> nome) {
			   temp = testa;
			   testa = nuovo;
			   testa -> succ = temp;
		   }
		   else{
			   temp= testa;
			   while (temp != NULL && nuovo -> nome >= temp -> nome) {
				   prec = temp;
				   temp = temp -> succ;
			   }
			   nuovo -> succ = temp;
			   prec -> succ = nuovo;
		   }
	   }
   } // Inserisci

   // estrazione di un nodo della lista
   void Elimina()
   {
	   string NomeInp;      // nome da eliminare
	   Nodo*temp;           // puntatori per confronti
	   Nodo* prec;
	   bool trovato = false;  //indicatore se trovato

	   cout << " Nome da eliminare: ";
	   cin >> NomeInp;
	   if(ListaVuota()) cout << " Lista vuota " << endl;
	   else{
		   if (testa -> nome == NomeInp) {
			   trovato = true;
			   temp = testa -> succ;
			   cout << " Nome eliminato: " << testa -> nome << endl;
			   delete testa;
			   testa = temp;
		   }
		   else{
			   temp = testa -> succ;
			   prec = testa;
			   do{
				   if (temp -> nome == NomeInp) {
					   trovato = true;
					   prec -> succ = temp -> succ;
					   cout << "nome eliminato: " << temp -> nome << endl;
					   delete temp;
				   }
				   else{
					   prec = temp;
					   temp = temp -> succ;
				   }
			   }while (!trovato && temp != NULL);
		   }
		   if (!trovato)
		   cout << " Il nome richiesto non esiste " << endl;
	   } // fine else
   } // Elimina

   // Visualizzazione della lista
   void Visualizza()
   {
	   Nodo*p;
	   cout << " -- Elenco dei nomi: -- " << endl;
	   p = testa;
	   while ( p != NULL ) {
		   cout << p -> nome << endl;
		   p = p -> succ;
	   }
	   cout << " -- Fine elenco: --" << endl;
   } // Visualizza

   // toglie tutti i nodi alla lista
   void SvuotaLista()
{

	Nodo* temp;
	while ( testa != NULL) {
		cout << " Nome eliminato: " << testa -> nome << endl;
		temp = testa;
		testa = testa -> succ;
		delete temp;
	};
	cout << " Lista vuota " << endl;
} // SvuotaLista

// menu delle scelte
void PresentaMenu()
{
	cout << endl << "-----------" << endl;
	cout << " 1. Inserisci un nome " << endl;
	cout << " 2. Elimina un nome " << endl;
	cout << " 3. Visualizza la lista " << endl;
	cout << " 4. Svuota la lista " << endl;
	cout << " 5. Fine " << endl;
	cout << " ------------------" << endl;
} // PresentaMenu