/* ============================================================
   RAILWAY SEAT ALLOCATION SYSTEM
   Data Structure Used : QUEUE (two array-based circular queues
                          form a simple priority queue)
   ------------------------------------------------------------
   Module 1 - Passenger Registration and Ticket Booking
   Module 2 - Confirmed Seat Allocation using Queue (FIFO scan)
   Module 3 - Waiting List Management using Queue
   Module 4 - Priority Queue for senior citizens + automatic
              reallocation of cancelled seats
   Module 5 - Ticket Cancellation, Search, Refund, Status Report
   ============================================================ */

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

#define MAX_SEATS         5
#define MAX_NORMAL_WAIT    5
#define MAX_PRIORITY_WAIT  3
#define MAX_PASSENGERS     60
#define NAME_LEN           30
#define STATION_LEN        6
#define FARE               450
#define CANCEL_FEE_PERCENT 15
#define SENIOR_AGE         60

/* status codes */
#define ST_CONFIRMED  0
#define ST_WAITING    1
#define ST_PRIORITY   2
#define ST_CANCELLED  3

/* ---------- Module 1 : passenger registry (array) ---------- */
typedef struct {
    int  pnr;
    char name[NAME_LEN];
    int  age;
    char gender[10];
    char phone[15];
    char from[STATION_LEN];   /* boarding station code, e.g. "MAS" */
    char to[STATION_LEN];     /* ending station code, e.g. "MDU"   */
    int  isSenior;
    int  status;
    int  seatNumber;   /* valid when status == ST_CONFIRMED or was, before cancel */
    int  fare;
    int  refund;
} Passenger;

Passenger passengers[MAX_PASSENGERS];
int passengerCount = 0;
int pnrCounter = 5000;

/* ---------- Module 2 : seat table (array) ---------- */
int seatOccupant[MAX_SEATS];   /* index into passengers[], -1 if empty */

/* ---------- Module 3 : normal waiting queue (circular) ---------- */
int normalQ[MAX_NORMAL_WAIT];
int nFront = -1, nRear = -1, nCount = 0;

/* ---------- Module 4 : priority queue for senior citizens (circular) ---------- */
int prioQ[MAX_PRIORITY_WAIT];
int pFront = -1, pRear = -1, pCount = 0;

/* ================= generic circular queue helpers ================= */
int qIsFull(int count, int max)  { return count == max; }
int qIsEmpty(int count)          { return count == 0; }

void qEnqueue(int q[], int max, int *front, int *rear, int *count, int value) {
    if (*front == -1) *front = 0;
    *rear = (*rear + 1) % max;
    q[*rear] = value;
    (*count)++;
}

int qDequeue(int q[], int max, int *front, int *rear, int *count) {
    int value = q[*front];
    *front = (*front + 1) % max;
    (*count)--;
    if (*count == 0) { *front = -1; *rear = -1; }
    return value;
}

/* remove one specific passenger index from a circular queue, keeping order */
int qRemove(int q[], int max, int *front, int *rear, int *count, int passengerIdx) {
    int i, found = -1, temp[MAX_NORMAL_WAIT > MAX_PRIORITY_WAIT ? MAX_NORMAL_WAIT : MAX_PRIORITY_WAIT];
    int n = *count;
    for (i = 0; i < n; i++) {
        int idx = (*front + i) % max;
        if (q[idx] == passengerIdx) { found = i; }
    }
    if (found == -1) return 0;
    /* rebuild queue without that element */
    int k = 0;
    for (i = 0; i < n; i++) {
        if (i == found) continue;
        temp[k++] = q[(*front + i) % max];
    }
    *front = (k == 0) ? -1 : 0;
    *rear  = (k == 0) ? -1 : k - 1;
    *count = k;
    for (i = 0; i < k; i++) q[i] = temp[i];
    return 1;
}

/* ================= Module 1 : registration ================= */
int registerPassenger(const char *name, int age, const char *gender, const char *phone,
                       const char *from, const char *to) {
    int idx = passengerCount++;
    Passenger *p = &passengers[idx];
    p->pnr = ++pnrCounter;
    strcpy(p->name, name);
    p->age = age;
    strcpy(p->gender, gender);
    strcpy(p->phone, phone);
    strcpy(p->from, from);
    strcpy(p->to, to);
    p->isSenior = (age >= SENIOR_AGE);
    p->status = -1;         /* not yet allocated */
    p->seatNumber = -1;
    p->fare = FARE;
    p->refund = 0;
    return idx;
}

