#include<iostream>
#include<stdexcept>

//	IN QUESO FILE SONO RIPORTATE DUE POSSIBILI SOLUZIONI ALL'ESERCIZIO, UNA BASATA
//	SU UN ALGORITMI ITERATIVO, L'ALTRA SU UN ALGORITMO RICORSIVO.
//	E' INOLTRE FORNITA, PER COMPLETEZZA,  L'IMPLEMENTAZIONE DI TUTTI I METODI DELLA 
//	CLASSE mylist, SEBBENE QUESTI NON FOSSERO RICHIESTI DALL'ESERCIZIO.
//
using namespace std;

class myEmptyList: public runtime_error {
public:
	 myEmptyList(): runtime_error("Errore: lista vuota"){};
};

class myEndOfList: public runtime_error {
public:
		        myEndOfList(): runtime_error("Errore: Raggiunto il limite della lista"){};
};

template <class ItemType>
class mynode {
public:
	ItemType data;
	mynode<ItemType> *next;
	mynode(ItemType i): data(i), next(nullptr) {};
	~mynode() {};
};

template <class ItemType>
class mylist {
	mynode<ItemType> *first, *last, *current;
public:
	mylist(): first(nullptr), last(nullptr), current(nullptr) {};
	~mylist(); 
	bool isEmpty() {
		// vero se la lista è vuota
		return first==nullptr;
	}
	bool isAtFirst() {
		if(isEmpty())
			throw myEmptyList();

		return current==first;
		// vero se current punta al primo nodo;
	}	
	bool isAtLast() {
		if(isEmpty())
			throw myEmptyList();

		return current==first;
		// vero se current punta all'ultimo nodo;
	}
	mylist<ItemType> *goFirst() {
		if(isEmpty())
			throw myEmptyList();
		current=first;
		return this;
		// assenga current al primo nodo della lista (first);
	}
	mylist<ItemType> *goNext() {
		if(isEmpty())
			throw myEmptyList();
		if(isAtLast())
			throw myEndOfList();
		current=current->next;
		return this;
		// sposta current al nodo succecssivo (current->next);
	}
	ItemType getCurrentData() {
		if(isEmpty())
			throw myEmptyList();
		return current->data;
		// restituisce l'item contenuto nel nodo corrente, SENZA ESTRARRE IL NODO
	}
	mylist<ItemType> *insert(ItemType i) {
		mynode<ItemType> *newnode;
		newnode=new mynode<ItemType>(i);
		if(isEmpty())
			first=last=newnode;
		else { 
			last->next=newnode;
			last=newnode;
		}
		current=newnode;
		return this;
		// inserisce un nuovo nodo in fondo alla lista con item i
	}
	ItemType extract() {
		mynode<ItemType> *tbd;
		ItemType rv;

		if(isEmpty())
			throw myEmptyList();
		tbd=first;
		if(first==last)
			first=last=nullptr;
		else 
			first=first->next;
		if(current==tbd)
			current=first;
		rv=tbd->data;
		delete tbd;
		return rv;
		// estrae il primo nodo della lista e restituisce il dato in esso contenuto
	}
};

//	POSSIBILE IMPLEMENTAZIONE DELLA FUNZIONE EQUALS RICHIESTA. APPROCCIO ITERATIVO
//
			
template <class ItemType>
bool equals (mylist<ItemType> *left, mylist<ItemType> *right)  {
	bool r=true;

	if(left->isEmpty() && right->isEmpty())
		return true;
	if(left->isEmpty() || right->isEmpty())
		return false;

	left->goFirst();
	right->goFirst();

	do {
		if(left->getCurrentData()!=right->getCurrentData()) {
			r=false;
			break;
		}

		if(left->isAtLast()!=right->isAtLast()) {
			r=false;
			break;
		}

		if(left->isAtLast())
			break;

		left->goNext();
		right->goNext();

	} while(1); 

	return r;
}

//      LE DUE FUNZIONI CHE SEGUONO, FORNISCONO UNA SOLUZIONE ALTERNATIVA,
//      UGUALMENTE ACCETTABILE E BASATA SU UN APPROCCIO RICORSIVO
//      

template <class ItemType>
bool equals_ricorsiva (mylist<ItemType> *left, mylist<ItemType> *right) {
	bool le,re;
	le=left->isEmpty();
	re=right->isEmpty();
	if(le && re)
		return true; // entrambe vuote: ok
	if(le != re)
		return false; // solo una vuota: no
	
	return do_equals(left->goFirst(),right->goFirst()); // entrambe non vuote: da vedere...
}

template <class ItemType>
bool do_equals (mylist<ItemType> *left, mylist<ItemType> *right) {
	
	bool llast, rlast, confronto;
	llast=left->isAtLast();
	rlast=right->isAtLast();

	if (llast!=rlast)
	       return false;
	
	confronto=left->getCurrentData()==right->getCurrentData();
	
	if(llast&&rlast)
		return confronto;
	else
		return confronto && do_equals(left->goNext(),right->goNext());
}

//	MAIN CON ALCUNE PROVE
//
int main() 
{
	mylist<int> *l1, *l2,*l3,*l4;
	bool b;

	l1=new mylist<int>();
	l2=new mylist<int>();
	l3=new mylist<int>();
	l4=new mylist<int>();

	l1->insert(1)->insert(2)->insert(3)->insert(4)->insert(5);
	l2->insert(1)->insert(2)->insert(3)->insert(4)->insert(5);
	l3->insert(1)->insert(2)->insert(3)->insert(5)->insert(6);
	l3->insert(1)->insert(2)->insert(3)->insert(5);

	b=equals(l1,l2);
	if(b) 
		cout<<"l1==l2"<<endl;
	else
		cout<<"l1!=l2"<<endl;

	b=equals(l2,l3);
	if(b) 
		cout<<"l2==l3"<<endl;
	else
		cout<<"l2!=l3"<<endl;
	
	b=equals(l3,l4);
	if(b) 
		cout<<"l3==l4"<<endl;
	else
		cout<<"l3!=l4"<<endl;

	b=equals(l4,l3);
	if(b) 
		cout<<"l4==l3"<<endl;
	else
		cout<<"l4!=l3"<<endl;

	b=equals(l4,l2);
	if(b) 
		cout<<"l4==l2"<<endl;
	else
		cout<<"l4!=l2"<<endl;
}