import java.io.*;
import java.util.*;

/*
 * This class models a collection fo cities and roads. 
 * It uses two graphs. One which keeps the distance of the roads 
 * in miles as the cost of the edges. The other of which keeps the
 * expected travel time, in minutes, as the cost of the edges.
 */

class RoadMap
{

  private class DijTableEntry
  {
    /*
     * This class should contain a vertex's entry in 
     * the table used by Dijkstra's algorithm. Basically,
     * it should be a row of this table (path, distance, known).
     * It should also contain conveniences such as toString()
     * You shoudl write this...
     */
  }

  private DataReader mapFile; // File abstraction for input file
  private String cityName[]; // City number to name mapping table
  private AdjList distanceMap; // Graph representing map w/cost as distance
  private AdjList timeMap; // Graph representing map w/cost as travel time

  /*
   * Helper method to return city's number, given its name
   * The reverse mapping is done by indexing into the table
   * 
   */
  private int getCityNumber (String givenCityName)
  {
    for (int index=0; index < cityName.length; index++)
    {
      if (cityName[index].equals(givenCityName))
        return index;
    }

    return -1;
  }

  /*
   * This creates the distanceMap and timeMap from a properly
   * formatted input file
   */
  public RoadMap (String mapFileName)
  {
    try 
    {
      mapFile = new DataReader (mapFileName);
      int numCities = mapFile.readInt();

      distanceMap = new AdjList(numCities);
      timeMap = new AdjList(numCities);
      cityName = new String [numCities];

      // Read city names into name:number mapping
      for (int index=0; index < numCities; index++)
        cityName[index] = mapFile.readWord();
    }
    catch (Exception e)
    {
      // An error -- not much to do.
      System.out.println (e);
      return;
    }

    try
    {
      while (true)
      {
        String startCity = mapFile.readWord();
        String destinationCity = mapFile.readWord();

        int distance = mapFile.readInt();
        int time = mapFile.readInt();

        distanceMap.addEdge(new Edge( getCityNumber(startCity), 
                                              getCityNumber(destinationCity), 
                                              distance));
        timeMap.addEdge(new Edge ( getCityNumber(startCity), 
                                           getCityNumber(destinationCity), 
                                           time));
      }
    }
    catch (EOFException e)
    { } // Normal exit -- no more roads to map

    catch (Exception e)
    {
      // A real error -- not much to do.
      System.out.println (e);
      System.exit (-1);
    }
  }

  public DijTableEntry[] dijkstra (String start, boolean distanceNotTime)
  {
    /*
     * You should write this.
     * It should implement Dijkstra's algorithm to determine the 
     * path from start to each other vertex. This path should
     * be stored (with distance) in a table, as we did in class.
     * This table is represented as an array of DijTableEntry 
     * with one entry (row) per vertex.
     * 
     * "distanceNotTime" is a boolean that indicates that the 
     * which of the two map files should be used: distance if true,
     * time if false.
     *
     * "start" is the name of the start city.
     */
    return dijTable;
  }

  public void printPath (DijTableEntry []dijTable, String finish)
  {
    /*
     * You should write this method. 
     * Given a table produced by dijkstra() above, and a destination
     * it should clearly, cleanly, and neatly print out the
     * path from start to finish, including the milestones. 
     * at each city in between. 
     *
     * The start is not provided. This is not a mistake. It can be
     * determined form the table.
     * 
     * Please note, this should print out the path from start to finish,
     * not backwards
     */
  }


  /*
   * This is a really simple method. Please feel free to
   * do something nicer
   */
  public String toString()
  {
    return "Distance\n\n" + distanceMap.toString() + "\n\n" + 
           "Time\n\n" + timeMap.toString() + "\n\n";
    
  }

  public static void main (String []args)
  {
    /*
     * Insert your test driver code here. Please submit your
     * test maps.
     *
     * Your test driver should demonstrate that your code can 
     * produce the shortest route and the quickest route between 
     * any pair of cities from a map.
     */
  }
}