/*
Considerando una lista de valores enteros, con dos punteros,
modifique la definición y operaciones básicas de listas de modo que sea
posible registrar la cantidad de valores. Desarrolle las operaciones
iniciar_lista, crear_nodo, agregar_inicio, quitar_final y mostrar_lista.
Agregar luego las operaciones
agregar pares al inicio, impares al final
mostrar de manera recursiva,
ordenar los valores
sumar los nodos
*/

#include <iostream>
#include <stdlib.h>
using namespace std;

const int MAX=10;
typedef struct tnodo *pnodo;

typedef struct tnodo{
                    int dato;
                    pnodo sig;
                    pnodo ant;
                    };

typedef struct tlista{
          pnodo inicio;
          int cont;
          pnodo fin;
};
//Inicialización de la lista
void iniciar_lista(tlista &lis);

//Creación del nodo
void crear(pnodo &nuevo);

//Agregar un elemento
void agregar_inicio(tlista &lis, pnodo &nuevo);
void agregar(tlista &lis, pnodo nuevo);

bool lista_llena(tlista lis);

//Quitar un elemento
pnodo quitar_final(tlista &lis);


//Recorrer/Mostrar la lista

void mostrar_lista(tlista lis);
void mostrar_rec(pnodo lis);

void ordenar(tlista lis);
int suma_rec(pnodo lis);

void menu(int &opc);



main()
{
    tlista lista;
    pnodo nuevo, eliminado;
    int op, valor, op2;
    iniciar_lista(lista);
    do{ system("cls");
        menu(op);
        switch(op)
        {
            case 1: cout<<".....Agregar valor ......"<<endl;
                    crear(nuevo);
                    if(nuevo!=NULL)
                      agregar(lista, nuevo);
                    else
                        cout<<"Memoria llena"<<endl;
                    break;

            case 2: cout<<".....Quitar valor ......"<<endl;
                    eliminado=quitar_final(lista);
                    if(eliminado!=NULL)
                    {
                      cout<<"Eliminado "<<eliminado->dato<<endl;
                      delete(eliminado);
                    }
                    else
                       cout<<" No se puede eliminar, lista vacia"<<endl;

                    break;

            case 3: cout<<"..........Lista.........."<<endl;
                    mostrar_lista(lista);
                    cout<<"\n cantidad de nodos: "<<lista.cont<<endl;
                    cout<<endl;
                    mostrar_rec(lista.fin);
                    //cout<<"suma total: "<<suma_rec(lista.inicio)<<endl;

                    break;
            case 4: cout<<"ordenando..."<<endl;
                    ordenar(lista);
                    mostrar_lista(lista);
                    break;
            case 5: cout<<"...........FIN DEL PROGRAMA..........."<<endl;

                    break;
            default : cout<<" OPCION INCORRECTA"<<endl;
        }
        system("pause");

    }while(op!=5);

}

//Inicialización
void iniciar_lista(tlista &lis)
{
    lis.inicio=NULL;
    lis.fin=NULL;
    lis.cont=0;

}

//Creación del nodo
void crear(pnodo &nuevo)
{
    nuevo=new tnodo;
    if(nuevo!=NULL)
    {
        cout<<"Ingrese valor: ";
        cin>> nuevo->dato;
        nuevo->sig=NULL;
        nuevo->ant=NULL;
    }
    else
        cout<<"Memoria llena"<<endl;
}

//Agregar elemento
void agregar_inicio(tlista &lis, pnodo &nuevo)//para liberar correctamente la memoria
{
  if(lis.cont==MAX)
    { cout<<"No se puede agregar mas nodos"<<endl;
      delete(nuevo);
    }
  else{
    if(lis.inicio==NULL) //lis.cont==0 lis.fin==NULL
    {
      lis.inicio=nuevo;
      lis.fin=nuevo;
      lis.cont++;
    }
    else{
      nuevo->sig=lis.inicio;
      lis.inicio->ant=nuevo;
      lis.inicio=nuevo;
      lis.cont++;
    }
  }
}

pnodo quitar_final(tlista &lis)
{ pnodo aux, i;
    if(lis.inicio==NULL)//lis.cont==0  lis.fin==NULL
        aux=NULL;
    else
    { if(lis.inicio->sig==NULL) //lis.cont==1 o lis.inicio==lis.fin
        {
            aux=lis.inicio; //aux=lis.fin
            lis.inicio=NULL;
            lis.fin=NULL;
        }
        else
        {
         aux=lis.fin;//aux=i->sig;
         lis.fin=aux->ant;
         lis.fin->sig=NULL;
         aux->ant=NULL;
        }
       lis.cont--;
    }
    return aux;
}


//Mostrar los elementos de la lista
void mostrar_lista(tlista lis)
{
    pnodo i;
    cout<<"\ndel principio al final"<<endl;
    for(i=lis.inicio; i!=NULL; i=i->sig)
        cout<<i->dato<<endl;
//    cout<<"\ndel final al principio"<<endl;
//    for(i=lis.fin; i!=NULL; i=i->ant)
//        cout<<i->dato<<endl;
}

//Menus de opciones
void menu(int &opc)
{
    cout<<"..........MENU.........."<<endl;
    cout<<"1- Agregar un elemento"<<endl;
    cout<<"2- Quitar un elemento"<<endl;
    cout<<"3- Mostrar lista"<<endl;
    cout<<"4-ordenar"<<endl;
    cout<<"5- Salir"<<endl;
    cout<<"Elija una opcion: ";
    cin>>opc;
}


void agregar(tlista &lis, pnodo nuevo)
{
  if(lista_llena(lis)==true)
  {
    cout<<"no se puede agregar"<<endl;
    delete(nuevo);
  }
  else
  {
    if(lis.cont==0)
      {
        lis.inicio=nuevo;
        lis.fin=nuevo;
    }
      else
        if(nuevo->dato %2==0)
        {
          nuevo->sig=lis.inicio;
          lis.inicio->ant=nuevo;
          lis.inicio=nuevo;
        }
        else
        {
          nuevo->ant=lis.fin;
          lis.fin->sig=nuevo;
          lis.fin=nuevo;
        }
    lis.cont++;
    }

  }

void mostrar_rec(pnodo lis)
{
  if(lis!=NULL)
  {cout<<lis->dato<<endl;
    mostrar_rec(lis->ant); //RRC
   // cout<<lis->dato<<endl;
  }
}



bool lista_llena(tlista lis)
{
  return (lis.cont==MAX);
}

void ordenar(tlista lis)
{
  pnodo i, j;
  int aux;
  for(i=lis.inicio;i!=lis.fin;i=i->sig)
  {
    for(j=i->sig; j!=NULL; j=j->sig)
      if(i->dato<j->dato)
      {
      aux=i->dato;
      i->dato=j->dato;
      j->dato=aux;
      }
  }
}

int suma_rec(pnodo lis)
{
  if(lis==NULL)
    return 0;
  else
    return lis->dato+suma_rec(lis->sig);
}