using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Graphs;
using System.Collections;

namespace Matching
{
    public class BeamSearchGraphEditDistanceAC : IGraphMatching
    {
        /// <summary>
        /// List of the possible EditPaths
        /// </summary>
        private LinkedList<EditPathAC> OPEN; 

        /// <summary>
        /// Source Graph
        /// </summary>
        private Graph G1; //Graph 1	

        /// <summary>
        /// Target Graph
        /// </summary>
        private Graph G2; //Graph 2	

        /// <summary>
        /// Minimun cost path
        /// </summary>
        private EditPathAC MeilleurPath;

        /// <summary>
        /// Node being processed
        /// </summary>
        Node NoeudCourant;
   
        /// <summary>
        /// Constructor of the Edit Distance between two graphs
        /// </summary>
        /// <param name="g1">Graphe source</param>
        /// <param name="g2">Graphe cible</param>
        /// <param name="iNbCheminsMax">Maximun number of EditPathAC in the list OPEN (List of possible Paths) </param>
        public BeamSearchGraphEditDistanceAC(Graph g1, Graph g2, int iNbCheminsMax)
        {          
            // Initialisation des graphes
            this.G1 = g1;
            this.G2 = g2;


            /// Initialisation de la liste des chemins
            this.OPEN = new LinkedList<EditPathAC>();

            this.MeilleurPath = null;

            // On compte le nombre de noeuds des 2 graphes
            int iNbNoeudsG1 = G1.ListNodes.Count;
            int iNbNoeudsG2 = /*this.iTailleComplet =*/ G2.ListNodes.Count;

           
            // Dans la liste OPEN on met toutes les substitions de u1 avec tous les noeuds de g2.
            EditPathAC path = new EditPathAC(this.G1, this.G2);
            LinkedList<Node> lNoeudsNonUtilisesG2 = path.GetNoeudsNonUtiliseG2();
            this.NoeudCourant = path.getNoeudSuivant();
            foreach (Node w in lNoeudsNonUtilisesG2)
            {
                EditPathAC NouveauPath = new EditPathAC(path);
                /* Ajout de la distortion entre le noeud courant de u1 et chaque noeud de g2
			      la distortion représente une insertion ou une substitution mais pas une suppression */
                NouveauPath.AjoutDistortion(this.NoeudCourant, w);
                this.OPEN.AddLast(NouveauPath);
            }

          
            // On ajoute la suppression du premier Noeud de g1
            // On met dans OPEN une suppresion de u1. Dans le cas ou supprimer u1 serait une possibilité optimale.
            EditPathAC NouveauPath2 = new EditPathAC(path);
            GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
            EPS_COMPONENT.IsNode = true;
            NouveauPath2.AjoutDistortion(this.NoeudCourant, EPS_COMPONENT);
            OPEN.AddLast(NouveauPath2);

            MeilleurPath = this.CalculDistanceDedition(iNbCheminsMax); // boucle de calcul de la distance d'édition           
        }


        public BeamSearchGraphEditDistanceAC(int iNbCheminsMax)
        {
            this.K = iNbCheminsMax;
        }

        

        /// <summary>
        /// Loop calculating the edit distance
        /// </summary>
        /// <param name="iNbCheminsMax">Maximun number of EditPathAC in the list OPEN (List of possible Paths) </param>
        /// <returns>Minimun cost path</returns>
        private EditPathAC CalculDistanceDedition(int iNbCheminsMax)
        {
            do
            {
                //Tri par ordre croissant des path de OPEN pour appliquer la distance d'édition a des grands graphes
                List<EditPathAC> OPENTemp = new List<EditPathAC>();
                OPEN = new LinkedList<EditPathAC>(BeamSearchGraphEditDistanceAC.TriOrdreCroissant(OPEN, iNbCheminsMax));

                // On cherche dans OPEN le chemin avec le cout minimum (Pmin) et on le supprime
                EditPathAC Pmin = OPEN.ElementAt(0);
                //EditPathAC Pmin = CalculEditPathCoutMinimum(OPEN); 
                OPEN.Remove(Pmin);

                // Test si l'EditPathAC est un chemin complet
                if (Pmin.EstComplet())
                {
                    return Pmin;
                }
                else
                {
                    // K est l'index du noeud de G1 en cours de traitement. Premier coup, k=1. 
                    // Si on a traité  k < taille de G1
                   if (Pmin.GetNoeudsNonUtiliseG1().Count > 0)
                    {
                        this.NoeudCourant = Pmin.getNoeudSuivant();
                        // Pour chaque noeud de g2 qui n'ont pas encore étés associés, on insert dans OPEN la substitution noeud g1 -> noeud g2
                        LinkedList<Node> lNoeudsNonUtilisesG2 = Pmin.GetNoeudsNonUtiliseG2();

                        foreach (Node w in lNoeudsNonUtilisesG2)
                        {
                            EditPathAC NouveauPath = new EditPathAC(Pmin);
                            NouveauPath.AjoutDistortion(this.NoeudCourant, w);
                            this.OPEN.AddLast(NouveauPath);
                        }
                           
                        /*for (int iIndiceNoeud = 0; iIndiceNoeud < lNoeudsNonUtilisesG2.Count; iIndiceNoeud++)
                        {
                            EditPathAC NouveauPath = new EditPathAC(Pmin);
                            Node w = lNoeudsNonUtilisesG2.ElementAt(iIndiceNoeud);
                            NouveauPath.AjoutDistortion(this.NoeudCourant, w);
                            this.OPEN.AddLast(NouveauPath);
                        }*/

                        // On ajoute la suppression du premier Noeud de g1
                        EditPathAC NouveauPath2 = new EditPathAC(Pmin);
                        GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
                        EPS_COMPONENT.IsNode = true;
                        NouveauPath2.AjoutDistortion(this.NoeudCourant, EPS_COMPONENT);
                        OPEN.AddLast(NouveauPath2);
                        
                    }
                    else
                    {
                        //Sinon si k= taille de G1
                        //On met dans pmin toutes les insertions des noeuds  de G2  qui ne sont pas encore utilisés dans Pmin. 
                        //On remet Pmin dans OPEN
                        EditPathAC NouveauPath3 = new EditPathAC(Pmin);
                        NouveauPath3.complete();
                        OPEN.AddLast(NouveauPath3);   
                    }
                }

            } while (true);
        }

