/**
  Funciones para crear una lista de 
  prioridad. Cada nodo de inserta de
  acuerdo a su prioridad. Si tienen 
  igual prioridad, se inserta antes

  Fraga 10/10/2017
**/
#include <stdio.h>
#include <stdlib.h>

struct punto2d {
	int x, y;
	int prioridad;
	struct punto2d * psig;
};

typedef struct punto2d NODO;

/**
NODO * crea_elemento( );
void insertaDespues( NODO *paqui, NODO *pnodo );
void insertaAntes( NODO **pL, NODO *paqui, NODO *pnodo );
void borra_lista( NODO **pL );
void imprime_lista( NODO *L );
int calcula_largo( NODO *L );
**/

NODO * crea_elemento( )
{
	NODO *p;

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

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

	return p;
}

/** Se le puede pasar una copia de la lista
  porque no modificamos la lista al imprimir
**/
void imprime_lista( NODO *p )
{
	while( p != NULL ) {
		printf("%d %d\n", p->x, p->y );
		p = p->psig;
	}
}

void borra_lista( NODO **pL )
{
	NODO *p;

	p = *pL;
	while( p != NULL ) {
		// Error: *pL = *pL->psig;
		*pL = (*pL)->psig;
		free( p );
		p = *pL;
	}
}


int calcula_largo( NODO *p )
{
	int n=0;

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

	return n;
}


NODO * borra( NODO **pL )
{
	NODO *p;

	if ( *pL != NULL ) {
		p = *pL;
		*pL = (*pL)->psig;

		p->psig = NULL;
		return p;
	}
	else
		return NULL;
}

void inserta( NODO **pL, NODO *p )
{
	NODO *pb1=NULL, *pb2;

	// Lista de prioridad vacía: 
	if ( *pL == NULL )
		*pL = p;
	else {
		pb2 = *pL;

		while( p->prioridad < pb2->prioridad )
		{
			pb1 = pb2;
			pb2 = pb2->psig;
			if ( pb2 == NULL ) 
				break;
		}

		// Se inserta al inicio
		if ( pb1 == NULL ) {
			p->psig = *pL;
			*pL = p;
		}
		// Se inserta al final
		else if ( pb2 == NULL ) {
			// Se inserta el nodo 'p' al final
			pb1->psig = p;
		}
		else {
			// insertaDespues( pb1, p );
			pb1->psig = p;
			p->psig = pb2; 
		}
	} 
}

int main( )
{
	NODO *L = NULL;
	NODO *pnodo, *paux;

	pnodo = crea_elemento( );
	pnodo->x = 1;  
	pnodo->y = 1;  
	pnodo->prioridad = 5;
	inserta( &L, pnodo );	

	pnodo = crea_elemento( );
	pnodo->x = 1;  
	pnodo->y = 4;  
	pnodo->prioridad = 10;
	inserta( &L, pnodo );	

	pnodo = crea_elemento( );
	pnodo->x = 2;  
	pnodo->y = 3;  
	pnodo->prioridad = 1;
	inserta( &L, pnodo );	

	imprime_lista( L );
	printf("\n");


	pnodo = L;
	while( pnodo != NULL ) {
		printf("%d %d %d\n", pnodo->x, pnodo->y, pnodo->prioridad );
		paux = pnodo;
		pnodo = pnodo->psig;
		free( paux );
	}

	return 0;
}