/*
 * File:   main.c
 * Author: Victor
 *
 * Created on 22 de octubre de 2014, 08:06 PM
 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/*Listas*/
typedef struct nodo {
    int elem;
    struct nodo *sig;
} TNodo;

typedef struct lista {
    int nElem;
    TNodo *inicio;
    TNodo *final;
} TLista;

typedef struct nodo_char {
    char elem;
    struct nodo_char *sig;
} TNodoChar;

typedef struct lista_char {
    int nElem;
    TNodoChar *inicio;
    TNodoChar *final;
} TListaChar;

/*Pila*/
typedef struct {
    TNodo *top;
} TPila;

/*Cola*/
typedef struct {
    TNodo *inicio;
    TNodo *final;
} TCola;

/*Deque*/
typedef struct deque {
    int elem;
    struct deque *sig;
    struct deque *ant;
} TNodoDeque;

typedef struct {
    int nElem;
    TNodoDeque *inicio;
    TNodoDeque *final;
} TDeque;

/*Listas*/
void crear_lista(TLista *L) {
    L->inicio = NULL;
    L->final = NULL;
    L->nElem = 0;
}

void finalizar_lista(TLista *L) {
    TNodo *ptrElim = L->inicio;
    while (ptrElim) {
        L->inicio = ptrElim->sig;
        free(ptrElim);
        ptrElim = L->inicio;
    }
}

int es_lista_vacia(TLista *L) {
    return L->nElem == 0;
}

void insertar_der(TLista *L, int n) {
    TNodo *ptrNuevo = malloc(sizeof (TNodo));
    if (ptrNuevo) {
        ptrNuevo->elem = n;
        ptrNuevo->sig = NULL;

        if (L->inicio == NULL)
            L->inicio = ptrNuevo;
        else
            L->final->sig = ptrNuevo;
        L->final = ptrNuevo;
        (L->nElem)++;
    }
}

void insertar_izq(TLista *L, int n) {
    TNodo *ptrNuevo = malloc(sizeof (TNodo));
    if (ptrNuevo) {
        ptrNuevo->elem = n;
        ptrNuevo->sig = NULL;

        if (L->inicio == NULL)
            L->inicio = ptrNuevo;
        else
            ptrNuevo->sig = L->inicio;
        L->inicio = ptrNuevo;
        (L->nElem)++;
    }
}

void eliminar(TLista *L, int n) {
    TNodo *ptrRec, *ptrAnt;
    int termino = 0;
    ptrRec = L->inicio;
    while (ptrRec && !termino) {
        if (ptrRec->elem == n) {
            if (ptrRec == L->inicio)
                L->inicio = L->inicio->sig;
            else
                if (ptrRec == L->final) {
                L->final = ptrAnt;
                L->final->sig = NULL;
            } else
                ptrAnt->sig = ptrRec->sig;
            free(ptrRec);
            termino = 1;
            (L->nElem)--;
        } else {
            ptrAnt = ptrRec;
            ptrRec = ptrRec->sig;
        }
    }
}

void eliminar_izq(TLista *L) {
    TNodo *ptrRec = L->inicio;
    if (ptrRec) {
        L->inicio = L->inicio->sig;
        free(ptrRec);
        (L->nElem)--;
    }
}

void imprimir_lista(TLista *L) {
    int i;
    TNodo *ptrRec = L->inicio;
    for (i = 0; i < L->nElem; i++) {
        printf("%d->", ptrRec->elem);
        ptrRec = ptrRec->sig;
    }
    printf("NULL\n");
}

/*Pilas*/

void crear_pila(TPila *P) {
    P->top = NULL;
}

void push(TPila *P, int n) {
    TNodo *ptrNodo = malloc(sizeof (TNodo));
    if (ptrNodo) {
        ptrNodo->elem = n;
        ptrNodo->sig = P->top;
        P->top = ptrNodo;
    }
}

int es_pila_vacia(TPila *P) {
    return (P->top == NULL);
}

