#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // For INT_MAX in optimal

// Function to check if a page is present in frames
int isPresent(int page, int *frames, int num_frames) {
    for (int i = 0; i < num_frames; i++) {
        if (frames[i] == page) {
            return 1; // Present
        }
    }
    return 0; // Not present
}

// Function to print the current state of frames (for debugging/visualization)
void printFrames(int *frames, int num_frames) {
    printf("Frames: ");
    for (int i = 0; i < num_frames; i++) {
        if (frames[i] == -1) {
            printf("[ ] ");
        } else {
            printf("[%d] ", frames[i]);
        }
    }
    printf("\n");
}

// FIFO Page Replacement Simulation
int simulateFIFO(int *ref_string, int num_refs, int num_frames) {
    int *frames = (int *)malloc(num_frames * sizeof(int));
    if (frames == NULL) {
        perror("Failed to allocate memory for frames");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < num_frames; i++) {
        frames[i] = -1; // Initialize frames as empty (-1 indicates empty)
    }

    int page_faults = 0;
    int frame_index = 0; // Points to the next frame to be replaced (FIFO queue head)

    printf("\n--- FIFO Simulation ---\n");
    for (int i = 0; i < num_refs; i++) {
        int current_page = ref_string[i];
        printf("Ref: %d -> ", current_page);

        if (!isPresent(current_page, frames, num_frames)) {
            page_faults++;
            frames[frame_index] = current_page;
            frame_index = (frame_index + 1) % num_frames; // Move to next frame in circular fashion
            printf("Fault! ");
            printFrames(frames, num_frames);
        } else {
            printf("Hit.   ");
            printFrames(frames, num_frames);
        }
    }

    free(frames);
    return page_faults;
}

// Function to find the optimal page to replace
int findOptimalVictim(int *frames, int num_frames, int *ref_string, int num_refs, int current_index) {
    int victim_frame = -1;
    int farthest_use = -1; // Index of the farthest future use

    for (int i = 0; i < num_frames; i++) {
        int page_in_frame = frames[i];
        int next_use = INT_MAX; // Assume page is never used again initially

        // Look for the next occurrence of this page in the reference string
        for (int j = current_index + 1; j < num_refs; j++) {
            if (ref_string[j] == page_in_frame) {
                next_use = j;
                break; // Found the *next* use
            }
        }

        // If this page is never used again, it's the best victim
        if (next_use == INT_MAX) {
            return i; // Return the index of the frame holding this page
        }

        // Otherwise, track the page whose next use is farthest away
        if (next_use > farthest_use) {
            farthest_use = next_use;
            victim_frame = i; // This frame holds the current best candidate for victim
        }
    }
    // Should always find a victim if frames are full, defaults to first if logic error/all used soon
    return (victim_frame == -1) ? 0 : victim_frame;
}


// Optimal Page Replacement Simulation
int simulateOptimal(int *ref_string, int num_refs, int num_frames) {
    int *frames = (int *)malloc(num_frames * sizeof(int));
     if (frames == NULL) {
        perror("Failed to allocate memory for frames");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < num_frames; i++) {
        frames[i] = -1; // Initialize frames as empty
    }

    int page_faults = 0;
    int current_frame_count = 0;

    printf("\n--- Optimal Simulation ---\n");
    for (int i = 0; i < num_refs; i++) {
        int current_page = ref_string[i];
        printf("Ref: %d -> ", current_page);

        if (!isPresent(current_page, frames, num_frames)) {
            page_faults++;
            printf("Fault! ");

            // Check if there are empty frames first
            if (current_frame_count < num_frames) {
                frames[current_frame_count] = current_page;
                current_frame_count++;
            } else {
                // Frames are full, need to find the optimal victim
                int victim_index = findOptimalVictim(frames, num_frames, ref_string, num_refs, i);
                frames[victim_index] = current_page; // Replace victim
            }
            printFrames(frames, num_frames);
        } else {
             printf("Hit.   ");
             printFrames(frames, num_frames);
        }
    }

    free(frames);
    return page_faults;
}


int main() {
    int num_frames;
    int num_refs;
    int *ref_string;

    // Get number of frames
    printf("Enter the number of page frames: ");
    scanf("%d", &num_frames);
    if (num_frames <= 0) {
        printf("Number of frames must be positive.\n");
        return 1;
    }

    // Get number of page references
    printf("Enter the number of page references in the sequence: ");
    scanf("%d", &num_refs);
     if (num_refs <= 0) {
        printf("Number of references must be positive.\n");
        return 1;
    }

    // Allocate memory for reference string
    ref_string = (int *)malloc(num_refs * sizeof(int));
     if (ref_string == NULL) {
        perror("Failed to allocate memory for reference string");
        return 1;
    }

    // Get the reference string
    printf("Enter the page reference sequence (e.g., 7 0 1 2 0 ...):\n");
    for (int i = 0; i < num_refs; i++) {
        if (scanf("%d", &ref_string[i]) != 1) {
             printf("Invalid input for reference sequence.\n");
             free(ref_string);
             return 1;
        }
        if (ref_string[i] < 0) {
            printf("Page numbers cannot be negative.\n");
            free(ref_string);
            return 1;
        }
    }

    // --- Run Simulations ---
    int fifo_faults = simulateFIFO(ref_string, num_refs, num_frames);
    int optimal_faults = simulateOptimal(ref_string, num_refs, num_frames);

    // --- Print Results ---
    printf("\n--- Results ---\n");
    printf("Reference String Length: %d\n", num_refs);
    printf("Number of Frames: %d\n", num_frames);
    printf("FIFO Page Faults: %d\n", fifo_faults);
    printf("Optimal Page Faults: %d\n", optimal_faults);

    // --- Cleanup ---
    free(ref_string);

    return 0;
}