/**
    Implementación de una cola
    doblemente ligada
    Fraga 5/10/2017
**/
#include <stdio.h>
#include <stdlib.h>

struct nodo {
	int x, y;
	struct nodo * psig;
	struct nodo * pant;
};

typedef struct nodo NODO;

struct cola {
	NODO *frente, *atras;
};

typedef struct cola COLA;

/**
NODO * crea_nodo( void );
void inserta_frente( COLA *pL, NODO *p );
void inserta_atras( COLA *pL, NODO *p );
void imprime_cola( COLA *pcola );
void largo( COLA *pcola );
void borra_frente( COLA *pcola );
**/

NODO * crea_nodo( )
{
	NODO *p;

	p = (NODO *)malloc( sizeof(NODO) );
	if( p == NULL )
		return NULL;

	p->psig = NULL; // Muy importante!!!
	p->pant = NULL; // Muy importante!!!

	return p;
}

void insertar_frente( COLA *pL, NODO *pnodo )
{
	if( pnodo != NULL ) {
		if( pL->frente == NULL ) {
			pL->frente = pnodo;
			pL->atras = pnodo;
		}
		else{
			pnodo->psig = pL->frente;
			pL->frente->pant = pnodo;
			pL->frente = pnodo;
		}
	}
}

void insertar_atras( COLA *pL, NODO *pnodo )
{
	if( pnodo != NULL ) {
		if( pL->frente == NULL ) {
			pL->frente = pnodo;
			pL->atras = pnodo;
		}
		else{
			pnodo->pant = pL->atras;
			pL->atras->psig = pnodo;
			pL->atras = pnodo;
		}
	}
}

/**
  Inserta el nodo pnodo después del nodo p.
  p debe ser un nodo que exista (no puede ser NULL)
**/
void insertar_despues( COLA *pcola, NODO *p, NODO *pnodo )
{
	if( p != pcola->atras  ) {
		pnodo->psig = p->psig;
		p->psig->pant = pnodo;
		pnodo->pant = p;
		p->psig = pnodo;
	}
	else{
		insertar_atras( pcola, pnodo );
	}
}

/**
  Inserta el nodo pnodo antes del nodo p.
  p debe ser un nodo que exista (no puede ser NULL)
**/
void insertar_antes( COLA *pcola, NODO *p, NODO *pnodo )
{
	if( p != pcola->frente  ) {
		pnodo->psig = p;
		pnodo->pant = p->pant;
		p->pant = pnodo;
		pnodo->pant->psig = pnodo;
	}
	else{
		insertar_frente( pcola, pnodo );
	}
}


NODO * borra_frente( COLA *pcola )
{
	NODO *p;

	if( pcola->frente == NULL ) 
		return NULL;
	if( pcola->frente == pcola->atras ){
		p = pcola->frente;
		pcola->frente = NULL;
		pcola->atras = NULL;
	}
	else {
		p = pcola->frente;
		pcola->frente = p->psig;
		p->psig = NULL;
		pcola->frente->pant = NULL;
	}
	return p;
}

NODO * borra_atras( COLA *pcola )
{
	NODO *p;

	if( pcola->atras == NULL ) 
		return NULL;
	if( pcola->frente == pcola->atras ){
		p = pcola->atras;
		pcola->atras = NULL;
		pcola->frente = NULL;
	}
	else {
		p = pcola->atras;
		pcola->atras = p->pant;
		p->pant = NULL;
		pcola->atras->psig = NULL;
	}
	return p;
}

/** Buscamos el elemente que sea igual a p
   Como no modificamos la cola, pasamos una copia
   del frente de ella
   Buscamos desde el frente de la cola
**/
NODO * busca_nodo( COLA *pcola, NODO * p )
{
	NODO *L;

	L = pcola->frente;

	while( L != NULL ) {
		if( L->x == p->x && L->y == p->y )
			return L;
		L = L->psig;
	}
	return NULL;
}

void imprime_cola( COLA *pcola )
{
	NODO *p;
	
	p = pcola -> frente;

	while( p != NULL ) {
		printf("%d %d\n", p->x, p->y );
		p = p->psig;
	}
}

/**
   Nos regresa cuantos elementos hay en la cola
**/
int largo( COLA *pcola )
{
	NODO * p;
	int n=0;

	p = pcola->frente;
	while( p != NULL ){
		n++;
		p = p->psig;
	}
	return n;
}

int main( )
{
	COLA colaDL1;
	NODO *pdato;
	NODO b;

	// Esto es muy importante!
	colaDL1.frente = NULL;
	colaDL1.atras = NULL;

	pdato = crea_nodo( );
	if( pdato != NULL ) {
		pdato->x = 1;
		pdato->y = 1;
	}
	insertar_frente( &colaDL1, pdato );

	pdato = crea_nodo( );
	if( pdato != NULL ) {
		pdato->x = 3;
		pdato->y = 4;
	}
	insertar_atras( &colaDL1, pdato );

	pdato = crea_nodo( );
	if( pdato != NULL ) {
		pdato->x = 4;
		pdato->y = 8;
	}
	insertar_despues( &colaDL1, colaDL1.frente->psig, pdato );

	imprime_cola( &colaDL1 );

	printf("Hay %d nodos\n", largo( &colaDL1 ) );

	printf( "Prueba de la función \"inserta_antes\"\n" );
	pdato = crea_nodo( );
	if( pdato != NULL ) {
		pdato->x = 10;
		pdato->y = 11;
	}
	insertar_antes( &colaDL1, colaDL1.frente->psig->psig, pdato );
	pdato = crea_nodo( );
	if( pdato != NULL ) {
		pdato->x = 15;
		pdato->y = 16;
	}
	insertar_antes( &colaDL1, colaDL1.frente, pdato );

	printf("Hay %d nodos\n", largo( &colaDL1 ) );

	// Recorremos la cola desde atrás
	pdato = colaDL1.atras;
	while( pdato != NULL ) {
		printf("%d %d\n", pdato->x, pdato->y );
		pdato = pdato -> pant;
	}

	printf( "Prueba de búsqueda\n" );
	b.x = 4; 
	b.y = 8;
	pdato = busca_nodo( &colaDL1, &b );
	if( pdato != NULL ) {
		printf("El dato existe! : %d %d\n", pdato->x, pdato->y );
	}

#ifdef TEST1
	// Quitamos los nodos del frente y
	// los borramos
	while( colaDL1.frente != NULL ) {
		pdato = borra_frente( &colaDL1 );
		printf("%d %d\n", pdato->x, pdato->y );
		// Aquí se libera la memoria
		free( pdato );
	}
#else
	// Quitamos los nodos desde atrás y
	// los borramos
	while( colaDL1.atras != NULL ) {
		pdato = borra_atras( &colaDL1 );
		printf("%d %d\n", pdato->x, pdato->y );
		// Aquí se libera la memoria
		free( pdato );
	}
#endif

	return 0;
}