/* ================= Module 2 : confirmed seat allocation ================= */
int allocateSeat(int idx) {
    int i;
    for (i = 0; i < MAX_SEATS; i++) {
        if (seatOccupant[i] == -1) {
            seatOccupant[i] = idx;
            passengers[idx].status = ST_CONFIRMED;
            passengers[idx].seatNumber = i + 1;
            printf("Seat %d CONFIRMED for %s (PNR %d).\n", i + 1, passengers[idx].name, passengers[idx].pnr);
            return 1;
        }
    }
    return 0; /* coach full */
}

/* ================= Module 3 / 4 : waiting + priority queue ================= */
void sendToQueue(int idx) {
    if (passengers[idx].isSenior) {
        if (qIsFull(pCount, MAX_PRIORITY_WAIT)) {
            printf("Priority queue FULL. %s could not be waitlisted.\n", passengers[idx].name);
            return;
        }
        qEnqueue(prioQ, MAX_PRIORITY_WAIT, &pFront, &pRear, &pCount, idx);
        passengers[idx].status = ST_PRIORITY;
        printf("Coach full - senior citizen %s added to PRIORITY QUEUE (PNR %d).\n",
               passengers[idx].name, passengers[idx].pnr);
    } else {
        if (qIsFull(nCount, MAX_NORMAL_WAIT)) {
            printf("Waiting list FULL. %s could not be waitlisted.\n", passengers[idx].name);
            return;
        }
        qEnqueue(normalQ, MAX_NORMAL_WAIT, &nFront, &nRear, &nCount, idx);
        passengers[idx].status = ST_WAITING;
        printf("Coach full - %s added to WAITING LIST (PNR %d).\n",
               passengers[idx].name, passengers[idx].pnr);
    }
}

/* Module 1+2+3+4 entry point: register then try to seat, else queue */
int bookTicket(const char *name, int age, const char *gender, const char *phone,
               const char *from, const char *to) {
    int idx = registerPassenger(name, age, gender, phone, from, to);
    if (!allocateSeat(idx)) sendToQueue(idx);
    return passengers[idx].pnr;
}

/* When a seat frees up: priority queue is served before the normal queue */
void reallocateSeat(int seatIndex) {
    int idx = -1;
    if (!qIsEmpty(pCount)) {
        idx = qDequeue(prioQ, MAX_PRIORITY_WAIT, &pFront, &pRear, &pCount);
    } else if (!qIsEmpty(nCount)) {
        idx = qDequeue(normalQ, MAX_NORMAL_WAIT, &nFront, &nRear, &nCount);
    }
    if (idx == -1) { seatOccupant[seatIndex] = -1; return; }

    seatOccupant[seatIndex] = idx;
    passengers[idx].status = ST_CONFIRMED;
    passengers[idx].seatNumber = seatIndex + 1;
    printf("%s promoted from queue to seat %d (PNR %d).\n",
           passengers[idx].name, seatIndex + 1, passengers[idx].pnr);
}

/* ================= Module 5 : cancellation, refund, search, report ================= */
int findByPNR(int pnr) {
    int i;
    for (i = 0; i < passengerCount; i++)
        if (passengers[i].pnr == pnr) return i;
    return -1;
}

void cancelTicket(int pnr) {
    int idx = findByPNR(pnr);
    if (idx == -1) { printf("PNR %d not found.\n", pnr); return; }
    Passenger *p = &passengers[idx];

    if (p->status == ST_CANCELLED) {
        printf("PNR %d is already cancelled.\n", pnr);
        return;
    }
    if (p->status == ST_CONFIRMED) {
        int seatIdx = p->seatNumber - 1;
        int fee = (p->fare * CANCEL_FEE_PERCENT) / 100;
        p->refund = p->fare - fee;
        p->status = ST_CANCELLED;
        printf("Seat %d cancelled for %s. Refund Rs.%d (fee Rs.%d).\n",
               p->seatNumber, p->name, p->refund, fee);
        reallocateSeat(seatIdx);
    } else { /* ST_WAITING or ST_PRIORITY : never occupied a seat, full refund */
        if (p->status == ST_PRIORITY)
            qRemove(prioQ, MAX_PRIORITY_WAIT, &pFront, &pRear, &pCount, idx);
        else
            qRemove(normalQ, MAX_NORMAL_WAIT, &nFront, &nRear, &nCount, idx);
        p->refund = p->fare;
        p->status = ST_CANCELLED;
        printf("Waiting request cancelled for %s. Full refund Rs.%d.\n", p->name, p->refund);
    }
}

