package ch.epfl.isochrone.timetable;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Classe servant à modélise un graphe d'horaire.
 * 
 * @author Charles Thiebaut (238935)
 * @author Arnaud Delamare (234841)
 * 
 */
public final class Graph {
    private final Set<Stop> stops;
    private final Map<Stop, List<GraphEdge>> outgoingEdges;

    /**
     * Constructeur du graph construit a partir des arrêts donnés
     * 
     * @throw IllegalArgumentException si un arrêt qui est clef de la table
     *        associative n'est pas présents dans l'ensemble des arrêts passée
     *        en premier argument de même que si un arrêt servant de destination
     *        aux arcs stockés n'est pas stockés dans cette même table.
     * @param sets
     *            les arrêts donnés comme noeuds.
     * @param outgoingEdges
     *            table associative associant un arrêt, donc un noeud, à une
     *            liste d'arcs partant de ce noeud.
     * 
     */
    private Graph(Set<Stop> stops, Map<Stop, List<GraphEdge>> outgoingEdges) {
        this.stops = stops;
        this.outgoingEdges = outgoingEdges;
    }

    /**
     * Retourne le plus court chemin vers tout les arrêts en prenant un arrêt de
     * départ et une heure de départ en arguments.
     * 
     * @param startingStop
     *            L'arrêt de départ
     * @param departureTime
     *            L'heure de départ
     * @return FastestPathTree le fastestpathtree correspondant au graph, au
     *         départ et à l'heure de départ
     */
    public FastestPathTree fastestPaths(Stop startingStop, int departureTime) {
        if (departureTime < 0) {
            throw new IllegalArgumentException(
                    "L'heure de départ doit être positive");
        }
        if (!(outgoingEdges.containsKey(startingStop))) {
            throw new IllegalArgumentException(
                    "L'arrêt n'est pas présent dans la table associative");
        }
        FastestPathTree.Builder fptb = new FastestPathTree.Builder(
                startingStop, departureTime);

        Set<Stop> v = new HashSet<Stop>(stops);

        int hVoisin;

        while (v.size() != 0) {
            int minimun = SecondsPastMidnight.INFINITE;
            Stop a = null;

            for (Stop s : v) {
                if (fptb.arrivalTime(s) < minimun) {
                    minimun = fptb.arrivalTime(s);
                    a = s; // on recherche le temps d'arrivée minimum
                }
            }
            v.remove(a);

            if (minimun == SecondsPastMidnight.INFINITE) {
                break;
            }

            assert (outgoingEdges.get(a) != null);

            for (GraphEdge g : outgoingEdges.get(a)) {
                hVoisin = g.earliestArrivalTime(minimun);
                if (hVoisin < fptb.arrivalTime(g.destination())) {
                    fptb.setArrivalTime(g.destination(), hVoisin, a);
                    // si le temps d'arrivée en passant par ce point est plus
                    // court, alors on met le nouveau temps comme temps
                    // d'arrivée
                }
            }

        }

        return fptb.build();

    }

    /**
     * class servant de Builder pour les Graph.
     */
    public static final class Builder {
        private final Set<Stop> stops;
        private final Map<Stop, Map<Stop, GraphEdge.Builder>> provisionalMap;

        /**
         * Construit un bâtisseur pour un graphe d'horaire ayant les arrêts
         * pasés en arguments comme noeuds.
         * 
         * @param stops
         *            les arrêts du graphe horaire
         */
        public Builder(Set<Stop> stops) {
            this.stops = new HashSet<Stop>(stops);
            this.provisionalMap = new HashMap<Stop, Map<Stop, GraphEdge.Builder>>();
        }

        /**
         * qui ajoute au graphe en construction un trajet entre les arrêts de
         * départ et d'arrivée donnés, aux heures données (en secondes après
         * minuit)
         * 
         * @throw IllegalArgumentException si l'un deux deux arrêts ne fait pas
         *        partie de ceux psssés au constructeur si l'une des deux heures
         *        est négative si l'heure d'arrivée est antérieur à l'heure de
         *        départ.
         * @param fromStop
         *            l'arrêt de départ.
         * @param toStop
         *            l'arrêt d'arrivée.
         * @param departureTime
         *            l'heure de départ.
         * @param arrivalTime
         *            l'heure d'arrivée.
         * @return le builder modifié
         */
        public Builder addTripEdge(Stop fromStop, Stop toStop,
                int departureTime, int arrivalTime) {
            if (!stops.contains(fromStop)) {
                throw new IllegalArgumentException(
                        "L'arrêt de départ n'est pas compris dans l'ensemble des arrêts");
            }

            if (!stops.contains(toStop)) {
                throw new IllegalArgumentException(
                        "L'arrêt d'arrivée n'est pas compris dans l'ensemble des arrêts");
            }

            if (departureTime < 0) {
                throw new IllegalArgumentException(
                        "L'heure de départ ne doit pas être négative");
            }

            if (arrivalTime < 0) {
                throw new IllegalArgumentException(
                        "L'heure d'arrivée ne doit pas être négative");
            }

            if (arrivalTime - departureTime < 0) {
                throw new IllegalArgumentException(
                        "L'heure d'arrivée doit être postérieure à l'heure de départ");
            }

            graphEdgeBuilder(fromStop, toStop).addTrip(departureTime,
                    arrivalTime);

            return this;
        }