int pop(TPila *P) {
    int valor;
    TNodo *ptrNodo;
    if (!es_pila_vacia(P)) {
        ptrNodo = P->top;
        valor = ptrNodo->elem;
        P->top = P->top->sig;
        free(ptrNodo);
        return valor;
    }
    return -1;
}

void finaliza_pila(TPila *P) {
    while (!es_pila_vacia(P))
        pop(P);
}

void imprime_pila(TPila *P) {
    TNodo *ptrRec = P->top;
    while (ptrRec) {
        printf("%d\n", ptrRec->elem);
        ptrRec = ptrRec->sig;
    }
}

/*Cola*/

void crear_cola(TCola *C) {
    C->inicio = NULL;
    C->final = NULL;
}

void encolar(TCola *C, int n) {
    TNodo *ptrNodo = malloc(sizeof (TNodo));
    if (ptrNodo) {
        ptrNodo->elem = n;
        ptrNodo->sig = NULL;
        if (C->inicio == NULL)
            C->inicio = ptrNodo;
        else
            C->final->sig = ptrNodo;
        C->final = ptrNodo;
    }
}

int es_cola_vacia(TCola *C) {
    return C->inicio == NULL;
}

int desencolar(TCola *C) {
    TNodo *ptrNodo;
    int valor;
    if (!es_cola_vacia(C)) {
        ptrNodo = C->inicio;
        valor = ptrNodo->elem;
        C->inicio = C->inicio->sig;
        free(ptrNodo);
        return valor;
    }
    return -1;
}

void finaliza_cola(TCola *C) {
    while (!es_cola_vacia) {
        desencolar(C);
    }
}

/*Ejercicios*/

TLista merge_listas(TLista *L1, TLista *L2) {
    TLista lMerged;
    crear_lista(&lMerged);

    TNodo *ptrRec1 = L1->inicio;
    TNodo *ptrRec2 = L2->inicio;

    while (ptrRec1 && ptrRec2) {
        if (ptrRec1->elem < ptrRec2->elem) {
            insertar_der(&lMerged, ptrRec1->elem);
            ptrRec1 = ptrRec1->sig;
        } else {
            insertar_der(&lMerged, ptrRec2->elem);
            ptrRec2 = ptrRec2->sig;
        }
    }

    while (ptrRec1) {
        insertar_der(&lMerged, ptrRec1->elem);
        ptrRec1 = ptrRec1->sig;
    }

    while (ptrRec2) {
        insertar_der(&lMerged, ptrRec2->elem);
        ptrRec2 = ptrRec2->sig;
    }

    return lMerged;
}

void partir_lista(TLista *L, TLista *primeraMitad, TLista *segundaMitad) {
    int lenLista = L->nElem;
    if (lenLista == 2) {
        insertar_der(primeraMitad, L->inicio->elem);
        insertar_der(segundaMitad, L->final->elem);
    } else {
        int i;
        TNodo *ptrRec = L->inicio;

        for (i = 0; i < lenLista / 2; i++) {
            insertar_der(primeraMitad, ptrRec->elem);
            ptrRec = ptrRec->sig;
        }

        for (i = lenLista / 2; i < lenLista; i++) {
            insertar_der(segundaMitad, ptrRec->elem);
            ptrRec = ptrRec->sig;
        }
    }
}

void merge_sort(TLista* L) {
    if (L->nElem > 1) {
        TLista primeraMitad, segundaMitad;
        crear_lista(&primeraMitad);
        crear_lista(&segundaMitad);
        partir_lista(L, &primeraMitad, &segundaMitad);
        merge_sort(&primeraMitad);
        merge_sort(&segundaMitad);
        *L = merge_listas(&primeraMitad, &segundaMitad);
    }

}

/*Pregunta 1*/
void imprimePosiciones(TLista *L, TLista *P) {
    TNodo *ptrRecP = P->inicio;
    TNodo *ptrRecL;
    while (ptrRecP) {
        ptrRecL = L->inicio;
        int i;
        if (ptrRecP->elem <= L->nElem) {
            for (i = 1; i < ptrRecP->elem; i++)
                ptrRecL = ptrRecL->sig;
            printf("%d ", ptrRecL->elem);
        }
        ptrRecP = ptrRecP->sig;
    }
    printf("\n");
}

