#include <iostream>

struct nodo_doble {
    int elem ;
    nodo_doble * sig ;
    nodo_doble * ant ;
};
typedef nodo_doble * lista ;

// listaVacia: retorna una lista vacia.
// O(1)
lista listaVacia(){
    return NULL;
}

// esVacia: dada una lista l, verifica si l esta vacia.
// O(1)
bool esVacia(lista l){
    return l==NULL;
}

// insPrincipio: dados un entero x y una lista l, retorna el resultado de insertar x al principio de l.
// O(1)
void insPrincipio(int x, lista &l){
    //creamos el nodo y lo inicializamos
    lista nuevo = new nodo_doble;
    nuevo->elem=x;
    nuevo->sig=l;
    nuevo->ant=NULL;
    
    //nos fijamos si no es vacia para que el primer elemento quede enlazado
    if (!esVacia(l)){
        l->ant=nuevo;
    }
    l=nuevo;
}


// esElemento: dados un entero x y una lista l, verifica si x pertenece a l.
// peor caso O(n)
// mejor caso O(1)

bool esElemento (int x, lista l){
    while (l!=NULL && l->elem!=x){
        l=l->sig;
    }
    return l!=NULL;
}

// insOrd: dados un entero x y una lista l ordenada, retorna el resultado de insertar x en l ordenadamente.
void insOrd(int x, lista &l){
    if (esVacia(l) || l->elem >=x){
        insPrincipio(x,l);
    }else{
        
        lista nuevo = new nodo_doble;
        nuevo->elem=x;
        nuevo->sig=NULL;
        nuevo->ant=NULL;
        
        lista aux=l;
        while(aux->sig!=NULL && aux->elem < x){
            aux=aux->sig;
        }
        if (aux->elem >= x){
            nuevo->sig=aux;
            nuevo->ant=aux->ant;
            aux->ant->sig=nuevo;
            aux->ant=nuevo;
        }else{
            nuevo->ant=aux;
            aux->sig=nuevo;
        }
    }
}



// removerTodos: dados un entero x y una lista l, retorna el resultado de eliminar todas las ocurrencias
//de x de l.
// en el peor caso O(n)
// en el mejor caso O(n)
void removerTodos(int x, lista &l){
    lista aux=l;
    while (aux!=NULL){
        if(aux->elem==x){
            if (aux->ant==NULL){
                l=aux->sig;
                if (aux->sig!=NULL)
                    aux->sig->ant=NULL;
            }else{
                aux->ant->sig=aux->sig;
                if (aux->sig!=NULL){
                    aux->sig->ant=aux->ant;
                }
            }
            lista aborrar=aux;
            aux=aux->sig;
            delete aborrar;
        }else{
            aux=aux->sig;   
        }
    }
}

// removerUltimo: dada una lista l ordenada, retorna el resultado de eliminar el último elemento de
//l. Analice el orden del tiempo de ejecución. Proponga una representación con la que el orden del
//tiempo de ejecución sea O(1).
//Falta hacer

/*struct cabezal {
    nodo_doble * inicio ;
    nodo_doble * fin ;
};

lista listaVacia(){
    cabezal* nuevo = new cabezal;
    nuevo->inicio=nuevo->final=NULL;
}
*/

void imprimir(lista l){
    lista aux=l;
    while (aux!=NULL){
        printf("%d ", aux->elem);
        aux=aux->sig;
    }   
}

int main()
{
    lista l = listaVacia(); 

    insPrincipio(15, l);
    insPrincipio(10, l);
    insPrincipio(10, l);
    insPrincipio(5, l);
    
    printf("Lista v1: ");
    imprimir(l);

    insOrd(12, l);
    insOrd(7, l);
    
    printf("\n");
    printf("Lista v2: ");
    imprimir(l);


    removerTodos(10, l);

    printf("\n");
    printf("Lista v3: ");
    imprimir(l);

    
    return 0;
}