#include <iostream>
#include <vector>
#include <list>
#include <random>
#include <queue>
#include <algorithm>
#include <functional>

#define vector std::vector

struct Anomalys{
    int sequence;
    int faults;
    int previousFaults;
    int previousFrameSize;
    int frameSize;
};

vector<vector<int>> sequenceGenerator();
void printOutPut(vector<Anomalys> anomalyVector);

int main(){
    vector<Anomalys> anomalyVector;
    vector<vector<int>> sequences = sequenceGenerator();
    //sequence loop each sequence holds a vector of 1000 randoms
    for(int i = 0; i < 100; i++){
        int lastFaultCount = 0;
        //page size loop will increment and run over same sequence 100 times.
        for(int m = 1; m <= 100; m++) {
            std::queue<int> fifoPaging;
            int pageFault = 0;
            bool boolArray[251] = {false};
            //queue loop
            for (int j = 0; j < 1000; j++) {
                if (boolArray[sequences[i][j]]) {
                    //do nothing because value is already in queue
                } else if (fifoPaging.size() < m) {
                    boolArray[sequences[i][j]] = true;
                    fifoPaging.push(sequences[i][j]);
                } else {
                    boolArray[fifoPaging.front()] = false;
                    fifoPaging.pop();
                    pageFault++;
                    fifoPaging.push(sequences[i][j]);
                    boolArray[sequences[i][j]] = true;
                }
            }
            if (lastFaultCount < pageFault && m != 1) {
                Anomalys *tmp = new Anomalys();
                tmp->sequence = i;
                tmp->faults = pageFault;
                tmp->previousFaults = lastFaultCount;
                tmp->previousFrameSize = m - 1;
                tmp->frameSize = m;
                anomalyVector.push_back(*tmp);
            }
            lastFaultCount = pageFault;
        }
    }
    printOutPut(anomalyVector);
}

void printOutPut(vector<Anomalys> anomalyVector){
    for( int i = 0; i < anomalyVector.size(); i++){
        std::cout << "\nAnomoly Found!" << std::endl;
        std::cout << "\tSequence: " << anomalyVector[i].sequence << std::endl <<
                  "\tPage faults: " << anomalyVector[i].faults << " @ Frame Size: " << anomalyVector[i].frameSize
                  << "\n" << "\tPage faults: " << anomalyVector[i].previousFaults << " @ Frame Size: "
                  << anomalyVector[i].previousFrameSize << "\n";
    }
    std::cout << "\n\nAnomaly detected: " << anomalyVector.size() << " times!\n";
}

vector<vector<int>> sequenceGenerator(){
    vector<vector<int>> sequences;
    for(int i = 0; i < 100; i++){
        std::random_device rnd_device;
        std::mt19937 mersenne_engine(rnd_device());
        std::uniform_int_distribution<int> range(1, 250);
        auto generator = std::bind(range, mersenne_engine);
        vector<int> page(1000);
        std::generate(begin(page), end(page), generator);
        sequences.push_back(page);
    }

    return sequences;
}