/* ========================================================================
   $Creator: Emanuel Truta $
   $Notice: (C) Copyright 2016 by Emanuel Truta. All Rights Reserved. $
   ======================================================================== */


#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <queue>


#include <stdint.h>
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef int32_t b32;

#define internal static
#define local_persist static
#define global_variable static

#define Assert(Expression) if (!(Expression)) { *((int *)0) = 0; }

// #include "graph.cpp"
// ======================================================================== GRAPH.H
// NOTE(manu): Vertices are specified as integers from 1 to N-1
struct graph
{
    struct edge
    {
        u32 Node;
        i32 Cost;
    };
    typedef std::vector<edge>::iterator iter;
    
    
    u32 Size;
    b32 Directed;
    b32 ProvideReverse;
    b32 StartIndex;

    std::vector< std::vector<edge> > Out;
    std::vector< std::vector<edge> > In;
    

    void Read(char *Filename);
    // void Print();
    b32 HasEdge(u32 Node1, u32 Node2);
    i32 GetCost(u32 Node1, u32 Node2);
    void SetCost(u32 Node1, u32 Node2, i32 NewCost);

    
    std::vector<u32> DoForwardBFS(u32 Node);
    std::vector<u32> DoBackwardBFS(u32 Node);
    std::vector<u32> DoDijkstra(u32 Node);
    u32 GetDistanceForwardBFS(u32 Node1, u32 Node2);
    u32 GetDistanceBackwardBFS(u32 Node1, u32 Node2);
    u32 GetDistandeDijkstra(u32 Node1, u32 Node2);
};
// ========================================================================

// ======================================================================== GRAPH.CPP
// #include "graph.h"


void graph::
Read(char *Filename)
{
    FILE *File = fopen(Filename, "r");

    u32 EdgesCount;
    fscanf(File, "%d %d\n", &Size, &EdgesCount);
    Size += StartIndex;
    Out.resize(Size);
    if (ProvideReverse)
    {
        In.resize(Size);
    }

    for (u32 Index = 0; Index < EdgesCount; ++Index)
    {
        u32 X, Y;
        i32 Cost;

        fscanf(File, "%d %d %d\n", &X, &Y, &Cost);

        if (Directed)
        {
            Out[X].push_back(edge{Y, Cost});
            if (ProvideReverse)
            {
                In[Y].push_back(edge{X, Cost});
            }
        }
        else
        {
            Out[X].push_back(edge{Y, Cost});
            Out[Y].push_back(edge{X, Cost});
        }
    }
}


// void graph::
// Print()
// {
//     for (u32 Index = 0; Index < Size; ++Index)
//     {
//         printf("%d: ", Index);
//         for (iter It = Out[Index].begin(); It != Out[Index].end(); ++It)
//         {
//             printf("%d ", It->Node);
//         }
//         printf("\n");
//     }
// }


b32 graph::
HasEdge(u32 Node1, u32 Node2)
{
    b32 Result = 0;

    for (iter It = Out[Node1].begin(); It != Out[Node1].end(); ++It)
    {
        if (It->Node == Node2)
        {
            Result = 1;
        }
    }
    
    return Result;
}


i32 graph::
GetCost(u32 Node1, u32 Node2)
{
    for (iter It = Out[Node1].begin(); It != Out[Node1].end(); ++It)
    {
        if (It->Node == Node2)
        {
            return It->Cost;
        }
    }

    return 0xcccccccc;
}


void graph::
SetCost(u32 Node1, u32 Node2, i32 NewCost)
{
    for (iter It = Out[Node1].begin(); It != Out[Node1].end(); ++It)
    {
        if (It->Node == Node2)
        {
            It->Cost = NewCost;
        }
    }

    if (Directed && ProvideReverse)
    {
        for (iter It = In[Node2].begin(); It != In[Node2].end(); ++It)
        {
            if (It->Node == Node1)
            {
                It->Cost = NewCost;
            }
        }
    }

    if (!Directed)
    {
        for (iter It = Out[Node2].begin(); It != Out[Node2].end(); ++It)
        {
            if (It->Node == Node1)
            {
                It->Cost = NewCost;
            }
        }
    }
}


std::vector<u32> graph::
DoForwardBFS(u32 Node)
{
    std::vector<u32> Dist;
    Dist.resize(Size);
    for (u32 I = 0; I < Size; ++I)
    {
        Dist[I] = 0x3f3f3f3f;
    }
    Dist[Node] = 0;

    std::queue<u32> Q;
    Q.push(Node);
    while (!Q.empty())
    {
        u32 Node = Q.front();
        Q.pop();

        for (u32 I = 0; I < Out[Node].size(); ++I)
        {
            if (Dist[Out[Node][I].Node] > Dist[Node] + Out[Node][I].Cost)
            {
                Dist[Out[Node][I].Node] = Dist[Node] + Out[Node][I].Cost;
                Q.push(Out[Node][I].Node);
            }
        }
    }
    
    return Dist;
}