/*Pregunta 2*/
void parentheses_balance(TListaChar *L) {

}

/*Pregunta 3*/

void crear_deque(TDeque *D) {
    D->nElem = 0;
    D->inicio = NULL;
    D->final = NULL;
}

void insertar_deque_der(TDeque *D, int n) {
    TNodoDeque *ptrNodo = malloc(sizeof (TNodoDeque));
    if (ptrNodo) {
        ptrNodo->elem = n;
        ptrNodo->ant = NULL;
        ptrNodo->sig = NULL;
        if (D->inicio == NULL)
            D->inicio = ptrNodo;
        else {
            D->final->sig = ptrNodo;
            ptrNodo->ant = D->final;
        }
        D->final = ptrNodo;
        (D->nElem)++;
    }
}

void insertar_deque_izq(TDeque *D, int n) {
    TNodoDeque *ptrNodo = malloc(sizeof (TNodoDeque));
    if (ptrNodo) {
        ptrNodo->elem = n;
        ptrNodo->ant = NULL;
        ptrNodo->sig = NULL;
        if (D->final == NULL)
            D->final = ptrNodo;
        else {
            D->inicio->ant = ptrNodo;
            ptrNodo->sig = D->inicio;
        }
        D->inicio = ptrNodo;
        (D->nElem)++;
    }
}

int eliminar_deque_der(TDeque *D) {
    int valor;
    TNodoDeque *ptrEliminar;
    if (D->final) {
        ptrEliminar = D->final;
        valor = ptrEliminar->elem;
        D->final = D->final->ant;
        D->final->sig = NULL;
        free(ptrEliminar);
        (D->nElem)--;
        return valor;
    }
    return -1;
}

int eliminar_deque_izq(TDeque *D) {
    int valor;
    TNodoDeque *ptrEliminar;
    if (D->inicio) {
        ptrEliminar = D->inicio;
        valor = ptrEliminar->elem;
        D->inicio = D->inicio->sig;
        D->inicio->ant = NULL;
        free(ptrEliminar);
        (D->nElem)--;
        return valor;
    }
    return -1;
}

/*Pregunta 4*/

int esta_en_lista(int n, TLista *L) {
    TNodo *ptrRec = L->inicio;
    int i;
    for (i = 0; i < L->nElem; i++) {
        if (ptrRec->elem == n)
            return 1;
        ptrRec = ptrRec->sig;
    }
    return 0;
}

TLista union_conjuntos(TLista *L1, TLista *L2) {
    TLista LUnion;
    crear_lista(&LUnion);
    TNodo *ptrL1, *ptrL2;
    ptrL1 = L1->inicio;
    ptrL2 = L2->inicio;

    int i;
    for (i = 0; i < L1->nElem; i++) {
        if (esta_en_lista(ptrL1->elem, L2))
            insertar_der(&LUnion, ptrL1->elem);
        ptrL1 = ptrL1->sig;
    }

    for (i = 0; i < L2->nElem; i++) {
        if (esta_en_lista(ptrL2->elem, L1))
            insertar_der(&LUnion, ptrL2->elem);
        ptrL2 = ptrL2->sig;
    }

    return LUnion;
}

TLista interseccion_conjuntos(TLista *L1, TLista *L2) {
    TLista LInt;
    crear_lista(&LInt);
    TNodo *ptrL1, *ptrL2;
    ptrL1 = L1->inicio;
    ptrL2 = L2->inicio;

    int i;
    for (i = 0; i < L1->nElem; i++) {
        if (!esta_en_lista(ptrL1->elem, L2))
            insertar_der(&LInt, ptrL1->elem);
        ptrL1 = ptrL1->sig;
    }

    for (i = 0; i < L2->nElem; i++) {
        if (!esta_en_lista(ptrL2->elem, L1))
            insertar_der(&LInt, ptrL2->elem);
        ptrL2 = ptrL2->sig;
    }

    return LInt;
}

