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


namespace Matching
{
    /// <summary>
    /// L'arbre de recherche est un graphe qui est toujours orienté.
    /// </summary>
    public class SearchTree : Graph
    {

        /// <summary>
        /// Utilise le constructeur Graph() mais reparamètre IsDirected à true.
        /// </summary>
        public SearchTree() : base()
        {
            IsDirected = true;
            ListNodes.Add(new Node("_root"));
        }

        /// <summary>
        /// Utilise le constructeur Graph() mais reparamètre IsDirected à true.
        /// </summary>
        /// <param name="id">Identifiant du graphe</param>
        /// <param name="name">Nom du graphe</param>
        public SearchTree(string id, String name): base()
        {
            this.Id = id;
            this.Name = name;
            IsDirected = true;
            ListNodes.Add(new Node("_root"));
        }

        /// <summary>
        /// On ajoute le graphe à l'arbre de recherche. 
        /// </summary>
        /// <param name="graph">Graphe à ajouter à l'arbre de recherche.</param>
        public void addGraph(Graph graph)
        {
            //Construction de la matrice de Label
            Label[,] matrixLabel = calculateMatrixLabel(graph);

            //Construction de la liste d'indices
            int[] inputSet = new int[graph.ListNodes.Count];
            for (int i = 0; i < graph.ListNodes.Count; i++) inputSet[i] = i;

            //Calcul de toutes les permutations de cette liste d'indice
            Permutations<int> permutations = new Permutations<int>(inputSet);


            int nbPerm = 0;
           // GraphSpeedTest speed = new GraphSpeedTest();
		    //speed.StartChrono();
            //Pour chaque permutation on calcule la matrice qui lui est associé
            foreach (IList<int> p in permutations)
            {
				nbPerm++;
                //Création de la matrice de permutation
                Label[,] permutationMatrixTemp = new Label[graph.ListNodes.Count, graph.ListNodes.Count];
                Label[,] permutationMatrix = new Label[graph.ListNodes.Count, graph.ListNodes.Count];
                
                //On inverse les colonnes par rapport à matrixLabel
                for (int indiceColonne = 0; indiceColonne < graph.ListNodes.Count; indiceColonne++)
                {
                    for (int indiceLigne = 0; indiceLigne < graph.ListNodes.Count; indiceLigne++)
                    {
                        
                        permutationMatrixTemp[indiceLigne, indiceColonne] = matrixLabel[indiceLigne, p.ElementAt(indiceColonne)];
                    }
                }

                //Maintenant on inverse toutes les lignes
                for (int indiceLigne = 0; indiceLigne < graph.ListNodes.Count; indiceLigne++)
                {
                    for (int indiceColonne = 0; indiceColonne < graph.ListNodes.Count; indiceColonne++)
                    {
                        permutationMatrix[indiceLigne, indiceColonne] = permutationMatrixTemp[p.ElementAt(indiceLigne), indiceColonne];
                    }
                }


                //A partir de cette matrice de Label on construit la liste de Labels. Chaque élément de la liste contient 
                //les labels de la forme canonique.
                List<Labels> listLabels = calculateListLabels(permutationMatrix, graph.ListNodes.Count);

                //On se positionne sur le root
                Node noeudCourant = ListNodes.ElementAt(0);

                //Permet de savoir si  le noeud qu'on veut ajouter existe déjà ou pas
                Boolean noeudExistant;


                //On parcourt listLabels pour ajouter chaque Labels de la liste à un noeud de l'arbre
                for (int indexLabels = 0; indexLabels < listLabels.Count; indexLabels++)
                {
                    noeudExistant = false;
                    //Si un fils a une dissimilarité de zéro avec notre Labels alors on se positionne sur celui-ci
                    foreach (Edge edge in noeudCourant.ListEdgesOut)
                    {
                        if (edge.NodeTarget.Label.dissimilarity(listLabels.ElementAt(indexLabels)) == 0)
                        {
                            noeudCourant = edge.NodeTarget;
                            noeudExistant = true;
                            break;
                        }
                    }

                    //Si le noeud courant n'a pas de fils ou que les fils ont une dissimilarité != 0 alors on ajoute tout le reste de la liste
                    if (noeudExistant == false || (noeudCourant.ListEdgesOut.Count == 0 && noeudExistant == false))
                    {
                        while (indexLabels < listLabels.Count)
                        {
                            //Ajout du noeud et de l'arc entre noeudCourant et nouveauNoeud
                            Node nouveauNoeud = new Node("_" + nbPerm.ToString() + "-" +graph.ListNodes[p.ElementAt(indexLabels)].Id); //graph.ListNodes[p.ElementAt(indexLabels)].Id
                            nouveauNoeud.Label = listLabels.ElementAt(indexLabels);
                            Edge nouveauEdge = new Edge(noeudCourant, nouveauNoeud, null);
                            addNode(nouveauNoeud);
                            addEdge(nouveauEdge);

                            noeudCourant = nouveauNoeud;
                            indexLabels++;
                        }
                    }
                }

                 /*if (nbPerm == 10000)
                {


                    /*speed.StopChrono();
                    using (System.IO.StreamWriter file = new System.IO.StreamWriter("speedWriteText.txt", true))
                    {
                        file.WriteLine("10000 ajout de matrice de perm en "+speed.DisplayElapsedTime());

                    }
                }*/

			//next permutation
            }//fin for toutes les permutations

           
        }

