#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define MAX 100
vector<int>adjlist[MAX];
vector<int>position;
int cashhit = 0,pagefault = 0,current_frame_size = 0;
int *frame;
int framesize;

int toDigit(char ch){
    return ch-'0';
}
void Erase(int index){
    vector<int>temp;
    for(int i = 1;i<adjlist[index].size();i++){
        temp.push_back(adjlist[index][i]);
    }
    adjlist[index] = temp;
}
void Insert(int new_process,int originalIndex){
    if(current_frame_size<=2){
        frame[current_frame_size] = new_process;
        ++current_frame_size;
        Erase(new_process);
    }
    else{
        int optimal,indexofOptimal,mx = -1,emptyIndex = -1;
        for(int i = 0;i<framesize;i++){
            int current_process = frame[i];
            if(current_process==new_process){
                ++cashhit;
                Erase(new_process);
                position.push_back(originalIndex+1);
                return;
            }
            else{
                if(!adjlist[current_process].empty()){
                    if(adjlist[current_process][0]>mx){
                        mx = adjlist[current_process][0];
                        optimal = current_process;
                        indexofOptimal = i;
                    }
                }
                else{
                    emptyIndex = i;
                }
            }
        }
        if(emptyIndex!=-1){
            frame[emptyIndex] = new_process;
        }
        else{
            Erase(new_process);
            frame[indexofOptimal] = new_process;
        }
    }
}
int main(){
    cout<<"Enter Frame Size: ";
    cin>>framesize;
    cin.ignore();
    frame = (int* )calloc(framesize,sizeof (int));
    string input;
    int mx = INT_MIN;
    cout<<"Enter Reference String: ";
    getline(cin,input);
    for(int i = 0;i<input.size();i++){
        int value = toDigit(input[i]);
        mx = max(mx,value);
        adjlist[value].push_back(i);
    }
    cout<<"Condition of Cache Memory"<<endl;
    for(int i = 0;i<input.size();i++){
        int process = toDigit(input[i]);
        Insert(process,i);
        cout<<"After Inserting process # "<<process<<"- ";
        for(int j = 0;j<3;j++){
            cout<<frame[j]<<" ";
        }
    }
    cout<<endl<<endl;
    cout<<"Page Fault: "<<input.size()-cashhit<<endl;
    cout<<"Cash Hit: "<<cashhit<<endl;
    cout<<"Cash Hit Position: ";
    for(int v : position){
        cout<<v<<" ";
    }
    return 0;
}