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

#define MAX_ZONES 5  // Maximum number of zones
#define STACK_SIZE 10 // Stack size for supplies

// Structures
typedef struct {
    int id;
    int priority;
    int people;
    int supplies;
} Zone;

typedef struct {
    int supplies[STACK_SIZE];
    int top;
} Stack;

typedef struct Node {
    int time;
    char name[20];
    struct Node *left, *right;
} RescuedPerson;

// Function Prototypes
void initStack(Stack *s);
int isStackEmpty(Stack *s);
int isStackFull(Stack *s);
void push(Stack *s, int supply);
int pop(Stack *s);
void addZone(Zone zones[], int *zoneCount);
void prioritizeZones(Zone zones[], int zoneCount);
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);

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

int isStackEmpty(Stack *s) { return s->top == -1; }

int isStackFull(Stack *s) { return s->top == STACK_SIZE - 1; }

void push(Stack *s, int supply) {
    if (!isStackFull(s)) s->supplies[++(s->top)] = supply;
}

int pop(Stack *s) {
    return isStackEmpty(s) ? -1 : s->supplies[(s->top)--];
}

// Priority Queue for Zones
void addZone(Zone zones[], int *zoneCount) {
    if (*zoneCount >= MAX_ZONES) {
        printf("Cannot add more zones.\n");
        return;
    }
    int id, priority, people, supplies;
    printf("Enter Zone ID, Priority (1-5), People, and Supplies: ");
    scanf("%d %d %d %d", &id, &priority, &people, &supplies);
    zones[*zoneCount] = (Zone){id, priority, people, supplies};
    (*zoneCount)++;
}

void prioritizeZones(Zone zones[], int zoneCount) {
    for (int i = 0; i < zoneCount - 1; i++) {
        for (int j = 0; j < zoneCount - i - 1; j++) {
            if (zones[j].priority > zones[j + 1].priority) {
                Zone temp = zones[j];
                zones[j] = zones[j + 1];
                zones[j + 1] = temp;
            }
        }
    }
}

// Rescue Operation
void rescue(Stack *s, Zone zones[], int *zoneCount, RescuedPerson **root) {
    if (*zoneCount == 0) {
        printf("No zones available for rescue.\n");
        return;
    }
    
    prioritizeZones(zones, *zoneCount);
    Zone zone = zones[0];
    printf("Rescuing in Zone %d with priority %d.\n", zone.id, zone.priority);
    
    int requiredSupplies = zone.people * 1;  // 1 supply per person as an assumption
    if (s->top + 1 < requiredSupplies) {
        printf("Not enough supplies for rescue in this zone.\n");
        return;
    }

    // Using supplies
    for (int i = 0; i < requiredSupplies; i++) pop(s);

    // Record rescued people
    for (int i = 0; i < zone.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);
    }

    // Shift remaining zones up
    for (int i = 1; i < *zoneCount; i++) zones[i - 1] = zones[i];
    (*zoneCount)--;
}

// Binary Search Tree Insertion and Display
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;
}

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

void inOrder(RescuedPerson *root) {
    if (root) {
        inOrder(root->left);
        printf("Name: %s, Time: %d\n", root->name, root->time);
        inOrder(root->right);
    }
}

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

    int choice, supply;
    do {
        printf("\nMenu:\n");
        printf("1. Add Zone\n2. Add Supply\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: 
                printf("Enter supply to add: ");
                scanf("%d", &supply);
                push(&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;
}

use priority queues to assign prioirty for the given code