#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_NAME 50
#define MAX_ZONES 100
#define MAX_PEOPLE_PER_ZONE 50

typedef struct {
    char name[MAX_NAME];
    int injury_status;
    int rescue_time;
    int has_supply;
    int is_rescued;
    int original_zone;  
} Person;

typedef struct {
    Person people[MAX_PEOPLE_PER_ZONE];
    int num_people;
    int supplies;
    int injured_count;
    int uninjured_count;
    int priority;
    int zone_id;
    int injured_needing_supplies;
    int total_needing_supplies;
    int people_remaining;
} Zone;

typedef struct {
    Zone zones[MAX_ZONES];
    int num_zones;
    int rescuer_supplies;
} RescueOperation;

typedef struct Node {
    Person person;
    struct Node* left;
    struct Node* right;
} Node;

int compare_names(const void* a, const void* b) {
    return strcmp(((Person*)a)->name, ((Person*)b)->name);
}

void calculate_zone_priorities(RescueOperation* op) {
    for (int i = 0; i < op->num_zones; i++) {

         // Creating the zones
        Zone* zone = &op->zones[i];
        zone->zone_id = i + 1;
        
        // Reset counts
        zone->injured_count = 0;
        zone->uninjured_count = 0;
        zone->people_remaining = 0;
        zone->injured_needing_supplies = 0;
        zone->total_needing_supplies = 0;
        
        // Count injured and uninjured people who haven't been rescued
        for (int j = 0; j < zone->num_people; j++) {
            if (!zone->people[j].is_rescued) {
                zone->people_remaining++;
                if (zone->people[j].injury_status == 1) {
                    zone->injured_count++;

                    // Count injured people needing supplies
                    if (!zone->people[j].has_supply) {
                        zone->injured_needing_supplies++;
                    }
                } else {
                    zone->uninjured_count++;
                }
                // Count total people needing supplies
                if (!zone->people[j].has_supply) {
                    zone->total_needing_supplies++;
                }
            }
        }
    }
}

int compare_zones(const void* a, const void* b) {
    Zone* zone_a = (Zone*)a;
    Zone* zone_b = (Zone*)b;
    
    // Priority 1: Number of injured people needing supplies
    if (zone_a->injured_needing_supplies != zone_b->injured_needing_supplies)
        return zone_b->injured_needing_supplies - zone_a->injured_needing_supplies;
    
    // Priority 2: Total number of injured people
    if (zone_a->injured_count != zone_b->injured_count)
        return zone_b->injured_count - zone_a->injured_count;
    
    // Priority 3: Total people needing supplies
    if (zone_a->total_needing_supplies != zone_b->total_needing_supplies)
        return zone_b->total_needing_supplies - zone_a->total_needing_supplies;
    
    // Priority 4: Total remaining people
    if (zone_a->people_remaining != zone_b->people_remaining)
        return zone_b->people_remaining - zone_a->people_remaining;
    
    // Priority 5: Lower zone ID has higher priority
    return zone_a->zone_id - zone_b->zone_id;
}

void initialize_system(RescueOperation* op) {
    op->num_zones = 0;
    op->rescuer_supplies = 0;
}

void add_zone(RescueOperation* op) {
    printf("Enter the number of zones to add: ");
    int zones_to_add;
    scanf("%d", &zones_to_add);
    
    if (op->num_zones + zones_to_add > MAX_ZONES) {
        printf("Error: Cannot add more zones. Maximum limit reached.\n");
        return;
    }

    for (int i = 0; i < zones_to_add; i++) {
        // Addition of more zones
        Zone* current_zone = &op->zones[op->num_zones + i];
        current_zone->injured_count = 0;
        current_zone->uninjured_count = 0;
        current_zone->people_remaining = 0;
        current_zone->supplies = 0;
        
        printf("\nEnter the number of people in Zone %d: ", op->num_zones + i + 1);
        scanf("%d", &current_zone->num_people);
        
        if (current_zone->num_people > MAX_PEOPLE_PER_ZONE) {
            printf("Error: Too many people for one zone.\n");
            return;
        }

        for (int j = 0; j < current_zone->num_people; j++) {
            printf("Enter name for person %d in Zone %d: ", j + 1, op->num_zones + i + 1);
            scanf("%s", current_zone->people[j].name);
            
            printf("Enter injury status for %s (0=WITHOUT_INJURY, 1=WITH_INJURY): ", 
                   current_zone->people[j].name);
            scanf("%d", &current_zone->people[j].injury_status);
            
            if (current_zone->people[j].injury_status == 1) {
                current_zone->injured_count++;
            } else {
                current_zone->uninjured_count++;
            }
            current_zone->people[j].has_supply = 0;
            current_zone->people[j].is_rescued = 0;
            current_zone->people[j].original_zone = op->num_zones + i + 1;  // Store original zone
            current_zone->people_remaining++; //Incrementing the amount of people in the zone
        }

        printf("Enter the number of supplies available in Zone %d: ", op->num_zones + i + 1);
        scanf("%d", &current_zone->supplies);
        
        // Sort people by name within zone before distributing supplies
        qsort(current_zone->people, current_zone->num_people, sizeof(Person), compare_names);
        
        // Distribute available zone supplies
        int supplies_left = current_zone->supplies;
        // First to injured (in alphabetical order)
        for (int j = 0; j < current_zone->num_people && supplies_left > 0; j++) {
            if (current_zone->people[j].injury_status == 1 && !current_zone->people[j].has_supply) {
                current_zone->people[j].has_supply = 1;
                supplies_left--;
            }
        }
        // Then to uninjured (in alphabetical order)
        for (int j = 0; j < current_zone->num_people && supplies_left > 0; j++) {
            if (current_zone->people[j].injury_status == 0 && !current_zone->people[j].has_supply) {
                current_zone->people[j].has_supply = 1;
                supplies_left--;
            }
        }
    }
    
    op->num_zones += zones_to_add; //Adding the additional zones
    calculate_zone_priorities(op);
}

