/*
	Gestione di una lista doppiamente linkata:
	add <intero>	aggiunge un nodo subito dopo il nodo corrente
	del		elimina il nodo corrente e setta il nodo corrente al nodo precedente (successivo se non esiste)
	print		stampa la lista con un asterisco a fianco del nodo corrente
	next		seleziona il prossimo nodo
	prev		seleziona il nodo precedente
	sort		ordina la lista con merge-sort
*/

#include <stdio.h>

/* definizione della struttura del nodo */
typedef
	struct nodo {
		int valore;
		struct nodo * next;
		struct nodo * prev;
	} Nodo ;

#define MAXLINE 1000
#define TRUE 1
#define FALSE 0

void add(Nodo ** lista, Nodo ** corrente, int valore);
void del(Nodo ** lista, Nodo ** corrente);
void prev(Nodo ** corrente);
void next(Nodo ** corrente);
void print(Nodo * lista, Nodo * corrente);
void sort(Nodo ** lista);
Nodo * merge(Nodo * L1, Nodo * L2); 
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari);
void push(Nodo * elemento, Nodo ** lista);

int main(int argc, char * argv[]) {
	char	riga[MAXLINE] = { 0 };
	int	 val	 = 0;
	Nodo * lista	 = NULL;
	Nodo * corrente = NULL;

	scanf("%[^\n]",riga);
	while (0 != strcmp(riga,"fine")) {
		if (1 == sscanf(riga,"add%*[ ]%d",&val))
			add(&lista, &corrente, val);
		else 
		if (0 == strcmp(riga,"del")) {
			if (lista != NULL)
				del(&lista, &corrente);
			else 
				printf("vuota\n");
		} else 
		if (0 == strcmp(riga,"next"))
			next(&corrente);
		else 
		if (0 == strcmp(riga,"prev"))
			prev(&corrente);
		else 
		if (0 == strcmp(riga,"sort")) {
			if (lista != NULL)
				sort(&lista);
			else 
				printf("vuota\n");
		} else 
		if (0 == strcmp(riga,"print")) {
			if (lista != NULL)
				print(lista, corrente);
			else 
				printf("vuota\n");
		};
		scanf("\n%[^\n]",riga);
	}
}

/*
	Aggiungo un nuovo nodo alla lista
*/
void add(Nodo ** lista, Nodo ** corrente, int valore)
{
	/* alloco un nuovo nodo */
	Nodo * nuovo = (Nodo*)malloc(sizeof(Nodo));
	nuovo->valore = valore;
	nuovo->next = NULL;
	nuovo->prev = NULL;

	/* caso speciale del primo nodo */
	if (*lista == NULL) {
		*lista = nuovo;
		*corrente = nuovo;
		return;
	}

	/* taglia e cuci della lista */
	if (*corrente != NULL) {
		nuovo->next = (*corrente)->next;
		nuovo->prev = *corrente;
		(*corrente)->next = nuovo;
		if (nuovo->next != NULL)
			nuovo->next->prev = nuovo;
	}

	/* aggiorno il cursore  */
	*corrente = nuovo;
}

/*
	Elimino il nodo corrente
*/
void del(Nodo ** lista, Nodo ** corrente)
{	
	Nodo * dacancellare = *corrente;
	if (*corrente == NULL) 
		return;

	/* il prossimo nodo (se c'e') diventa il nodo corrente */
	if ((*corrente)->next != NULL)
		*corrente = (*corrente)->next;
	else
		*corrente = (*corrente)->prev;

	/* taglia e cuci della lista */
	if (dacancellare->prev != NULL)
		dacancellare->prev->next = dacancellare->next;
	if (dacancellare->next != NULL)
		dacancellare->next->prev = dacancellare->prev;
	if (*lista == dacancellare)
		*lista = dacancellare->next;

	/* libero la memoria */
	free(dacancellare);
}

/*
	Mi sposto sul nodo precedente
*/
void prev(Nodo ** corrente)
{
	if (*corrente == NULL || (*corrente)->prev == NULL)
		return;
	else
		*corrente = (*corrente)->prev;
}

/*
	Mi sposto sul nodo successivo
*/
void next(Nodo ** corrente)
{
	if (*corrente == NULL || (*corrente)->next == NULL)
		return;
	else
		*corrente = (*corrente)->next;
}

/*
	Stampa della lista
*/
void print(Nodo * lista, Nodo * corrente)
{
	if (lista == NULL) return;
	if (lista == corrente)
		printf("%d *\n",lista->valore);
	else	
		printf("%d\n",lista->valore);
	print(lista->next,corrente);
}

/*
	Mergesort della lista
*/
void sort(Nodo ** lista)
{
	Nodo * pari = NULL;
	Nodo * dispari = NULL;

	/* caso base, 0 o 1 elementi */
	if (*lista == NULL) return;
	if ((*lista)->next == NULL) return;
	
	/* divido la lista in due gruppi di pari dimensioni */
	split(*lista,&pari,&dispari);

	/* ordino le due parti */
	sort(&pari);
	sort(&dispari);

	/* ora che sono ordinate le posso fondere */
	*lista = merge(pari,dispari);
}

/*
	merge distruttivo di due liste doppiamente linkate e ordinate
*/
Nodo * merge(Nodo * L1, Nodo * L2) 
{	
	Nodo * minore = NULL;
	/* casi base */
	if (L1 == NULL) return L2;
	if (L2 == NULL) return L1;
	/* trovo il minore */
	if (L1->valore < L2->valore) {
		minore = L1;
		minore->next = merge(minore->next,L2);
	} else {
		minore = L2;
		minore->next = merge(L1,minore->next);
	}
	/* aggiusto il legame inverso */
	if (minore->next != NULL)
		minore->next->prev = minore;
	/* torno il primo nodo */
	return minore;
}

/*
	divido una lista in due (elementi in posizione pari/dispari)
*/
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari)
{
	/* caso base: nessun elemento */
	if (lista == NULL) {
		*pari = NULL;
		*dispari = NULL;
		return;
	}
	/* se ci sono almeno 2 elementi ricorro saltando i primi due 
		ed ottengo il resto della lista separato in pari e dispari */
	if (lista->next != NULL)
		split(lista->next->next,pari,dispari);

	/* aggiungo i due elementi iniziali a pari e dispari */
	/* prima il secondo (se c'e') */
	if (lista->next != NULL) 
		push(lista->next,dispari);
	/* poi il primo */
	push(lista,pari);
}

void push(Nodo * elemento, Nodo ** lista) 
{
	if (*lista != NULL)
		(*lista)->prev = elemento;
	elemento->next = *lista;
	*lista = elemento;
}