void searchPassenger(int pnr) {
    int idx = findByPNR(pnr);
    if (idx == -1) { printf("PNR %d not found.\n", pnr); return; }
    Passenger *p = &passengers[idx];
    printf("\nPNR %d | %s | Age %d | %s | %s -> %s\n", p->pnr, p->name, p->age,
           p->isSenior ? "Senior" : "General", p->from, p->to);
    if (p->status == ST_CONFIRMED)      printf("Status: CONFIRMED, Seat %d\n", p->seatNumber);
    else if (p->status == ST_WAITING)   printf("Status: WAITING LIST\n");
    else if (p->status == ST_PRIORITY)  printf("Status: PRIORITY WAITING (senior citizen)\n");
    else                                 printf("Status: CANCELLED, Refund Rs.%d\n", p->refund);
}

void showStatusReport(void) {
    int i;
    printf("\n===== CONFIRMED =====\n");
    for (i = 0; i < passengerCount; i++)
        if (passengers[i].status == ST_CONFIRMED)
            printf("Seat %2d | PNR %d | %-15s | %s -> %s\n", passengers[i].seatNumber,
                   passengers[i].pnr, passengers[i].name, passengers[i].from, passengers[i].to);

    printf("\n===== WAITING LIST =====\n");
    for (i = 0; i < passengerCount; i++)
        if (passengers[i].status == ST_WAITING)
            printf("PNR %d | %s\n", passengers[i].pnr, passengers[i].name);

    printf("\n===== PRIORITY QUEUE (SENIOR) =====\n");
    for (i = 0; i < passengerCount; i++)
        if (passengers[i].status == ST_PRIORITY)
            printf("PNR %d | %s\n", passengers[i].pnr, passengers[i].name);

    printf("\n===== CANCELLED =====\n");
    for (i = 0; i < passengerCount; i++)
        if (passengers[i].status == ST_CANCELLED)
            printf("PNR %d | %s | Refund Rs.%d\n", passengers[i].pnr, passengers[i].name, passengers[i].refund);
}

/* ================= driver ================= */
int main(void) {
    int i, choice, pnr, age;
    char name[NAME_LEN], gender[10], phone[15], from[STATION_LEN], to[STATION_LEN];

    for (i = 0; i < MAX_SEATS; i++) seatOccupant[i] = -1;

    while (1) {
        printf("\n===== RAILWAY SEAT ALLOCATION SYSTEM =====\n");
        printf("1. Register & Book Ticket\n");
        printf("2. Cancel Ticket (Refund)\n");
        printf("3. Search Passenger by PNR\n");
        printf("4. Show Seat Chart\n");
        printf("5. Show Waiting Queue\n");
        printf("6. Show Priority Queue\n");
        printf("7. Show Full Status Report\n");
        printf("8. Exit\n");
        printf("Enter choice: ");
        if (scanf("%d", &choice) != 1) break;

        if (choice == 1) {
            printf("Name: "); scanf("%s", name);
            printf("Age: "); scanf("%d", &age);
            printf("Gender: "); scanf("%s", gender);
            printf("Phone: "); scanf("%s", phone);
            printf("Boarding station code (e.g. MAS): "); scanf("%s", from);
            printf("Ending station code (e.g. MDU): "); scanf("%s", to);
            bookTicket(name, age, gender, phone, from, to);
        } else if (choice == 2) {
            printf("Enter PNR to cancel: "); scanf("%d", &pnr);
            cancelTicket(pnr);
        } else if (choice == 3) {
            printf("Enter PNR to search: "); scanf("%d", &pnr);
            searchPassenger(pnr);
        } else if (choice == 4) {
            printf("\n---- SEAT CHART ----\n");
            for (i = 0; i < MAX_SEATS; i++) {
                if (seatOccupant[i] == -1) printf("Seat %2d : EMPTY\n", i + 1);
                else printf("Seat %2d : %s\n", i + 1, passengers[seatOccupant[i]].name);
            }
        } else if (choice == 5) {
            printf("\n---- WAITING QUEUE ----\n");
            for (i = 0; i < nCount; i++)
                printf("%d. %s\n", i + 1, passengers[normalQ[(nFront + i) % MAX_NORMAL_WAIT]].name);
        } else if (choice == 6) {
            printf("\n---- PRIORITY QUEUE ----\n");
            for (i = 0; i < pCount; i++)
                printf("%d. %s\n", i + 1, passengers[prioQ[(pFront + i) % MAX_PRIORITY_WAIT]].name);
        } else if (choice == 7) {
            showStatusReport();
        } else if (choice == 8) {
            printf("Exiting...\n"); break;
        } else {
            printf("Invalid choice.\n");
        }
    }
    return 0;
}