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

void cycle_detection(Graph *g) {
    int n = g->num_vertices;
    int indegree[n];
    memset(indegree, 0, n * sizeof(int));

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

    Vector *list = vector_new();
    if (!list) {
        fprintf(stderr, "Memory allocation failed: could not create vector.\n");
        linked_list_delete(queue);
        return;
    }

    // Compute in-degrees
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (int)g->vertices[i].out_neighbours->size; j++) {
            Vertex neighbor = *(Vertex *)
                g->vertices[i].out_neighbours->data[j];
            indegree[neighbor.id]++;
        }
    }

    // Add all vertices with no incoming edges
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0)
            linked_list_append(queue, (void *)(intptr_t)i);
    }

    // Process queue for topological sort
    while (queue->size != 0) {
        int top = (int)(intptr_t)linked_list_popfront(queue);
        vector_push(list, (void *)(intptr_t)top);

        // Process all neighbors of current vertex
        for (int j = 0; j < (int)g->vertices[top].out_neighbours->size; j++) {
            Vertex neighbor = *(Vertex *)
                g->vertices[top].out_neighbours->data[j];
            indegree[neighbor.id]--;
            if (!indegree[neighbor.id])
                linked_list_append(queue, (void *)(intptr_t)neighbor.id);
        }
    }

    // Output result
    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);
}