        /// <summary>
        /// Calculating the minimum cost EditPathAC
        /// </summary>
        /// <param name="OPEN2">List of Paths (EditPathAC)</param>
        /// <returns>minimum cost EditPathAC</returns>
        private EditPathAC CalculEditPathCoutMinimum(LinkedList<EditPathAC> OPEN2)
        {
            int i = 0;
            int iNbPaths = OPEN.Count;
            double dMinValue = Double.MaxValue;
            int iIndexMin = -1;
            for (i = 0; i < iNbPaths; i++)
            {
                EditPathAC p = OPEN.ElementAt(i);
                if (p.getCoutTotal() < dMinValue)
                {
                    dMinValue = p.getCoutTotal();
                    iIndexMin = i;
                }
            }
            return OPEN.ElementAt(iIndexMin);
        }

        /// <summary>
        /// Order the list in descending by the cost of the EditPathAC and delete all the EditPathAC after the index iKNbChemins
        /// </summary>
        /// <param name="OPEN">List of Paths (EditPathAC)</param>
        /// <param name="iKNbChemins"> Number of EdithPath to save in OPEN</param>
        /// <returns>The new list of EditPaths</returns>
        public static List<EditPathAC> TriOrdreCroissant(LinkedList<EditPathAC> OPEN, int iKNbChemins)
        { 
            List<EditPathAC> test = new List<EditPathAC>(OPEN);

            if (iKNbChemins < OPEN.Count)
            {           
                test.Sort();
                if (iKNbChemins != -1) test.RemoveRange(iKNbChemins, (test.Count - iKNbChemins));
               
            }
            return test;
        }



        public Dictionary<string, string> GraphMatching(Graph g1, Graph g2)
        {

            // Initialisation des graphes
            this.G1 = g1;
            this.G2 = g2;


            /// Initialisation de la liste des chemins
            this.OPEN = new LinkedList<EditPathAC>();

            this.MeilleurPath = null;

            // On compte le nombre de noeuds des 2 graphes
            int iNbNoeudsG1 = G1.ListNodes.Count;
            int iNbNoeudsG2 = /*this.iTailleComplet =*/ G2.ListNodes.Count;


            // Dans la liste OPEN on met toutes les substitions de u1 avec tous les noeuds de g2.
            EditPathAC path = new EditPathAC(this.G1, this.G2);
            LinkedList<Node> lNoeudsNonUtilisesG2 = path.GetNoeudsNonUtiliseG2();
            this.NoeudCourant = path.getNoeudSuivant();
            foreach (Node w in lNoeudsNonUtilisesG2)
            {
                EditPathAC NouveauPath = new EditPathAC(path);
                /* Ajout de la distortion entre le noeud courant de u1 et chaque noeud de g2
			      la distortion représente une insertion ou une substitution mais pas une suppression */
                NouveauPath.AjoutDistortion(this.NoeudCourant, w);
                this.OPEN.AddLast(NouveauPath);
            }


            // On ajoute la suppression du premier Noeud de g1
            // On met dans OPEN une suppresion de u1. Dans le cas ou supprimer u1 serait une possibilité optimale.
            EditPathAC NouveauPath2 = new EditPathAC(path);
            GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
            EPS_COMPONENT.IsNode = true;
            NouveauPath2.AjoutDistortion(this.NoeudCourant, EPS_COMPONENT);
            OPEN.AddLast(NouveauPath2);

            MeilleurPath = this.CalculDistanceDedition(K); // boucle de calcul de la distance d'édition 
            //return new Dictionary<string, string>(this.MeilleurPath.getDistortion());
           // return this.MeilleurPath.getDistortion().Cast<DictionaryEntry>().ToDictionary(kvp => (K)kvp.Key, kvp => (V)kvp.Value);
            Dictionary<string, string>  dict = new Dictionary<string, string>();
            foreach (GraphComponent key in this.MeilleurPath.getDistortion().Keys)
            {
                dict.Add(key.Id, ((GraphComponent)this.MeilleurPath.getDistortion()[key]).Id);
            }
            return dict;
        }

