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

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.junit.Assert;
import org.junit.Test;
import org.junit.BeforeClass;

public class SimpleTest {
    
    private static GraafDoorloper dg;
    
    
    @BeforeClass 
    public static void init() {
        dg = new BreedteEerstDoorloper();
    }

    @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 = dg.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 = dg.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 = dg.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 = dg.doorloop(Graphs.unmodifiableUndirectedGraph(graph));
        check(antwStud, graph);
    }

    public void check(List<Node<String>> antwStud, UndirectedGraph<String> graph){
        // Nagaan of de lijst antwStud geen dubbels bevat
        Set<Node<String>> antwStudSet = new HashSet<>(antwStud);
        Assert.assertEquals("In je antwoord " + antwStud + " komen sommige toppen meermaals voor.", antwStudSet.size(), antwStud.size());

        // Nagaan of de lengte van de lijst antwStud wel klopt
        Assert.assertEquals("Het aantal toppen in je antwoord " + antwStud + " klopt niet.", graph.getAllNodes().size(), antwStud.size());
         
        Set<Node<String>> bezochteToppen = new HashSet<>();
        int i = 0;
        // hulpindex e om de subintervallen in antwStud te bepalen waar de onbezochte adj toppen vd huidige top moeten staan.
        int e = 0;
        while(i < graph.getAllNodes().size()){
            // Begin controle van een nieuwe component van de graaf
            e = i + 1;
            while(i < e){
                Node<String> n = antwStud.get(i);
                // Bepaal alle adjacente toppen van top n die nog niet bezocht zijn
                Set<Node<String>> onbezochteAdjToppen = new HashSet<>(graph.getNeighbours(n));
                onbezochteAdjToppen.removeAll(bezochteToppen);
                // Bepaal de sublijst van antwStud waar deze onbezochteAdjToppen moeten staan
                int lengte = onbezochteAdjToppen.size();
                Set<Node<String>> teControleren = new HashSet<>(antwStud.subList(e, e + lengte));
                Assert.assertEquals("Je antwoord " + antwStud + " is geen BFS van de graaf.", onbezochteAdjToppen, teControleren);
                // Top n en onbezochteAdjToppen zijn nu reeds bezocht
                bezochteToppen.add(n);
                bezochteToppen.addAll(onbezochteAdjToppen);
                // Volgende sublijst zal starten van andere index. e wordt aangepast:
                e += lengte;
                i++;
            }
        }
    }
    
    public void voegBoogToe(UndirectedGraph<String> graph, String n1, String n2){
        graph.addEdge(new UndirectedEdge<>(graph.getNode(n1), graph.getNode(n2)));
    }

}