/*
Copyright 2005-2013 Samuel Gesche

This file is part of ArcEnCiel.

ArcEnCiel is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

ArcEnCiel is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with ArcEnCiel.  If not, see <http://www.gnu.org/licenses/>.
*/

package ihm.townto;

import ihm.Charte;

import java.awt.Color;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
import java.util.Vector;

/**
 * Cette classe fournit une structure de stockage pour les graphes "graphiques"
 * (ceux qui vont être dessinés dans un GraphPanel). Pour la structure
 * "logique", voir la classe Graphe.<br>
 * Cette classe est à remplissage progressif, c'est-à-dire que l'on utilise les
 * méthodes setActive et addLink pour rajouter des noeuds et des liens. L'ajout
 * se fait de la manière suivante : on rajoute un noeud principal, puis des
 * liens entre les noeuds existants et d'autres noeuds.<br>
 * Le graphe stocké dans cette classe a trois composantes : le centre et deux
 * couronnes.<br>
 *
 * @author Samuel GESCHE
 * @version 4.0.1
 * @since 3.0.0
 * @see data.Graphe
 */

public class Graph {
    protected Node activeConcept;
    protected Vector firstCrown;
    protected Vector secondCrown;
    protected Vector links;
    protected int maxIdCrown1 = 1;
    protected int maxIdCrown2 = 1;
    protected final static int MAX_NODES_1 = 30;
    protected final static int MAX_NODES_2 = 30;
    protected int maxParCour1 = 10;
    protected boolean suppr = false;

    /**
     * Crée un graphe vide.
     * @since 3.0.1
     */
    public Graph() {
        setActive("", "");
        suppr = false;
    }

    /**
     * Renvoie le nombre maximal de noeuds qui peuvent être affichés par ce
     * graphe.
     * @return int le nombre en question
     * @since 3.0.0
     */
    public static int getMaxNumberofNodes() {
        return MAX_NODES_2 + MAX_NODES_1 + 1;
    }

    /**
     * Renvoie le nombre de noeuds du graphe.
     * @return int le nombre en question
     * @since 3.0.1
     */
    public int getNumberOfNodes() {
        return 1 + firstCrown.size() + secondCrown.size();
    }

    /**
     * Renvoie vrai si aucun noeud n'a été refusé pour cause de taille.
     * @return boolean
     * @since 3.0.5
     */
    public boolean isExhaustive() {
        return!(suppr);
    }

    /**
     * Définit le noeud principal. Ce noeud sera le centre du graphe.
     * @param concept String le nom de ce noeud
     * @param description String la description associée à ce noeud
     * @since 3.0.1
     */
    public void setActive(String concept, String description) {
        activeConcept = new Node(concept, description, 0);
        firstCrown = new Vector();
        secondCrown = new Vector();
        links = new Vector();
        maxIdCrown1 = 1;
        maxIdCrown2 = 1;
    }

    /**
     * Renvoie le noeud principal de ce graphe.
     * @return String le noeud principal
     * @since 3.0.0
     */
    public String getActiveConcept() {
        return activeConcept.getName();
    }

    /**
     * Essaie d'ajouter un lien et son noeud terminal au graphe. La procédure
     * d'ajout est définie comme suit :
     * <ul><li> On essaie d'associer un noeud aux noms donnés.</li>
     * <li> Si on n'en trouve pas pour l'un d'entre eux, on essaie de créer un
     * nouveau noeud. Si on n'en trouve pas pour les deux, c'est l'échec.</li>
     * <li> Pour créer un nouveau noeud :
     * <ul><li> Il ne peut pas y avoir plus d'un certain nombre de noeuds dans
     * la seconde couronne pour chaque noeud de la première couronne, et le
     * nombre total est lui aussi limité.</li>
     * <li> Tous les noeuds de la première couronne seront entrés.</li></ul></li>
     * <li> Si les deux noeuds existent finalement, on crée un lien entre eux.
     * </li></ul>
     * Equivalent à addLink(linkFrom, descFrom, 0, linkTo, String descTo, 0,
     * linkName).
     * @param linkFrom String le nom du noeud origine du lien
     * @param descFrom String la description associée
     * @param linkTo String le nom du noeud destination du lien
     * @param descTo String la description associée
     * @param linkName String le nom de la relation entre les noeuds
     * @throws LinkFailureException si le lien n'a pas été ajouté
     * @since 3.0.1
     */
    public void addLink(String linkFrom, String descFrom, String linkTo,
                        String descTo, String linkName) throws
            LinkFailureException {
        addLink(linkFrom, descFrom, 0, linkTo, descTo, 0, linkName);
    }

