#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<conio.h>
#include<windows.h>
#include"arista1.h"
#include"cola.h"
#include"pila.h"
 
using namespace std;
 
class vertice{
	public:
		vertice *sig;
		arista *ady;
		bool marc;
		char dato;
		char leer();
		vertice *insertar(vertice *cab);
		vertice *crear();
		bool verificar(vertice *cab);
		int counternodes(vertice *cab);
		void print(vertice *cab,arista *cab2);
		void *creararistaa(vertice *Cab);
		vertice *searchpositondata(vertice *Cab);
		vertice *searchpositondata4(vertice *Cab);
		vertice *searchpositondata2(vertice *cab,char id);
		vertice *searchpositondata3(vertice *cab);
		void grado(vertice *cab);
		bool recorrido(vertice *cab,arista *nuevo);
		void encolar(vertice *cab);
};
 
bool vertice::verificar(vertice *cab){ //verifica que exista el grafo o en su defecto que la cabecera sa dferente de NULL
	bool v;
	if(cab==NULL){
		v=false;
		return v;
	}else{
		if(cab!=NULL){
			v=true;
			return true;
		}
	}
}
char vertice::leer(){ //lee el dato de un archivo
	char dato;
	gotoxy(9,23);
	cout<<"Por favor ingrese el dato(LETRA):";
	cout<<"\x10 ";
	cin>>dato;
	return dato;
}		
 
 
vertice *vertice::crear(){ //crea el vertice o nodo del grafo
	vertice *nuevo;
	nuevo =new vertice;
	nuevo->dato=nuevo->leer();
	nuevo->ady=NULL;
	nuevo->sig=NULL;
	nuevo->marc=false;
	return nuevo;
}
 
vertice *vertice::insertar(vertice *cab){// se comienza a dar forma a el grafo
	vertice *nuevo;
	nuevo=nuevo->crear();
	if(cab==NULL){
		cab=nuevo;
		gotoxy(9,24);
		cout<<" HA INGRESADO EXITOSAMENTE EL PRIMER NODO DEL GRAFO\n";
		return nuevo;
	}else{
		vertice *aux;
		aux=cab;
		while(aux->sig!=NULL){
			aux=aux->sig;
		}
		aux->sig=nuevo;
	}
}
 
int vertice::counternodes(vertice *cab){   //contador de nodos existentes en el grafo
	vertice *aux;
	aux=cab;
	int c=0;
	while(aux!=NULL){
		aux=aux->sig;
		c++;
	}
	return c;
}
 
void vertice::print(vertice *cab,arista *cab2){  //mostrar en pantalla del grafo en general
	vertice *aux;
	aux=cab;
	int c=1;
	arista *aux2;
	aux2=cab->ady;
	cout<<"\n GRAFO	\n\n";
	cout<<"[Lista principal(\31)]   sublista(\32)}\n\n\n";
	while(aux!=NULL){
		cout<<c<<"["<<aux->dato<<"]\32";
		while(aux2!=NULL){
			cout<<"{"<<aux2->dato<<"|"<<aux2->peso<<"}\32";
			aux2=aux2->sig;
 
		}
		if(aux2==NULL){
				cout<<"\xB0\xB1\xB2\xDB";
		}
		cout<<endl;
		cout<<"   \31  \n";
		aux=aux->sig;
		if(aux!=NULL){
			aux2=aux->ady;	
		}
		if(aux==NULL){
			cout<<"  \xCD\xCB\xCD";
		}
		c++;
	}
	cout<<"\n\n";
}
 
vertice *vertice::searchpositondata3(vertice *cab){
	vertice *aux;
	char id;
	aux=cab;
	cout<<"Ingrese la letra del nodo del cual desa saber el grado\n\n";
	gotoxy(9,26);
	cout<<"\x10 ";
	cin>>id;
	while(aux->sig!=NULL&&aux->dato!=id){
		aux=aux->sig;
		if(aux->dato==id){
		return aux;
		}
	}
	while(aux->dato!=id&&aux->sig==NULL){
		cout<<"Esta letra no existe, por favor ingrese una letra valido\n\n";
		gotoxy(9,29);
		cout<<"\x10 ";
		cin>>id;
	}
	return aux;
}
 
vertice *vertice::searchpositondata(vertice *cab){
	vertice *aux;
	char id;
	aux=cab;
	cout<<"Ingrese la letra donde desea ingresar la arista\n\n";
	gotoxy(9,26);
	cout<<"\x10 ";
	cin>>id;
	while(aux->sig!=NULL&&aux->dato!=id){
		aux=aux->sig;
		if(aux->dato==id){
		return aux;
		}
	}
	while(aux->dato!=id&&aux->sig==NULL){
		cout<<"Esta letra no existe, por favor ingrese una letra valido\n\n";
		gotoxy(9,29);
		cout<<"\x10 ";
		cin>>id;
	}
	return aux;
}
 
vertice *vertice::searchpositondata4(vertice *cab){
	vertice *aux;
	char id;
	aux=cab;
	cout<<"Ingrese la letra donde desea ingresar la arista\n\n";
	gotoxy(9,26);
	cout<<"\x10 ";
	cin>>id;
	while(aux->sig!=NULL&&aux->dato!=id){
		aux=aux->sig;
		if(aux->dato==id){
		return aux;
		}
	}
	while(aux->dato!=id&&aux->sig==NULL){
		cout<<"Esta letra no existe, por favor ingrese una letra valido\n\n";
		gotoxy(9,29);
		cout<<"\x10 ";
		cin>>id;
	}
	return aux;
}
 
