// ============================================================
// Shortest Job First (SJF) CPU Scheduling Algorithm in C++
// Non-preemptive: selects process with smallest burst time first
// ============================================================

#include <iostream>
using namespace std;

// Structure to group all attributes of a single process together
struct Process {
    int processNo;    // Original process number (preserved after sorting)
    int arrivalTime;  // Time at which process arrives in the ready queue
    int burstTime;    // CPU burst time required by the process
    int waitingTime;  // Time spent waiting before CPU is allocated
    int turnaroundTime; // Total time from arrival to completion
};

int main() {

    const int PROCESS_COUNT = 4;
    Process processes[PROCESS_COUNT];

    // -------------------------------------------------------
    // Step 1: Read arrival and burst times from the user
    // -------------------------------------------------------
    for (int i = 0; i < PROCESS_COUNT; i++) {
        cout << "\n Enter arrival time of P" << i + 1 << ": ";
        cin  >> processes[i].arrivalTime;
        cout << " Enter burst time of P"    << i + 1 << ": ";
        cin  >> processes[i].burstTime;
        processes[i].processNo = i + 1;  // Remember original process number
    }

    // Display the entered data before sorting
    cout << "\n\n Entered Data (before sorting)";
    cout << "\n PNO\tAT\tBT";
    for (int i = 0; i < PROCESS_COUNT; i++) {
        cout << "\n P" << processes[i].processNo
             << "\t" << processes[i].arrivalTime
             << "\t" << processes[i].burstTime;
    }

    // -------------------------------------------------------
    // Step 2: Sort processes by burst time (ascending = SJF order)
    // Uses selection sort; swaps entire Process struct to keep data intact
    // -------------------------------------------------------
    for (int outer = 0; outer < PROCESS_COUNT - 1; outer++) {
        for (int inner = outer + 1; inner < PROCESS_COUNT; inner++) {
            if (processes[outer].burstTime > processes[inner].burstTime) {
                // Swap the entire process record
                Process temp        = processes[outer];
                processes[outer]    = processes[inner];
                processes[inner]    = temp;
            }
        }
    }
    // After sorting: processes[0] has the shortest burst time

    // -------------------------------------------------------
    // Step 3: Compute Waiting Time and Turnaround Time
    // -------------------------------------------------------
    processes[0].waitingTime    = 0;                        // First job waits 0
    processes[0].turnaroundTime = processes[0].burstTime;   // TT = 0 + BT

    int totalBurstTime = processes[0].burstTime;

    for (int i = 1; i < PROCESS_COUNT; i++) {
        // WT[i] = WT[i-1] + BT[i-1] - gap in arrival times
        processes[i].waitingTime =
            processes[i-1].waitingTime + processes[i-1].burstTime
            - (processes[i].arrivalTime - processes[i-1].arrivalTime);

        // Guard: waiting time cannot go negative
        if (processes[i].waitingTime < 0) processes[i].waitingTime = 0;

        processes[i].turnaroundTime =
            processes[i].waitingTime + processes[i].burstTime;

        totalBurstTime += processes[i].burstTime;
    }

    // -------------------------------------------------------
    // Step 4: Print results
    // -------------------------------------------------------
    cout << "\n\n Result (sorted by burst time — shortest first)";
    cout << "\n PNO\tAT\tWT\tBT\tTT";
    for (int i = 0; i < PROCESS_COUNT; i++) {
        cout << "\n P" << processes[i].processNo
             << "\t" << processes[i].arrivalTime
             << "\t" << processes[i].waitingTime
             << "\t" << processes[i].burstTime
             << "\t" << processes[i].turnaroundTime;
    }
    cout << "\n Total Burst Time: " << totalBurstTime;

    // -------------------------------------------------------
    // Step 5: Compute averages
    // -------------------------------------------------------
    int totalWaiting = 0, totalTurnaround = 0;
    for (int i = 0; i < PROCESS_COUNT; i++) {
        totalWaiting    += processes[i].waitingTime;
        totalTurnaround += processes[i].turnaroundTime;
    }

    cout << "\n Average Waiting Time    : " << (float)totalWaiting    / PROCESS_COUNT;
    cout << "\n Average Turnaround Time : " << (float)totalTurnaround / PROCESS_COUNT;
    cout << endl;

    return 0;
}