#include "lista_int.H"

ListaInt::ListaInt(ListaInt const& outra_lista)
    : numero_de_itens(0), elo_inicial(new Elo), elo_livre(0) 
{
    // Captura-se qualquer excepção, pois reimplementações podem levar o
    // construtor dos itens a lançar outro tipo de excepção que não bad_alloc.
    try {
        elo_inicial->seguinte = elo_final = new Elo(elo_inicial);
    } catch(...) {
        delete elo_inicial;
        throw;
    }

    // A primeira parte em nada difere do construtor por omissão.

    // A segunda faz a cópia dos itens:

    // Captura-se qualquer excepção, pois reimplementações podem levar
    // poeFim() a lançar outro tipo de excepção que não bad_alloc, e
    // além disso pode ser o construtor de algum item a falhar...
    try {
        for(Elo* elo = outra_lista.elo_inicial->seguinte; 
	    elo != outra_lista.elo_final; 
            elo = elo->seguinte)
            poeAtras(elo->item);
    } catch(...) {
        // Se não se conseguiu colocar algum item, a construção falhou
        // e é necessário destruir tudo o que entretanto foi
        // construído:
        esvazia();
        delete elo_inicial;
        delete elo_final;
        // Finalmente é necessário relançar a excepção!  Afinal, houve
        // um erro e por isso a construção falhou...
        throw;
    }

    assert(cumpreInvariante());
}

ListaInt::IteradorConstante 
ListaInt::primeiraOcorrenciaDe(Item const& item) const
{
    IteradorConstante i = primeiro();
    while(i != fim() && *i != item)
	++i;
    return i;
}

ListaInt::IteradorConstante 
ListaInt::ultimaOcorrenciaDe(Item const& item) const
{
    IteradorConstante i = ultimo();
    while(i != inicio() && *i != item)
	--i;
    return i;
}

/* Aqui podia-se resolver o problema de várias formas.  Com iteradores,
   por exemplo.  Ou chamando tiraDaFrente() até a lista estar vazia.  A
   solução escolhida é da baixo nível, e é também mais eficiente...  Mas é 
   a que exige maiores alterações se se mudar a implementação da lista...
*/
void ListaInt::esvazia()
{
    assert(cumpreInvariante());

    numero_de_itens = 0;

    // Destruir elos dinâmicos:
    for(Elo* elo = elo_inicial->seguinte; elo != elo_final; ) {
	Elo* seguinte = elo->seguinte;
	delete elo;
	elo = seguinte;
    }

    // A cadeia duplamente ligada tem de ficar vazia:
    elo_inicial->seguinte = elo_final;
    elo_final->anterior = elo_inicial;

    assert(cumpreInvariante());
}

ListaInt::Iterador ListaInt::primeiraOcorrenciaDe(Item const& item)
{
    Iterador i = primeiro();
    while(i != fim() && *i != item)
	++i;
    return i;
}

ListaInt::Iterador ListaInt::ultimaOcorrenciaDe(Item const& item) 
{
    Iterador i = ultimo();
    while(i != inicio() && *i != item)
	--i;
    return i;
}


std::ostream& operator << (std::ostream& saida, ListaInt const& lista)
{
    saida << '(';
    for(ListaInt::IteradorConstante i = lista.primeiro(); 
	i != lista.fim(); ++i) {
        saida << *i;
        if(i != lista.ultimo())
            saida << ",";
    }
    return saida << ')';
}


#ifdef TESTE

void testeSimples()
{
    ListaInt l;

    l.poeAtras(1);
    l.poeAtras(2);
    l.poeAtras(3);
    l.poeAtras(4);

    for(ListaInt::Iterador i = l.primeiro(); i != l.fim(); ++i)
        cout << *i << ' ';
    cout << endl;

    for(ListaInt::Iterador i = l.ultimo(); i != l.inicio(); --i)
        cout << *i << ' ';
    cout << endl;

    cout << l << endl;

    ListaInt::Iterador i = l.primeiro();
    ++i;

    l.insereAntes(i, 10);

    cout << l << endl;

    l.remove(i);

    cout << l << endl;

    l.tiraDaFrente();
    cout << l << endl;

    l.tiraDeTras();
    cout << l << endl;

    l.tiraDaFrente();
    cout << l << endl;

    l.tiraDeTras();
    cout << l << endl;

    l.poeNaFrente(10);
    cout << l << endl;
    l.poeNaFrente(20);
    cout << l << endl;
    l.poeNaFrente(30);
    cout << l << endl;
    l.poeNaFrente(40);
    cout << l << endl;
    l.poeAtras(100);
    cout << l << endl;
    l.poeAtras(200);
    cout << l << endl;
    l.poeAtras(300);
    cout << l << endl;
    l.poeAtras(400);
    cout << l << endl;

    ListaInt::Iterador j = l.ultimo();
    --j;
    --j;
    --j;
    l.remove(j);
    cout << l << endl;
    --j;
    --j;
    l.remove(j);
    cout << l << endl;
    l.insereAntes(j, 1000);
    cout << l << endl;
    l.insereAntes(j, 2000);
    cout << l << endl;
    l.insereAntes(j, 3000);
    cout << l << endl;
    l.insereAntes(j, 4000);
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
    l.tiraDaFrente();
    cout << l << endl;
}

