// data types

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

typedef struct NodoLista *PNodoLista;


/* ------------------------------------------------------- */
/* --------------- library function headers -------------- */
/* ------------------------------------------------------- */

// operations on a node (NodoLista)

// to create a node of a list,
//  from an element of type INFOLista
PNodoLista criarNodoLista(INFOLista);

// free a guiven node
PNodoLista libertarNodoLista(PNodoLista);


// Operations on an ADT list (PNodoLista)

// to create an (empty) list
PNodoLista criarLista();

// free all nodes from a given list
PNodoLista libertarLista(PNodoLista);

// given a list, returns 1 if it is empty,
//  and 0 if it is not empty
int listaVazia(PNodoLista);

// shows all elements of a given list,
//  from the beginning to the end of the list
void mostrarListaInicio(PNodoLista);
void mostrarListaInicioRec(PNodoLista);

// shows all elements of a given list,
//  from the end of the list to the beginning
void mostrarListaFimRec(PNodoLista);

// given an element (of type INFOLista) and a list,
//  returns 1 if that element is in the list, and 
//  returns 0 if that element is not in the list
int pesquisarLista(INFOLista, PNodoLista);
int pesquisarListaRec(INFOLista, PNodoLista);

// given an element (of type INFOLista) and a list, returns
//  the element of the list with a value in the "key" field
//  equal to the value of that field of the given element
// note: that element exists in the list
INFOLista consultarLista(INFOLista, PNodoLista);
INFOLista consultarListaRec(INFOLista, PNodoLista);

// given an element (of type INFOLista) and a list,
//  update the element information in the list
// note: that element exists in the list
void atualizarLista(INFOLista, PNodoLista);

// given an element (of type INFOLista) and a list,
//  inserts that element at the beginning of the list
PNodoLista inserirListaInicio(INFOLista, PNodoLista);

// given an element (of type INFOLista) and a list,
//  inserts that element at the end of the list
PNodoLista inserirListaFim(INFOLista, PNodoLista);

// given an element (of type INFOLista) and a list
//  ordered in ascending order of the "key" field, 
//  inserts this element into the list keeping it ordered
PNodoLista inserirListaOrdem(INFOLista, PNodoLista);

// given an element (of type INFOLista) and a list,
//  remove that element from the list
// note: that element exists in the list
PNodoLista removerLista(INFOLista, PNodoLista);


/* ------------------------------------------------------- */
/* ------------- implementation of functions ------------- */
/* ------------------------------------------------------- */

// operations on a node (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;
}


// Operations on an ADT list (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 exists in the list
INFOLista consultarLista(INFOLista X, PNodoLista L)
{
  PNodoLista P = L;
  while (P != NULL && compararElementosLista(P->Elemento, X) != 0)
    P = P->Prox;
  return P->Elemento;
}

// X exists in the list
INFOLista consultarListaRec(INFOLista X, PNodoLista L)
{
  if (compararElementosLista(L->Elemento, X) == 0)
    return L->Elemento;
  return consultarListaRec(X, L->Prox);
}

// X exists in the list
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;
}

// the list is sorted in ascending order of the "key" field
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 exists in the list
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;
}