#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

typedef struct list_item {
    vertex_t *v;
    struct list_item *next;
    struct list_item *prev;
} list_item_t;

typedef struct {
    int len;
    struct list_item *begin;
    struct list_item *end;
} list_t;

void list_push(list_t *s, vertex_t *v)
{
    // Create
    list_item_t *i = malloc(sizeof(list_item_t));
    i->next = NULL;
    i->prev = NULL;
    i->v = v;

    // Link
    if (s->len == 0) {
        s->begin = i;
    } else {
        s->end->next = i;
        i->prev = s->end;
    }

    s->end = i;
    s->len++;
}

vertex_t *list_pop_smallest(list_t *s)
{
    list_item_t *smallest = s->begin;

    // Search
    list_item_t *i = s->begin;
    while (i) {
        if (i->v->dist != -1 && i->v->dist < smallest->v->dist) {
            smallest = i;
        }
        i = i->next;
    }

    if (smallest == s->begin) {
        s->begin = smallest->next;
    } else {
        smallest->prev->next = smallest->next;
    }

    if (smallest == s->end) {
        s->end = smallest->prev;
    } else {
        smallest->next->prev = smallest->prev;
    }

    vertex_t *v = smallest->v;
    free(smallest);

    s->len--;

    return v;
}

graph_t g;

// Assumes u has an edge to v
void relax(vertex_t *u, vertex_t *v)
{
    // Get edge between these two guys
    edge_t *e = u->adj;
    while (e && e->next && e->to->ref != v->ref) {
        e = e->next;
    }

    if (v->dist == -1 || v->dist > (u->dist + e->weight)) {
        v->dist = u->dist + e->weight;
        v->p = u;
    }
}

void dijkstra(graph_t *g, vertex_t *s)
{
    list_t list;
    list.len = 0;
    list.end = list.begin = 0;

    s->dist = 0;

    {
        vertex_t *v = vertex_next(g, NULL);
        while (v) {
            list_push(&list, v);
            v = vertex_next(g, v);
        }
    }

    while (list.len) {
        vertex_t *u = list_pop_smallest(&list);
        edge_t *e = u->adj;
        while (e) {
            relax(u, e->to);
            e = e->next;
        }
    }
}

int main()
{
    graph_edge(&g, 'a', 'b', 2);
    graph_edge(&g, 'a', 'f', 1);

    graph_edge(&g, 'b', 'd', 3);
    graph_edge(&g, 'b', 'c', 4);

    graph_edge(&g, 'd', 'b', 1);
    graph_edge(&g, 'd', 'e', 8);

    graph_edge(&g, 'c', 'a', 7);
    graph_edge(&g, 'c', 'd', 7);
    graph_edge(&g, 'c', 'f', 2);

    graph_edge(&g, 'e', 'c', 2);
    graph_edge(&g, 'e', 'f', 2);

    dijkstra(&g, g.vertexes['a']);

    graph_to_dot(stdout, &g);

    return 0;
}