#include <cassert>
#include <iostream>

#include "testdijkstra.h"

#include "../algo.h"
#include "../graph.h"
#include "../node.h"
#include "../result.h"


void test_One_node()
{
    Graph g( 1 );

    Node& n = g[0];

    Result res = dijkstra( g, n, n );

    assert( res.distance == 0 );
    assert( res.path.size() == 1 );
    assert( res.path[0] == &n );
}


void test_Two_nodes()
{
    Graph g( 2 );

    Node& n1 = g[0];
    Node& n2 = g[1];

    n1.AddNeighbour( n2, 3 );

    // n1 --3--> n2

    Result res = dijkstra( g, n1, n2 );

    assert( res.distance == 3 );
    assert( res.path.size() == 2 );
    assert( res.path[0] == &n1 );
    assert( res.path[1] == &n2 );
}


void test_Two_branches()
{
    Graph g( 3 );

    Node& n1 = g[0];
    Node& n2 = g[1];
    Node& n3 = g[2];

    n1.AddNeighbour( n2, 3 );
    n1.AddNeighbour( n3, 1 );

    // n1 --3--> n2
    //    --1--> n3

    Result res = dijkstra( g, n1, n2 );

    assert( res.distance == 3 );
    assert( res.path.size() == 2 );
    assert( res.path[0] == &n1 );
    assert( res.path[1] == &n2 );
}


void test_Two_paths()
{
    Graph g( 4 );

    Node& n1 = g[0];
    Node& n2 = g[1];
    Node& n3 = g[2];
    Node& n4 = g[3];

    n1.AddNeighbour( n2, 3 );
    n1.AddNeighbour( n3, 1 );
    n2.AddNeighbour( n4, 1 );
    n3.AddNeighbour( n4, 7 );

    // n1 --3--> n2 --1--> n4
    //    --1--> n3 --7-->

    Result res = dijkstra( g, n1, n4 );

    assert( res.distance == 4 );
    assert( res.path.size() == 3 );
    assert( res.path[0] == &n1 );
    assert( res.path[1] == &n2 );
    assert( res.path[2] == &n4 );
}



void test_Many_nodes()
{
    Graph g( 10 );

    g[0].AddNeighbour( g[1], 3 );
    g[0].AddNeighbour( g[2], 1 );
    g[1].AddNeighbour( g[3], 1 );
    g[2].AddNeighbour( g[3], 7 );
    g[3].AddNeighbour( g[4], 1 );
    g[2].AddNeighbour( g[5], 1 );
    g[0].AddNeighbour( g[5], 1 );
    g[5].AddNeighbour( g[3], 17 );

    // *0* --3--> 1 --1--> *3* --1--> 4
    //     --1--> 2 --7-->
    //              --1--> 5
    // *0* ------1-------> 5 --17--> *3*

    Result res = dijkstra( g, g[0], g[3] );

    assert( res.distance == 4 );
    assert( res.path.size() == 3 );
    assert( res.path[0] == &g[0] );
    assert( res.path[1] == &g[1] );
    assert( res.path[2] == &g[3] );
}





void test_dijkstra()
{
    test_One_node();
    test_Two_nodes();
    test_Two_branches();
    test_Two_paths();
    test_Many_nodes();
}