#ifndef LISTA_H
#define LISTA_H

#include <iostream>

using namespace std;

typedef int T;

struct Nodo{
    T elemento;
    Nodo * next;
};

class Lista{
    friend ostream & operator<<(ostream &, const Lista &);

    private:
        Nodo * testa;
        void clear();
        bool find(const T &, Nodo * &)const;
        bool push(const T &);
        bool pop(T &);

    public:
        Lista() {testa = 0;} //start
        bool empty()const;
        bool full()const {return false;}
        bool inList(const T &)const;
        int getCount()const;
        bool Insert(const T &);
        bool Delete(const T &);
        ~Lista() {clear();}
};

#endif

//ti ho messo tutto in un file perchè mi scocciavo di mandarne due, ma su dev chiaramente li devi separare

#include "Lista.h"



bool Lista::empty()const
{
    if(testa == 0)
        return true;

    return false;
}//fine empty

//------------------------------------------------------------------------------

bool Lista::inList(const T & e)const
{
    if(empty())
        return false;

    Nodo * temp = testa;
    bool trovato = false;
    while(temp && !trovato)
    {
        if(temp->elemento == e)
            trovato = true;

        else
            temp = temp->next;
    }//fine while

    return trovato;
}//fine inList

//------------------------------------------------------------------------------

bool Lista::find(const T & e, Nodo * & pos)const
{
    if(empty())
        return false;

    Nodo * temp = testa;
    bool trovato = false;
    while(temp && !trovato)
    {
        if(temp->elemento == e)
            trovato = true;

        else
        {
            pos = temp;
            temp = temp->next;
        }//fine else
    }//fine while

    return trovato;
}//fine find

//------------------------------------------------------------------------------

bool Lista::push(const T & e)
{
    if(full())
        return false;

    Nodo * q;
    q = new Nodo;
    q->elemento = e;
    q->next = testa;
    testa = q;
    return true;
}//fine push

//------------------------------------------------------------------------------

bool Lista::Insert(const T & e)
{
    if(full())
        return false;

    else if((testa == 0) || (testa->elemento > e)) //l'elemento va inserito in testa
        push(e);

    else //altrimenti l'elemento va inserito al centro o in coda
    {
        Nodo * prec = testa;
        Nodo * succ;
        Nodo * q; //allocazione e inizializzazione di un nuovo non da inserire
        q = new Nodo;
        q->elemento = e;
        q->next = 0;
        while((prec->next) && (prec->next->elemento < e))  //si scorre l'intera lista (prec->next)
             prec = prec->next;                        //fin quando gli elementi sono minori di quello da inserire(prec->next->elemento < e)
        succ = prec->next; //succ rappresenta la posizione in cui deve avvenire l'inserimento del nuovo Nodo
        q->next = succ; //queste due righe permettono di collegare il nuovo nodo al resto della lista
        prec->next = q;
        return true;
    }//fine else

}//fine Insert

//------------------------------------------------------------------------------

bool Lista::pop(T & e)
{
    if(empty())
        return false;

    Nodo * temp = testa;
    e = testa->elemento;
    testa = testa->next;
    delete temp;
    return true;
}//fine pop

//------------------------------------------------------------------------------

bool Lista::Delete(const T & e)
{
    if(empty())
        return false;

    else if(testa->elemento == e)
    {
        T value;
        return pop(value);
    }//fine else if

    else
    {
        Nodo * posizione;
        if(find(e,posizione)) //la funzione find determina l'indirizzo "posizione" dell'elemento che precede quello da eliminare
        {
            Nodo * temp;
            temp = posizione->next;
            posizione->next = posizione->next->next;
            delete temp;
            return true;
        }//fine if

        else
            return false;
    }//fine else
}//fine Delete

//------------------------------------------------------------------------------

int Lista::getCount()const
{
    int count = 0;
    Nodo * temp = testa;
    while(temp)
    {
        count++;
        temp = temp->next;
    }//fine while

    return count;
}//fine getCount

//------------------------------------------------------------------------------

void Lista::clear()
{
    Nodo * temp = testa;
    while(testa)
    {
        temp = testa;
        testa = testa->next;
        delete temp;
    }//fine while
}//fine clear

//------------------------------------------------------------------------------

ostream & operator<<(ostream & out, const Lista & L)
{
    if(L.empty())
        out<<" Non ci sono elementi.";

    else
    {
        Nodo * temp = L.testa;
        while(temp)
        {
            out<<temp->elemento<<" ";
            temp = temp->next;
        }//fine while
    }//fine else

    return out;
}//fine operator<<