#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <vector>
#include <sys/time.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <list>
#include <unordered_map>

#define DEBUG 0

using namespace std;
// using namespace __gnu_pbds;

struct pairr{
    char op;
    uint64_t p;
};

struct Node{
    int page;
    bool dirty=0; // 1: dirty, 0: clean
    Node* next;
    Node* prev;
    Node* prev_clean;
    Node* next_clean;
};

int page_size = 4096;
int start_frame = 4096;
int end_frame = 65536;
int max_tcn = 100000000;
int tcn;
vector<pairr> tc(max_tcn);
// typedef gp_hash_table<uint64_t, Node*> PageTable;
typedef vector<Node*> PageTable;

int readfile(string filename) {
    ifstream file;
    file.open(filename);
    if (!file) {
        cout << "Unable to open filen\n";
        exit(1);
    }
    tcn = 0;
    // read to eof, "op hex_address\n" each line(the last line is only \n), store to tc, tc.op=op, tc.p=decimal(hex_address)/page_size
    string line;
    while(getline(file, line)){
        if(line.size()==0) break;
        stringstream ss(line);
        ss >> tc[tcn].op >> hex >> tc[tcn].p;
        tc[tcn].p /= page_size;
        // cout<<tc[tcn].op<<" "<<tc[tcn].p<<"\n";
        tcn++;
    }

    return 0;
}

Node* victim(int mode,Node &head, Node &tail){
    if (mode == 0){  // FIFO LRU
        return &tail;
    } 
    Node* cur = &tail;
    while (cur->dirty == 0){
        cur = cur->prev;
    }
    return cur;
}

Node *remove(Node &target){
    if (target.next != nullptr){
        target.next->prev = target.prev;
    }
    if(target.prev != nullptr){
        target.prev->next = target.next;
    }
    return target.prev;
}

Node *insert(Node &head, Node &target){
    target.next=&head;
    target.prev=head.prev; //nullptr
    head.prev=&target;
    return &target;
}

/** /
//search is page in the list, use hash table
Node *search(int page, PageTable &pageTable, Node* head){
    auto it = pageTable.find(page);
    if (it != pageTable.end()){
        return it->second;
    }
    return nullptr;
}
/**/
Node *search(int page, PageTable &pageTable, Node* head){
    if(pageTable[page] != nullptr){
        return pageTable[page];
    }
    return nullptr;
}

int print_list(Node* head){
    Node* cur = head;
    while (cur != nullptr){
        cout<<cur->page<<"("<<cur->dirty<<") "<<"-> ";
        cur = cur->next;
    }
    cout<<"null\n";
    return 0;
}

int print_both(Node* head, Node* tail){
    //head->node->node->tail, 10 head, 10 tail
    Node* cur = head;
    int count = 0;
    while(count<5){
        cout<<cur->page<<"("<<cur->dirty<<") "<<"-> ";
        cur = cur->next;
        count++;
    }
    cout<<"... ->";
    cur = tail;
    while(count!=0){
        cur = cur->prev;
        count--;
    }
    while(cur != nullptr){
        cout<<cur->page<<"("<<cur->dirty<<") "<<"-> ";
        cur = cur->next;
    }
    cout<<"null\n";
    return 0;
}

int LRU(int frame){
    int hit = 0, miss = 0, write_back = 0;
    Node *head, *tail;
    head = new Node();
    tail = new Node();
    head->next = tail;
    head->prev = nullptr;
    tail->next = nullptr;
    tail->prev = head;
    int inframe = 0;
    PageTable pageTable(268435456, nullptr);
    for (int i = 0; i < tcn; i++){
        // cout<<i<<"\r";
        if(DEBUG ==1){
            print_list(head);
            cout<<"i: "<<i<<" "<<tc[i].op<<" "<<tc[i].p<<"\n";
        }
        int page = tc[i].p;
        Node* target = search(page, pageTable, head);
        if (target == nullptr){ // page not in frame, page fault
            miss++;
            if (inframe < frame){
                if(miss==1){  // 0 node in list
                    tail->page = page;
                    tail->dirty = tc[i].op == 'W' ? 1 : 0;
                    pageTable[page] = tail;
                    inframe++;
                }
                else if(miss==2){ // 1 node in list
                    head->page = page;
                    head->dirty = tc[i].op == 'W' ? 1 : 0;
                    pageTable[page] = head;
                    inframe++;
                }else{
                    Node* new_node = new Node;
                    new_node->page = page;
                    new_node->dirty = tc[i].op == 'W' ? 1 : 0;
                    head = insert(*head, *new_node);
                    pageTable[page] = head;
                    inframe++;
                }
            }
            else{ // need to replace
                Node* victim_node = victim(0, *head, *tail);
                pageTable[victim_node->page] = nullptr;
                if (victim_node->dirty == 1){
                    write_back++;
                }
                // print_both(head,tail);
                tail = remove(*victim_node);
                victim_node->page = page;
                victim_node->dirty = tc[i].op == 'W' ? 1 : 0;
                head = insert(*head, *victim_node);
                // print_both(head,tail);
                pageTable[page] = head;
            }
        }
        else{ //update the list
            hit++;
            if(target != head){
                Node* temp = remove(*target);
                if(target->next == nullptr){
                    tail = temp;
                }
                target->dirty = (target->dirty)|(tc[i].op == 'W' ? 1 : 0);
                head = insert(*head, *target);
            }else{ //no need to update the list
                target->dirty = (target->dirty)|(tc[i].op == 'W' ? 1 : 0);
            }
        }
        if(tail->next != nullptr){
            cout<<"tail->next is not null\n";
        }
    }
    //clean up
    Node* cur = head;
    while(cur != nullptr){
        Node* temp = cur;
        cur = cur->next;
        delete temp;
    }
    //Frame Hit Miss Page fault ratio Write back count
    printf("%d\t%d\t%d\t\t%.10f\t\t%d\n", frame, hit, miss, (double)miss/tcn, write_back);
    return 0;
}

