using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Drawing;
using System.Data;
using System.Text;
using System.Windows.Forms;

using FactorsNamespace;

namespace CodeGenerator
{
	public class FactorGraph
	{
		enum TypeOfFactor
		{
			Unvisited,
			Visited,
			InProgress
		}

		#region private variables

		private List<FutureFactor> factorsList;
		private List<FutureFactor> independentFactorsList;
		private bool isTheGraphMade;

		private Dictionary<FutureFactor, List<FutureFactor>> factor2itsDependent;

    /// <summary>
    /// needed for DFS
    /// </summary>
		private Dictionary<FutureFactor, TypeOfFactor> factor2StatusDict;

    /// <summary>
		/// result <b>REVERSE</b> sorted array of factorsList
    /// </summary>
		private List<FutureFactor> resultOrderOfFactors;

		#endregion

		/// <summary>
		/// Depth-first search.
		/// </summary>
		/// <param name="factor">Start factor to search</param>
		/// <returns>Returns true if there are no cicles</returns>
		private bool DFS(FutureFactor factor)
		{
			//
			factor2StatusDict[factor] = TypeOfFactor.InProgress;
			foreach (FutureFactor fDeps in factor2itsDependent[factor])
			{
				TypeOfFactor curType = (TypeOfFactor)factor2StatusDict[fDeps];
				if (curType == TypeOfFactor.InProgress)
				{
					return false;
				}
				DFS(fDeps);
			}
			factor2StatusDict[factor] = TypeOfFactor.Visited;
			//
			resultOrderOfFactors.Add(factor);
			return true;
		}


		/// <summary>
		/// It is <b>true</b> if the graph was made
		/// </summary>
		public bool IsTheGraphMade
		{
			get { return isTheGraphMade; }
		}
		
		public List<FutureFactor> GetSorted() 
    {
			List<FutureFactor> res = new List<FutureFactor>(resultOrderOfFactors);
			res.Reverse();
			return res;
    }

    public void Init(List<FutureFactor> factors)
    {
      this.factorsList = factors;
      independentFactorsList = new List<FutureFactor>();
      factor2itsDependent = new Dictionary<FutureFactor,List<FutureFactor>>();
			isTheGraphMade = false;

			resultOrderOfFactors = new List<FutureFactor>();
    }

    /// <summary>
    /// Makes calculating graph of factorsList on "factor" array
    /// </summary>
    /// <returns>true - if exist right oriented graph, false - else</returns>
    public bool MakeGraph()
    {
      independentFactorsList = new List<FutureFactor>(factorsList);

      List<FutureFactor> tempDependentArray;
      foreach (FutureFactor fMain in factorsList)
      {
        tempDependentArray = new List<FutureFactor>();

        foreach (FutureFactor fDependent in factorsList)
        {
          if (fMain == fDependent)
          {
            if (fMain.IsSelfDependent())
            {
              throw new GraphException(GraphException.GraphExceptionType.SelfDependentFactor);
            }
          }
          if (fDependent.IsDependentFrom(fMain.Name))
          {
            independentFactorsList.Remove(fDependent);
            tempDependentArray.Add(fDependent);
          }
        }
        factor2itsDependent[fMain] = tempDependentArray;
      }


      //
      factor2StatusDict = new Dictionary<FutureFactor,TypeOfFactor>();
      foreach (FutureFactor f in factorsList)
      {
        //
        factor2StatusDict[f] = TypeOfFactor.Unvisited;
      }
      bool res = true;
      foreach(FutureFactor f in independentFactorsList)
      {
        res &= DFS(f);
      }

      if(resultOrderOfFactors.Count != factorsList.Count)
      {
        throw new GraphException(GraphException.GraphExceptionType.NoBaseFactors);
      }

      return res;
    }
	}
}