    /**
     * Essaie d'ajouter un lien et son noeud terminal au graphe. La procédure
     * d'ajout est définie comme suit :
     * <ul><li> On essaie d'associer un noeud aux noms donnés.</li>
     * <li> Si on n'en trouve pas pour l'un d'entre eux, on essaie de créer un
     * nouveau noeud. Si on n'en trouve pas pour les deux, c'est l'échec.</li>
     * <li> Pour créer un nouveau noeud :
     * <ul><li> Il ne peut pas y avoir plus d'un certain nombre de noeuds dans
     * la seconde couronne pour chaque noeud de la première couronne, et le
     * nombre total est lui aussi limité.</li>
     * <li> Tous les noeuds de la première couronne seront entrés.</li></ul></li>
     * <li> Si les deux noeuds existent finalement, on crée un lien entre eux.
     * </li></ul>
     * Equivalent à addLink(linkFrom, descFrom, 0, linkTo, String descTo, 0,
     * linkName).
     * @param linkFrom String le nom du noeud origine du lien
     * @param descFrom String la description associée
     * @param countFrom int le nombre d'autres liens partant de ce noeud
     * @param linkTo String le nom du noeud destination du lien
     * @param descTo String la description associée
     * @param countTo int le nombre d'autres liens partant de ce noeud
     * @param linkName String le nom de la relation entre les noeuds
     * @throws LinkFailureException si le lien n'a pas été ajouté
     * @since 3.0.1
     */
    public void addLink(String linkFrom, String descFrom, int countFrom,
                        String linkTo, String descTo, int countTo,
                        String linkName) throws LinkFailureException {

        Node nodeFrom = new Node("", "", -1);
        Node nodeTo = new Node("", "", -1);

        // Recherche d'ids connus (un nom = un id)
        if (linkFrom.equalsIgnoreCase(activeConcept.getName())) {
            nodeFrom = activeConcept; // l'id du concept actif est 0
        }
        if (linkTo.equalsIgnoreCase(activeConcept.getName())) {
            nodeTo = activeConcept;
        }
        for (int i = 0; i < firstCrown.size(); i++) {
            Node s = (Node) (firstCrown.elementAt(i));
            if (linkFrom.equalsIgnoreCase(s.getName())) {
                nodeFrom = s;
            }
            if (linkTo.equalsIgnoreCase(s.getName())) {
                nodeTo = s;
            }
        }
        for (int i = 0; i < secondCrown.size(); i++) {
            Node s = (Node) (secondCrown.elementAt(i));
            if (linkFrom.equalsIgnoreCase(s.getName())) {
                nodeFrom = s;
            }
            if (linkTo.equalsIgnoreCase(s.getName())) {
                nodeTo = s;
            }
        }


        // verifying current ids and assigning new
        if (nodeFrom.getId() == -1 && nodeTo.getId() == -1) {
            throw new LinkFailureException(
                    Charte.getMessage("Graph_Error_NoConcept") + " " + linkFrom +
                    " " + Charte.getMessage("Graph_Error_NoConcept2") + " " +
                    linkTo + ".");
        }
        if (nodeFrom.getId() == nodeTo.getId()) {
            throw new LinkFailureException(
                    Charte.getMessage("Graph_Error_SameConcept") + " " +
                    linkFrom + " " +
                    Charte.getMessage("Graph_Error_SameConcept2") + " " +
                    linkTo + ".");
        }
        int nFrom = nodeFrom.getId();
        int nTo = nodeTo.getId();
        if (nFrom == -1) {
            if (nTo <= 9) {
                nFrom = maxIdCrown1 * 10 + nTo;
                maxIdCrown1++;
                nodeFrom = new Node(linkFrom, descFrom, nFrom, countFrom);
                addToFirstCrown(nodeFrom);
            }
            if (nTo >= 10 && nTo <= 999) {
                nFrom = maxIdCrown2 * 1000 + nTo;
                maxIdCrown2++;
                nodeFrom = new Node(linkFrom, descFrom, nFrom, countFrom);
                addToSecondCrown(nodeFrom);
            }
            if (nTo >= 1000 && nTo <= 99999) {
                // on ne fait rien : pas de troisième couronne
                nodeFrom.relations++;
                throw new LinkFailureException(
                        Charte.getMessage("Graph_Error_ThirdCrown"));
            }
        }
        if (nTo == -1) {
            if (nFrom <= 9) {
                nTo = maxIdCrown1 * 10 + nFrom;
                maxIdCrown1++;
                nodeTo = new Node(linkTo, descTo, nTo, countTo);
                addToFirstCrown(nodeTo);
            }
            if (nFrom >= 10 && nFrom <= 999) {
                nTo = maxIdCrown2 * 1000 + nFrom;
                maxIdCrown2++;
                nodeTo = new Node(linkTo, descTo, nTo, countTo);
                addToSecondCrown(nodeTo);
            }
            if (nFrom >= 1000 && nFrom <= 99999) {
                nodeTo.relations++;
                // on ne fait rien : pas de troisième couronne
                throw new LinkFailureException(
                        Charte.getMessage("Graph_Error_ThirdCrown"));
            }
        }
        /*if(nFrom != -1 && nTo != -1){
            if(nFrom <= 9 && nTo >= 1000){
                System.err.println(nodeTo.name);
                for(int i=0; i<links.size(); i++){
                    Link l = (Link)(links.elementAt(i));
                    if(l.idFrom==nodeTo.id){
                        l.idFrom = maxIdCrown1 * 10;
                    }
                    if(l.idTo==nodeTo.id){
                        l.idTo = maxIdCrown1 * 10;
                    }
                }
                nodeTo.id = maxIdCrown1 * 10;
                maxIdCrown1++;
                secondCrown.remove(nodeTo);
                addToFirstCrown(nodeTo);
            }
            if(nTo <= 9 && nFrom >= 1000){
                System.err.println(nodeFrom.name);
                for(int i=0; i<links.size(); i++){
                    Link l = (Link)(links.elementAt(i));
                    if(l.idFrom==nodeFrom.id){
                        l.idFrom = maxIdCrown1 * 10;
                    }
                    if(l.idTo==nodeFrom.id){
                        l.idTo = maxIdCrown1 * 10;
                    }
                }
                nodeFrom.id = maxIdCrown1 * 10;
                maxIdCrown1++;
                secondCrown.remove(nodeFrom);
                addToFirstCrown(nodeFrom);
            }
        }*/

        // creating the link
        addToLinks(new Link(nodeFrom, nodeTo, linkName));
    }