vertice *vertice::searchpositondata2(vertice *cab,char id){
	vertice *aux;
	aux=cab;
	while(aux->sig!=NULL&&aux->dato!=id){
		aux=aux->sig;
		if(aux->dato==id){
		return aux;
		}
	}
	int i=26,c=0;
	while(aux->dato!=id&&aux->sig==NULL){
		c++;
		cout<<"Esta letra no existe, por favor ingrese una letra valido\n\n";
		gotoxy(9,i);
		if(c>0){
			i=i+2;
		}
		cout<<"\x10 ";
		cin>>id;
	}
	return aux;
}
 
void *vertice::creararistaa(vertice *Cab){  //inserta nodos al inicio de una sublista
	int position,c;
	bool v;
	vertice *aux,*aux3;
	arista  *b,*aux2,*aux4,*s;
	bool verifyb;
	gotoxy(9,25);
	aux=aux->searchpositondata(Cab);
	aux2=b->creararista(aux->ady);
	v=aux->recorrido(Cab,aux2);
	while(v==false){
		delete aux2;
		cout<<"\nESTE DATO NO EXISTE EN EL GRAFO POR FAVOR INGRESE UN DATO VALIDO\n";
		aux2=b->creararista(aux->ady);
		v=aux->recorrido(Cab,aux2);
	}
	/*aux3=aux3->searchpositondata2(Cab,aux2->dato);
	aux4=b->creararista2(aux->ady,aux->dato);
	s=aux3->ady;
	aux3->ady=aux4;*/
	aux->ady=aux2;
 
}
 
bool vertice::recorrido(vertice *cab,arista *nuevo){
	vertice *aux;
	arista *aux2;
	bool v=false;
	aux=cab;
	aux2=nuevo;
	while(aux!=NULL){
		if(aux->dato==aux2->dato){
			v=true;
			return v;
		}
		aux=aux->sig;
	}
	if(aux==NULL){
		v=false;
		return v;
	}
}
 
void vertice:: grado(vertice *cab){
	vertice *aux1, *aux;
	arista *aux2;
	aux1=cab;
	aux=cab;
	char letra;
	int pos=0,suma=0, con=0, suma2=0, con2=0;
	if (cab==NULL){
		cout<<"--> No hay elementos por mostrar \n\n";
	}
	else{
		cout<<"Digite la letra del nodo a la que quiere saber su grado de entrada y de salida: \n";
		gotoxy(9,26);
		cin>>letra;    
		while (aux!=NULL){
			if(aux->dato==letra){
				pos=1;
				aux1=aux; //aux1 es el nodo de la letra       
			}
			aux=aux->sig;
		}
		if(pos==0){
			gotoxy(9,27);
			cout<<"\32NO SE ENCUENTRA EL NODO  \n";
		}
		else{
			gotoxy(9,27);
			cout<<"Nodo: "<<aux1->dato<<"\n";
			aux2=aux1->ady;
			while(aux2!=NULL){
				suma=suma+aux2->peso;
				con++;
				aux2=aux2->sig;
			}
			gotoxy(9,28);
			cout<<"Grado de salida: "<<con<<endl;
			gotoxy(9,29);
			cout<<"Suma de arcos de salida: "<<suma<<endl;
 
			aux1=cab;
			while (aux1!=NULL){
				aux2=aux1->ady;
			while (aux2!=NULL){
				if(aux2->dato==letra){
						suma2=suma2+aux2->peso;
						con2++;
				}
				aux2=aux2->sig;
				}
				aux1=aux1->sig;
			}
			gotoxy(9,32);
			cout<<"Grado de entrada: "<<con2<<endl;
			gotoxy(9,33);
			cout<<"Suma de arcos de entrada: "<<suma2<<endl;
		}		
	}
}
void vertice::encolar(vertice *cab){
	Nodo *cola=NULL;
/*	vertice *aux;
	int c=0;
	while(aux!=NULL){
		c++;
		aux=aux->sig;
	}
	char cola[2][c];
	for(int i = 0;i<=c;i++){
		cola[0][i]='N';
	}
	aux=cab;
	int i=0;
	while(aux!=NULL&&i<=c){
		cola[1][i]=aux->dato;
		i++;
	}
	for(int i = 0;i<=1;i++){
		for(int a = 0;a<=c;a++){
			cout<<cola[i][a]<<" ";
		}
}*/
	vertice *aux,*aux2;
	arista *aux3,*aux4;
	aux=cab;
	aux4=cab->ady;
	aux2=aux2->searchpositondata4(cab);
	aux3=aux2->ady;
	cola=cola->encolar(cola,aux2->dato);
	while(aux!=NULL){
		while(aux4!=NULL){
			if(aux4->dato=aux2->dato){
				aux4->marc=true;
			}
		}
		aux=aux->sig;
		if(aux!=NULL){
			aux4=aux->ady;
		}
	}
	cola->eliminar(cola);
 
}