import graphlib.edges.UndirectedEdge;
import graphlib.graphs.UndirectedGraph;
import graphlib.nodes.Node;
import graphlib.util.Graphs;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Deque;
import java.util.ArrayDeque;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.BeforeAll;

public class SimpleTest {
    
    private static GraafDoorloper gd;
    
    
    @BeforeAll 
    public static void init() {
        gd = new DiepteEerstDoorloper();
    }

    @Test
    public void test1() {

        UndirectedGraph<String> graph = new UndirectedGraph<>();
        for(int i = 0; i < 6; i++){
            graph.addNode("n" + i);
        }
        voegBoogToe(graph,"n0","n1");
        voegBoogToe(graph,"n0","n2");
        voegBoogToe(graph,"n1","n3");
        voegBoogToe(graph,"n1","n4");
        voegBoogToe(graph,"n3","n5");
        
        List<Node<String>> antwStud = gd.doorloop(Graphs.unmodifiableUndirectedGraph(graph));
        
        check(antwStud, graph);
        
    }
    
    @Test
    public void test2() {
        UndirectedGraph<String> graph = new UndirectedGraph<>();
        for(int i = 0; i < 8; i++){
            graph.addNode("n" + i);
        }
        voegBoogToe(graph,"n0","n2");
        voegBoogToe(graph,"n0","n3");
        voegBoogToe(graph,"n1","n6");
        voegBoogToe(graph,"n2","n4");
        voegBoogToe(graph,"n4","n3");
        voegBoogToe(graph,"n4","n5");
        voegBoogToe(graph,"n6","n7");
        
        List<Node<String>> antwStud = gd.doorloop(Graphs.unmodifiableUndirectedGraph(graph));
        
        check(antwStud, graph);
    }
    
    @Test
    public void test3() {
        UndirectedGraph<String>graph = new UndirectedGraph<>();
        for(int i = 0; i < 8; i++){
            graph.addNode("n" + i);
        }
        voegBoogToe(graph,"n0","n1");
        voegBoogToe(graph,"n0","n2");
        voegBoogToe(graph,"n0","n3");
        voegBoogToe(graph,"n0","n4");
        voegBoogToe(graph,"n0","n6");
        voegBoogToe(graph,"n0","n7");
        voegBoogToe(graph,"n1","n5");
        voegBoogToe(graph,"n1","n2");
        voegBoogToe(graph,"n2","n5");
        voegBoogToe(graph,"n2","n6");
        voegBoogToe(graph,"n3","n4");
        voegBoogToe(graph,"n3","n7");
        voegBoogToe(graph,"n5","n6");
        
        List<Node<String>> antwStud = gd.doorloop(Graphs.unmodifiableUndirectedGraph(graph));
        
        check(antwStud, graph);
    }
    
    @Test
    public void test4() {
        UndirectedGraph<String>graph = new UndirectedGraph<>();
        for(int i = 0; i < 12; i++){
            graph.addNode("n" + i);
        }
        voegBoogToe(graph,"n0","n1");
        voegBoogToe(graph,"n0","n2");
        voegBoogToe(graph,"n1","n4");
        voegBoogToe(graph,"n1","n3");
        voegBoogToe(graph,"n2","n4");
        voegBoogToe(graph,"n5","n6");
        voegBoogToe(graph,"n5","n7");
        voegBoogToe(graph,"n5","n9");
        voegBoogToe(graph,"n7","n10");
        voegBoogToe(graph,"n7","n11");
        voegBoogToe(graph,"n6","n9");
        voegBoogToe(graph,"n6","n8");
        
        List<Node<String>> antwStud = gd.doorloop(Graphs.unmodifiableUndirectedGraph(graph));
        check(antwStud, graph);
    }

    public void check(List<Node<String>> solution, UndirectedGraph<String> graph){
        Assertions.assertEquals(new HashSet<>(graph.getAllNodes()), new HashSet<>(solution), "De invoer en uitvoer moeten dezelfde toppen bevatten.");

        Assertions.assertEquals(graph.numNodes(), solution.size(), "Je antwoord bevat dubbels.");

        if(solution.isEmpty()) return; // correct.

        Deque<Node<String>> path = new ArrayDeque<>();
        Set<Node<String>> visited = new HashSet<>();
        int i = 0;
        while(i < solution.size()) {
            Node<String> node = solution.get(i);
            visited.add(node);
            if(path.isEmpty()) {
                // nieuwe component? Dan zou deze node met geen enkele
                // voorgaande verbonden mogen zijn.
                for(int j = 0; j < i; j++) {
                    Assertions.assertFalse(graph.containsEdge(node, solution.get(j)), String.format("from %s to %s", solution.get(j), node));
                }
                path.push(node);
                i++;
            } else if(graph.containsEdge(node, path.peek())) {
                // gewoon dieper in de doorloop
                path.push(node);
                i++;
            } else {
                // een recursie tijdens het opstellen
                // einde van het pad moet volledig bezocht zijn
                Node<String> deadEnd = path.pop();
                Assertions.assertTrue(visited.containsAll(graph.getNeighbours(deadEnd)), "Recursie in een niet-doodlopende top.");
            }
        }
    }
    
    public void voegBoogToe(UndirectedGraph<String>graph, String n1, String n2){
        graph.addEdge(new UndirectedEdge<>(graph.getNode(n1), graph.getNode(n2)));
    }

}