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


using Graphs;

namespace Matching
{
    public class EditPathAC : IComparable
    {

        /// <summary>
        /// source graphe
        /// </summary>
        private Graph gSource;

        /// <summary>
        /// Target graphe
        /// </summary>
        private Graph gCible;

        /// <summary>
        /// Distortions table
        /// </summary>
        private Hashtable   Distortions;

        /// <summary>
        /// total cost of the EditPathAC
        /// </summary>
        private double      dCoutTotal;

        /// <summary>
        /// List of unused nodes of the source graphe
        /// </summary>
        private LinkedList<Node> lNoeudsNonUtiliseG1;

        /// <summary>
        /// List of unused nodes of the target graphe
        /// </summary>
        private LinkedList<Node> lNoeudsNonUtiliseG2;

        /// <summary>
        /// List of unused edges of the source graphe
        /// </summary>
        private LinkedList<Edge> lArcsNonUtiliseG1;

        /// <summary>
        /// List of unused edges of the target graphe
        /// </summary>
        private LinkedList<Edge> lArcsNonUtiliseG2;
        private static NodeLabelDistanceEditionAC nodeepslabel;
        private static EdgeLabelDistanceEditionAC edgeepslabel;

        /// <summary>
        /// Constructor of the Edit Path. Initialize the members
        /// </summary>
        /// <param name="G1">Graph source</param>
        /// <param name="G2">Graph target</param>
        public EditPathAC(Graph G1, Graph G2)
        {
		    this.init();
            nodeepslabel = new NodeLabelDistanceEditionAC();
            nodeepslabel.Id = ConstantsAC.EPS_ID;

            edgeepslabel = new EdgeLabelDistanceEditionAC();
            edgeepslabel.Id = ConstantsAC.EPS_ID;

		    this.gSource = G1;
	    	this.gCible = G2;

            for(int i = 0 ; i != G1.ListNodes.Count; i++)
            {
		        this.lNoeudsNonUtiliseG1.AddLast(G1.ListNodes[i]);
            }
            for(int i = 0 ; i != G2.ListNodes.Count; i++)
            {
		        this.lNoeudsNonUtiliseG2.AddLast(G2.ListNodes[i]);
            }
            for (int i = 0; i != G1.ListEdges.Count; i++)
            {
                this.lArcsNonUtiliseG1.AddLast(G1.ListEdges[i]);
            }
            for (int i = 0; i != G2.ListEdges.Count; i++)
            {
                this.lArcsNonUtiliseG2.AddLast(G2.ListEdges[i]);
            }
	    }

        /// <summary>
        /// Constructor of the Edit Path. Initialize the members
        /// </summary>
        /// <param name="Ep">Edit path to add to the new EditPathAC</param>
        public EditPathAC(EditPathAC Ep)
        {
            this.init();
            this.gSource = Ep.getGraphSource();
            this.gCible  = Ep.getGraphCible();

            for (int i = 0; i != Ep.GetNoeudsNonUtiliseG1().Count; i++)
            {
                this.lNoeudsNonUtiliseG1.AddLast(Ep.GetNoeudsNonUtiliseG1().ElementAt(i));
            }

            for (int i = 0; i != Ep.GetNoeudsNonUtiliseG2().Count; i++)
            {
                this.lNoeudsNonUtiliseG2.AddLast(Ep.GetNoeudsNonUtiliseG2().ElementAt(i));
            }

            for (int i = 0; i != Ep.GetArcsNonUtiliseG1().Count; i++)
            {
                this.lArcsNonUtiliseG1.AddLast(Ep.GetArcsNonUtiliseG1().ElementAt(i));
            }

            for (int i = 0; i != Ep.GetArcsNonUtiliseG2().Count; i++)
            {
                this.lArcsNonUtiliseG2.AddLast(Ep.GetArcsNonUtiliseG2().ElementAt(i));
            }
          
            this.dCoutTotal = Ep.getCoutTotal();

            this.Distortions = (Hashtable)Ep.getDistortion().Clone();
            
        }

