#include <iostream>

using namespace std;

const int MAX=5;

typedef struct tnodo *pnodo;
typedef struct tnodo{
	char dato;
	pnodo sig;
};

typedef struct tlista{
	pnodo inicio;
	pnodo final;
	int contador;
};

void iniciar_lista(tlista &lista);
void crear_nodo(pnodo &nuevo,char valor);
void agregar_final(tlista &lista,pnodo nuevo);
pnodo quitar_inicio(tlista &lista);
void mostrar(tlista lista);
bool buscar(tlista lista,char valor);
void copiar(tlista original, tlista &copia);

main()
{ int op;
  tlista milista, lista2;
  pnodo nuevo;
  pnodo aux;
  char valor;
  iniciar_lista(milista);

  do{ system("cls");
		cout << "1-Agregar nodo" << endl;
		cout << "2-Quitar nodo" << endl;
		cout << "3-Mostrar" << endl;
		cout << "4-Buscar" << endl;
		cout << "5-Copiar" << endl;
		cout << "6-Salir" << endl;
		cout << "Ingrese opcion: ";
		cin >> op;
		switch (op)
		{ case 1: 	cout << "### AGREGANDO DATOS ###" << endl;
					cout << "Ingrese el valor a agregar: ";
					cin >> valor;
					crear_nodo(nuevo,valor);
					if (nuevo!=NULL)
						agregar_final(milista,nuevo);
					else
						cout << "No hay espacio suficiente en memoria" << endl;
					break;
		  case 2: cout << "### EXTRAYENDO DATOS ###" << endl;
					aux=quitar_inicio(milista);
					if (aux!=NULL)
					{ cout << "se extrajo: " << aux->dato << endl;
					  delete(aux);	
					}
					else
					  cout << "no se realizo la extraccion" << endl;
					break;
		  case 3: cout << "### MOSTRANDO DATOS ###" << endl;
					mostrar(milista);
					break;
		  case 4: cout << "### BUSCANDO DATOS ###" << endl;
					cout << "Ingrese valor a buscar:";
					cin >> valor;
					if (buscar(milista,valor)==true)
						cout << valor << " existe en la lista" << endl;
					else
						cout << valor << " no pertenece a la lista" << endl;
					break;
		  case 5: cout << "### COPIAR LISTA ###" << endl;
					copiar(milista,lista2);
					cout << "LISTA ORIGINAL" << endl;
					mostrar(milista);
					cout << "LISTA COPIADA" << endl;
					mostrar(lista2);
					break;
		  case 6: cout << "FIN DE PROGRAMA" << endl;
					break;
		  default: cout << "Error de opcion" << endl;
		}
		system("pause");
	} while(op!=6);
}

void iniciar_lista(tlista &lista)
{
	lista.inicio=NULL;
	lista.final=NULL;
	lista.contador=0;
}

void crear_nodo(pnodo &nuevo,char valor)
{
	nuevo=new tnodo;
	if (nuevo!=NULL)
	{ nuevo->dato=valor;
	nuevo->sig=NULL;		
	}
}

void agregar_final(tlista &lista,pnodo nuevo)
{ 
	if (lista.contador==0)
	{	lista.inicio=nuevo;
		lista.final=nuevo;
		lista.final->sig=lista.inicio;
		lista.contador++;
	}
	else
	{ if (lista.contador<MAX)
	{	lista.final->sig=nuevo;
		lista.final=nuevo;
		lista.final->sig=lista.inicio;
		lista.contador++;
	}
	else
	{ cout << "CAPACIDAD COMPLETA" << endl;
	  delete(nuevo);
	}  
	}
}

pnodo quitar_inicio(tlista &lista)
{ pnodo extraido;
  if (lista.contador==0)
	extraido=NULL;
  else
  { if (lista.contador==1)
    {extraido=lista.inicio;
	 extraido->sig=NULL;
     lista.inicio=NULL;
	 lista.final=NULL;
    }
    else
    { extraido=lista.inicio;
      lista.inicio=lista.inicio->sig;
      extraido->sig=NULL;
	  lista.final->sig=lista.inicio;
    }
    lista.contador--;
  }
  return extraido;
}

void mostrar(tlista lista)
{ pnodo i;
  if (lista.inicio==NULL)
	cout << "vacio" << endl;
  else
  { cout << "Cant. elementos: " << lista.contador << endl;  
    for(i=lista.inicio;i!=lista.final;i=i->sig)
	  cout << i->dato << endl;
	cout << i->dato << endl;
  }
}


bool buscar(tlista lista,char valor)
{ pnodo i;
  bool existe=false;
  if (lista.inicio!=NULL)
  { if (lista.inicio->dato==valor)
	  existe=true;
    else
      for(i=lista.inicio;i!=lista.final && existe==false;i=i->sig)
	   if ((i->sig)->dato==valor)
		   existe=true;
  }
  return existe;
}

void copiar(tlista original, tlista &copia)
{ pnodo i,n;
  if (original.contador==0)
	cout << "Lista vacia, no se puede copiar" << endl;
  else
   { iniciar_lista(copia);
     crear_nodo(n,original.inicio->dato);
	 agregar_final(copia,n);
     for(i=original.inicio;i!=original.final;i=i->sig)
     { crear_nodo(n,(i->sig)->dato);
       agregar_final(copia,n);
     }
   }
}