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

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



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