package ch.epfl.isochrone.timetable;

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

import static org.junit.Assert.assertTrue;
/**
 * 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;
    public final Map<Stop, List<GraphEdge>> outgoingEdges;  // private
    
    /**
    *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())
        {
            assertTrue(stops.contains(s));
        }
        
        for (List<GraphEdge> l : outgoingEdges.values())
        {
            for (GraphEdge g : l)
            {
                assertTrue(stops.contains(g.destination()));
            }
        }
        
        
        this.stops = stops;
        this.outgoingEdges = outgoingEdges;
    }
    
    
    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 da'rrivé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]);
                        
                        if (m==null)
                        {
                            m = new HashMap<Stop, GraphEdge.Builder>();
                        }
                        
                        GraphEdge.Builder newEdgeBuilder = new GraphEdge.Builder(stops1[j]);
                        newEdgeBuilder.setWalkingTime((int) (d/walkingSpeed));
                        
                        m.put(stops1[j], newEdgeBuilder);
                        mapProvisoire.put(stops1[i], m);
                    }
                }
            }
            
            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);
        }
    }
}
