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

/**
  * class implements BackendInterface
  *
  */

public class Backend implements BackendInterface {

	private GraphADT<String, Double> graph;
	private List<String> nodeList;

	/**
	 * Constructs a Backend with the given graph instance.
	 * 
	 * @param graph the graph object used to store and query rail data
	 */
	public Backend(GraphADT<String, Double> graph) {
		if (graph == null) {
			throw new NullPointerException("graph cannot be null");
		}
		this.graph = graph;
		this.nodeList = new ArrayList<>();
	}

	/**
     * Loads graph data from a .dot file. Clears any previously loaded data first.
     *
     * @param filename path to the .dot file
     * @throws IOException if the file cannot be read or found
     */
    @Override
    public void loadGraphData(String filename) throws IOException {
        for (String node : new ArrayList<>(nodeList)) {
            graph.removeNode(node);
        }
        nodeList.clear();
 
        try (BufferedReader reader = new BufferedReader(new FileReader(filename))) {
            String line;
            while ((line = reader.readLine()) != null) {
                line = line.trim();
 
 
                try {
                    int firstOpen  = line.indexOf('"');
                    int firstClose = line.indexOf('"', firstOpen + 1);
                    String firstCity = line.substring(firstOpen + 1, firstClose);
 
                    int secondOpen  = line.indexOf('"', firstClose + 1);
                    int secondClose = line.indexOf('"', secondOpen + 1);
                    String secondCity = line.substring(secondOpen + 1, secondClose);
 
                    int minutesIdx = line.indexOf("minutes=");
                    int valStart   = minutesIdx + "minutes=".length();
                    int valEnd     = valStart;
                    while (valEnd < line.length()) {
                        char c = line.charAt(valEnd);
                        if (c == ']' ) {
                        	break;
                        }
                        valEnd++;
                    }
                    double weight = Double.parseDouble(line.substring(valStart, valEnd));
 
                    if (!nodeList.contains(firstCity)) {
                        graph.insertNode(firstCity);
                        nodeList.add(firstCity);
                    }
                    if (!nodeList.contains(secondCity)) {
                        graph.insertNode(secondCity);
                        nodeList.add(secondCity);
                    }
 
                    graph.insertEdge(firstCity, secondCity, weight);
 
                } catch (Exception e) {
                    
                }
            }
        }
        }
        /**
         * Returns all location names currently in the graph.
         * @return list of all node names; empty if no data has been loaded
         */
        @Override
        public List<String> getListOfAll() {
            return new ArrayList<>(nodeList);
        }
        
        
        /**
         * Returns the sequence of locations along the shortest path from start to end.
         * Returns an empty list (rather than throwing) if either node is not found
         * or no directed path exists.
         *
         * @param start the starting location
         * @param end   the destination location
         * @return ordered list of location names on the shortest path, or empty list
         */
        @Override
        public List<String> findLocationsOnShortestPath(String start, String end) {
            try {
                return graph.shortestPathData(start, end);
            } catch (NoSuchElementException e) {
                return new ArrayList<>();
            }
        }
        /**
         * Returns the travel times in minutes between each pair of consecutive stops
         * on the shortest path from start to end. The returned list has length
         * (number of locations on path - 1). Returns an empty list if no path exists.
         *
         * @param start the starting location
         * @param end   the destination location
         * @return list of per-edge travel times in minutes, or empty list
         */
        @Override
        public List<Double> findTimesOnShortestPath(String start, String end) {
            List<String> path = findLocationsOnShortestPath(start, end);
            if (path.isEmpty()) return new ArrayList<>();
     
            List<Double> times = new ArrayList<>();
            for (int i = 0; i < path.size() - 1; i++) {
                try {
                    times.add(graph.getEdge(path.get(i), path.get(i + 1)));
                } catch (NoSuchElementException e) {
                    return new ArrayList<>();
                }
            }
            return times;
        }
        

        /**
         * Returns up to ten locations closest to the given start, ordered by
         * ascending total travel time in minutes (shortest-path cost).
         *
         * @param start the location to search outward from
         * @return list of up to ten reachable location names, nearest first
         * @throws NoSuchElementException if start does not exist in the graph, or
         *                                if no other locations are reachable from it
         */
        @Override
        public List<String> getTenClosestLocations(String start) throws NoSuchElementException {
            if (!graph.containsNode(start)) {
                throw new NoSuchElementException("Start location not found in graph: " + start);
            }
     
            // Store pairs for sorting
            List<double[]> reachable = new ArrayList<>();
            for (int i = 0; i < nodeList.size(); i++) {
                String candidate = nodeList.get(i);
                if (candidate.equals(start)) continue;
                try {
                    double cost = graph.shortestPathCost(start, candidate);
                    reachable.add(new double[]{cost, i});
                } catch (NoSuchElementException e) {
                    // Not reachable from start — skip
                }
            }
     
            if (reachable.isEmpty()) {
                throw new NoSuchElementException("No locations reachable from: " + start);
            }
     
            Collections.sort(reachable, (a, b) -> Double.compare(a[0], b[0]));
     
            List<String> result = new ArrayList<>();
            int limit = Math.min(10, reachable.size());
            for (int i = 0; i < limit; i++) {
                result.add(nodeList.get((int) reachable.get(i)[1]));
            }
            return result;
        }
    }