        /**
         * ajoute au graphe en construction la totalité des trajets à pied qu'il
         * est possible d'effectuer entre n'importe quelle paire d'arrêts.
         * 
         * @throw IllegalArgumentException si le temps de marche est négatif si
         *        la vitesse de marche est négative ou nulle
         * @param maxWalkingTime
         *            temps maximale de marche (en secondes)
         * @param walkingSpeed
         *            vitesse de marche (en mètres par seconde)
         * @return le builder modifié
         */
        public Builder addAllWalkEdges(int maxWalkingTime, double walkingSpeed) {
            if (maxWalkingTime < 0) {
                throw new IllegalArgumentException(
                        "Le temps maximal de marche doit être positif");
            }

            if (walkingSpeed <= 0) {
                throw new IllegalArgumentException(
                        "La vitesse de marche doit être positive");
            }

            Stop[] stops1 = new Stop[stops.size()];
            stops1 = stops.toArray(stops1);

            for (int i = 0; i < stops1.length; i++) {
                for (int j = 0; j < i; j++) {
                    double d = stops1[i].position().distanceTo(
                            stops1[j].position());
                    if (d <= maxWalkingTime * walkingSpeed) {

                        graphEdgeBuilder(stops1[i], stops1[j]).setWalkingTime(
                                (int) Math.round((d / walkingSpeed)));

                        graphEdgeBuilder(stops1[j], stops1[i]).setWalkingTime(
                                (int) Math.round((d / walkingSpeed)));

                        // si on peut parcourir la distance en un temps
                        // raisonnable, on ajoute le temps de marche aux
                        // grapheEdgeBuilder dans les deux sens
                    }
                }
            }

            return this;
        }

        /**
         * @return le Graphe construit via le Builder.
         */
        public Graph build() {

            Map<Stop, List<GraphEdge>> outgoingEdges = new HashMap<Stop, List<GraphEdge>>();

            for (Stop s : provisionalMap.keySet()) {
                Map<Stop, GraphEdge.Builder> m = provisionalMap.get(s);
                List<GraphEdge> list = new ArrayList<GraphEdge>();

                for (GraphEdge.Builder g : m.values()) {
                    list.add(g.build());
                }

                outgoingEdges.put(s, list);
            }

            for (Stop s : stops) {
                if (!outgoingEdges.containsKey(s)) {
                    outgoingEdges.put(s, new ArrayList<GraphEdge>());
                }
            }

            return new Graph(stops, outgoingEdges);
        }

        /**
         * Renvoie le graphEdge correspondant ou le crée. Crée également la
         * sous-map de provisionalMap correspondante à l'arrêt de départ si
         * celui-ci n'en a pas encore
         * 
         * @param fromStop
         *            l'arrêt de départ
         * @param toStop
         *            l'arrêt d'arrivée
         * @return le bon graphEdge correspondant aux stop de départ et
         *         d'arrivée
         */
        private GraphEdge.Builder graphEdgeBuilder(Stop fromStop, Stop toStop) {
            Map<Stop, GraphEdge.Builder> m = provisionalMap.get(fromStop);

            GraphEdge.Builder newEdgeBuilder;
            if (m == null) {
                m = new HashMap<Stop, GraphEdge.Builder>();
                newEdgeBuilder = new GraphEdge.Builder(toStop);
            } else {
                if (m.containsKey(toStop)) {
                    newEdgeBuilder = m.get(toStop);
                } else {
                    newEdgeBuilder = new GraphEdge.Builder(toStop);
                }

            }

            m.put(toStop, newEdgeBuilder);

            provisionalMap.put(fromStop, m);

            return newEdgeBuilder;
        }
    }
}