        /// <summary>
        /// Initialization of the members. This method is called by the constructors
        /// </summary>
        private void init() 
        {
		    this.lNoeudsNonUtiliseG1 = new LinkedList<Node>();
		    this.lNoeudsNonUtiliseG2 = new LinkedList<Node>();
            this.lArcsNonUtiliseG1 = new LinkedList<Edge>();
            this.lArcsNonUtiliseG2 = new LinkedList<Edge>();
            this.Distortions = new Hashtable();
		    this.dCoutTotal = 0.0;
           
	    }

        /// <summary>
        /// Add a new row in the distortions table
        /// </summary>
        /// <param name="gc1">GraphComponent of the source graph to add in the distortions table</param>
        /// <param name="gc2">GraphComponent of the targeted graph to add in the distortions table</param>
        public void AjoutDistortion(GraphComponent gc1, GraphComponent gc2)
        {
            if (gc1.Id == ConstantsAC.EPS_ID){

                if (gc2.IsNode == true && gc1.IsNode == true)
                {
                    this.dCoutTotal += nodeepslabel.dissimilarity(gc2.Label);
                }

                if (gc2.IsNode == false && gc1.IsNode == false)
                {
                    this.dCoutTotal += edgeepslabel.dissimilarity(gc2.Label);
                }
                
            }

            if (gc2.Id == ConstantsAC.EPS_ID) {
       
                //this.dCoutTotal += gc1.Label.dissimilarity(epslabel);

                if (gc2.IsNode == true && gc1.IsNode == true)
                {
                    this.dCoutTotal += gc1.Label.dissimilarity(nodeepslabel);
                }

                if (gc2.IsNode == false && gc1.IsNode == false)
                {
                    this.dCoutTotal += gc1.Label.dissimilarity(edgeepslabel);
                }

            }
            if (gc1.Id != ConstantsAC.EPS_ID && gc2.Id != ConstantsAC.EPS_ID) this.dCoutTotal += gc1.Label.dissimilarity(gc2.Label);
            this.Distortions.Add(gc1, gc2);

            //si noeud gc1 et gc2
            if (gc1.IsNode == true && gc2.IsNode == true)
            {
                if (gc1.Id != ConstantsAC.EPS_ID) this.lNoeudsNonUtiliseG1.Remove((Node)gc1);    
                this.handleEdges(this, gc1, gc2);
                if (gc2.Id != ConstantsAC.EPS_ID) this.lNoeudsNonUtiliseG2.Remove((Node)gc2);
                
            }
            else
            {
                //arc
                if (gc1.Id != ConstantsAC.EPS_ID) this.lArcsNonUtiliseG1.Remove((Edge)gc1);
                if (gc2.Id != ConstantsAC.EPS_ID) this.lArcsNonUtiliseG2.Remove((Edge)gc2);
            }
        }

        /// <summary>
        /// Get the next node in the list of unused Nodes of the souce graph
        /// </summary>
        /// <returns>The next Node to process</returns>
        public Node getNoeudSuivant()
        {
		    return this.lNoeudsNonUtiliseG1.First.Value;
	    }

        /// <summary>
        /// Return the total cost of an EditPathAC
        /// </summary>
        /// <returns>The total cost</returns>
        public double getCoutTotal()
        {
		    return dCoutTotal;
	    }

        /// <summary>
        /// Complete the distortion table with the unused nodes of the targeted graph
        /// </summary>
        public void complete()
        {
            LinkedList<Node> lTempNodes = new LinkedList<Node>();
            lTempNodes = this.lNoeudsNonUtiliseG2;
            for(int i = 0; i < lTempNodes.Count; i++)
            {
                Node w = lTempNodes.ElementAt(i);
                GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
                EPS_COMPONENT.IsNode = true;
                this.AjoutDistortion(EPS_COMPONENT, w);
            }
        }

        // Retourne vrai si le chemin est complet
        public Boolean EstComplet()
        {
            int iNbNoeudsRestants = this.lNoeudsNonUtiliseG1.Count;
		    iNbNoeudsRestants += this.lNoeudsNonUtiliseG2.Count;
		    return (iNbNoeudsRestants == 0);
        }