TLista diferencia_conjuntos(TLista *L1, TLista *L2) {
    TLista LDif;
    crear_lista(&LDif);
    TNodo *ptrL1, *ptrL2;
    ptrL1 = L1->inicio;
    ptrL2 = L2->inicio;

    int i;

    while (ptrL1) {
        if (esta_en_lista(ptrL1->elem, L2))
            ptrL1 = ptrL1->sig;
        else
            insertar_der(&LDif, ptrL1->elem);
    }

    return LDif;
}

void crearConjuntoVacio(TLista *L) {
    finalizar_lista(L);
}

void insertar_elem_conjunto(TLista *L, int n) {
    if (!esta_en_lista(n, L)) {
        insertar_der(L, n);
    }
}

void remover_elem_conjunto(TLista *L, int n) {
    if (esta_en_lista(n, L)) {
        eliminar(L, n);
    }
}

int min_conjunto(TLista *L) {
    int min = INT_MAX;
    TNodo *ptrRec = L->inicio;
    int i;
    for (i = 0; i < L->nElem; i++) {
        if (ptrRec->elem < min)
            min = ptrRec->elem;
        ptrRec = ptrRec->sig;
    }
    return min;
}

int max_conjunto(TLista *L) {
    int max = 0;
    TNodo *ptrRec = L->inicio;
    int i;
    for (i = 0; i < L->nElem; i++) {
        if (ptrRec->elem > max)
            max = ptrRec->elem;
        ptrRec = ptrRec->sig;
    }
    return max;
}

int igual_conjuntos(TLista *L1, TLista *L2) {
    int igualL1 = 1, igualL2 = 1;
    TNodo *ptrL1, *ptrL2;
    ptrL1 = L1->inicio;
    ptrL2 = L2->inicio;
    int i;
    for (i = 0; i < L1->nElem; i++) {
        igualL1 = igualL1 && esta_en_lista(ptrL1->elem, L2);
        ptrL1 = ptrL1->sig;
    }

    for (i = 0; i < L2->nElem; i++) {
        igualL2 = igualL2 && esta_en_lista(ptrL2->elem, L1);
        ptrL2 = ptrL2->sig;
    }

    return igualL1 && igualL2;
}

/*Pregunta 5*/

TLista suma_listas(TLista *L1, TLista *L2) {
    TLista LSuma;
    crear_lista(&LSuma);

    TPila P1;
    TPila P2;
    crear_pila(&P1);
    crear_pila(&P2);

    int res = 0;
    int sum_parcial = 0;
    TNodo *ptrL1, *ptrL2;
    ptrL1 = L1->inicio;
    ptrL2 = L2->inicio;

    //se pasan las listas a pilas P1 y P2
    while (ptrL1 != NULL) {
        push(&P1, ptrL1->elem);
        ptrL1 = ptrL1->sig;
    }

    while (ptrL2 != NULL) {
        push(&P2, ptrL2->elem);
        ptrL2 = ptrL2->sig;
    }

    TNodo *ptrP1 = P1.top;
    TNodo *ptrP2 = P2.top;

    //sum_parcial tendra el valor de sumar las dos cimas de las pilas
    //si el valor es mayor a 9, se coloca solo la cifra de mas a la izquierda
    //y el res contendra la otra cifra que se sumara a la siguiente suma
    while (ptrP1 && ptrP2) {
        sum_parcial = (ptrP1->elem) + (ptrP2->elem) + res;
        res = 0;
        if (sum_parcial <= 9) {
            insertar_izq(&LSuma, sum_parcial);
        } else {
            res = sum_parcial / 10;
            sum_parcial = sum_parcial % 10;
            insertar_izq(&LSuma, sum_parcial);
        }
        pop(&P1);
        pop(&P2);
        ptrP1 = P1.top;
        ptrP2 = P2.top;
    }

    //se insertan los numeros que pudieron haber quedado en las pilas,
    //pues pueden ser listas de diferentes longitudes
    while (ptrP1) {
        insertar_izq(&LSuma, ptrP1->elem + res);
        ptrP1 = ptrP1->sig;
        res = 0;
    }

    while (ptrP2) {
        insertar_izq(&LSuma, ptrP2->elem + res);
        ptrP2 = ptrP2->sig;
        res = 0;
    }

    return LSuma;
}

