// Dijkstra'sshortest path algorithm.
// The program is for adjacency matrix representation of the graph
#include <stdio.h>
#include <uart.h>
#include <system/peripherals.h>
#include <libacc.h>

// Number of vertices in the graph
#define V 24

typedef char bool;
#define true 1
#define false 0
#define INT_MAX  131071

int printSolution(int dist[], int n) {
    printf("\r\nVertex   Distance from Source\r\n");
    for (int i = 0; i < V; i++)
       printf("%d \t\t %d\r\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src) {
    int min = 0, min_index = 0, u = 0;
    // The output array.  dist[i] will hold the shortest distance from src to i
    int dist[V];
    // sptSet[i] will true if vertex i is included in shortest
    // path tree or shortest distance from src to i is finalized
    bool sptSet[V];

    for (int i = 0; i < V; i++) {
       //NO_SYNTHESIS;
       dist[i] = INT_MAX, sptSet[i] = false;
    }

    //printSolution(dist, V);
    dist[src] = 0;

    // Find shortest path for all vertices
    for (int count = 0; count < V-1; count++) {
        // Pick the minimum distance vertex from the set of vertices not
        // yet processed. u is always equal to src in first iteration.
        min = INT_MAX;
        for (int v = 0; v < V; v++) {
            //NO_SYNTHESIS;
            if (sptSet[v] == false && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
        }
        u = min_index;
        sptSet[u] = true;

        /*
         * Update dist value of the adjacent vertices of the picked vertex.
         * Update dist[v] only if is not in sptSet, there is an edge from
         * u to v, and total weight of path from src to  v through u is
         * smaller than current value of dist[v]
         */
        for (int v = 0; v < V; v++) {
            //NO_SYNTHESIS;
            //printf("\r\n v: %d", v);
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                //&& graph[u][v] < dist[v]) {
                && dist[u]+graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                //dist[v] = graph[u][v];
                //printf("\r\n dist[v]: %d graph[u][v]: %d", dist[v],graph[u][v]);
                //printf("\r\n dist[u]: %d sptSet[v]: %d", dist[u],sptSet[v]);
            }
        }
    }
    printSolution(dist, V);
}

int main() {
    stdio_uart_open(UART_LIGHT_0);
    TIMER_0->limit = 131072;    //2^17     = 0x20000
    TIMER_1->limit = 262143;    //2^18 - 1 = 0x3ffff
    /* Example Graph */
   // int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
   //                    {4, 0, 8, 0, 0, 0, 0, 11,0},
   //                    {0, 8, 0, 7, 0, 4, 0, 0, 2},
   //                    {0, 0, 7, 0, 9, 14,0, 0, 0},
   //                    {0, 0, 0, 9, 0, 10,0, 0, 0},
   //                    {0, 0, 4, 0, 10,0, 2, 0, 0},
   //                    {0, 0, 0, 14,0, 2, 0, 1, 6},
   //                    {8, 11,0, 0, 0, 0, 1, 0, 7},
   //                    {0, 0, 2, 0, 0, 0, 6, 7, 0}
   //                  };


    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {4, 0, 8, 0, 0, 0, 0, 11,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 7, 0, 9, 14,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 9, 0, 10,0, 0, 0, 0, 0, 6,15, 8, 0, 0, 0, 0,12, 0, 0, 0, 0 ,0},
                       {0, 0, 4, 0, 10,0, 2, 0, 0, 0, 0,12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 14,0, 2, 0, 1, 6, 0, 0, 0, 0, 0, 0, 0, 0, 4, 5, 0, 0, 0, 0 ,0},
                       {8, 11,0, 0, 0, 0, 1, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0 ,0},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,13, 7, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 6,12, 0, 0, 0, 0, 0, 0, 8, 0, 6, 0, 0, 0, 0, 0, 4, 0, 0 ,0},
                       {0, 0, 0, 0,15, 0, 0, 0, 0, 0, 0, 8, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 1, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0,13, 0, 6, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,9},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 2, 0, 5, 0, 0 ,0},
                       {0, 0, 0, 0,12, 0, 5, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 3, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0 ,0},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ,0},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ,2},
                       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 2 ,0}
                     };

     printf("\r\n === Dijkstra Algorithm ===\r\n");

     // HW Execution
     libacc_enable_accels();
     TIMER_0->control |= TIMER_CNT_RST;
     TIMER_0->control &= !TIMER_CNT_RST;
     TIMER_1->control |= TIMER_CNT_RST;
     TIMER_0->control &= !TIMER_CNT_RST;
     TIMER_1->control = TIMER_EN;
     TIMER_0->control = TIMER_EN;
     dijkstra(graph, 0);
     TIMER_0->control = 0;
     TIMER_1->control = 0;
     printf("\r\n HW timer value: %6u ov: %6u", TIMER_0->value, TIMER_1->value);


     // SW Execution
     libacc_disable_accels();
     TIMER_0->control |= TIMER_CNT_RST;
     TIMER_0->control &= !TIMER_CNT_RST;
     TIMER_1->control |= TIMER_CNT_RST;
     TIMER_0->control &= !TIMER_CNT_RST;
     TIMER_1->control = TIMER_EN;
     TIMER_0->control = TIMER_EN;
     dijkstra(graph, 0);
     TIMER_0->control = 0;
     TIMER_1->control = 0;
     printf("\r\n SW timer value: %6u ov: %6u", TIMER_0->value, TIMER_1->value);

     while(1);
}