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

#define MAX_ZONES 5   // Define the maximum number of zones
#define STACK_SIZE 50 // Define the maximum stack size for supplies

typedef struct {
    int id;           // Zone ID
    int priority;     // Priority of the zone (lower number means higher priority)
    int people;       // Number of people to rescue
    int zoneSupplies; // Supplies specific to the zone
} Zone;

typedef struct {
    int supplies[STACK_SIZE]; // Array to store the supplies
    int top;                  // Top index of the stack
} Stack;

typedef struct Node {
    int time;                 // Time of the rescue
    char name[20];            // Name of the rescued person
    struct Node *left, *right; // Pointers for left and right children in BST
} RescuedPerson;

// Function prototypes
void initStack(Stack *s);
int isStackEmpty(Stack *s);
int canAddSupplies(Stack *s, int quantity);
void addSupplies(Stack *s, int quantity);
void useSupplies(Stack *s, int quantity);
void addZone(Zone zones[], int *zoneCount);
void heapifyDown(Zone zones[], int size);
void rescue(Stack *s, Zone zones[], int *zoneCount, RescuedPerson **root);
RescuedPerson* insertBST(RescuedPerson *root, int time, char name[]);
void displayRescued(RescuedPerson *root);
void inOrder(RescuedPerson *root);

void initStack(Stack *s) { s->top = -1; } // Initialize the stack

int isStackEmpty(Stack *s) { return s->top == -1; } // Check if stack is empty

int canAddSupplies(Stack *s, int quantity) { return s->top + quantity < STACK_SIZE; } // Check if supplies can be added

// Add multiple supplies to the stack
void addSupplies(Stack *s, int quantity) {
    if (canAddSupplies(s, quantity)) {
        s->top += quantity; // Directly adjust the top pointer to add supplies
    } else {
        printf("Cannot add %d more supplies, stack overflow.\n", quantity);
    }
}

// Use (pop) multiple supplies from the stack
void useSupplies(Stack *s, int quantity) 
{
    for (int i = 0; i < quantity; i++) {
        if (!isStackEmpty(s)) {
            s->top--;
        } else {
            printf("Ran out of supplies unexpectedly.\n");
            return;
        }
    }
}

// Add a zone with heap property maintenance
void addZone(Zone zones[], int *zoneCount) {
    if (*zoneCount >= MAX_ZONES) {
        printf("Cannot add more zones.\n");
        return;
    }
    int id, priority, people, zoneSupplies;
    printf("Enter Zone ID, Priority (1-5), People, and Zone Specific Supplies: ");
    scanf("%d %d %d %d", &id, &priority, &people, &zoneSupplies);
    Zone newZone = {id, priority, people, zoneSupplies};
    int i = (*zoneCount)++;
    while (i > 0 && zones[(i-1)/2].priority > priority) {
        zones[i] = zones[(i-1)/2]; // Bubble up
        i = (i-1)/2;
    }
    zones[i] = newZone; // Insert new zone
}

// Maintain heap by sinking down an element
void heapifyDown(Zone zones[], int size) {
    int i = 0;
    while (2 * i + 1 < size) {
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int smallest = leftChild;

        if (rightChild < size && zones[rightChild].priority < zones[leftChild].priority) {
            smallest = rightChild;
        }

        if (zones[i].priority <= zones[smallest].priority) break;

        Zone temp = zones[i];
        zones[i] = zones[smallest];
        zones[smallest] = temp;

        i = smallest; // Move down the heap
    }
}

// Perform the rescue operation
void rescue(Stack *s, Zone zones[], int *zoneCount, RescuedPerson **root) {
    if (*zoneCount == 0) {
        printf("No zones available for rescue.\n");
        return;
    }

    Zone *topZone = &zones[0];
    printf("Rescuing in Zone %d with priority %d.\n", topZone->id, topZone->priority);

    int requiredSupplies = topZone->people - topZone->zoneSupplies;
    if (requiredSupplies > 0 && s->top + 1 < requiredSupplies) {
        printf("Not enough supplies for rescue in this zone.\n");
        return;
    }

    if (requiredSupplies > 0) {
        useSupplies(s, requiredSupplies);
    }

    for (int i = 0; i < topZone->people; i++) {
        char name[20];
        int time;
        printf("Enter name and time of rescue for person %d: ", i + 1);
        scanf("%s %d", name, &time);
        *root = insertBST(*root, time, name);
    }

    zones[0] = zones[--(*zoneCount)];
    heapifyDown(zones, *zoneCount);
}

// Insert rescued person into a binary search tree
RescuedPerson* insertBST(RescuedPerson *root, int time, char name[]) {
    if (root == NULL) {
        RescuedPerson* newNode = (RescuedPerson*)malloc(sizeof(RescuedPerson));
        newNode->time = time;
        strcpy(newNode->name, name);
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (time < root->time) root->left = insertBST(root->left, time, name);
    else root->right = insertBST(root->right, time, name);
    return root;
}

// Display all rescued people
void displayRescued(RescuedPerson *root) {
    if (root == NULL) {
        printf("No rescued people.\n");
        return;
    }
    printf("Rescued people:\n");
    inOrder(root);
}

// In-order traversal of the binary search tree
void inOrder(RescuedPerson *root) {
    if (root) {
        inOrder(root->left);
        printf("Name: %s, Time: %d\n", root->name, root->time);
        inOrder(root->right);
    }
}

int main() {
    Zone zones[MAX_ZONES];
    int zoneCount = 0;
    Stack supplyStack;
    initStack(&supplyStack);
    RescuedPerson *rescuedRoot = NULL;

    int choice;
    do {
        printf("\nMenu:\n");
        printf("1. Add Zone\n2. Add Supply to Rescuers\n3. Perform Rescue\n4. Display Rescued People\n5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                addZone(zones, &zoneCount);
                break;
            case 2: {
                int supply;
                printf("Enter the number of supplies to add: ");
                scanf("%d", &supply);
                addSupplies(&supplyStack, supply);
                break;
            }
            case 3:
                rescue(&supplyStack, zones, &zoneCount, &rescuedRoot);
                break;
            case 4:
                displayRescued(rescuedRoot);
                break;
            case 5:
                printf("Exiting...\n");
                break;
            default:
                printf("Invalid choice. Try again.\n");
        }
    } while (choice != 5);

    return 0;
}

for th given code if we are already sorting in add_zone function ,why are we using heapify down function to sort again