using namespace System;
using namespace System::Collections::Generic;
using namespace System::Text;
using namespace System::Collections;

namespace CLITableur
{	
	/// <summary>
	/// Représente un sommet au sein d'un graphe
	///	</summary>
	public ref class Sommet
	{
	public: 
		/// <summary>
		/// Nom du sommet
		///	</summary>
		String^ name;
	
		/// <summary>
		/// Sommets du graphe adjacents
		///	</summary>
		List<Sommet^>^ adjacents;

	public:
		Sommet()
		{
			adjacents = gcnew List<Sommet^>();
			name = "";
		}
	};    


	/// <summary>
	/// Représente un graphe dirigé
	///	</summary>
	public ref class Graphe
	{
	private:
		/// <summary>
		/// Ensemble des sommets du graphe (membre privé)
		///	</summary>
		List<Sommet^>^ g;

	public:
		/// <summary>
		/// Constructeur
		///	</summary>
		Graphe()
		{
			g = gcnew List<Sommet^>();
		}        

	public:
		/// <summary>
		/// Ajoute un sommet au graphe, avec ses dépendances (sommets adjacents)
		///	</summary>
		void AjouterSommet(String^ name, array<String^>^ dependances)
		{
			Sommet^ adj;
			Sommet^ s;
			if ((s = GetSommetByName(name)) == nullptr)
			{
				// le sommet n'existe pas encore
				s = gcnew Sommet();
				s->name = name->ToUpper();
				g->Add(s);
			}

			// ajoute ses dépendances
			for (int i = 0; i < dependances->Length; i++)
				if ((adj = GetSommetByName(dependances[i])) != nullptr)
				{
					s->adjacents->Add(adj);
				}
				else
				{
					// créé un nouveau sommet adjacent
					adj = gcnew Sommet();
					adj->name = dependances[i]->ToUpper();
					g->Add(adj);
					s->adjacents->Add(adj);
				}
			//}
			//else
			//{
			//	// ajoute ses dépendances
			//	for (int i = 0; i < dependances->Length; i++)
			//		if ((adj = GetSommetByName(dependances[i])) != nullptr)
			//		{
			//			s->adjacents->Add(adj);
			//		}
			//		else
			//		{
			//			// créé un nouveau sommet adjacent
			//			adj = gcnew Sommet();
			//			adj->name = dependances[i]->ToUpper();
			//			g->Add(adj);
			//			s->adjacents->Add(adj);
			//		}
			//}
		}

	public:
		/// <summary>
		/// Identifie le sommet appelé name
		///	</summary>
		Sommet^ GetSommetByName(String^ name)
		{			
			for (int i=0;i<g->Count;i++)
			{
				Sommet^s = g[i];
				if (s->name == name)
					return s;
			}
			return nullptr;
		}

	private:
		bool hasError;

	public:
		bool HasError()
		{
			return hasError; 
		}
		void setError(bool value)
		{ 
			hasError = value; 
		}


	private:
		StringBuilder^ errors;

	public:
		StringBuilder^ getErrors()
		{
			return errors; 
		}
		void setErrors(StringBuilder^ value)
		{ 
			errors = value; 
		}

		/*
		 * Tri topologique
		 */
	private:
		Hashtable^ visites;	
		void init_visites()
		{
			visites = gcnew Hashtable();
		}
	
		System::Collections::Generic::Stack<Sommet^>^ pile;
		Sommet^ depart;

	public:
		/// <summary>
		/// Effectue un tri topologique à partir des adjacences entre sommet (dépendances inverses)
		///	</summary>
		array<String^>^ TriTopologique()
		{			
			pile = gcnew System::Collections::Generic::Stack<Sommet^>();
			List<String^>^ plan = gcnew List<String^>();
			hasError = false;
			errors = gcnew StringBuilder();

			for (int i=0;i<g->Count;i++)
			{
				Sommet^s = g[i];

				init_visites();
				depart = s;

				// le tri est basé sur un parcours en profondeur d'abord
				parcours_profondeur(s);
			}

			while (pile->Count != 0)
				plan->Add(pile->Pop()->name);

			return plan->ToArray();
		}

	private:
		void parcours_profondeur(Sommet^ s)
		{
			if (s == nullptr)
				return;

			if (visites[s->name] != nullptr /*&& visites[s->name] is bool*/)
				return;
			else
				visites[s->name] = true;

			pile->Push(s);

			for(int i=0;i<s->adjacents->Count;i++)
			{
				Sommet^ adj=s->adjacents[i];
				if (adj == depart)
				{
					// déjà visité : erreur, graphe cyclique
					hasError = true;
					errors->Append("Référence circulaire sur " + depart->name + " : " + s->name + "\n");
					return;
				}

				parcours_profondeur(adj);
			}
		}

	};
}