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

#define MAX 50

// ── FIFO ──────────────────────────────────────────────────────────────────
void fifo(int pages[], int n, int frames) {
    int mem[MAX], front = 0, faults = 0;
    memset(mem, -1, sizeof(mem));

    printf("\n--- FIFO ---\n");
    printf("Page\tFrames\t\t\tFault\n");

    for (int i = 0; i < n; i++) {
        int found = 0;

        // check if page already in memory
        for (int j = 0; j < frames; j++)
            if (mem[j] == pages[i]) { found = 1; break; }

        printf("%d\t", pages[i]);

        if (!found) {
            mem[front] = pages[i];       // replace oldest page
            front = (front + 1) % frames;
            faults++;

            for (int j = 0; j < frames; j++)
                if (mem[j] == -1) printf("- "); else printf("%d ", mem[j]);
            printf("\t\tFault");
        } else {
            for (int j = 0; j < frames; j++)
                if (mem[j] == -1) printf("- "); else printf("%d ", mem[j]);
        }
        printf("\n");
    }

    printf("Total Page Faults: %d\n", faults);
}

// ── OPTIMAL ───────────────────────────────────────────────────────────────
void optimal(int pages[], int n, int frames) {
    int mem[MAX], faults = 0, count = 0;
    memset(mem, -1, sizeof(mem));

    printf("\n--- Optimal ---\n");
    printf("Page\tFrames\t\t\tFault\n");

    for (int i = 0; i < n; i++) {
        int found = 0;

        // check if page already in memory
        for (int j = 0; j < frames; j++)
            if (mem[j] == pages[i]) { found = 1; break; }

        printf("%d\t", pages[i]);

        if (!found) {
            if (count < frames) {
                // frames not full yet, just fill
                mem[count++] = pages[i];
            } else {
                // find which page in memory is used farthest in future
                int replaceIdx = -1, farthest = -1;
                for (int j = 0; j < frames; j++) {
                    int nextUse = n;  // assume never used again
                    for (int k = i + 1; k < n; k++) {
                        if (pages[k] == mem[j]) { nextUse = k; break; }
                    }
                    if (nextUse > farthest) {
                        farthest = nextUse;
                        replaceIdx = j;
                    }
                }
                mem[replaceIdx] = pages[i];
            }
            faults++;

            for (int j = 0; j < frames; j++)
                if (mem[j] == -1) printf("- "); else printf("%d ", mem[j]);
            printf("\t\tFault");
        } else {
            for (int j = 0; j < frames; j++)
                if (mem[j] == -1) printf("- "); else printf("%d ", mem[j]);
        }
        printf("\n");
    }

    printf("Total Page Faults: %d\n", faults);
}

// ── MAIN ──────────────────────────────────────────────────────────────────
int main() {
    int pages[MAX], n, frames;

    printf("Enter number of pages in reference string: ");
    scanf("%d", &n);
    printf("Enter reference string: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &pages[i]);

    printf("Enter number of frames: ");
    scanf("%d", &frames);

    fifo(pages, n, frames);
    optimal(pages, n, frames);

    return 0;
}