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

   PROG-LISTDUP
   ============

   Usa 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

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

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

#include "listdup.c"

/***

 => 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 insere_ordenando_ld    (Nodo_LD **LD, Tipo_Dado Dado);
int pesquisa_ld   	       (Nodo_LD **LD, Tipo_Dado Dado);
int remove_nodo_ld         (Nodo_LD **LD, Tipo_Dado *Dado);
int quantidade_ld          (Nodo_LD **LD);
void exibe_ld              (Nodo_LD **LD);
int percorre_lista         (Nodo_LD **LD, Tipo_Dado *Dado);
void apaga_ld              (Nodo_LD **LD);

***/

/*****

  Programa Principal

*****/

main()
{
  Nodo_LD *L1,*L2,*LFim;
  Tipo_Dado Dado;
  int acabou;
  
  /* Lista 1 */
  inicializa_ld(&L1);
  insere_fim_ld(&L1,5);
  insere_fim_ld(&L1,9);
  insere_fim_ld(&L1,15);
  insere_fim_ld(&L1,18);
  insere_fim_ld(&L1,32);        
  insere_fim_ld(&L1,40);
  insere_fim_ld(&L1,65);
            
  posiciona_inicio_ld(&L1);
  exibe_ld(&L1);

  system("pause");
 
  /* Lista 2 */
  inicializa_ld(&L2);
  insere_fim_ld(&L2,3);
  insere_fim_ld(&L2,4);
  insere_fim_ld(&L2,8);
  insere_fim_ld(&L2,10);
  insere_fim_ld(&L2,11);        
  insere_fim_ld(&L2,32);
  insere_fim_ld(&L2,35);
  insere_fim_ld(&L2,70);
  
  posiciona_inicio_ld(&L2);
  exibe_ld(&L2);
  
  system("pause");
  
  /* Merge */
 
  posiciona_inicio_ld(&L1);
  posiciona_inicio_ld(&L2);
  inicializa_ld(&LFim);
  
  acabou=0;
  while (!acabou)
  {
     if ((L1 != NULL) && (L2 != NULL))
     {
        if (L1->Dado <= L2->Dado)
        {
           insere_fim_ld(&LFim,L1->Dado);
           L1=L1->Proximo;
        }   
        else
        {
           insere_fim_ld(&LFim,L2->Dado);
           L2=L2->Proximo;
        }
     }
     else
        acabou=1;
     
  }
  /* Acabou o loop */
  
  if (L1 == NULL)
  {
     while (L2 != NULL)
     {
         insere_fim_ld(&LFim,L2->Dado);
         L2=L2->Proximo;
     }
  }
  
  if (L2 == NULL)
  {
     while (L1 != NULL)
     {
         insere_fim_ld(&LFim,L1->Dado);
         L1=L1->Proximo;
     }
  }

  posiciona_inicio_ld(&LFim);
  exibe_ld(&LFim);
  
  printf ("\n\n");
  system("pause");
  
}