#include "cycle_detection.h"
#include "graph.h"
#include "linked_list.h"
#include "vector.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

void cycle_detection(Graph *g) {
    int n = g->num_vertices;

    /* Use `calloc()` to allocate memory
     * initialized to zero */
    int *indegree = calloc(n, sizeof(int));

    LinkedList *queue = linked_list_new();
    if (!queue) {
        fprintf(stderr, "Memory allocation failed: could not create queue.\n");
        free(indegree);
        return;
    }

    Vector *list = vector_new();
    if (!list) {
        fprintf(stderr, "Memory allocation failed: could not create vector.\n");
        free(indegree);
        linked_list_delete(queue);
        return;
    }
    
    // Compute in-degrees
    LinkedListNode *node;
    for (int i = 0; i < n; i++) {
        node = g->vertices[i].out_neighbours->head;
        while (node) {
            indegree[((Vertex *)node->data)->id]++;
            node = node->next;
        }
    }
    
    // Add all vertices with no incoming edges
    for (int i = 0; i < n; i++)
        if (!indegree[i])
            /* Use `intptr_t` to safely store the int as a pointer.
             * `intptr_t` is guaranteed to be pointer-sized
             * (8 bytes on 64-bit systems). */
            linked_list_append(queue, (void *)(intptr_t)i);
    
    while (queue->size) {
        int top = (int)(intptr_t)linked_list_popfront(queue);
        vector_push(list, (void *)(intptr_t)top);

        /* Walk the linked list `out_neighbours`
         * for the graph vertex */
        node = g->vertices[top].out_neighbours->head;
        Vertex *v;
        while (node) {
            v = (Vertex *)node->data;
            indegree[v->id]--;
            if (!indegree[v->id])
                linked_list_append(queue, (void *)(intptr_t)v->id);
            node = node->next;
        }
    }
    
    if ((int)list->size != n)
        fprintf(stdout, "CYCLE DETECTED!\n");
    else {
        for (int i = 0; i < (int)list->size; i++) {
            if (i != 0)
                fprintf(stdout, ", ");
            fprintf(stdout, "%d", (int)(intptr_t)vector_get(list, i));
        }
        fprintf(stdout, "\n");
    }

    linked_list_delete(queue);
    vector_delete(list);
    free(indegree);
}