    /**
     * Renvoie le noeud principal sous forme de GraphNode.
     * @return GraphNode le noeud principal en question
     * @since 3.0.0
     */
    GraphNode getActive() {
        return new GraphNode(activeConcept);
    }

    /**
     * Renvoie les noeuds de la première couronne, triés par nom.
     * @return GraphNode[] les noeuds de la première couronne
     * @since 3.0.0
     */
    GraphNode[] getSortedFirstCrown() {
        Node[] n = new Node[firstCrown.size()];
        firstCrown.toArray(n);
        sortFirst(n);
        GraphNode[] result = new GraphNode[n.length];
        for (int i = 0; i < n.length; i++) {
            Set linkSet = new HashSet(); // avoids double links (if any)
            boolean ok = true;
            for (int j = 0; j < links.size(); j++) {
                Link link = (Link) (links.elementAt(j));
                if (link.getFrom() == n[i].getId() ||
                    link.getTo() == n[i].getId()) {
                    if (link.getFrom() == 0 || link.getTo() == 0) { // avoids double links
                        if (ok) {
                            ok = false;
                            linkSet.add(link);
                        }
                    } else {
                        linkSet.add(link);
                    }
                }
            }
            result[i] = new GraphNode(n[i], linkSet.size());
        }
        return result;
    }

