//////////////// FILE HEADER (INCLUDE IN EVERY FILE) //////////////////////////
//
// Title: CampusPaths Backend
// Course: CS 400 Fall 2025
//
// Author: Peter Zeng
// Email: qzeng48@wisc.edu
//
//
///////////////////////////////////////////////////////////////////////////////////

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Implementation of the BackendInterface.
 * This class manages graph data, stores location names, and performs 
 * pathfinding operations using a GraphADT.
 */
public class Backend implements BackendInterface {

  private GraphADT<String, Double> graph;

  // store all location names we have seen while loading the file
  private final Set<String> locations = new LinkedHashSet<>();

  // required constructor (see BackendInterface comment)
  public Backend(GraphADT<String, Double> graph) {
    this.graph = graph;
  }

  /**
   * Clears the graph of all previously added nodes.
   * This method performs a "best-effort" clear. It iterates through known locations
   * and attempts to remove them. If a node is not found or cannot be removed,
   * the exception is caught and ignored to ensure the cleanup process continues
   * for the remaining nodes.
   */
  private void clearGraph() {
    List<String> copy = new ArrayList<>(locations);
    for (String s : copy) {
      try { 
          graph.removeNode(s); 
      } catch (Exception ignore) {
          // Ignore failure to remove; node might already be gone or graph might be empty.
          // This ensures we can proceed to load new data cleanly.
      }
    }
    locations.clear();
  }

  // Matches lines like: "Node A" -> "Node B" [seconds=123.4];
  private static final Pattern EDGE =
      Pattern.compile("\\s*\"([^\"]+)\"\\s*->\\s*\"([^\"]+)\"\\s*\\[seconds=([0-9.]+)\\];");

  /**
   * Loads graph data from a dot file.
   * @param filename the path to the file to load
   * @throws IOException if there is an issue reading the file
   */
  @Override
  public void loadGraphData(String filename) throws IOException {
    clearGraph();
    try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
      String line;
      while ((line = br.readLine()) != null) {
        Matcher m = EDGE.matcher(line);
        if (m.matches()) {
          String u = m.group(1);
          String v = m.group(2);
          double w = Double.parseDouble(m.group(3));

          locations.add(u);
          locations.add(v);

          // insert into the graph (placeholder accepts a tiny path; real graph will accept all)
          // We catch general Exception here to handle any implementation-specific errors 
          // (like DuplicateNodeException or IllegalArgumentException) from the partner's code
          // without crashing the loading process.
          try { 
              graph.insertNode(u); 
          } catch (Exception e) { 
              System.out.println("Node already exists or cannot be inserted: " + u); 
          }
          
          try { 
              graph.insertNode(v); 
          } catch (Exception e) { 
              System.out.println("Node already exists or cannot be inserted: " + v); 
          }
          
          try { 
              graph.insertEdge(u, v, w); 
          } catch (Exception e) { 
              System.out.println("Edge already exists or cannot be inserted: " + u + "-" + v); 
          }
        }
      }
    }
  }

  /**
   * Returns a list of all locations in the graph.
   * @return list of location names
   */
  @Override
  public List<String> getListOfAllLocations() {
    return new ArrayList<>(locations);
  }

  /**
   * Finds the shortest path between two locations.
   * @param startLocation the start node
   * @param endLocation the end node
   * @return list of nodes along the path
   */
  @Override
  public List<String> findLocationsOnShortestPath(String startLocation, String endLocation) {
    // GraphADT already returns a list of node data along the shortest path
    return new ArrayList<>(graph.shortestPathData(startLocation, endLocation));
  }

  /**
   * Finds the edge weights (times) along the shortest path.
   * @param startLocation the start node
   * @param endLocation the end node
   * @return list of edge weights
   */
  @Override
  public List<Double> findTimesOnShortestPath(String startLocation, String endLocation) {
    List<String> nodes = findLocationsOnShortestPath(startLocation, endLocation);
    List<Double> times = new ArrayList<>();
    // Iterate through path nodes to get edge weights between them
    for (int i = 0; i + 1 < nodes.size(); i++) {
      try {
        Double w = graph.getEdge(nodes.get(i), nodes.get(i + 1));
        times.add(w.doubleValue());
      } catch (NoSuchElementException nse) {
        // if an edge is not present (possible with placeholder), skip it
      }
    }
    return times;
  }

  /**
   * Finds the destination furthest from the start location.
   * @param startLocation the start node
   * @return the name of the furthest location
   * @throws NoSuchElementException if start location invalid or no reachable nodes
   */
  @Override
  public String getFurthestDestinationFrom(String startLocation) throws NoSuchElementException {
    if (!locations.contains(startLocation))
      throw new NoSuchElementException("The start location '" + startLocation + "' is not in the graph.");

    boolean found = false;
    String best = null;
    double bestCost = -1.0;

    // Check shortest path cost to every other location
    for (String dest : locations) {
      if (dest.equals(startLocation)) continue;
      try {
        double c = graph.shortestPathCost(startLocation, dest);
        // real graph throws for unreachable; placeholder may return a number
        if (c >= 0) {
          found = true;
          // Update best if current cost is greater
          if (c > bestCost) { bestCost = c; best = dest; }
        }
      } catch (NoSuchElementException ignore) {
        // Destination unreachable, continue to next
      }
    }
    
    if (!found) 
        throw new NoSuchElementException("No reachable destination found starting from '" + startLocation + "'.");
        
    return best;
  }
}