// ============================================================
// LRU (Least Recently Used) Page Replacement Algorithm in C++
// Evicts the page that was accessed least recently on a page fault
// ============================================================

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

int main() {

    int frameCount, pageRefCount;

    // -------------------------------------------------------
    // Step 1: Read frame size and page reference string
    // -------------------------------------------------------
    cout << "\n Enter Frame Size (number of frames in memory): ";
    cin  >> frameCount;

    cout << "\n Enter Number of Pages in the reference string: ";
    cin  >> pageRefCount;

    vector<int> pageReferenceString(pageRefCount);
    vector<int> frameContents(frameCount, -1);   // -1 = empty frame

    cout << "\n Enter the Page Reference String: ";
    for (int i = 0; i < pageRefCount; i++) cin >> pageReferenceString[i];

    int hitCount  = 0;
    int faultCount = 0;

    // -------------------------------------------------------
    // Step 2: Process each page reference
    // -------------------------------------------------------
    for (int refIndex = 0; refIndex < pageRefCount; refIndex++) {
        int currentPage = pageReferenceString[refIndex];

        // --- Check if page is already in a frame (Hit) ---
        bool isHit = false;
        for (int frameIdx = 0; frameIdx < frameCount; frameIdx++) {
            if (frameContents[frameIdx] == currentPage) {
                isHit = true;
                break;
            }
        }

        if (isHit) {
            hitCount++;
            cout << "\n Page " << currentPage << " [HIT]  | Frames: ";
        } else {
            faultCount++;

            // --- Page Fault: try to place in an empty frame first ---
            bool placedInEmptyFrame = false;
            for (int frameIdx = 0; frameIdx < frameCount; frameIdx++) {
                if (frameContents[frameIdx] == -1) {
                    frameContents[frameIdx] = currentPage;  // Load into empty frame
                    placedInEmptyFrame = true;
                    break;
                }
            }

            // --- If no empty frame, apply LRU replacement ---
            if (!placedInEmptyFrame) {
                // For each frame, find the most recent index in the page history
                // (before the current reference) where that frame's page was used.
                // The frame with the smallest (oldest) last-use index is the LRU victim.
                vector<int> lastUsedIndex(frameCount, -1);

                for (int frameIdx = 0; frameIdx < frameCount; frameIdx++) {
                    // Scan backwards from refIndex-1 to find last use of frameContents[frameIdx]
                    for (int pastRef = refIndex - 1; pastRef >= 0; pastRef--) {
                        if (pageReferenceString[pastRef] == frameContents[frameIdx]) {
                            lastUsedIndex[frameIdx] = pastRef;  // Most recent past use found
                            break;
                        }
                    }
                    // If never found, lastUsedIndex[frameIdx] remains -1
                    // (never used in the past = definitely the LRU victim)
                }

                // Find the frame with the smallest last-use index (least recently used)
                int lruFrameIdx = 0;
                for (int frameIdx = 1; frameIdx < frameCount; frameIdx++) {
                    if (lastUsedIndex[frameIdx] < lastUsedIndex[lruFrameIdx]) {
                        lruFrameIdx = frameIdx;  // This frame is even less recently used
                    }
                }

                frameContents[lruFrameIdx] = currentPage;  // Replace LRU page with new page
            }

            cout << "\n Page " << currentPage << " [MISS] | Frames: ";
        }

        // Display current frame contents after this reference
        for (int frameIdx = 0; frameIdx < frameCount; frameIdx++) {
            if (frameContents[frameIdx] == -1) cout << "- ";
            else cout << frameContents[frameIdx] << " ";
        }
    }

    // -------------------------------------------------------
    // Step 3: Summary statistics
    // -------------------------------------------------------
    cout << "\n\n ------- Summary -------";
    cout << "\n Total Page References : " << pageRefCount;
    cout << "\n Page Hits             : " << hitCount;
    cout << "\n Page Faults (Misses)  : " << faultCount;
    cout << "\n Hit Ratio             : " << (float)hitCount  / pageRefCount * 100 << "%";
    cout << "\n Fault Ratio           : " << (float)faultCount/ pageRefCount * 100 << "%";
    cout << endl;

    return 0;
}