// ============================================================
// First Fit Memory Allocation Algorithm in C++
// Scans blocks from the start and allocates the FIRST one that fits
// ============================================================

#include <iostream>
using namespace std;

// Represents a single memory block (partition) in main memory
struct MemoryBlock {
    int blockNo;    // Block number (display order, 1-based)
    int blockSize;  // Total size of this memory block
    int isOccupied; // 0 = free, 1 = allocated to a job
    int jobNo;      // Job number currently in this block (0 = empty)
};

// Represents a job (process) that needs memory
struct Job {
    int jobNo;       // Job number (1-based)
    int jobSize;     // Memory required by this job
    int isAllocated; // 0 = not yet placed, 1 = successfully allocated
};

int main() {

    // -------------------------------------------------------
    // Step 1: Read memory block information
    // -------------------------------------------------------
    cout << "\n Enter No of Blocks in memory: ";
    int blockCount;
    cin  >> blockCount;

    MemoryBlock memBlocks[99];
    for (int blockIdx = 0; blockIdx < blockCount; blockIdx++) {
        cout << "\n Enter Size of Block " << blockIdx + 1 << ": ";
        cin  >> memBlocks[blockIdx].blockSize;
        memBlocks[blockIdx].blockNo    = blockIdx + 1;
        memBlocks[blockIdx].isOccupied = 0;   // All blocks start free
        memBlocks[blockIdx].jobNo      = 0;   // No job assigned
    }

    // -------------------------------------------------------
    // Step 2: Read job information
    // -------------------------------------------------------
    int jobCount;
    cout << "\n Enter No of Jobs: ";
    cin  >> jobCount;

    Job jobs[99];
    for (int jobIdx = 0; jobIdx < jobCount; jobIdx++) {
        cout << "\n Enter size of Job " << jobIdx + 1 << ": ";
        cin  >> jobs[jobIdx].jobSize;
        jobs[jobIdx].jobNo       = jobIdx + 1;
        jobs[jobIdx].isAllocated = 0;   // No block assigned yet
    }

    // Display entered job data
    cout << "\n JobNotJobSize";
    for (int jobIdx = 0; jobIdx < jobCount; jobIdx++) {
        cout << "\n " << jobs[jobIdx].jobNo << "\t" << jobs[jobIdx].jobSize;
    }

    // -------------------------------------------------------
    // Step 3: First Fit Allocation
    // For each job, scan blocks from the beginning and allocate
    // the FIRST free block that is large enough.
    // The 'break' ensures we stop at the first fit (not the best fit).
    // -------------------------------------------------------
    for (int jobIdx = 0; jobIdx < jobCount; jobIdx++) {
        for (int blockIdx = 0; blockIdx < blockCount; blockIdx++) {
            // Allocate if: block is free AND block is large enough AND job not yet placed
            if (memBlocks[blockIdx].isOccupied == 0
                && memBlocks[blockIdx].blockSize >= jobs[jobIdx].jobSize
                && jobs[jobIdx].isAllocated != 1) {

                memBlocks[blockIdx].jobNo      = jobs[jobIdx].jobNo;  // Record which job
                memBlocks[blockIdx].isOccupied = 1;                   // Mark block as taken
                jobs[jobIdx].isAllocated       = 1;                   // Mark job as placed
                break;  // First Fit: stop after finding the FIRST suitable block
            }
        }
    }

    // -------------------------------------------------------
    // Step 4: Display allocation results
    // -------------------------------------------------------
    cout << "\n\n BlockNo\tBlockSize\tJobNo\tJobSize\tStatus\tInternal Frag";
    for (int blockIdx = 0; blockIdx < blockCount; blockIdx++) {
        cout << "\n " << memBlocks[blockIdx].blockNo
             << "\t\t" << memBlocks[blockIdx].blockSize;

        if (memBlocks[blockIdx].jobNo != 0) {
            int allocatedJobIdx = memBlocks[blockIdx].jobNo - 1;   // Convert job number to array index
            int internalFrag    = memBlocks[blockIdx].blockSize - jobs[allocatedJobIdx].jobSize;

            cout << "\t" << memBlocks[blockIdx].jobNo
                 << "\t" << jobs[allocatedJobIdx].jobSize
                 << "\t" << memBlocks[blockIdx].isOccupied
                 << "\t" << internalFrag;
        } else {
            // Block is empty (no job allocated)
            cout << "\t0\t0\t" << memBlocks[blockIdx].isOccupied << "\t0";
        }
    }

    // Report any jobs that could not be allocated
    cout << "\n";
    for (int jobIdx = 0; jobIdx < jobCount; jobIdx++) {
        if (jobs[jobIdx].isAllocated == 0) {
            cout << "\n Job " << jobs[jobIdx].jobNo
                 << " (size " << jobs[jobIdx].jobSize
                 << ") could NOT be allocated — no suitable block found.";
        }
    }

    cout << endl;
    return 0;
}