        /// <summary>
        /// Return the list of the unused nodes of the source graph
        /// </summary>
        /// <returns>List of the unused nodes of the source graph</returns>
        public LinkedList<Node> GetNoeudsNonUtiliseG1()
        {
            return this.lNoeudsNonUtiliseG1;
        }

        /// <summary>
        /// Return the list of the unused nodes of the targeted graph
        /// </summary>
        /// <returns>List of the unused nodes of the targeted graph</returns>
        public LinkedList<Node> GetNoeudsNonUtiliseG2()
        {
            return this.lNoeudsNonUtiliseG2;
        }

        /// <summary>
        /// Return the list of the unused edges of the source graph
        /// </summary>
        /// <returns>List of the unused edges of the source graph</returns>
        public LinkedList<Edge> GetArcsNonUtiliseG1()
        {
            return this.lArcsNonUtiliseG1;
        }

        /// <summary>
        /// Return the list of the unused edges of the targeted graph
        /// </summary>
        /// <returns>List of the unused edges of the targeted graph</returns>
        public LinkedList<Edge> GetArcsNonUtiliseG2()
        {
            return this.lArcsNonUtiliseG2;
        }

        /// <summary>
        /// Return the source graph
        /// </summary>
        /// <returns>the source graph</returns>
        public Graph getGraphSource()
        {
            return(this.gSource);
        }

        /// <summary>
        /// Return the targeted graph
        /// </summary>
        /// <returns>the targeted graph</returns>
        public Graph getGraphCible()
        {
            return(this.gCible);
        }

        /// <summary>
        /// Return the Distortions table
        /// </summary>
        /// <returns>the Distortions table</returns>
        public Hashtable getDistortion()
        {
            return (this.Distortions);
        }

        /// <summary>
        /// Get the incoming Edges of the node n in the list edg
        /// </summary>
        /// <param name="n">Node to be analized</param>
        /// <param name="edg">List of the incoming Edges</param>
        public void getArcEntrants(Node n, LinkedList<Edge> edg)
        {          
            int iNbArcsEntrants = n.ListEdgesIn.Count;
            for (int iIndiceArcsEntrants = 0; iIndiceArcsEntrants != iNbArcsEntrants; iIndiceArcsEntrants++)
            {
                edg.AddLast(n.ListEdgesIn[iIndiceArcsEntrants]);
            }         
        }

        /// <summary>
        /// Get the outgoing Edges of the node n in the list edg
        /// </summary>
        /// <param name="n">Node to be analized</param>
        /// <param name="edg">List of the outgoing Edges</param>
        public void getArcSortants(Node n, LinkedList<Edge> edg)
        {       
            int iNbArcsSortants = (n.ListEdgesOut.Count);
            for (int iIndiceArcsSortants = 0; iIndiceArcsSortants != iNbArcsSortants; iIndiceArcsSortants++)
            {
                edg.AddLast(n.ListEdgesOut[iIndiceArcsSortants]);
            }   
        }

