// tipos de dados

struct NodoLista{
  INFOLista  Elemento;
  struct NodoLista *Prox;
};

typedef struct NodoLista *PNodoLista;


/* ------------------------------------------------------- */
/* ---- protótipos/headers das funções da biblioteca ----- */
/* ------------------------------------------------------- */

// operações sobre um nodo (NodoLista)

// cria um nodo de uma lista, a partir 
//  de um elemento do tipo INFOLista
PNodoLista criarNodoLista(INFOLista);

// liberta um nodo de uma lista,
//  dado um ponteiro para esse nodo
PNodoLista libertarNodoLista(PNodoLista);

// Operações sobre uma EAD lista (PNodoLista)

// cria uma lista vazia
PNodoLista criarLista();

// liberta todos os nodos de uma dada lista
PNodoLista libertarLista(PNodoLista);

// dada uma lista, devolve 1 se está vazia,
//  e 0 se não está vazia 
int listaVazia(PNodoLista);

// mostra todos os elementos de uma dada lista,
//  do início para o fim da lista
void mostrarListaInicio(PNodoLista);
void mostrarListaInicioRec(PNodoLista);

// mostra todos os elementos de uma dada lista,
//  do fim para o início da lista
void mostrarListaFimRec(PNodoLista);

// dado um elemento (do tipo INFOLista) e uma lista,
//  devolve 1 se aquele elemento está na lista, e
//  devolve 0 se aquele elemento não está na lista
// nota: o elemento pode ter apenas o campo "chave" preenchido
int pesquisarLista(INFOLista, PNodoLista);
int pesquisarListaRec(INFOLista, PNodoLista);

// dado um elemento (do tipo INFOLista) e uma lista,
//  devolve o elemento da lista com valor no campo
//  "chave" igual ao valor daquele campo do elemento dado
// nota 1: o elemento dado pode ter apenas o campo "chave" preenchido
// nota 2: o elemento procurado existe na lista
INFOLista consultarLista(INFOLista, PNodoLista);
INFOLista consultarListaRec(INFOLista, PNodoLista);

// dado um elemento (do tipo INFOLista) e uma lista,
//  atualiza a informação do elemento na lista
// nota: o elemento dado existe na lista
void atualizarLista(INFOLista, PNodoLista);

// dado um elemento (do tipo INFOLista) e uma lista,
//  insere aquele elemento no início da lista
PNodoLista inserirListaInicio(INFOLista, PNodoLista);

// dado um elemento (do tipo INFOLista) e uma lista,
//  insere aquele elemento no fim da lista
PNodoLista inserirListaFim(INFOLista, PNodoLista);

// dado um elemento (do tipo INFOLista) e uma lista
//  ordenada por ordem crescente do campo "chave",
//  insere aquele elemento na lista mantendo-a ordenada
PNodoLista inserirListaOrdem(INFOLista, PNodoLista);

// dado um elemento (do tipo INFOLista) e uma lista,
//  remover aquele elemento da lista
// nota: o elemento dado está na lista
PNodoLista removerLista(INFOLista, PNodoLista);


/* ------------------------------------------------------- */
/* -------------- implementação das funções -------------- */
/* ------------------------------------------------------- */

// operações sobre um nodo (NodoLista)

PNodoLista criarNodoLista(INFOLista X)
{
  PNodoLista P;
  P = (PNodoLista) malloc(sizeof(struct NodoLista));
  if (P == NULL)
    return NULL;
  P->Elemento = X;
  P->Prox = NULL;
  return P;
}

PNodoLista libertarNodoLista(PNodoLista P)
{
  P->Prox = NULL;
  free(P);
  P = NULL;
  return P;
}


// Operações sobre uma EAD lista (PNodoLista)

PNodoLista criarLista()
{
  PNodoLista L;
  L = NULL;
  return L;
}

PNodoLista libertarLista(PNodoLista L)
{
  PNodoLista P;
  while (L != NULL){
    P = L;
    L = L->Prox;
    P = libertarNodoLista(P);
  }
  return  L;
}