int CFLRU(int frame){
    int hit = 0, miss = 0, write_back = 0;
    Node *head, *tail;
    head = new Node();
    tail = new Node();
    head->next = tail;
    head->prev = nullptr;
    tail->next = nullptr;
    tail->prev = head;
    int inframe = 0;
    PageTable pageTable(268435456, nullptr);
    for (int i = 0; i < tcn; i++){
        // cout<<i<<"\r";
        if(DEBUG ==1){
            print_list(head);
            cout<<"i: "<<i<<" "<<tc[i].op<<" "<<tc[i].p<<"\n";
        }
        int page = tc[i].p;
        Node* target = search(page, pageTable, head);
        if (target == nullptr){ // page not in frame, page fault
            miss++;
            if (inframe < frame){
                if(miss==1){  // 0 node in list
                    tail->page = page;
                    tail->dirty = tc[i].op == 'W' ? 1 : 0;
                    pageTable[page] = tail;
                    inframe++;
                }
                else if(miss==2){ // 1 node in list
                    head->page = page;
                    head->dirty = tc[i].op == 'W' ? 1 : 0;
                    pageTable[page] = head;
                    inframe++;
                }else{
                    Node* new_node = new Node;
                    new_node->page = page;
                    new_node->dirty = tc[i].op == 'W' ? 1 : 0;
                    head = insert(*head, *new_node);
                    pageTable[page] = head;
                    inframe++;
                }
            }
            else{ // need to replace
                Node* victim_node = victim(0, *head, *tail);
                pageTable[victim_node->page] = nullptr;
                if (victim_node->dirty == 1){
                    write_back++;
                }
                // print_both(head,tail);
                tail = remove(*victim_node);
                victim_node->page = page;
                victim_node->dirty = tc[i].op == 'W' ? 1 : 0;
                head = insert(*head, *victim_node);
                // print_both(head,tail);
                pageTable[page] = head;
            }
        }
        else{ //update the list
            hit++;
            if(target != head){
                Node* temp = remove(*target);
                if(target->next == nullptr){
                    tail = temp;
                }
                target->dirty = (target->dirty)|(tc[i].op == 'W' ? 1 : 0);
                head = insert(*head, *target);
            }else{ //no need to update the list
                target->dirty = (target->dirty)|(tc[i].op == 'W' ? 1 : 0);
            }
        }
        if(tail->next != nullptr){
            cout<<"tail->next is not null\n";
        }
    }
    //clean up
    Node* cur = head;
    while(cur != nullptr){
        Node* temp = cur;
        cur = cur->next;
        delete temp;
    }
    //Frame Hit Miss Page fault ratio Write back count
    printf("%d\t%d\t%d\t\t%.10f\t\t%d\n", frame, hit, miss, (double)miss/tcn, write_back);
    return 0;
}


int main(int argc, char* argv[]) {
    //  print argc, argv to check if the input is correct
    // cout << "argc: " << argc << "\n";
    // for (int i = 0; i < argc; i++) cout << argv[i] << "\n";
    // cout<<"-------------------"<<"\n";
    readfile(argv[1]);
    // cout<<"Total instruction count: "<<tcn<<"\n";
    timeval start, end;

    gettimeofday(&start, 0);
    cout<<"LRU policy:\n";
    cout<<"Frame\tHit\t\tMiss\t\tPage fault ratio\tWrite back count\n";
    for (int frame=start_frame; frame<=end_frame; frame<<=1){
        // cout<<frame<<"\n";
        LRU(frame);
    }
    gettimeofday(&end, 0);
    double diff = end.tv_sec - start.tv_sec + (end.tv_usec - start.tv_usec) / 1000000.0;
    //Total elapsed time %.6f sec
    printf("Elapsed time: %.6f sec\n\n", diff);

    gettimeofday(&start, 0);
    cout<<"CFLRU policy:\n";
    cout<<"Frame\tHit\t\tMiss\t\tPage fault ratio\tWrite back count\n";
    for (int frame=start_frame; frame<=end_frame; frame<<=1){
        LRU(frame);
    }
    gettimeofday(&end, 0);
    diff = end.tv_sec - start.tv_sec + (end.tv_usec - start.tv_usec) / 1000000.0;
    //Total elapsed time %.6f sec
    printf("Elapsed time: %.6f sec\n\n", diff);
}