#include "lista.h"
#include <stdlib.h>

struct nodo_lista* nuevo_nodo(Objeto item, struct nodo_lista *siguiente) {
	/* rutina auxuiliar, crea un nodo nuevo y asigna valores.  Verifica que el nodo haya sido creado */
	struct nodo_lista* N = malloc(sizeof(struct nodo_lista));
	if (N == NULL) {
		/* error: no se pudo crear nodo, por ahora no hace nada */
	} else {
		N->data = item;
		N->sig = siguiente;
	}
	return N;
}

struct nodo_lista* borre_nodo(struct nodo_lista **refnodo) {
	/* rutina auxiliar, borra un nodo y deja a su referencia apuntando al siguiente nodo */
	struct nodo_lista* J;
	if (*refnodo == NULL) return NULL;
	J = *refnodo;
	*refnodo = J->sig;
	free(J);
	return *refnodo;
}

Objeto extraiga_nodo(struct nodo_lista **refnodo) {
	/* rutina auxiliar, borra un nodo y deja a su referencia apuntando al siguiente nodo,
	   devuelve el objeto que había en el nodo borrado */
	Objeto item;
	if (*refnodo == NULL) return NULL;
	item = (*refnodo)->data;
	borre_nodo(refnodo);
	return item;
}

Lista nueva_lista(void) {
	return NULL;
}

int borra_lista(Lista* reflista) {
	while(*reflista!=NULL)
		borre_nodo(reflista);
}

Lista copia_lista(Lista origen) {
	struct nodo_lista *I,*J,**K;
	Lista L=NULL;
	K = &L;
	for ( I=origen; I!=NULL; I=I->sig ) {
		J = nuevo_nodo( I->data, NULL );
		if ( J==NULL ) return L; /* si no puede crear un nodo, retorna la lista creada hasta ahora */
		*K = J;
		K = &(J->sig);
	}
	return L;
}

Lista copia_sublista(Lista origen, int inicio, int final) {
	struct nodo_lista *I,*J,**K;
	Lista L = NULL;
	K = &L;
	I = origen;
	int n;
	for ( n=0; n<inicio; n++ ) {
		if ( I==NULL ) return L;
		I = I->sig;
	}
	for ( ; n<final; n++ ) {
		if ( I==NULL ) return L;
		J = nuevo_nodo( I->data, NULL );
		if ( J==NULL ) return L;
		*K = J;
		K = &(J->sig);
		I = I->sig;
	}
	return L;
}

int lista_vacia(Lista lalista) {
	return lalista == NULL;
}

int lista_contar(Lista lalista) {
	int n=0;
	struct nodo_lista *I;
	for ( I=lalista; I!=NULL; I=I->sig ) {
		n++;
	}
	return n;
}

struct nodo_lista* lista_buscar(Lista *reflista, int posicion) {
	/* rutina auxiliar: regresa un apuntador al posicion-ésimo nodo de la lista */
	int n;
	struct nodo_lista* I=*reflista;
	for ( n=0; n<posicion; n++ ) {
		if ( I==NULL ) return NULL;
		I = I->sig;
	}
	return I;
}

struct nodo_lista** lista_previo(Lista *reflista, int posicion) {
	/* rutina auxiliar: regresa una referencia al apuntador al posicion-ésimo nodo de la lista */
	int n;
	struct nodo_lista** K=reflista;
	for ( n=0; n<posicion; n++ ) {
		if ( *K==NULL ) return K;
		K = &((*K)->sig);
	}
	return K;
}

struct nodo_lista* lista_ultimo(Lista *reflista) {
	/* rutina auxiliar: regresa un apuntador al último nodo de la lista */
	struct nodo_lista* I;
	if (*reflista==NULL) return NULL;
	for(I=*reflista; I->sig!=NULL; I=I->sig);
	return I;
}

struct nodo_lista** lista_penultimo(Lista *reflista) {
	/* rutina auxiliar: regresa una referencia al apuntador al último nodo de la lista */
	struct nodo_lista** K;
	if (*reflista==NULL) return NULL;
	for ( K=reflista; (*K)->sig!=NULL; K = &((*K)->sig) );
	return K;
}