void add_supplies_to_rescuers(RescueOperation* op) {
    printf("Current supplies with rescuers: %d\n", op->rescuer_supplies);
    printf("Enter supply quantity to add to rescuers: ");
    int add_supplies;
    scanf("%d", &add_supplies);
    
    if (add_supplies < 0) {
        printf("Error: Cannot add negative supplies.\n");
        return;
    }
    
    op->rescuer_supplies += add_supplies;
    printf("Supplies added. Total available supplies with rescuers: %d\n", 
           op->rescuer_supplies);
}

Node* insert_rescued_person(Node* root, Person person) {
    if (root == NULL) {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->person = person;
        new_node->left = new_node->right = NULL;
        return new_node;
    }
    
    if (person.rescue_time < root->person.rescue_time)
        root->left = insert_rescued_person(root->left, person);
    else
        root->right = insert_rescued_person(root->right, person);
    
    return root;
}

void display_zone_details(RescueOperation* op) {
    printf("\nZone Details (Ordered by Priority):\n");
    for (int i = 0; i < op->num_zones; i++) {
        Zone* zone = &op->zones[i];
        printf("\nZone %d:", zone->zone_id);
        printf("\nTotal People: %d, Injured People: %d", 
               zone->num_people, zone->injured_count);
        printf("\nPeople with Supplies:");
        
        // Display people who have supplies (sorted by name)
        for (int j = 0; j < zone->num_people; j++) {
            if (zone->people[j].has_supply) {
                printf("\n  %s [%s]", 
                       zone->people[j].name,
                       zone->people[j].injury_status ? "With Injury" : "Without Injury");
            }
        }
        printf("\n");
    }
}

void rescue_phase(RescueOperation* op, Node** rescued_tree, int* current_time) {
    int total_people_remaining;
    do {
        total_people_remaining = 0;
        calculate_zone_priorities(op);
        qsort(op->zones, op->num_zones, sizeof(Zone), compare_zones);
        
        // First pass: Rescue injured people zone by zone based on priority
        for (int i = 0; i < op->num_zones; i++) {
            Zone* current_zone = &op->zones[i];
            
            for (int j = 0; j < current_zone->num_people; j++) {
                if (!current_zone->people[j].is_rescued && 
                    current_zone->people[j].injury_status == 1) {
                    (*current_time)++;
                    current_zone->people[j].is_rescued = 1;
                    current_zone->people[j].rescue_time = *current_time;
                    current_zone->people_remaining--;
                    printf("Rescued injured person: %s at time %d from Zone %d\n",
                           current_zone->people[j].name, *current_time, current_zone->people[j].original_zone);
                    *rescued_tree = insert_rescued_person(*rescued_tree, current_zone->people[j]);
                }
            }
        }
        
        // Second pass: Rescue uninjured people zone by zone based on priority
        for (int i = 0; i < op->num_zones; i++) {
            Zone* current_zone = &op->zones[i];
            
            for (int j = 0; j < current_zone->num_people; j++) {
                if (!current_zone->people[j].is_rescued && 
                    current_zone->people[j].injury_status == 0) {
                    (*current_time)++;
                    current_zone->people[j].is_rescued = 1;
                    current_zone->people[j].rescue_time = *current_time;
                    current_zone->people_remaining--;
                    printf("Rescued uninjured person: %s at time %d from Zone %d\n",
                           current_zone->people[j].name, *current_time, current_zone->people[j].original_zone);
                    *rescued_tree = insert_rescued_person(*rescued_tree, current_zone->people[j]);
                }
            }
        }
        
        // Count remaining people
        for (int i = 0; i < op->num_zones; i++) {
            total_people_remaining += op->zones[i].people_remaining;
        }
        
    } while (total_people_remaining > 0);
}

