/********************************************************

   LISTDUP
   ========

   Rotinas de manipulacao de LISTAS ENCADEADAS DUPLAS:
   - Estruturas de dados com alocacao dinamica
   - Insere no inicio ou no final da lista
   - Insere de modo ordenado (antes ou depois de um nodo qualquer)
   - Remove do inicio ou do final da lista

   Aplicacao tipica:
   - Lista de dinamica de elementos de tamanho variavel

   Por: Fernando Osorio
   Data da ultima atualizacao: Out. 2013

*********************************************************/

/* Incluir: stdio.h */

#define FALSO      0
#define VERDADEIRO 1

#define OK         1
#define ERRO       0

typedef int Tipo_Dado;

typedef struct bloco_ld {
							Tipo_Dado Dado;
							char   Removido;
							struct bloco_ld  *Proximo, *Anterior;
						}  Nodo_LD;


/*************************************************************** 

 => Rotinas de Manipulacao de LISTAS DUPLAMENTE ENCADEADAS
    Alocacao dinamica

***
     
void inicializa_ld         (Nodo_LD **LD);
void posiciona_inicio_ld   (Nodo_LD **LD);
void posiciona_fim_ld      (Nodo_LD **LD);
int insere_antes_ld        (Nodo_LD **LD, Tipo_Dado Dado);
int insere_depois_ld       (Nodo_LD **LD, Tipo_Dado Dado);
int insere_inicio_ld       (Nodo_LD **LD, Tipo_Dado Dado);
int insere_fim_ld	   	   (Nodo_LD **LD, Tipo_Dado Dado);
int remove_nodo_ld         (Nodo_LD **LD, Tipo_Dado *Dado);
void exibe_ld              (Nodo_LD **LD);
int pesquisa_ld   	       (Nodo_LD **LD, Tipo_Dado Dado);
int quantidade_ld          (Nodo_LD **LD);

int insere_ordenando_ld    (Nodo_LD **LD, Tipo_Dado Dado);     
int percorre_lista         (Nodo_LD **LD, Tipo_Dado *Dado);
void apaga_ld              (Nodo_LD **LD);

*****************************************************************/

void inicializa_ld (LD)
Nodo_LD **LD;
{
  *LD = NULL;
}


void posiciona_inicio_ld (LD)
Nodo_LD **LD;
{
   if (*LD != NULL)
   {
      while ((*LD) -> Anterior != NULL)
            *LD = (*LD) -> Anterior;
   }
}


void posiciona_fim_ld (LD)
Nodo_LD **LD;
{
   if (*LD != NULL)
   {
      while ((*LD) -> Proximo != NULL)
            *LD = (*LD) -> Proximo;
   }
}


int insere_antes_ld (LD, Dado)
Nodo_LD   **LD;
Tipo_Dado Dado;
{
   Nodo_LD *novo, *aux;

   novo=(Nodo_LD *)calloc(1, sizeof(Nodo_LD));
   if (novo == NULL)
      return (ERRO);

   novo -> Dado = Dado;
   novo -> Removido = FALSO;

   if (*LD == NULL)
   {
       *LD = novo;
       novo -> Anterior = NULL;
       novo -> Proximo = NULL;
   }
   else
   {
      aux=(*LD)->Anterior;
      (*LD)->Anterior=novo;
      novo->Proximo=(*LD);
      novo->Anterior=aux;
      if (aux != NULL)
  	     aux->Proximo=novo;
   }
   return(OK);
}

int insere_depois_ld (LD, Dado)
Nodo_LD   **LD;
Tipo_Dado Dado;
{
   Nodo_LD *novo, *aux;

   novo=(Nodo_LD *)calloc(1, sizeof(Nodo_LD));
   if (novo == NULL)
      return (ERRO);

   novo -> Dado = Dado;
   novo -> Removido = FALSO;

   if (*LD == NULL)
   {
       *LD = novo;
       novo -> Anterior = NULL;
       novo -> Proximo = NULL;
   }
   else
   {
      aux = (*LD)->Proximo;
	  (*LD)->Proximo=novo;
      novo ->Anterior=(*LD);
	  novo->Proximo=aux;
      if (aux != NULL)
  	     aux->Anterior=novo;  
   }
   return(OK);
}

   
int insere_inicio_ld (LD, Dado)
Nodo_LD   **LD;
Tipo_Dado Dado;
{
   posiciona_inicio_ld(LD);
   return(insere_antes_ld(LD, Dado));
}


int insere_fim_ld (LD, Dado)
Nodo_LD   **LD;
Tipo_Dado Dado;
{
   posiciona_fim_ld(LD);
   return(insere_depois_ld(LD, Dado));
}


int remove_nodo_ld (LD, Dado)
Nodo_LD **LD; 
Tipo_Dado *Dado;
{
   *Dado = (*LD)->Dado;
   (*LD)->Removido=VERDADEIRO;
}


void exibe_ld (LD)
Nodo_LD **LD;
{
   Nodo_LD *aux;

   printf ("Lista Dupla encadeada:\n");
   aux = *LD;
   while ( aux != NULL )
   {
      if (!(aux->Removido))
         printf ("Dado: %d\n",aux->Dado);
      aux = aux->Proximo;
   }
   printf ("\n");
}


int pesquisa_ld (LD, Dado)
Nodo_LD **LD; 
Tipo_Dado Dado;
{
   Nodo_LD *aux;

   aux = *LD;
   while ( aux != NULL )
   {
      if (!(aux->Removido))
         if (aux->Dado == Dado) 
		 {
		    *LD = aux;
		    return (VERDADEIRO);  // Achou!
		 }
      aux = aux->Proximo;
   }
   return (FALSO);  // Nao Achou!
}


int quantidade_ld (LD)
Nodo_LD **LD; 
{
   Nodo_LD *aux;
   int qtde=0;

   aux = *LD;
   while ( aux != NULL )
   {
      if (!(aux->Removido))
         qtde++;
      aux = aux->Proximo;
   }
   return (qtde); 
}


/*************************
  Fim: rotinas listdup.c
*************************/