    /**
     * Renvoie les noeuds de la seconde couronne, triés par noeud de
     * rattachement dans la première couronne.
     * @return GraphNode[] les noeuds de la seconde couronne
     * @since 3.0.0
     */
    GraphNode[] getSortedSecondCrown() {
        Node[] nc1 = new Node[firstCrown.size()];
        Node[] nc2 = new Node[secondCrown.size()];
        firstCrown.toArray(nc1);
        secondCrown.toArray(nc2);
        sortFirst(nc1);
        nc2 = sortSecond(nc1, nc2);
        GraphNode[] result = new GraphNode[nc2.length];
        for (int i = 0; i < nc2.length; i++) {
            Set linkSet = new HashSet(); // avoids double links (if any)
            boolean ok = true;
            for (int j = 0; j < links.size(); j++) {
                Link link = (Link) (links.elementAt(j));
                if (link.getFrom() == nc2[i].getId() ||
                    link.getTo() == nc2[i].getId()) {
                    if (link.getFrom() == 0 || link.getTo() == 0) { // avoids double links
                        if (ok) {
                            ok = false;
                            linkSet.add(link);
                        }
                    } else {
                        linkSet.add(link);
                    }
                }
            }
            result[i] = new GraphNode(nc2[i], linkSet.size());
        }
        return result;
    }

    /**
     * Renvoie les liens du graphe.
     * @return GraphLink[] les liens du graphe.
     * @since 3.0.0
     */
    GraphLink[] getLinks() {
        Link[] l = new Link[links.size()];
        links.toArray(l);
        GraphLink[] result = new GraphLink[links.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = new GraphLink(l[i]);
        }
        return result;
    }

