import java.io.File;
import java.util.Scanner;

/**
 * The Test class is the main class used to test and grade the CPS420 assignment.
 * <br> DO NOT MODIFY THIS CLASS.
 * @author Sophie Quigley
 */
public class Test {

    /** 
    * Input stream.
    */
    private static Scanner input = null;
    
    /** 
    * Path of directory containing test files.
    */
    public static final String testDirPath = "/misc/cps420/public_html/doc/Now/A/Tests/";
    
    /**
    * Main test program calculates score for program.
    * <br>It first tests the getEulerian method on graphs in test files.
    * <br>Then it tests it on randomly generated undirected simple graphs.
    * @param args the command line arguments
    */

    public static void main(String[] args) {

      int result;
      int score=0;

      // Run test files
      System.out.println("\n=======================  TEST CORRECTNESS  =======================");
  
      score += 6 - testFile("noEulerian", 0, true);
      System.out.println("Score so far: " + score);

      score += testFile("small", 7, true);
      System.out.println("Score so far: " + score);
      
      score += testFile("medium", 5, true);
      System.out.println("Score so far: " + score);
 
      score += 2*testFile("large", 6, true);
      System.out.println("Score so far: " + score);
 
      score += 5*testFile("verylarge", 1, true);
      System.out.println("Score so far: " + score + " out of 35.");

      System.out.println("=======================  TEST EFFICIENCY   =======================");

      score += 4*testFile("huge1", 1, true);
      System.out.println("Score so far: " + score);
 
      score += 4*testFile("huge2", 1, true);
      System.out.println("Score so far: " + score);
 
      score += 4*testFile("huge3", 1, true);
      System.out.println("Score so far: " + score);
 
      score += 4*testFile("huge4", 1, true);
      System.out.println("Score so far: " + score);
 
      score += 4*testFile("huge5", 1, true);
      System.out.println("Score so far: " + score);
 
  
      // Print final score   
      System.out.println("Total score: " + score + " out of 55.");
      
    }

    /**
    * Reads graphs described in a test file and tests the findEuler method on these graphs.
    * @param filename name of test file. The directory containing that file is hard coded in testDirPath
    * @param expected number of graphs in file which have a Eulerian circult
    * @param showcircuit when this is true, the Eulerian circuits found will be printed.
    * @return The number of valid Eulerian circuits found for the graphs in the file.
    */
    public static int testFile(String filename, int expected, boolean showcircuit) {
        String filepath = testDirPath + filename;

        System.out.println("\n=======  Test " + filepath +"  =======");
        try {
            input = new Scanner(new File(filepath));
        } catch (Exception ex) {
            System.out.println(ex);
            System.exit(0);
        }
        
        int found = 0;
        Graph graph = null;
          
        while (input.hasNext())    {
            // Read and print input Graph
            try {
                graph = new Graph(input);
            } catch (InstantiationException ex) {
                System.out.println(ex);
                System.exit(0);
            } catch (Exception ex) {
                System.out.println(ex);
                System.exit(0);
            }
            found += testGraph(graph,showcircuit);
        }
        System.out.println("\nEulerian circuits expected: " + expected + ", found: " + found);
        return found;
    }

    /**
    * Tests the findEuler method for a graph and prints the results.
    * @param graph graph on which the findEuler method will be tested
    * @param showcircuit when this is true, the Eulerian circuit found will be printed.
    * @return 1 if a valid Eulerian circuit has been found and 0 otherwise
    */      
    public static int testGraph(Graph graph, boolean showcircuit) {
        // Print graph
        System.out.println("\nGraph has " + graph.getTotalVertices() 
            + " vertices, and " + graph.getTotalEdges() + " edges.");
                    
        // Try to find a Eulerian circuit
        Walk circuit = Euler.findEuler(graph);
        if (circuit == null) {
            System.out.println("Graph has no Eulerian circuit");
            return 0;
        }
        if (showcircuit)
          System.out.println("The following circuit was found:\n" + circuit);
        if (isValidEulerian(graph,circuit)) {
            System.out.println("Valid Eulerian Circuit");
            return 1;
        }
        else  {
            System.out.println("Invalid Eulerian Circuit");
            return 0;
        }
    }

    /**
    * Verifies whether a walk is a valid Eulerian circuit for a graph.
    * @param graph original graph
    * @param walk potential Eulerian circuit for graph
    * @return true iff walk is a valid Eulerian circuit for graph, and false otherwise.
    */  
    public static boolean isValidEulerian(Graph graph, Walk walk) {
        // First check if the walk is a circuit
        if (!walk.isClosed()) {
            System.out.println("Error: This walk is not a circuit");
            return false;
        }

        // Then check if the circuit has the correct number of edges
        int totalEdges = graph.getTotalEdges();
        int walklength = walk.getLength();
        if (walklength < totalEdges)  {
            System.out.println("Error: Some edges have not been visited");
            return false;
        }
        if (walklength > totalEdges)  {
            System.out.println("Error: Some edges have not been visited more than once");
            return false;
        }

        // Now check whether the circuit encompasses the same number of vertices as the graph
        // By finding the highest vertex index in the circuit
        int maxvertex = 0;
        for (int i=walk.getTotalVertices()-1; i>=0; i--)
            if (walk.getVertex(i) > maxvertex)  maxvertex = walk.getVertex(i);
        if (maxvertex != graph.getTotalVertices()-1) {
            System.out.println("Error: The circuit does not have the same number of vertices as the original graph");
            return false;
        }      
         
        // Finally, check whether the graph formed by this circuit is the same as the original graph:
        // The edges counts between vertices should be identical.
        // Because the circuit and the graph do have the same number of edges at this point,
        // then if these edges are not the identical,
        // there will be n>0 graph edges that are unvisited in the circuit
        // matched by n>0 graph edges that are visited too much in the circuit.
        // This algorithm checks the second condition. 
        graph.resetVisitation();
        int i, v1, v2;
        v1 = walk.getVertex(0);
        for (i=1; i<walklength; i++) {
            v2 = walk.getVertex(i);
            if (graph.getEdgeCount(v1,v2) == 0) {
                System.out.println("Error: The original graph has no edge between " + v1 + " and " + v2);
                graph.resetVisitation();
                return false;
            }
            graph.visitE(v1,v2);
            if (graph.getUnvisitedE(v1,v2) < 0) {
                System.out.println("Error: same edge visited twice between " + v1 + " and "+ v2 );
                graph.resetVisitation();
                return false;
            }
            v1 = v2;
        }
        graph.resetVisitation();
        return true;
    }

}