        public double GraphDistance(Graph g1, Graph g2)
        {
            // Initialisation des graphes
            this.G1 = g1;
            this.G2 = g2;


            /// Initialisation de la liste des chemins
            this.OPEN = new LinkedList<EditPathAC>();

            this.MeilleurPath = null;

            // On compte le nombre de noeuds des 2 graphes
            int iNbNoeudsG1 = G1.ListNodes.Count;
            int iNbNoeudsG2 = /*this.iTailleComplet =*/ G2.ListNodes.Count;


            // Dans la liste OPEN on met toutes les substitions de u1 avec tous les noeuds de g2.
            EditPathAC path = new EditPathAC(this.G1, this.G2);
            LinkedList<Node> lNoeudsNonUtilisesG2 = path.GetNoeudsNonUtiliseG2();
            this.NoeudCourant = path.getNoeudSuivant();
            foreach (Node w in lNoeudsNonUtilisesG2)
            {
                EditPathAC NouveauPath = new EditPathAC(path);
                /* Ajout de la distortion entre le noeud courant de u1 et chaque noeud de g2
			      la distortion représente une insertion ou une substitution mais pas une suppression */
                NouveauPath.AjoutDistortion(this.NoeudCourant, w);
                this.OPEN.AddLast(NouveauPath);
            }


            // On ajoute la suppression du premier Noeud de g1
            // On met dans OPEN une suppresion de u1. Dans le cas ou supprimer u1 serait une possibilité optimale.
            EditPathAC NouveauPath2 = new EditPathAC(path);
            GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
            EPS_COMPONENT.IsNode = true;
            NouveauPath2.AjoutDistortion(this.NoeudCourant, EPS_COMPONENT);
            OPEN.AddLast(NouveauPath2);

            MeilleurPath = this.CalculDistanceDedition(K); // boucle de calcul de la distance d'édition 
            return MeilleurPath.getCoutTotal();
        }

        public int K { get; set; }

        public Dictionary<Node, Node> getNodeMatching()
        {
            Dictionary<Node, Node> dict = new Dictionary<Node, Node>();
            foreach (GraphComponent key in this.MeilleurPath.getDistortion().Keys)
            {
                if(key.IsNode == true)
                     dict.Add((Node)key, ((Node)this.MeilleurPath.getDistortion()[key]));
            }
            return dict;
        }

        public double getCost()
        {
            return MeilleurPath.getCoutTotal();
        }

        public void Compute(Graph g1, Graph g2)
        {
            MeilleurPath = null;
              // Initialisation des graphes
            this.G1 = g1;
            this.G2 = g2;


            /// Initialisation de la liste des chemins
            this.OPEN = new LinkedList<EditPathAC>();

            this.MeilleurPath = null;

            // On compte le nombre de noeuds des 2 graphes
            int iNbNoeudsG1 = G1.ListNodes.Count;
            int iNbNoeudsG2 = /*this.iTailleComplet =*/ G2.ListNodes.Count;


            // Dans la liste OPEN on met toutes les substitions de u1 avec tous les noeuds de g2.
            EditPathAC path = new EditPathAC(this.G1, this.G2);
            LinkedList<Node> lNoeudsNonUtilisesG2 = path.GetNoeudsNonUtiliseG2();
            this.NoeudCourant = path.getNoeudSuivant();
            foreach (Node w in lNoeudsNonUtilisesG2)
            {
                EditPathAC NouveauPath = new EditPathAC(path);
                /* Ajout de la distortion entre le noeud courant de u1 et chaque noeud de g2
			      la distortion représente une insertion ou une substitution mais pas une suppression */
                NouveauPath.AjoutDistortion(this.NoeudCourant, w);
                this.OPEN.AddLast(NouveauPath);
            }


            // On ajoute la suppression du premier Noeud de g1
            // On met dans OPEN une suppresion de u1. Dans le cas ou supprimer u1 serait une possibilité optimale.
            EditPathAC NouveauPath2 = new EditPathAC(path);
            GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
            EPS_COMPONENT.IsNode = true;
            NouveauPath2.AjoutDistortion(this.NoeudCourant, EPS_COMPONENT);
            OPEN.AddLast(NouveauPath2);

            MeilleurPath = this.CalculDistanceDedition(K); // boucle de calcul de la distance d'édition 
        }

        public bool isOptimal()
        {
            if (this.K == -1)
            {
                return true;
            }
            return false;
        }
    }

    
}