    protected static void sortFirst(Node[] firstNodes) {
        Comparator cmp = new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((Node) o1).getName().compareToIgnoreCase(((Node) o2).
                        getName());
            }
        };
        Arrays.sort(firstNodes, cmp);
    }

    protected static Node[] sortSecond(Node[] sortedFirstNodes,
                                       Node[] secondNodes) {
        Vector result = new Vector();
        for (int i = 0; i < sortedFirstNodes.length; i++) {
            int idToFind = sortedFirstNodes[i].getId();
            for (int j = 0; j < secondNodes.length; j++) {
                int idFound = secondNodes[j].getId() % 1000;
                if (idFound == idToFind) {
                    result.addElement(secondNodes[j]);
                }
            }
        }
        Node[] nres = new Node[result.size()];
        result.toArray(nres);
        return nres;
    }

    protected void addToFirstCrown(Node node) {
        firstCrown.addElement(node);
        if (firstCrown.size() > MAX_NODES_1) {
            maxParCour1 = 0;
            clearSecondCrown();
        }
    }

    protected void clearSecondCrown() {
        for (int i = 0; i < firstCrown.size(); i++) {
            int baseId = ((Node) (firstCrown.elementAt(i))).getId();
            int nb = 0;

            for (int j = 0; j < secondCrown.size(); j++) {
                int nodeId = ((Node) (secondCrown.elementAt(j))).getId();

                boolean removed = false;
                for (int k = 0; k < links.size(); k++) {
                    Link link = (Link) (links.elementAt(k));
                    if (link.getFrom() == nodeId && link.getTo() == baseId ||
                        link.getTo() == nodeId && link.getFrom() == baseId) {
                        if (nb >= maxParCour1) {
                            secondCrown.remove(j);
                            removed = true;
                            suppr = true;
                            links.remove(k);
                            k--;
                        } else {
                            nb++;
                        }
                    }
                }
                if (removed) j--;
            }
        }
    }

    protected void addToSecondCrown(Node node) {
        if (maxParCour1 > 0) {
            secondCrown.addElement(node);
            clearSecondCrown();
            boolean hasEnoughPlace =
                    (secondCrown.size() < MAX_NODES_2 &&
                     firstCrown.size() <= MAX_NODES_1);
            if (!hasEnoughPlace) {
                maxParCour1--;
                clearSecondCrown();
            }
        }
    }

    protected void addToLinks(Link link) {
        int id1 = link.getFrom();
        int id2 = link.getTo();
        boolean b1 = false;
        boolean b2 = false;
        if (id1 == activeConcept.getId()) {
            b1 = true;
        }
        if (id2 == activeConcept.getId()) {
            b2 = true;
        }
        for (int i = 0; i < firstCrown.size(); i++) {
            if (id1 == ((Node) (firstCrown.elementAt(i))).getId()) {
                b1 = true;
            }
            if (id2 == ((Node) (firstCrown.elementAt(i))).getId()) {
                b2 = true;
            }
        }
        for (int i = 0; i < secondCrown.size(); i++) {
            if (id1 == ((Node) (secondCrown.elementAt(i))).getId()) {
                b1 = true;
            }
            if (id2 == ((Node) (secondCrown.elementAt(i))).getId()) {
                b2 = true;
            }
        }
        boolean areIn = (b1 && b2);
        if (areIn) {
            links.addElement(link);
        }
    }

    /**
     * Cette classe est la structure de stockage des noeuds du graphe. Elle est
     * utilisée durant les échanges avec la classe GraphPanel.
     * @since 3.0.0
     */
    class GraphNode {
        protected String name;
        protected String description;
        protected int id;
        protected int relations;

        /**
         * L'id minimal pour le noeud actif.
         * @since 3.0.0
         */
        public final static int MIN_ACTIVE = 0;

        /**
         * L'id maximal pour le noeud actif.
         * @since 3.0.0
         */
        public final static int MAX_ACTIVE = 9;

        /**
         * L'id minimal pour un noeud de la première couronne.
         * @since 3.0.0
         */
        public final static int MIN_CROWN1 = 10;

        /**
         * L'id maximal pour un noeud de la première couronne.
         * @since 3.0.0
         */
        public final static int MAX_CROWN1 = 999;

        /**
         * L'id minimal pour un noeud de la seconde couronne.
         * @since 3.0.0
         */
        public final static int MIN_CROWN2 = 1000;

        /**
         * L'id maximal pour un noeud de la seconde couronne.
         * @since 3.0.0
         */
        public final static int MAX_CROWN2 = 99999;

        protected GraphNode(Node node) {
            this(node, 0);
        }

        protected GraphNode(Node node, int drawnRelations) {
            name = node.getName();
            description = node.getDescription();
            id = node.getId();
            relations = node.getRelationsCount() - drawnRelations;
        }

        /**
         * Renvoie le nom du noeud.
         * @return String le nom en question
         * @since 3.0.0
         */
        public String getName() {
            return name;
        }

        /**
         * Renvoie la description du noeud.
         * @return String la description du noeud
         * @since 3.0.1
         */
        public String getDescription() {
            return description;
        }


        /**
         * Renvoie l'identifiant du noeud.
         * @return l'identifiant en question
         * @since 3.0.0
         */
        public int getId() {
            return id;
        }

        /**
         * Renvoie le nombre de liens non représentés partant de ce noeud.
         * @return int le nombre en question
         * @since 3.0.0
         */
        public int getRelationsCount() {
            return relations;
        }

    }

    /**
     * Cette classe est la structure de stockage des liens du graphe. Elle est
     * utilisée durant les échanges avec la classe GraphPanel.
     * @since 3.0.0
     */
    class GraphLink {
        protected int concept1;
        protected int concept2;
        protected String linkText;
        protected Color color;

        protected GraphLink(Link link) {
            concept1 = link.getFrom();
            concept2 = link.getTo();
            linkText = link.getName();
            color = Charte.getForeground();
        }

        /**
         * Renvoie l'id du premier concept connecté par ce lien.
         * @return int l'id en question
         * @since 3.0.0
         */
        public int getIdConcept1() {
            return concept1;
        }

        /**
         * Renvoie l'id du second concept connecté par ce lien.
         * @return int l'id en question
         * @since 3.0.0
         */
        public int getIdConcept2() {
            return concept2;
        }

        /**
         * Renvoie le texte associé avec le lien.
         * @return String le texte en question
         * @since 3.0.0
         */
        public String getText() {
            return linkText;
        }

        /**
         * Retourne la couleur du lien.
         * @return Color la couleur en question
         * @since 3.0.0
         */
        public Color getColor() {
            return color;
        }
    }

    protected class Link {
        protected int idFrom;
        protected int idTo;
        protected String linkName;

        protected Link(Node from, Node to, String name) {
            idFrom = from.getId();
            idTo = to.getId();
            linkName = name;
        }

        protected int getFrom() {
            return idFrom;
        }

        protected int getTo() {
            return idTo;
        }

        protected String getName() {
            return linkName;
        }
    }

    protected class Node {
        protected String name;
        protected String description;
        protected int id;
        protected int relations;

        protected Node(String name, String description, int id) {
            this(name, description, id, 0);
        }

        protected Node(String name, String description, int id, int relations) {
            this.name = name;
            this.description = description;
            this.id = id;
            this.relations = relations;
        }

        protected String getName() {
            return name;
        }

        protected String getDescription() {
            return description;
        }

        protected int getId() {
            return id;
        }

        protected int getRelationsCount() {
            return relations;
        }
    }
}