TLista resta_listas(TLista *L1, TLista *L2) {
    TLista LResta;
    crear_lista(&LResta);
    if (L1->nElem >= L2->nElem) {
        //difLen es la diferencia de longitudes de las 2 listas
        int difLen = L1->nElem - L2->nElem;

        //paso las listas a colas
        TCola C1, C2;
        crear_cola(&C1);
        crear_cola(&C2);

        TNodo *ptrRec1, *ptrRec2;
        ptrRec1 = L1->inicio;
        ptrRec2 = L2->inicio;

        while (ptrRec1) {
            encolar(&C1, ptrRec1->elem);
            ptrRec1 = ptrRec1->sig;
        }

        //como el numero en la lista L1 debe ser mayor,
        //puede tener mas cifras que el de L2, encolo 0 a la C2
        //para que sea mas facil la resta
        if (difLen > 0) {
            int i;
            for (i = 0; i < difLen; i++) {
                encolar(&C2, 0);
            }
        }

        while (ptrRec2) {
            encolar(&C2, ptrRec2->elem);
            ptrRec2 = ptrRec2->sig;
        }

        TNodo *ptrC1, *ptrC2, *ptrRecL;
        ptrC1 = C1.inicio;
        ptrC2 = C2.inicio;
        ptrRecL = LResta.inicio;

        int lleva = 0;
        while (ptrC1 && ptrC2) {
            int res;
            //res lleva la resta de los numeros que ahora estan en las colas
            //lleva sera 1 si es que el valor que sigue sale negativo de la resta
            //lo cual significa que se le sumara 10 para obtener el valor real
            //y se resta 1 a la anterior resta para luego insertarse a la lista LResta
            res = ptrC1->elem - ptrC2->elem;
            if (lleva == 1) {
                res += 10;
                lleva = 0;
            }
            if (ptrC1->sig && ptrC2->sig) {
                if (ptrC1->sig->elem < ptrC2->sig->elem) {
                    res--;
                    lleva = 1;
                }
            }
            insertar_der(&LResta, res);

            desencolar(&C1);
            desencolar(&C2);
            ptrC1 = C1.inicio;
            ptrC2 = C2.inicio;
        }

        //como ha podido quedar 0's a la izquierda en el resultado se eliminan
        ptrRecL = LResta.inicio;
        while (ptrRecL->elem == 0) {
            eliminar_izq(&LResta);
            ptrRecL = ptrRecL->sig;
        }
    }
    return LResta;
}

TLista multiplicar_listas(TLista *L1, TLista *L2) {
    TLista LMult;
    crear_lista(&LMult);




    return LMult;
}

int main(int argc, char** argv) {
    TLista L1, L2, L3;
    TPila P;

    crear_lista(&L1);
    insertar_der(&L1, 1);
    insertar_der(&L1, 8);
    insertar_der(&L1, 0);
    insertar_der(&L1, 0);

    crear_lista(&L2);
    insertar_der(&L2, 7);
    insertar_der(&L2, 9);
    insertar_der(&L2, 8);

    //merge_sort(&L1);
    //merge_sort(&L2);

    imprimir_lista(&L1);
    imprimir_lista(&L2);

    //imprimePosiciones(&L1,&L2);

    //finalizar_lista(&L1);
    //finalizar_lista(&L2);

    //crear_pila(&P);
    //push(&P, 2);
    //push(&P, 5);
    //push(&P, 1);

    //pop(&P);

    //imprime_pila(&P);
    //finaliza_pila(&P);

    TLista LS = suma_listas(&L1, &L2);
    imprimir_lista(&LS);

    TLista LR = resta_listas(&L1, &L2);
    imprimir_lista(&LR);

    return (EXIT_SUCCESS);
}