#include<iostream>
#include<stdexcept>

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
	bool isAtFirst();
		// vero se current punta al primo nodo;
	bool isAtLast();
		// vero se current punta all'ultimo nodo;
	mylist<ItemType> *goFirst(); 
		// assenga current al primo nodo della lista (first);
	mylist<ItemType> *goNext(); 
		// sposta current al nodo succecssivo (current->next);
	ItemType getCurrentData();
		// restituisce l'item contenuto nel nodo corrente, SENZA ESTRARRE IL NODO
	mylist<ItemType> *insert(ItemType i);
		// inserisce un nuovo nodo in fondo alla lista con item i
	ItemType extract();
		// 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());
}

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;
}