int listaVazia(PNodoLista L)
{
  if (L == NULL)
    return 1;
  else
    return 0;
}

void mostrarListaInicio(PNodoLista L)
{
  PNodoLista P = L;
  while (P != NULL){
    mostrarElementoLista(P->Elemento);
    P = P->Prox;
  }
}

void mostrarListaInicioRec(PNodoLista L)
{
  if (L != NULL){
    mostrarElementoLista(L->Elemento);
    mostrarListaInicioRec(L->Prox);
  }
}

void mostrarListaFimRec(PNodoLista L)
{
  if (L != NULL){
    mostrarListaFimRec(L->Prox);
    mostrarElementoLista(L->Elemento);
  }
}

int pesquisarLista(INFOLista X, PNodoLista L)
{ 
  while (L != NULL && compararElementosLista(L->Elemento, X) != 0)
    L = L->Prox;
  if (L == NULL)
    return 0;
  else
    return 1;
} 

int pesquisarListaRec(INFOLista X, PNodoLista L)
{
  if (L == NULL)
    return  0;
  if (compararElementosLista(L->Elemento, X) == 0)
    return  1;
  return pesquisarListaRec(X, L->Prox);
}

// X está na lista L
INFOLista consultarLista(INFOLista X, PNodoLista L)
{
  PNodoLista P = L;
  while (P != NULL && compararElementosLista(P->Elemento, X) != 0)
    P = P->Prox;
  return P->Elemento;
}

// X está na lista L
INFOLista consultarListaRec(INFOLista X, PNodoLista L)
{
  if (compararElementosLista(L->Elemento, X) == 0)
    return L->Elemento;
  return consultarListaRec(X, L->Prox);
}

//  existe um elemento na lista com a chave X
void atualizarLista(INFOLista X, PNodoLista L)
{
  PNodoLista P = L;
  while (compararElementosLista(P->Elemento, X) != 0)
    P = P->Prox;
  P->Elemento = X;
}

PNodoLista inserirListaInicio(INFOLista X, PNodoLista L)
{
  PNodoLista P;
  P = criarNodoLista(X);
  if (P == NULL)
    return L;
  P->Prox = L;
  L = P;
  return L;
}

PNodoLista inserirListaFim(INFOLista X, PNodoLista L)
{ 
  PNodoLista Fim, P;
  P = criarNodoLista(X);
  if (P == NULL) 
    return L; 
  if (L == NULL)
    return P;
  Fim = L; 
  while (Fim->Prox != NULL)
    Fim = Fim->Prox;
  Fim->Prox = P;
  return L;
}

// a lista está ordenada por ordem crescente do campo "chave"
PNodoLista inserirListaOrdem(INFOLista X, PNodoLista L)
{
  PNodoLista Ant, P, Aux;
  P = criarNodoLista(X);
  if (P == NULL)
    return L; 
  if (L == NULL){
  	L = P;
    return L;
  }
  Ant = NULL;
  Aux = L;
  while (Aux != NULL && compararElementosLista(Aux->Elemento, X) < 0){
    Ant = Aux;
    Aux = Aux->Prox;
  }
  if (Ant == NULL){
    P->Prox = L; 
    L = P;
    return L;
  }
  P->Prox = Ant->Prox;
  Ant->Prox = P;
  return L;
}

// X está na lista
PNodoLista removerLista(INFOLista X, PNodoLista L)
{ 
  PNodoLista P, Ant; 
  if (compararElementosLista(L->Elemento, X) == 0){
    P = L;
    L = L->Prox;
    P = libertarNodoLista(P);
    return L;
  }
  Ant = L;
  while (compararElementosLista(Ant->Prox->Elemento, X) != 0)
    Ant = Ant->Prox;
  P = Ant->Prox;
  Ant->Prox = P->Prox;
  P = libertarNodoLista(P);
  return L;
}