#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_ITERATIONS 5

int main(int argc, char** argv) {
    MPI_Init(&argc, &argv);

    int world_rank, world_size;
    MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
    MPI_Comm_size(MPI_COMM_WORLD, &world_size);

    // Phase 1: Leader Election
    int leader = world_rank;
    for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
        for (int i = 0; i < world_size; i++) {
            if (i != world_rank) {
                MPI_Send(&leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
                int received_leader;
                MPI_Recv(&received_leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                if (received_leader > leader) {
                    leader = received_leader;
                }
            }
        }
    }

    // Phase 2: Epidemic Algorithm for Node Count
    double val = (world_rank == leader) ? 1.0 : 0.0;
    for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
        for (int i = 0; i < world_size; i++) {
            if (i != world_rank) {
                MPI_Send(&val, 1, MPI_DOUBLE, i, 0, MPI_COMM_WORLD);
                double recv_val;
                MPI_Recv(&recv_val, 1, MPI_DOUBLE, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                val = (val + recv_val) / 2.0;
            }
        }
    }
    double node_count = 1.0 / val;

    // Phase 3: Tree Algorithm for Topology Matrix
    int *topology = (int*)malloc(world_size * sizeof(int));
    for (int i = 0; i < world_size; i++) {
        topology[i] = -1;  // Initialize topology array
    }

    if (world_rank == leader) {
        for (int i = 0; i < world_size; i++) {
            if (i != leader) {
                topology[i] = leader;  // Leader assumes it is the parent
            }
        }
    } else {
        topology[world_rank] = world_rank;  // Non-leader nodes assume they are their own parent
    }

    // Broadcast the topology
    MPI_Bcast(topology, world_size, MPI_INT, leader, MPI_COMM_WORLD);

    // Print results
    printf("Process %d: Leader is %d, Node count is %.0f\n", world_rank, leader, node_count);
    for (int i = 0; i < world_size; i++) {
        printf("Process %d: Parent of node %d is %d\n", world_rank, i, topology[i]);
    }

    free(topology);
    MPI_Finalize();
    return 0;
}