std::vector<u32> graph::
DoBackwardBFS(u32 Node)
{
    std::vector<u32> Dist;
    Dist.resize(Size);
    for (u32 I = 0; I < Size; ++I)
    {
        Dist[I] = 0x3f3f3f3f;
    }
    Dist[Node] = 0;

    if (!ProvideReverse)
    {
        return Dist;
    }

    std::queue<u32> Q;
    Q.push(Node);
    while (!Q.empty())
    {
        u32 Node = Q.front();
        Q.pop();

        for (u32 I = 0; I < In[Node].size(); ++I)
        {
            if (Dist[In[Node][I].Node] > Dist[Node] + In[Node][I].Cost)
            {
                Dist[In[Node][I].Node] = Dist[Node] + In[Node][I].Cost;
                Q.push(In[Node][I].Node);
            }
        }
    }
    
    return Dist;
}

std::vector<u32> graph::
DoDijkstra(u32 Node)
{
    std::vector<b32> Viz;
    std::vector<u32> Dist;
    Viz.resize(Size);
    Dist.resize(Size);
    for (u32 I = 0; I < Size; ++I)
    {
        Dist[I] = 0x3f3f3f3f;
        Viz[I] = 0;
    }
    Dist[Node] = 0;

    std::priority_queue< std::pair<i32, u32> > PQ;
    PQ.push(std::make_pair(0, Node));
    while (!PQ.empty())
    {
        u32 Node = PQ.top().second;
        PQ.pop();

        if (Viz[Node])
        {
            continue;
        }
        Viz[Node] = 1;

        for (u32 I = 0; I < Out[Node].size(); ++I)
        {
            if (Dist[Out[Node][I].Node] > Dist[Node] + Out[Node][I].Cost)
            {
                Dist[Out[Node][I].Node] = Dist[Node] + Out[Node][I].Cost;
                PQ.push(std::make_pair(-Dist[Out[Node][I].Node], Out[Node][I].Node));
            }
        }
    }
    return Dist;
}

u32 graph::
GetDistanceForwardBFS(u32 Node1, u32 Node2)
{
    std::vector<u32> Dist = DoForwardBFS(Node1);
    return Dist[Node2];
}

u32 graph::
GetDistanceBackwardBFS(u32 Node1, u32 Node2)
{
    std::vector<u32> Dist = DoBackwardBFS(Node2);
    return Dist[Node1];
}


// ========================================================================


int main()
{
    printf("===========================\n");
    graph Graph = {};
    Graph.Directed = 1;
    Graph.StartIndex = 1;

    // Reading a graph from a file.
    char *GraphInputFile = "dijkstra.in";
    Graph.Read(GraphInputFile);
    printf("Graph read from file: %s\n", GraphInputFile);

    // Get Graph Size.
    printf("Size of graph: %d\n", Graph.Size);

    // Check if edge exists.
    printf("Edge between %d and %d: %d\n", 1, 2, Graph.HasEdge(1, 3));

    // GetInDeggee of vertex.
    // printf("In degree of %d is: %d: \n", 1, Graph.In[1].size());

    // GetOutDeggee of vertex.
    printf("Out degree of %d is: %d: \n", 1, Graph.Out[1].size());

    // GetOutboundNeighbours
    i32 CheckVertex = 1;
    printf("Outbound neighbours of %d: ", CheckVertex);
    for (graph::iter it = Graph.Out[CheckVertex].begin(); it != Graph.Out[CheckVertex].end(); ++it)
    {
        printf("%d ", it->Node);
    }
    printf("\n");

    // // GetInboundNeighbours
    // CheckVertex = 1;
    // printf("Outbound neighbours of %d: ", CheckVertex);
    // for (graph::iter it = Graph.In[CheckVertex].begin(); it != Graph.In[CheckVertex].end(); ++it)
    // {
    //     printf("%d ", it->Node);
    // }
    // printf("\n");


    // GetCost
    printf("Cost of edge %d %d is: %d\n", 1, 5, Graph.GetCost(1, 5));

    // SetCost
    Graph.SetCost(1, 5, 100);
    printf("Changed cost of edge %d %d is now: %d\n", 1, 5, Graph.GetCost(1, 5));

    std::vector<u32> Dist = Graph.DoDijkstra(1);
    FILE* OutFile = fopen("dijkstra.out", "w");
    for (u32 I = 2; I < Dist.size(); I++)
    {
        if (Dist[I] == 0x3f3f3f3f) Dist[I] = 0;
        fprintf(OutFile, "%d ", Dist[I]);
    }
    fprintf(OutFile, "\n");

    printf("\n");
    return 0;
}