/*
Lista de exercícios de Estrutura de Dados TCC00319 - Estruturas de Dados

Novembro de 2018

Christiano Braga
Instituto de Computação
Universidade Federal Fluminense

http://www.ic.uff.br/~cbraga

### Objetivo

O objetivo desta lista é exercitar o conteúdo das aulas 15 e 16 nos slides do curso na linguagem de programação C.

Requisito: Conhecimento mínimo de ponteiros e alocação dinâmica em C.

Esta lista é continuação do código em ed-lista-circ.c. Reescreva as funções que você implementou para listas circulares
agora para listas circulares duplamente encadeadas.
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct _NoDupl {
    int info ;
    struct _NoDupl* ant  ;
    struct _NoDupl* prox ;
} ;

typedef struct _NoDupl NoDupl ;

NoDupl* cria_no(int x, NoDupl* p_ant, NoDupl* p_prox){
    NoDupl* p_n = (NoDupl*) malloc(sizeof(NoDupl)) ;
    assert(p_n) ;
    p_n->info = x ;
    p_n->ant = p_ant ;
    p_n->prox = p_prox ;
    return p_n ;
}

typedef struct {
    NoDupl * ptlista ;    
} ListaDupl ;

ListaDupl* cria_lista(void) {
    ListaDupl* p_l = (ListaDupl*) malloc(sizeof(ListaDupl)) ;
    assert(p_l) ;
    p_l->ptlista = cria_no(-1, NULL, NULL) ;
    p_l->ptlista->ant = p_l->ptlista ;
    p_l->ptlista->prox = p_l->ptlista ;
    return p_l ;
}

int vazia(ListaDupl* p_l){
    return (p_l->ptlista->ant == p_l->ptlista) && (p_l->ptlista == p_l->ptlista->prox) ;
}

void print(ListaDupl* p_l){
    if (!vazia(p_l)) {
        NoDupl* p_n = p_l->ptlista->prox ;
        while (p_n != p_l->ptlista){
            printf("%d", p_n->info) ;
            p_n = p_n->prox ;
        }
    }
}

ListaDupl* teste() {
    ListaDupl* p_l = cria_lista() ;
    NoDupl* p_n0 = cria_no(0, NULL, NULL) ;
    NoDupl* p_n1 = cria_no(1, NULL, NULL) ;
    NoDupl* p_n2 = cria_no(2, NULL, NULL) ;
    p_l->ptlista->prox = p_n0 ;
    p_l->ptlista->ant = p_n2 ;
    p_n0->ant = p_l->ptlista ;
    p_n0->prox = p_n1 ;
    p_n1->ant = p_n0 ;
    p_n1->prox = p_n2 ;
    p_n2->ant = p_n1 ;
    p_n2->prox = p_l->ptlista ;
    return p_l ; 
}

int busca(ListaDupl* p_l, int x, NoDupl** p_pont) {
    NoDupl* ultimo = p_l->ptlista->ant ;
    * p_pont = ultimo ;
    if (! vazia(p_l)) {
	if (x <= ultimo->info) {
           * p_pont = p_l->ptlista->prox ;
   	   while ((* p_pont)->info < x) {
                 * p_pont = (* p_pont)->prox ;
           } 
	   if ( (* p_pont)->info == x) 
		return 1 ;
           return 0 ;
        }
    }
    return 0 ;
}

int insere(ListaDupl* p_l, int x) {
    if (p_l) {
        // ...
    assert(inv_lista-dupl(p_l)) ;
    } 
    return 0 ;
}


int retira(ListaDupl* p_l, int x){
    if (p_l) {
        // ...
    } 
    return 0 ;
}


int tamanho(ListaDupl* p_l){
    if (p_l){
        // ...
    }
    return 0 ;
}

int* cria_vetor(ListaDupl* p_l){
	int tam = tamanho(p_l) ;
	int* v = (int*) malloc(sizeof(int)*tam) ; 
    assert(v) ;
    // ...
}

int main(void){
/*    ListaDupl* p_l = teste() ;
    printf("%d", vazia(p_l)) ;
    print(p_l) ;
*/  ListaDupl* p_l = cria_lista() ;
    insere(p_l, 0) ;
    insere(p_l, 1) ;
    insere(p_l, 2) ;
    print(p_l) ;
    printf("\n") ; 
    NoDupl *p_pont ;
    int busca_res ;
    busca_res = busca(p_l, 1, &p_pont) ;
    printf("%d %d\n", busca_res, p_pont->info) ;
    insere(p_l, 3) ;
    print(p_l) ; 
    printf("\n") ;
    int tam = tamanho(p_l) ; 
    printf("%d\n", tam) ;
    int* v = cria_vetor(p_l) ;
    if (v) {
        for (int i = 0; i < tam ; i++)
            printf("%d\n", v[i]) ;
        }
    retira(p_l, 2) ;
    print(p_l) ;
    printf("\n") ;
    return 1 ;
}