#include <iostream>
#include <vector>
#include <limits>
using namespace std;

// Function to display the allocation and remaining space
void displayResults(string method, vector<int> allocation, vector<int> partitions, vector<int> partitionSize) {
    cout << "\n" << method << " Results:\n";
    cout << "Process\tSize\tPartition\tRemaining Space\n";
    for (size_t i = 0; i < allocation.size(); i++) {
        if (allocation[i] != -1) {
            cout << i + 1 << "\t" << partitions[i] << "\t" << allocation[i] + 1 
                 << "\t\t" << partitionSize[allocation[i]] << "\n";
        } else {
            cout << i + 1 << "\t" << partitions[i] << "\tNot Allocated\n";
        }
    }
}

// First Fit Algorithm
void firstFit(vector<int> partitions, vector<int> &memory, vector<int> &allocation) {
    for (size_t i = 0; i < partitions.size(); i++) {
        for (size_t j = 0; j < memory.size(); j++) {
            if (memory[j] >= partitions[i]) {
                allocation[i] = j;
                memory[j] -= partitions[i];
                break;
            }
        }
    }
}

// Best Fit Algorithm
void bestFit(vector<int> partitions, vector<int> &memory, vector<int> &allocation) {
    for (size_t i = 0; i < partitions.size(); i++) {
        int bestIdx = -1, minSpace = numeric_limits<int>::max();
        for (size_t j = 0; j < memory.size(); j++) {
            if (memory[j] >= partitions[i] && memory[j] - partitions[i] < minSpace) {
                bestIdx = j;
                minSpace = memory[j] - partitions[i];
            }
        }
        if (bestIdx != -1) {
            allocation[i] = bestIdx;
            memory[bestIdx] -= partitions[i];
        }
    }
}

// Worst Fit Algorithm
void worstFit(vector<int> partitions, vector<int> &memory, vector<int> &allocation) {
    for (size_t i = 0; i < partitions.size(); i++) {
        int worstIdx = -1, maxSpace = 0;
        for (size_t j = 0; j < memory.size(); j++) {
            if (memory[j] >= partitions[i] && memory[j] - partitions[i] > maxSpace) {
                worstIdx = j;
                maxSpace = memory[j] - partitions[i];
            }
        }
        if (worstIdx != -1) {
            allocation[i] = worstIdx;
            memory[worstIdx] -= partitions[i];
        }
    }
}

int main() {
    vector<int> memory = {100, 500, 200, 300, 600};
    vector<int> partitions = {212, 417, 112, 426};

    // First Fit
    vector<int> firstFitMemory = memory;
    vector<int> firstFitAllocation(partitions.size(), -1);
    firstFit(partitions, firstFitMemory, firstFitAllocation);
    displayResults("First Fit", firstFitAllocation, partitions, firstFitMemory);

    // Best Fit
    vector<int> bestFitMemory = memory;
    vector<int> bestFitAllocation(partitions.size(), -1);
    bestFit(partitions, bestFitMemory, bestFitAllocation);
    displayResults("Best Fit", bestFitAllocation, partitions, bestFitMemory);

    // Worst Fit
    vector<int> worstFitMemory = memory;
    vector<int> worstFitAllocation(partitions.size(), -1);
    worstFit(partitions, worstFitMemory, worstFitAllocation);
    displayResults("Worst Fit", worstFitAllocation, partitions, worstFitMemory);

    return 0;
}