BIGBRAIN.cpp

#include<iostream>

using namespace std;

struct LLNode {
    int frame_id;
    int meta;
    LLNode* next;

    LLNode(int fid) : frame_id(fid), meta(0) {};
    LLNode(int fid, int mv) : frame_id(fid), meta(mv) {};
};

struct LL {
    LLNode *head, *tail;
    int len = 0;
};

int contains(LL &b, int fid, int nmv) {
    LLNode *h = b.head;
    while (h != nullptr) {
        if (h->frame_id == fid) {
            if (nmv == -1) {
                h->meta++;
            }
            else h->meta = nmv;
            return 1; 
        }
        h = h->next;
    }
    return 0;
}

void append(LL &b, LLNode *c) {
    if (b.len == 0) {
        b.head = c;
        b.tail = c;
    }
    else {
        b.tail->next = c;
        b.tail = c;
    }
    c->next = nullptr;
    b.len++;
}

LLNode* find_min(LL &b) {
    LLNode *h = b.head;
    int mv = b.head->meta;
    LLNode *am = b.head;
    while (h != nullptr) {
        if (h->meta < mv) {
            am = h;
            mv = h->meta;
        }
        h = h->next;
    }
    return am;
}

void show(LL &b) {
    LLNode *h = b.head;
    cout << "> ";
    while (h != nullptr) {
        cout << h->frame_id << ' ';
        h = h->next;
    }
    cout << '\n';
}

// FIFO
// LFU = minimum uses, gets replaced
// LRU = minimum time, gets replaced


int main() {
    int n, f;
    cout << "Number of frames: ";
    cin >> f;
    cout << "Refrence string length: ";
    cin >> n;

    if (n < f) {
        cout << "Reference string length is less than frame size";
    }

    int is_lru = 0, is_lfu = 0;
    int faults = f;

    cout << "Enter reference string sequentially\n";
    LL a;
    int t = 0;
    for (; t < f; t++) {
        int id;
        cin >> id;
        LLNode *b = new LLNode(id, (is_lru == 1 ? t : 1));
        append(a, b);
        show(a);
    }
    for (; t < n; t++) {
        int id;
        cin >> id;

        if (contains(a, id, (is_lru == 1 ? t : (is_lfu == 1 ? -1 : 1))) == 0) {
            cout << "> Fault | ";
            faults++;
            LLNode *rframe = find_min(a);
            rframe->meta = (is_lru == 1 ? t : 1);
            rframe->frame_id = id;
        }
        show(a);
    }

    cout << "Number of faults: " << faults;
}