        /// <summary>
        /// Calcule la matrice de Label du graphe. Les Label de noeuds sont présents sur la diagonale. 
        /// </summary>
        /// <param name="graph">Graphe pour lequel la matrice de Label sera retournée</param>
        /// <returns>Matrice de Label du Graphe </returns>
        public Label[,] calculateMatrixLabel(Graph graph)
        {
            /////////////////////////////////
            //On peut améliorer ça en faisant qu'une moitié quand c'est non orienté
            //////////////////


            //Représente la matrice d'adjacence contenant les attributs
            Label[,] tabLabel = new Label[graph.ListNodes.Count, graph.ListNodes.Count];

            //Gestion des unlabel
            for (int i = 0; i < graph.ListNodes.Count; i++)
            {
                for (int j = 0; j < graph.ListNodes.Count; j++) tabLabel[i, j] = new UnLabel();
            }

            //On ajoute le Label à la matrice
            for (int i = 0; i < graph.ListNodes.Count; i++)
            {
                for (int j = 0; j < graph.ListNodes.Count; j++)
                {
                    //On ajoute le label des noeuds sur la diagonale
                    if (i == j)
                    {
                        tabLabel[i, j] = graph.ListNodes.ElementAt(i).Label;
                    }

                    // On ajoute le Label qu'il y a sur les Edge
                    else
                    {
                        //On parcours les Edge du noeud i
                        foreach (Edge edge in graph.ListNodes.ElementAt(i).ListEdgesOut)
                        {
                            //Si le noeud j est le noeud destination du noeud i alors on ajoute le Label
                            if (edge.NodeTarget == graph.ListNodes.ElementAt(j))
                            {
                                tabLabel[i, j] = edge.Label;

                                if (!graph.IsDirected) tabLabel[j, i] = edge.Label;
                            }

                        }
                    }
                }
            }

            return tabLabel;
        }

        /// <summary>
        /// Récupère les formes canoniques de la matrice de Label sous forme de Labels et retourne ces Label sous une liste dans l'ordre d'exploration de l'arbre.
        /// </summary>
        /// <param name="matrixLabel">Matrice de Label.</param>
        /// <param name="nbNode">Nombre de noeud du graphe qui est la taille de matrixLabels.</param>
        /// <returns></returns>
        public List<Labels> calculateListLabels(Label[,] matrixLabel, int nbNode)
        {
            List<Labels> listLabels = new List<Labels>();

            //Il y a N Labels
            for(int indiceLabel = 0; indiceLabel < nbNode;indiceLabel++)
            {
                listLabels.Add(new Labels());

                //On ajoute la partie horizontale 
                for (int indiceHorizontal = 0; indiceHorizontal <= indiceLabel; indiceHorizontal++)
                {
                    listLabels.ElementAt(indiceLabel).ListLabels.Add(matrixLabel[indiceLabel,indiceHorizontal]);
                }

                //On ajoute la partie vertical en remontant
                for (int indiceVertical = indiceLabel-1; indiceVertical >= 0; indiceVertical--)
                {
                    listLabels.ElementAt(indiceLabel).ListLabels.Add(matrixLabel[indiceVertical, indiceLabel]);
                }
            }

            return listLabels;
        }

        /// <summary>
        /// Permet de charger les Node.Label depuis les Node.AttributesGXL. 
        /// Contrairement à Graph.attributesToLabel ici seuls les labelNode sont nécessaires puisque 
        /// l'arbre de recherche ne possède pas d'attributs sur les arcs.
        /// </summary>
        /// <param name="labelNode">Label qui est utilisé pour les noeuds du graphe. Les Labels de l'arbre de recherche contiendra des Label du type de labelNode.
        /// La valeur du Label n'est pas importante, seul le type du Label est utilisé.</param>
        public void attributesToLabelTree(Label labelNode,Label labelEdge)
        {
            //Récupération des types de Label
            Type typeNode = labelNode.GetType();
            Type typeEdge = labelEdge.GetType();

            

                //Pour tous les noeuds, on charge les Label à partir des attributs, et on les mets dans un Labels
                foreach (Node n in ListNodes)
                {
                    List<int> listIndiceUnlabel = new List<int>();
                    //Comptage du nombre de Label dans Labels pour déclarer tous les Label dans Labels.listLabels
                    int nbLabel = 0;
                    foreach (AttributeGXL attr in n.AttributesGXL)
                    {
                        if (attr.Name == "Labels") nbLabel++;
                        if (attr.Name == "UnLabel") listIndiceUnlabel.Add(nbLabel);
                    }

                    n.Label = new Labels();

                    //On créer tous les Label de Labels
                    for (int i = 1; i <= nbLabel; i++)
                    {
                        //Label créé à partir du type du Label
                        object obj;

                        if (listIndiceUnlabel.Contains(i)) obj = new UnLabel();
                        //Les label node se trouve au milieu de la liste de label
                        else if(i==nbLabel/2+1) obj = Activator.CreateInstance(typeNode);

                        //Tous les autres Label sont des labelEdge
                        else obj = Activator.CreateInstance(typeEdge);

                        ((Labels)n.Label).ListLabels.Add((Label)obj);
                    }

                    if (n.AttributesGXL.Count > 0) n.Label.fromAttributes(n.AttributesGXL);
            }
        }
    }
}
