// nuovi concetti: manipolazione di liste
//                 parametro stream
#include <iostream>
#include <fstream>

using namespace std;

struct Lnodo {
  int dato;
  Lnodo *succ;
};

void writelist(Lnodo*);
void InserisciPrima(Lnodo*&, Lnodo*, Lnodo*);
void InserisciDopo(Lnodo*&, Lnodo*, Lnodo*);
void InvertiLista(Lnodo*&);
int  ListeUguali(Lnodo*, Lnodo*);
void LeggiInTesta(ifstream&, Lnodo*&);
void LeggiInCoda(ifstream&, Lnodo*&);
void DistruggiLista(Lnodo*&);


int main () {
  Lnodo *lista1=NULL, *lista2=NULL;
  ifstream fin("lista.txt");
  cout << "\nDati letti dal file:\n";
  LeggiInTesta(fin,lista1);
  cout << "Dati come inseriti nella lista N. 1:\n";
  writelist(lista1);
  fin.clear();
  fin.seekg(0);
  cout << "\nDati letti dal file:\n";
  LeggiInCoda(fin,lista2);
  fin.close();
  cout << "Dati come inseriti nella lista N. 2:\n";
  writelist(lista2);
  InvertiLista(lista2);
  cout << "\nContenuto della lista N. 2 rovesciata:" << endl;
  writelist(lista2);
  if (ListeUguali(lista1,lista2))
    cout << "OK";
  else
    cout << "Oh Oh...!!!";
  cout << endl;
  DistruggiLista(lista2);
  DistruggiLista(lista1);
}


void writelist(Lnodo* ptr) {
  while (ptr) {
    cout << ptr->dato << " ";
    ptr = ptr->succ;
  }
  cout << endl;
}


void InserisciPrima(Lnodo* &testa, Lnodo* posto, Lnodo* nuovo) {
  // Inserisce il nodo 'nuovo' nella lista 'testa' prima di 'posto'
  if (testa == NULL) {
    nuovo->succ = NULL;
    testa = nuovo;
  }
  else if (posto==testa) {
    nuovo->succ = testa;
    testa = nuovo;
  }
  else {
    Lnodo* precedente;
    for(precedente=testa;precedente->succ!=posto;precedente=precedente->succ)
      continue;
    nuovo->succ = posto;
    precedente->succ = nuovo;
  }
}


void InserisciDopo(Lnodo* &testa, Lnodo* posto, Lnodo* nuovo) {
  // Inserisce il nodo 'nuovo' nella lista 'testa' dopo 'posto'
  if (testa == NULL) {
    nuovo->succ = NULL;
    testa = nuovo;
  }
  else {
    nuovo->succ = posto->succ;
    posto->succ = nuovo;
  }
}


void InvertiLista(Lnodo*& testa) {
  // Inverte la lista 'testa' (il nodo di coda diventa il nodo di testa e viceversa)
  Lnodo *prima=NULL, *corrente=testa, *dopo;
  while (corrente) {
    dopo = corrente->succ;
    corrente->succ = prima;
    prima = corrente;
    corrente = dopo;
  }
  testa = prima;
}


int ListeUguali(Lnodo* l1, Lnodo* l2) {
  // Restituisce vero (1) se le due liste sono uguali, cioe'
  // se le due liste sono entrambe vuote, oppure
  // il contenuto della testa coincide e le liste private della testa
  // sono uguali
  return (!(l1 || l2) ||
      l1 && l2 && l1->dato==l2->dato &&
      ListeUguali(l1->succ,l2->succ));
}


void LeggiInTesta(ifstream& fin, Lnodo*& testa) {
  int n;
  Lnodo *ptr;
  testa = NULL;
  while (fin >> n) {
    ptr = new Lnodo;
    ptr->dato = n;
    cout << n << " ";
    InserisciPrima(testa, testa, ptr);
  }
  cout << endl;
}


void LeggiInCoda(ifstream& fin, Lnodo*& testa) {
  int n;
  Lnodo *ptr, *ultimo;
  testa = NULL;
  while (fin >> n) {
    ptr = new Lnodo;
    ptr->dato = n;
    cout << n << " ";
    InserisciDopo(testa, ultimo, ptr);
    ultimo = ptr;
  }
  cout << endl;
}

void DistruggiLista(Lnodo*& testa) {
  while (testa) {
    Lnodo* ptr = testa;
    testa = testa->succ;
    delete ptr;
  }
}