        /// <summary>
        /// handles the edge operations
        /// </summary>
        /// <param name="p">Edit Path to be handle</param>
        /// <param name="u_start">GraphComponent to handle </param>
        /// <param name="u_end">GraphComponent to handle</param>
        public void handleEdges(EditPathAC p, GraphComponent u_start, GraphComponent u_end)
        {
            /**
             * node deletion
            */
            if (u_end.Id == ConstantsAC.EPS_ID)
            {
                // Récupération des arcs entrant et sortants du noeud u_start
                LinkedList<Edge> edges = new LinkedList<Edge>();
                getArcEntrants((Node)u_start, edges);
                getArcSortants((Node)u_start, edges);

                Node v;
                for (int i = 0; i < edges.Count; i++)
                {
                    Edge e = (Edge)edges.ElementAt(i);
                    //other pense bete
                    v = e.getOtherNode((Node)u_start);                                                                                                       //A vérifier !!!!
                    //si noeud cibe de g1 est déja utilisé alors on surpprime l'arc
                    if (!p.GetNoeudsNonUtiliseG1().Contains(v))
                    {
                        GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
                        EPS_COMPONENT.IsNode = false;
                        p.AjoutDistortion(e, EPS_COMPONENT);
                    }
                }
            }
            /**
             * node insertion
             */
            if (u_start.Id ==  ConstantsAC.EPS_ID)
            {
                // Récupération des arcs entrant et sortants du noeud u_end
                LinkedList<Edge> edges = new LinkedList<Edge>();
                getArcEntrants((Node)u_end, edges);
                getArcSortants((Node)u_end, edges);

                Node v;
                for (int i = 0; i < edges.Count; i++)
                {
                    Edge e = (Edge)edges.ElementAt(i);
                    v = e.getOtherNode((Node)u_end);                                                                                                       //A vérifier !!!!
                    //si noeud cibe de g2 est déja utilisé alors on surpprime l'arc
                    if (!p.GetNoeudsNonUtiliseG2().Contains(v))
                    {
                        GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
                        EPS_COMPONENT.IsNode = false;
                        p.AjoutDistortion(EPS_COMPONENT, e);
                    }
                }
            }
            /**
             * node substitution
             */
            if (u_end.Id != ConstantsAC.EPS_ID && u_start.Id != ConstantsAC.EPS_ID)
            {
                // on récupère tous les arcs du noeud de G1
                // Récupération des arcs entrant et sortants du noeud u_start
                LinkedList<Edge> edges = new LinkedList<Edge>();
                getArcEntrants((Node)u_start, edges);
                getArcSortants((Node)u_start, edges);

                GraphComponent v_start;
                GraphComponent v_end;

                // pour tous les arcs du noeud de G1
                for (int i = 0; i < edges.Count; i++)
                {
                    //on récupère l'arc courant dans g1
                    Edge e_start = (Edge)edges.ElementAt(i);
                    //on récupère le noeud cible dans g1 de l'arc courant
                    v_start = e_start.getOtherNode((Node)u_start);                                                                           //A VERIFIER

                    //Si la distortion sur les noeuds a déja été faite alors on peut s'attaquer aux arcs 
                    if (p.getDistortion().ContainsKey(v_start))
                    {
                        //on récupère le noeud appareillé dans g2 (vstart est apparaillé avec vend).
                        //vend est un noeud de g2
                        v_end = (GraphComponent)p.getDistortion()[v_start];
                        //si le noeud vend  de g2 doit être détruit alors on détruit l'arc aussi
                        if (v_end.Id == ConstantsAC.EPS_ID)
                        {
                            GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
                            EPS_COMPONENT.IsNode = false;
                            p.AjoutDistortion(e_start, EPS_COMPONENT);
                        }
                        else
                        {
                            //si le noeud vend de g2  doit être substitué alors l'arc aussi
                            //on récupère l'arc entre les deux noeuds de g2 uend et vend
                            Edge e_end = getEdgeBetween((Node)u_end, v_end);
                            if (e_end != null)
                            {
                                p.AjoutDistortion(e_start, e_end);
                            }
                            else
                            {
                                //Il n'y a pas d'arc entre les noeud du graphe g2 alors on supprime l'arc dans g1
                                //entre uend et vend il n'y a pas d'arc alors en surpprime l'arc entre ustart et vstart
                                GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
                                EPS_COMPONENT.IsNode = false;
                                p.AjoutDistortion(e_start, EPS_COMPONENT);
                            }
                        }
                    }
                }

                //on récupère tous les arcs du noeud de G2
                getArcEntrants((Node)u_end, edges);
                getArcSortants((Node)u_end, edges);

                Edge e_start2;
                //	pour tous les arcs du noeud de G2
                for (int i = 0; i < edges.Count; i++)
                {
                    //on récupère l'arc courant dans g2
                    Edge e_end = (Edge)edges.ElementAt(i);
                    //on récupère le noeud cible dans g2
                    v_end = e_end.getOtherNode((Node)u_end);                                                                                                     //A VERIFIER
                    //on regarde si le noeud cible a été appareillé avec un noeud de un noeud de g1
                    if (p.getDistortion().ContainsValue(v_end))
                    {
                        //on récupère le noeud appareillé de g1
                        //annuaire inversé des distortions
                        Hashtable distor = p.getDistortion();
                        v_start = (GraphComponent)this.LookupFirstKey(distor, v_end);
                        //v_start = (GraphComponent)p.getDistortion()[v_end];                                                                         //A VERIFIER
                        //on récupère l'arc du noeud de g1
                        e_start2 = getEdgeBetween((Node)u_start, v_start);

                        //si il n'y a pas d'arc entre les deux noeuds de g1
                        //entre vend et uend il y a une arc mais entre ustart et vstart ll n'y en pas 
                        //alors on insère un arc entre vstart et ustart
                        if (e_start2 == null)
                        {
                            //on fait une insertion d'un arc dans g1.
                            GraphComponent EPS_COMPONENT = new GraphComponent(ConstantsAC.EPS_ID);
                            EPS_COMPONENT.IsNode = false;
                            p.AjoutDistortion(EPS_COMPONENT, e_end);
                        }
                    }
                }

            }
        }

