#include <c_DepthFirstOrder.h>


/* Private recursive engine helper */
static void c_DepthFirstOrder_DFS(c_DepthFirstOrder_t* self, c_Digraph_t* graph, c_size_t v) {
    self->marked[v] = C_TRUE;

    /* A. Pre-order: append vertex before visiting neighbors */
    c_VertexIdList_Append(&self->pre_order, (c_uint_t)v);

    c_AdjList_t* adj = &graph->adj_list[v];
    c_size_t size = (c_size_t)c_AdjList_GetSize(adj);

    for (c_size_t i = 0; i < size; ++i) {
        c_uint_t target_value = 0;
        c_err_t err = c_AdjList_Get(adj, i, &target_value);

        if (err == C_SUCCESS) {
            c_size_t w = (c_size_t)target_value;
            if (!self->marked[w]) {
                c_DepthFirstOrder_DFS(self, graph, w);
            }
        }
    }

    /* B. Post-order: append vertex after visiting all its outgoing branches */
    c_VertexIdList_Append(&self->post_order, (c_uint_t)v);
}

c_err_t c_DepthFirstOrder_Init(c_DepthFirstOrder_t* self, c_Digraph_t* graph, c_Allocator_t* allocator) {
    if (!self || !graph) return C_ERR_PARAM;

    self->allocator = allocator ? *allocator : c_DefaultAllocator;
    self->marked = (c_bool_t*)c_Allocator_Calloc(&self->allocator, graph->V, sizeof(c_bool_t));
    if (!self->marked) return C_ERR_NOMEM;

    c_VertexIdList_Init(&self->pre_order, 0, allocator);
    c_VertexIdList_Init(&self->post_order, 0, allocator);
    c_VertexIdList_Init(&self->reverse_post, 0, allocator);

    /* Run DFS across all vertices to guarantee full coverage of disconnected graph structures */
    for (c_size_t v = 0; v < graph->V; ++v) {
        if (!self->marked[v]) {
            c_DepthFirstOrder_DFS(self, graph, v);
        }
    }

    /* C. Build Reverse Post-Order by reading the post-order sequence backwards */
    c_size_t post_size = (c_size_t)c_VertexIdList_GetSize(&self->post_order);
    for (c_size_t i = post_size; i > 0; --i) {
        c_uint_t val = 0;
        c_err_t err = c_VertexIdList_Get(&self->post_order, i - 1, &val);
        if (err == C_SUCCESS) {
            c_VertexIdList_Append(&self->reverse_post, val);
        }
    }

    return C_SUCCESS;
}

void c_DepthFirstOrder_Destroy(c_DepthFirstOrder_t* self) {
    if (!self) return;
    if (self->marked) {
        c_Allocator_Free(&self->allocator, self->marked);
        self->marked = NULL;
    }
    c_VertexIdList_Destroy(&self->pre_order);
    c_VertexIdList_Destroy(&self->post_order);
    c_VertexIdList_Destroy(&self->reverse_post);
}

static c_err_t CopyVertexIdList(c_VertexIdList_t* src, c_VertexIdList_t* dest) {
    if (!src || !dest) return C_ERR_PARAM;
    c_size_t size = (c_size_t)c_VertexIdList_GetSize((c_VertexIdList_t*)src);
    for (c_size_t i = 0; i < size; ++i) {
        c_uint_t val = 0;
        c_err_t err = c_VertexIdList_Get((c_VertexIdList_t*)src, i, &val);
        if (err == C_SUCCESS) {
            c_err_t app_err = c_VertexIdList_Append(dest, val);
            if (app_err != C_SUCCESS) return app_err;
        }
    }
    return C_SUCCESS;
}

c_err_t c_DepthFirstOrder_GetPre(c_DepthFirstOrder_t* self, c_VertexIdList_t* out_list) {
    return CopyVertexIdList(&self->pre_order, out_list);
}

c_err_t c_DepthFirstOrder_GetPost(c_DepthFirstOrder_t* self, c_VertexIdList_t* out_list) {
    return CopyVertexIdList(&self->post_order, out_list);
}

c_err_t c_DepthFirstOrder_GetReversePost(c_DepthFirstOrder_t* self, c_VertexIdList_t* out_list) {
    return CopyVertexIdList(&self->reverse_post, out_list);
}