// ------------------------------------------------------------------------------------------------
// Secao 10.2 do Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein)
// Implementacao de Listas Duplamente Ligadas com Sentinelas
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <list>
using namespace std;

    typedef struct edge {
        int v1, v2;
    } edge;

typedef struct node {
	int valor;
	struct node* proximo;
	struct node* anterior;
} node;


typedef struct lista {
        node* nulo;
} lista;


void lista_insert(lista* L, node* novo, bool ini);
void lista_delete(lista* L, node* x);
node* lista_search(lista* L, int k);
bool lista_empty(lista* L);
void lista_free(lista* L);
lista* lista_create();


int main() {
    int i;
    int N = 30;

    lista* L = lista_create();

    // pilha usando listas
    for (i=1;i<=N;i++) {
        cout<<i<<" ";
        node* novo = new node;
        novo->valor = i;
        lista_insert(L,novo,1);
    }
    cout<<endl;
    while (!lista_empty(L)) {
        node* x = L->nulo->proximo;
        cout<<x->valor<<" ";
        lista_delete(L,x);
        delete x;
    }
    cout<<endl;

    // fila usando listas
    for (i=1;i<=N;i++) {
        cout<<i<<" ";
        node* novo = new node;
        novo->valor = i;
        lista_insert(L, novo, 1);
    }
    cout<<endl;
    while (!lista_empty(L)) {
        node* x = L->nulo->anterior;
        cout<<x->valor<<" ";
        lista_delete(L,x);
        delete x;
    }
    cout<<endl;


    lista_free(L);



    int A[] = {75,23,65,42,13};
    edge B[5];
    B[0].v1 = 11; B[0].v2 = 111;
    B[1].v1 = 22; B[1].v2 = 222;
    B[2].v1 = 33; B[2].v2 = 333;
    B[3].v1 = 44; B[3].v2 = 444;
    B[4].v1 = 55; B[4].v2 = 555;

    list<edge> mylist2 (B,B+5);
    list<edge>::iterator it;
    edge e;
    e.v1=66; e.v2=666; mylist2.push_front(e);
    e.v1=77; e.v2=777; mylist2.push_back(e);

    cout << "\n\n\n Lista pronta do C++:\n";
    for (it=mylist2.begin(); it != mylist2.end(); ++it) {
        cout << ' ' << (*it).v1;
    }
    cout<<endl;
    for (it=mylist2.begin(); it != mylist2.end(); ++it) {
        cout << ' ' << (*it).v2;
    }
    cout<<endl;
    cout<<endl;
}



// ------------------------------------------------------------------------------------------------
// ---- Algoritmos de LISTAS ----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------

// INSERT (Novo na frente de x)
void lista_insert(lista* L, node* x, node* novo) {
    novo->anterior = x;
    novo->proximo = novo->anterior->proximo;
    novo->anterior->proximo = novo;
    novo->proximo->anterior = novo;
}

// INSERT (INICIO ini=1 / FIM ini=0)
void lista_insert(lista* L, node* novo, bool ini) {
    node* x = L->nulo;
    if (!ini) x = x->anterior;
    lista_insert(L, x, novo);
}

// DELETE
void lista_delete(lista* L, node* x) {
    x->anterior->proximo = x->proximo;
    x->proximo->anterior = x->anterior;
}

// SEARCH
node* lista_search(lista* L, int k) {
    node* x = L->nulo->proximo;
    while ((x!=L->nulo)&&(x->valor!=k)) {
        x = x->proximo;
    }
    return x;
}

// EMPTY
bool lista_empty(lista* L) {
    if (L==NULL) return true;
    if (L->nulo->proximo==L->nulo) return true;
    return false;
}

// CREATE (cria uma lista na memoria)
lista* lista_create() {
    lista* L = new lista;
    node* nulo = new node;
    L->nulo = nulo;

    nulo->anterior = nulo;
    nulo->proximo = nulo;
    nulo->valor = 0; // irrelevante, ja que o valor de nulo nao interessa
    return L;
}

// FREE (libera memoria da lista)
void lista_free(lista* L) {
    delete L->nulo;
    delete L;
}