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.Assert;
import org.junit.Test;
import org.junit.BeforeClass;

public class SimpleTest {
    
    private static GraafDoorloper gd;
    
    
    @BeforeClass 
    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){
        Assert.assertEquals("De invoer en uitvoer moeten dezelfde toppen bevatten.",
                new HashSet<>(graph.getAllNodes()),
                new HashSet<>(solution));

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

        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++) {
                    Assert.assertFalse(String.format("from %s to %s", solution.get(j), node),
                                       graph.containsEdge(node, solution.get(j)));
                }
                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();
                Assert.assertTrue("Recursie in een niet-doodlopende top.",
                        visited.containsAll(graph.getNeighbours(deadEnd)));
            }
        }
    }
    
    public void voegBoogToe(UndirectedGraph<String>graph, String n1, String n2){
        graph.addEdge(new UndirectedEdge<>(graph.getNode(n1), graph.getNode(n2)));
    }

}