Objeto lista_item(Lista *reflista, int posicion) {
	struct nodo_lista* I=lista_buscar(reflista, posicion);
	if (I==NULL) return NULL; /* si la posicion no existe regresa NULL, si NULL es un valor válido de Objeto no se determinaria error */
	return I->data;
}

Lista lista_agregar(Lista* reflista, Objeto item, int posicion) {
	struct nodo_lista *J,**K=lista_previo(reflista,posicion);
	J = nuevo_nodo(item,*K);
	if (J!=NULL) *K=J;
	return *reflista;
}

Lista lista_agregar_inicio(Lista* reflista, Objeto item) {
	struct nodo_lista *J = nuevo_nodo(item,*reflista);
	if (J!=NULL) *reflista = J;
	return *reflista;
}

Lista lista_agregar_final(Lista* reflista, Objeto item) {
	struct nodo_lista* J=lista_ultimo(reflista);
	if (J==NULL) {
		/* lista vacia, crear primer elemento */
		*reflista = nuevo_nodo(item,*reflista);
	} else {
		J->sig = nuevo_nodo(item,J->sig);
	}
	return *reflista;
}

Lista lista_insertar(Lista* reflista, Lista origen, int posicion) {
	struct nodo_lista *I,*J,**K=lista_previo(reflista,posicion);
	for (I=origen; I!=NULL; I=I->sig) {
		J = nuevo_nodo(I->data,*K);
		if (J==NULL) return *reflista; /* si no se pudo crear nodo, regrese lista hasta ahí */
		*K = J;
		K = &(J->sig);
	}
	return *reflista;
}

Lista lista_insertar_inicio(Lista* reflista, Lista origen) {
	struct nodo_lista *I, *J, **K=reflista;
	for (I=origen; I!=NULL; I=I->sig) {
		J = nuevo_nodo(I->data,*K);
		if (J==NULL) return *reflista; /* si no se pudo crear nodo, regrese lista hasta ahí */
		*K = J;
		K = &(J->sig);
	}
	return *reflista;
}

Lista lista_insertar_final(Lista* reflista, Lista origen) {
	struct nodo_lista *I,*J;
	if (lista_vacia(*reflista))
		return lista_insertar_inicio(reflista,origen);
	J = lista_ultimo(reflista);
	for (I=origen; I!=NULL; I=I->sig) {
		J = J->sig = nuevo_nodo(I->data,J->sig);
		if (J==NULL) return *reflista; /* si no se pudo crear nodo, regrese lista hasta ahí */
	}
	return *reflista;
}

Lista lista_borrar(Lista* reflista, int posicion) {
	borre_nodo(lista_previo(reflista,posicion));
	return *reflista;
}

Lista lista_borrar_primero(Lista* reflista) {
	borre_nodo(reflista);
	return *reflista;
}

Lista lista_borrar_ultimo(Lista* reflista) {
	borre_nodo(lista_penultimo(reflista));
	return *reflista;
}

Lista lista_borrar_rango(Lista* reflista, int inicio, int final) {
	int n;
	struct nodo_lista **K=lista_previo(reflista,inicio);
	for (n=inicio;n<final && K!=NULL;n++) {
		borre_nodo(K);
	}
	return *reflista;
}

Objeto lista_extraer(Lista* reflista, int posicion) {
	return extraiga_nodo(lista_previo(reflista,posicion));
}

Objeto lista_extraer_primero(Lista* reflista) {
	return extraiga_nodo(reflista);
}

Objeto lista_extraer_ultimo(Lista* reflista) {
	return extraiga_nodo(lista_penultimo(reflista));
}

Lista lista_extraer_rango(Lista* reflista, int inicio, int final) {
	int n;
	Lista L=NULL;
	struct nodo_lista **K,**P;
	P = K = lista_previo(reflista,inicio);
	L = *K;
	for ( n=inicio; n<final && (*K)!=NULL; ++n ) {
		K = &((*K)->sig);
	}
	*P = *K; /* lista original continúa donde termina el rango extraído */
	*K = NULL; /* rango extraído termina */
	return L;
}