/*
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.
*/

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

/* 

#### Declaração de um tipo de dados em C.

Na linguagem C, tipos de dados são declarados (dentre outras formas) com a palavra reservada `struct`. (Matematicamente, denota um _produto cartesiano_.) 
Ao declararmos um tipo T através da palavra reservada `struct`, nos referimos a T como `struct T`. Utilizamos esta declaração para implementar o tipo `No` 
de uma lista circular.
*/
struct _No {
    int info ;
    struct _No* prox ;
} ;

/* 
O comando `typedef` nos permite criar um "sinônimo" para um tipo. Definimos então que `struct No` será chamada simplesmente de `No`.
*/
typedef struct _No No ;

/* 
Lembre-se que um ponteiro em C é uma variável que armazena um endereço de memória. O operador `*`, quando aplicado a uma variável `p` do tipo _ponteiro_
como em `* p`, retorna o valor do endereço apontado por `p`. Já o operador `&`, quando aplicado a uma variável (ponteiro ou não), como em `& v` retorna o endereço de 
memória daquela variável. Podemos então escrever
```C
int v = 0 ;
int* p = & v ;
printf("%d", * p) ; 
```
que escreve `0` na saída padrão. A sintaxe `p->campo` acessa o atributo `campo` (como `info` no caso de um nó) do ponteiro `p`.

A função `cria_no` aloca espaço dinamicamente para uma variável do tipo `No`. A função `malloc` da biblioteca padrão de C se encarrega disso,
como a função `obter()` do tipo LED nos slides do curso. A função `malloc` recebe um número de bytes como parâmetro, `sizeof(No)` no nosso caso, 
uma vez que `sizeof` retorna o número de bytes do tipo dado. O retorno de `malloc` é um ponteiro para `void`. Por isso fazemos um _typecast_ para
o tipo apropriado, neste caso, `No*`. Após a alocação de memória, precisamos ajustar os ponteiros do nó.
*/
No* cria_no(int x, No* p_prox){
    No* p_n = (No*) malloc(sizeof(No)) ;
    assert(p_n) ;
    p_n->info = x ;
    p_n->prox = p_prox ;
    return p_n ;
}

/*
O tipo de dados `ListaCirc` é criado de maneira similar. A célular "hachurada" nos slides do curso é codificada como um nó cujo campo `info` é -1.
*/
typedef struct {
    No * ptlista ;    
} ListaCirc ;

/*
Ex.: Desenhe num papel como fica a mémoria representando uma lista vazia.
*/
ListaCirc* cria_lista(void) {
    ListaCirc* p_l = (ListaCirc*) malloc(sizeof(ListaCirc)) ;
    assert(p_l) ;
    p_l->ptlista = cria_no(-1, NULL) ;
    p_l->ptlista->prox = p_l->ptlista ;
    return p_l ;
}

/*
Seu desenho está coerente com a implementação da função `vazia()`?
*/
int vazia(ListaCirc* p_l){
    return p_l->ptlista->prox == p_l->ptlista ;
}

/*
A função `print` simplesmente percorre a lista imprimindo o conteúdo 
dos elementos da lista. 
Ex.: Fica clara a condição de parada da repetição?
*/
void print(ListaCirc* p_l){
    if (!vazia(p_l)) {
        No* p_n = p_l->ptlista->prox ;
        while (p_n != p_l->ptlista){
            printf("%d", p_n->info) ;
            p_n = p_n->prox ;
        }
    }
}

/*
A função `teste()` cria uma lista de exemplo para exercitarmos as funções criadas a acima assim como a função de busca.
*/
ListaCirc* teste() {
    ListaCirc* p_l = cria_lista() ;
    No* p_n0 = cria_no(0, NULL) ;
    No* p_n1 = cria_no(1, NULL) ;
    No* p_n2 = cria_no(2, NULL) ;
    p_l->ptlista->prox = p_n0 ;
    p_n0->prox = p_n1 ;
    p_n1->prox = p_n2 ;
    p_n2->prox = p_l->ptlista ;
    return p_l ; 
}

/*
A função `busca(x, ant, pont)` como descrita nos slides é implementada pelo código abaixo.
O único detalhe é com relação a declaração dos ponteiros `ant` e `pont`. Note que seu tipo é
```C
No** p_ant ;
```
o que declara p_ant como sendo um ponteiro para um ponteiro do tipo No. Uma outra forma de ler essa
declaração é interpretarmos `p_ant` como uma _referência_ à um ponteiro do tipo `No`. Isso é 
necessário para que os parâmetros `p_ant` e `p_pont` sejam passados por _referência_ e consequentemente
possam receber (parte) do resultado da computação de `busca(x, ant, pos)`. Como descrito nos slides, `busca(x, ant, pos)` 
diz se `x` foi encontrado na lista, ou não, com `ant` e `pont` denotando os elementos anterior e o que contém `x`
quando `x` está na lista e ptlista, em ambos, caso contrário.
*/
int busca(ListaCirc* p_l, int x, No** p_ant, No** p_pont) {
    * p_ant = p_l->ptlista ;
    * p_pont = p_l->ptlista ;
    if (! vazia(p_l)) {
       * p_ant = p_l->ptlista ;
       * p_pont = p_l->ptlista->prox ;
       while ((* p_pont)->info < x && (* p_pont) != p_l->ptlista) {
             * p_ant = * p_pont ;
             * p_pont = (* p_pont)->prox ;
       }
       if ( (* p_pont) != p_l->ptlista)
	  if( (* p_pont)->info == x) return 1 ;
       return 0 ;
    }
    return 0 ;
}

/*
Ex.1: Implemente o invariante do tipo lista circular.
*/
int inv_lista_circ(ListaCirc* p_l) {
    // Substitua a linha abaixo pelo código apropriado.
    return 1 ;
}

/* 
Ex.2: Implemente a função que insere um elemento na lista circular.
*/
int insere(ListaCirc* p_l, int x) {
    if (p_l) {
	// ...
    assert(inv_lista_circ(p_l)) ;
    } 
    return 0 ;
}

/* 
Ex.3: Implemente a função que retira um elemento na lista circular.
*/
int retira(ListaCirc* p_l, int x){
    if (p_l) {
	// ...
    } 
    return 0 ;
}

/* 
Ex.4: Implemente a função que calcula o tamanho de uma lista circular.
*/
int tamanho(ListaCirc* p_l){
    if (p_l){
	// ...
    }
    return 0 ;
}

/* 
Ex.5: Implemente a função que dada uma lista circular retorna um vetor contendo seus 
elementos, presenvando a ordem da lista.
*/
int* cria_vetor(ListaCirc* p_l){
	int tam = tamanho(p_l) ;
	int* v = (int*) malloc(sizeof(int)*tam) ; 
    assert(v) ;
	// ...
	return v ;
}

int main(void){
    ListaCirc* p_l = cria_lista() ;
    insere(p_l, 0) ;
    insere(p_l, 1) ;
    insere(p_l, 2) ;
    print(p_l) ;
    printf("\n") ; 
    No *p_ant, *p_pont ;
    int busca_res ;
    busca_res = busca(p_l, 1, &p_ant, &p_pont) ;
    printf("%d %d %d\n", busca_res, p_ant->info, 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 ;
}