#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;
}

instead of assigning priorities ourself , use priority queues using heaps to assign the priority of the zones
also fix the supply stack function to consider the no of supplies as that many no of stacks rather than a single stack