        /// <summary>
        /// Return an edge between a node and a graphComponent (node or epsilon)
        /// </summary>
        /// <param name="n1">Node to be analized</param>
        /// <param name="u_start">GraphComponent to be analized</param>
        private Edge getEdgeBetween(Node n1, GraphComponent n2)
        {
            // Récupération des arcs entrant et sortants du noeud n1
            LinkedList<Edge> edges = new LinkedList<Edge>();
            getArcEntrants(n1, edges);
            getArcSortants(n1, edges);

            Node temp;
            for (int i = 0; i < edges.Count; i++)
            {
                Edge e = edges.ElementAt(i);
                temp =e.getOtherNode(n1);
                //temp = e.NodeTarget; // A VERIFIER
                if (temp == n2)
                {
                    return e;
                }
            }
            return null;
        }

        /// <summary>
        /// Return a value used to sort the list oh Edit Path (OPEN)
        /// </summary>
        /// <param name="obj">EditPathAC to be analized</param>
        int IComparable.CompareTo(object obj)
        {  
            EditPathAC ep = (EditPathAC)obj;
            double hp1, hp2;
            hp1 = this.ComputeHeuristic();
            hp2 = ep.ComputeHeuristic();
            int iRetour = 0;
            if ((this.dCoutTotal + hp1) > (ep.getCoutTotal() + hp2))
            {
                iRetour = 1;
            }
            else
                if ((this.dCoutTotal + hp1) < (ep.getCoutTotal() + hp2))
                {
                    iRetour = -1;
                }
                else
                    if ((this.dCoutTotal + hp1) == (ep.getCoutTotal() + hp2))
                    {
                        iRetour = 0;
                    }

            return iRetour;
        }

        double ComputeHeuristic()
        {
            double hp = 0;
            int nbinsertion = 0;
            int nbdeletion = 0;
            int n1, n2;
            n1 = this.GetNoeudsNonUtiliseG1().Count;
            n2 = this.GetNoeudsNonUtiliseG2().Count;
            nbdeletion = Math.Max(0, (n1 - n2));
            nbinsertion = Math.Max(0, (n2 - n1));
            for (int i = 0; i < nbdeletion; i++)
            {
                hp+=this.GetNoeudsNonUtiliseG1().ElementAt(0).Label.dissimilarity(nodeepslabel);
            }

            for (int i = 0; i < nbinsertion; i++)
            {
                hp += nodeepslabel.dissimilarity(this.GetNoeudsNonUtiliseG2().ElementAt(0).Label);
               
            }


            ///edge////
            n1 = this.GetArcsNonUtiliseG1().Count;
            n2 = this.GetArcsNonUtiliseG2().Count;
            nbdeletion = Math.Max(0, (n1 - n2));
            nbinsertion = Math.Max(0, (n2 - n1));
            for (int i = 0; i < nbdeletion; i++)
            {
                hp += this.GetArcsNonUtiliseG1().ElementAt(0).Label.dissimilarity(edgeepslabel);
            }

            for (int i = 0; i < nbinsertion; i++)
            {
                hp += edgeepslabel.dissimilarity(this.GetArcsNonUtiliseG2().ElementAt(0).Label);

            }

            return hp;
        }

            Object LookupFirstKey(Hashtable table, Object value) {
                foreach (DictionaryEntry e in table)
                    if (object.Equals(e.Value, value))
                        return e.Key;

                return null;
                       
            }

    }


} 
