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) {

        for (Stop s : outgoingEdges.keySet()) {
            assert stops.contains(s); 
            
        }

        for (List<GraphEdge> l : outgoingEdges.values()) {
            for (GraphEdge g : l) {
                assert stops.contains(g.destination()); 
                
            }
        }

        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
     */
    public FastestPathTree fastestPaths(Stop startingStop, int departureTime) {
        if (departureTime < 0 || !(outgoingEdges.containsKey(startingStop))) {
            throw new IllegalArgumentException();
        }
        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;
                }
            }
            v.remove(a);

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

            for (GraphEdge g : outgoingEdges.get(a)) {
                hVoisin = g.earliestArrivalTime(minimun);
                if (hVoisin < fptb.arrivalTime(g.destination())) {
                    fptb.setArrivalTime(g.destination(), hVoisin, a);
                }
            }

        }

        return fptb.build();

    }

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

        /*
         * §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.outgoingEdges = new HashMap<Stop, List<GraphEdge>>();
            this.mapProvisoire = 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) || !stops.contains(toStop)
                    || departureTime < 0 || arrivalTime < 0
                    || arrivalTime - departureTime < 0) {
                throw new IllegalArgumentException();
            }

            Map<Stop, GraphEdge.Builder> m = mapProvisoire.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);
                }

            }
            newEdgeBuilder.addTrip(departureTime, arrivalTime);

            m.put(toStop, newEdgeBuilder);
            mapProvisoire.put(fromStop, m);

            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 || walkingSpeed <= 0) {
                throw new IllegalArgumentException();
            }

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

            int k = 0;
            for (Stop s : stops) // on remplit les tableaux
            {
                stops1[k] = s;
                k++;
            }

            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) {
                        Map<Stop, GraphEdge.Builder> m = mapProvisoire
                                .get(stops1[i]);

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

                        }

                        newEdgeBuilder.setWalkingTime((int) Math
                                .round((d / walkingSpeed)));

                        m.put(stops1[j], newEdgeBuilder);
                        mapProvisoire.put(stops1[i], m);

                        Map<Stop, GraphEdge.Builder> m2 = mapProvisoire
                                .get(stops1[j]);

                        GraphEdge.Builder newEdgeBuilder2;
                        if (m2 == null) {
                            m2 = new HashMap<Stop, GraphEdge.Builder>();
                            newEdgeBuilder2 = new GraphEdge.Builder(stops1[i]);
                        } else {
                            if (m2.containsKey(stops1[i])) {
                                newEdgeBuilder2 = m2.get(stops1[i]);
                            } else {
                                newEdgeBuilder2 = new GraphEdge.Builder(
                                        stops1[i]);
                            }

                        }

                        newEdgeBuilder2.setWalkingTime((int) Math
                                .round((d / walkingSpeed)));

                        m2.put(stops1[i], newEdgeBuilder2);
                        mapProvisoire.put(stops1[j], m2);
                    }
                }
            }

            return this;
        }

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

            for (Stop s : mapProvisoire.keySet()) {
                Map<Stop, GraphEdge.Builder> m = mapProvisoire.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);
        }
    }
}