void testeComplicado()
{
    ListaInt l;
    
    cout.precision(2);
    cout << "Cria l e preenche com -11 2 3 4." << endl;
    l.poeAtras(11);
    l.poeAtras(2);
    l.poeAtras(3);
    l.poeAtras(4);
    for(ListaInt::Iterador i = l.primeiro(); i != l.fim(); ++i)
	cout << *i << ' ';
    cout << endl;
    for(ListaInt::Iterador i = l.primeiro(); i != l.fim(); ++i)
	cout << *i << ' ';
    cout << endl;

    cout << "l por ordem inversa:" << endl;
    for(ListaInt::Iterador i = l.ultimo(); i != l.inicio(); --i)
	cout << *i << ' ';
    cout << endl;

    cout << "Frente de l: " << l.frente() << endl;
    cout << "Tras de l: " << l.tras() << endl;

    cout << "l por ordem:" << endl;
    cout << "l: " << l << endl;

    cout << "Insere 10 antes do 3 em l:" << endl;
    ListaInt::Iterador k = l.primeiro();
    k++;
    ++k;
    l.insereAntes(k, 10);
    cout << "l: " << l << endl;

    cout << "Insere 11 antes do 10 em l (iterador temporário):" << endl;
    l.insereAntes(l.primeiraOcorrenciaDe(10), 
		  11);
    cout << "l: " << l << endl;

    cout << "Insere 12 antes do 11 em l (iterador não temporário):" << endl;
    ListaInt::Iterador kk = 
	l.primeiraOcorrenciaDe(11);
    l.insereAntes(kk, 12);
    cout << "l: " << l << endl;

    cout << "Remove 3 de l:" << endl;
    l.remove(k);
    cout << "l: " << l << endl;

    ListaInt ll = l;
    cout << "Cópia ll da lista l:" << endl;
    cout << "ll: " << ll << endl;

    cout << "ll sem o primeiro (a cópia):" << endl;
    ll.tiraDaFrente();
    cout << "ll: " << ll << endl;

    cout << "Copia ll para l:" << endl;
    l = ll;
    cout << "l: " << l << endl;

    cout << "Cria lll a partir de l:" << endl;
    ListaInt lll = l;

    cout << "lll: " << lll << endl;

    cout << "Concatena lll com ll:" << endl;
    lll += ll;
    cout << "lll: " << lll << endl;

    cout << "Cria llll vazia:" << endl;
    ListaInt llll;
    cout << "llll: " << llll << endl;
    
    cout << "Transfere lll para llll:" << endl;
    llll.transfereDe(lll);
    cout << "llll: " << llll << endl;
    cout << "lll: " << lll << endl;

    cout << "Poe 22 no fim de lll:" << endl;
    lll.poeAtras(22);
    cout << "lll: " << lll << endl;

    cout << "Poe 33 no fim de llll:" << endl;
    llll.poeAtras(33);
    cout << "llll: " << llll << endl;

    cout << "Concatena llll com llll:" << endl;
    llll += llll;
    cout << "llll: " << llll << endl;
    
    cout << "Transfere llll para llll:" << endl;
    llll.transfereDe(llll);
    cout << "llll: " << llll << endl;
    
    cout << "Cria lista constante lc por cópia de llll:" << endl;

    ListaInt const lc = llll;

    cout << lc << endl;
    cout << "Frente de lc: " << lc.frente() << endl;
    cout << "Tras de lc: " << lc.tras() << endl;
    cout << "Vazia? " << lc.estaVazia() << endl;

    cout << "Tira primeiro de l:" << endl;
    l.tiraDaFrente();
    cout << "l: " << l << endl;

    cout << "Tira último de l:" << endl;
    l.tiraDeTras();
    cout << "l: " << l << endl;

    cout << "Tira primeiro de l:" << endl;
    l.tiraDaFrente();
    cout << "l: " << l << endl;

    cout << "Comprimento de l: " << l.comprimento() << endl;

    cout << "Tira último de l:" << endl;
    l.tiraDeTras();
    cout << "l: " << l << endl;

    ListaInt::Iterador i = l.primeiro();
    ListaInt::Iterador j = i;
    cout << "Primeiro item da lista (de iterador): " << endl;
    cout << *j << endl;
}

int main()
{
    testeSimples();
    testeComplicado();
}

#endif // TESTE