void supply_distribution_phase(RescueOperation* op) {
    while (op->rescuer_supplies > 0) {
        calculate_zone_priorities(op);
        qsort(op->zones, op->num_zones, sizeof(Zone), compare_zones);
        
        int supplies_distributed = 0;
        
        // First distribute to injured people based on zone priority
        for (int i = 0; i < op->num_zones && op->rescuer_supplies > 0; i++) {
            Zone* current_zone = &op->zones[i];
            
            // Distribute to injured people in alphabetical order
            for (int j = 0; j < current_zone->num_people && op->rescuer_supplies > 0; j++) {
                if (current_zone->people[j].injury_status == 1 && 
                    !current_zone->people[j].has_supply) {
                    current_zone->people[j].has_supply = 1;
                    op->rescuer_supplies--;
                    supplies_distributed++;
                    printf("Provided supply to injured person: %s in Zone %d\n",
                           current_zone->people[j].name, current_zone->people[j].original_zone);
                    current_zone->injured_needing_supplies--;
                    current_zone->total_needing_supplies--;
                }
            }
            
            // Then distribute to uninjured people in alphabetical order
            for (int j = 0; j < current_zone->num_people && op->rescuer_supplies > 0; j++) {
                if (current_zone->people[j].injury_status == 0 && 
                    !current_zone->people[j].has_supply) {
                    current_zone->people[j].has_supply = 1;
                    op->rescuer_supplies--;
                    supplies_distributed++;
                    printf("Provided supply to uninjured person: %s in Zone %d\n",
                           current_zone->people[j].name, current_zone->people[j].original_zone);
                    current_zone->total_needing_supplies--;
                }
            }
        }
        
        if (supplies_distributed == 0) break;  // No more people need supplies
    }
}

void execute_rescue_mission(RescueOperation* op, Node** rescued_tree, int* current_time) {
    if (op->num_zones == 0) {
        printf("No zones to rescue from.\n");
        return;
    }
    
    printf("\nStarting Rescue Phase...\n");
    rescue_phase(op, rescued_tree, current_time);
    
    // Display zone details after rescue phase
    display_zone_details(op);
    
    printf("\nStarting Supply Distribution Phase...\n");
    supply_distribution_phase(op);
    
    printf("\nRescue mission completed.\n");
}

void display_rescued_tree(Node* root) {
    if (root != NULL) {
        display_rescued_tree(root->left);
        printf("Rescued %s at Time %d [%s]\n",
               root->person.name,
               root->person.rescue_time,
               root->person.injury_status ? "With Injury" : "Without Injury");
        display_rescued_tree(root->right);
    }
}

void display_rescued_members(Node* rescued_tree) {
    if (rescued_tree == NULL) {
        printf("No rescued members yet.\n");
        return;
    }
    printf("\nRescued Members (in order of rescue time):\n");
    display_rescued_tree(rescued_tree);
}

void cleanup_tree(Node* root) {
    if (root != NULL) {
        cleanup_tree(root->left);
        cleanup_tree(root->right);
        free(root);
    }
}

int main() {
    RescueOperation operation;
    Node* rescued_tree = NULL;
    int current_time = 0;
    
    initialize_system(&operation);
    int choice;
    
    do {
        printf("\nMenu:\n");
        printf("1. Add Zone\n");
        printf("2. Add Supplies to Rescuers\n");
        printf("3. Execute Rescue Mission\n");
        printf("4. Display Rescued Members\n");
        printf("5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                add_zone(&operation);
                break;
            case 2:
                add_supplies_to_rescuers(&operation);
                break;
            case 3:
                execute_rescue_mission(&operation, &rescued_tree, &current_time);
                break;
            case 4:
                display_rescued_members(rescued_tree);
                break;
            case 5:
                printf("Exiting program.\n");
                cleanup_tree(rescued_tree);
                break;
            default:
                printf("Invalid choice. Please try again.\n");
        }
    } while (choice != 5);
    
    return 0;
}

use priority queues in the given code rathen than assigning priority