#include "c_Test.h"
#include "c_EdgeWeightedGraph.h"
#include "c_KruskalMST.h"
#include "c_VertexIdList.h"

TEST_CASE(test_kruskal_mst_with_quick_find_uf) {
    c_EdgeWeightedGraph_t g;
    c_err_t err = c_EdgeWeightedGraph_Init(&g, 4, NULL);
    ASSERT_INT_EQ(C_SUCCESS, err);

    /* Construct a graph topology to test tree minimization:
     * 0 - 1 (Weight: 1.0)
     * 1 - 2 (Weight: 2.0)
     * 2 - 3 (Weight: 3.0)
     * 3 - 0 (Weight: 4.0) -> Redundant loop closer skipped
     * 0 - 2 (Weight: 5.0) -> Heavier cross edge skipped
     */
    c_EdgeWeightedGraph_AddEdge(&g, 0, 1, 1.0);
    c_EdgeWeightedGraph_AddEdge(&g, 1, 2, 2.0);
    c_EdgeWeightedGraph_AddEdge(&g, 2, 3, 3.0);
    c_EdgeWeightedGraph_AddEdge(&g, 3, 0, 4.0);
    c_EdgeWeightedGraph_AddEdge(&g, 0, 2, 5.0);

    c_KruskalMST_t kruskal;
    err = c_KruskalMST_Init(&kruskal, &g, &g.allocator);
    ASSERT_INT_EQ(C_SUCCESS, err);

    /* Total minimum weight summation must equal 1.0 + 2.0 + 3.0 = 6.0 */
    ASSERT_DOUBLE_EQ_MSG(6.0, c_KruskalMST_Weight(&kruskal), "Kruskal MST calculation failed");

    c_VertexIdList_t result_list;
    c_VertexIdList_Init(&result_list, 0, 0);

    err = c_KruskalMST_GetEdges(&kruskal, &result_list);
    ASSERT_INT_EQ(C_SUCCESS, err);
    ASSERT_INT_EQ(3, c_UIntArray_GetSize(&result_list));

    c_VertexIdList_Destroy(&result_list);
    c_KruskalMST_Destroy(&kruskal);
    c_EdgeWeightedGraph_Destroy(&g);
}

int main(void) {
    TEST_START(Kruskal_MST_QuickFind_UF_Suite);
    RUN_TEST(test_kruskal_mst_with_quick_find_uf);
    TEST_REPORT();
    RETURN_TEST_STATUS;
}