/*-------------------------------------------------------------------*/
/* "DISENO Y MANEJO DE ESTRUCTURAS DE DATOS EN C" - V. 1.0           */
/* J. Villalobos, A. Quintero - Universidad de los Andes             */
/*-------------------------------------------------------------------*/
/* TAD Lista de parejas [sucesor, costo ] adaptada para grafos       */
/*-------------------------------------------------------------------*/

#include <stdio.h>
#include <alloc.h>

typedef struct
{	int vertice;		/* Vertice sucesor */
	int costo;		/* Costo del arco */
} TipoLP;

#include "Listap.h"

/*-------------------------------------------------------------------*/
/* Constructora: Crea una lista vacia. La ventana es indefinida      */
/* Complejidad:    O(1)                                              */

ListaP inicListaP(void)
{   ListaP resp;
    resp=(ListaP)malloc(sizeof(TListaP));
    resp->primero=resp->ultimo=resp->ventana=NULL;
    resp->longitud=0;
    return resp;
}

/*-------------------------------------------------------------------*/
/* Modificadora: Coloca el nuevo elemento en la posicion siguiente a */
/*               la ventana. Si la lista es vacia lo coloca de       */
/*               primero en la lista                                 */
/* Complejidad:  O(1)                                                */

void anxListaP(ListaP lst, TipoLP elem)
{   pListaNodoP nuevo=(pListaNodoP)malloc(sizeof(struct ListaNodoP));
    nuevo->info=elem;
    nuevo->ant=nuevo->sig=NULL;
    if (lst->longitud==0)
       lst->primero=lst->ultimo=nuevo;
     else if (lst->ventana==lst->ultimo)
     { lst->ventana->sig=lst->ultimo=nuevo;
       nuevo->ant=lst->ventana;
     }
     else
     { nuevo->ant=lst->ventana;
       nuevo->sig=lst->ventana->sig;
       lst->ventana->sig->ant=nuevo;
       lst->ventana->sig=nuevo;
     }
    lst->ventana=nuevo;
    lst->longitud++;
}

/*-------------------------------------------------------------------*/
/* Modificadora: Coloca el nuevo elemento en la posicion anterior a  */
/*               la ventana. Si la lista es vacia lo coloca de       */
/*               primero en la lista                                 */
/* Complejidad:  O(1)                                                */

void insListaP(ListaP lst, TipoLP elem)
{   pListaNodoP nuevo=(pListaNodoP)malloc(sizeof(struct ListaNodoP));
    nuevo->info=elem;
    nuevo->ant=nuevo->sig=NULL;
    if (lst->longitud==0)
       lst->primero=lst->ultimo=nuevo;
     else if (lst->ventana==lst->primero)
     { lst->primero=lst->ventana->ant=nuevo;
       nuevo->sig=lst->ventana;
     }
     else
     { nuevo->sig=lst->ventana;
       nuevo->ant=lst->ventana->ant;
       lst->ventana->ant->sig=nuevo;
       lst->ventana->ant=nuevo;
     }
     lst->ventana=nuevo;
     lst->longitud++;
}

/*-------------------------------------------------------------------*/
/* Modificadora: Elimina el elemento que se encuentra en la ventana  */
/*               de la lista. La ventana queda sobre el siguiente    */
/*               elemento. Si era el ultimo, la ventana queda        */
/*               indefinida.                                         */
/* Complejidad:  O(1)                                                */

void elimListaP(ListaP lst)
{   pListaNodoP aux;
    if (lst->ventana==lst->primero)
    {  if (lst->ultimo==lst->primero)
	  lst->ultimo=NULL;
       lst->primero=lst->primero->sig;
       free(lst->ventana);
       lst->ventana=lst->primero;
     }
      else
      { if (lst->ultimo==lst->ventana)
	   lst->ultimo=lst->ultimo->ant;
	lst->ventana->ant->sig=lst->ventana->sig;
	if ( lst->ventana->sig!=NULL)
	   lst->ventana->sig->ant=lst->ventana->ant;
	aux=lst->ventana;
	lst->ventana=lst->ventana->sig;
	free(aux);
      }
      lst->longitud--;
}

/*-------------------------------------------------------------------*/
/* Modificadora: Mueve una posicion a la derecha la ventana. Si esta */
/*               sobre el ultimo elemento la ventana queda           */
/*               indefinida                                          */
/* Complejidad:  O(1)                                                */

void sigListaP(ListaP lst)
{   lst->ventana=lst->ventana->sig;
}

/*-------------------------------------------------------------------*/
/* Modificadora: Coloca la ventana sobre el primer elemento          */
/* Complejidad:  O(1)                                                */

void primListaP(ListaP lst)
{   lst->ventana=lst->primero;
}

/*-------------------------------------------------------------------*/
/* Modificadora: Coloca la ventana sobre el ultimo elemento          */
/* Complejidad:  O(1)                                                */

void ultListaP(ListaP lst)
{   lst->ventana=lst->ultimo;
}

/*-------------------------------------------------------------------*/
/* Modificadora: Coloca la ventana sobre una posicion dada           */
/* Complejidad:  O(N)                                                */

void posListaP(ListaP lst, int pos)
{   int i;
    for ( lst->ventana=lst->primero,i=1; i<pos; i++)
	lst->ventana=lst->ventana->sig;
}

/*-------------------------------------------------------------------*/
/* Modificadora: Coloca la ventana en vent                           */
/* Complejidad:	O(1)                                                 */

void situarListaP(ListaP lst, VentanaP vent)
{ lst->ventana=vent;
}

/*-------------------------------------------------------------------*/
/* Analizadora: Retorna el elemento que se encuentra en la ventana   */
/* Complejidad: O(1)                                                 */

TipoLP infoListaP(ListaP lst)
{   return lst->ventana->info;
}

/*-------------------------------------------------------------------*/
/* Analizadora: Retorna la longitud de la lista                      */
/* Complejidad: O(1)                                                 */

int longListaP(ListaP lst)
{   return lst->longitud;
}

/*-------------------------------------------------------------------*/
/* Analizadora: Indica si la ventana se encuentra indefinida         */
/* Complejidad: O(1)                                                 */

int finListaP(ListaP lst)
{   return lst->ventana==NULL;
}

/*-------------------------------------------------------------------*/
/* Analizadora: Retorna la ventana                                   */
/* Complejidad:	O(1)                                                 */

VentanaP ventanaListaP(ListaP lst)
{ return lst->ventana;
}

/*-------------------------------------------------------------------*/
/* Destructora: Retorna la memoria ocupada por una lista             */
/* Complejidad:	O(N)                                                 */

void destruirListaP(ListaP lst)
{ pListaNodoP p,q;
  for(p=lst->primero;p!=NULL;)
  { q=p;
    p=p->sig;
    free(q);
  }
 free(lst);
}

/*-------------------------------------------------------------------*/
/* Depuracion: Imprime el contenido de una lista, mostrando su       */
/*             longitud y la posicion de la ventana                  */
/* Complejidad:	O(N)                                                 */

void impListaP(ListaP lst)
{   pListaNodoP p=lst->primero;

    /* Imprime la longitud */
    printf("< ",lst->longitud);

    /* Recorre la lista imprimiendo sus elementos */
    while(p!=NULL)
    { /* Indica la posicion de la ventana */
	printf("(%d-%d) ",p->info.vertice, p->info.costo);
	/* Indica la posicion de la ventana */
	p=p->sig;
    }

    printf(">");
    /* Indica si la ventana se encuentra indefinida */
    printf("\n");
}
