memory-paging.cpp

/**
 *    @Author: Icaro Lima Magalhaes - 2016
 */

#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <utility>
#include <vector>
#include <climits>
#include <iterator>

unsigned long result(0);

#define COUT(msg) std::cout << msg << std::endl
#define PRINT(s, f) std::cout << s << ' ' << f << std::endl

class MemoryPaging
{

public:
    /*Aux functions*/
    static void print_vector(const std::vector< std::pair<int, int> > &);
    static bool memory_contains(std::vector< std::pair<int, int> > &, const int);
    /*Algorithms*/
    static int FIFOAlgorithm(const std::vector<int> &, const int);
    static int OptimumAlgorithm(const std::vector<int> &, const int);
    static int LRUAlgorithm(const std::vector<int> &, const int);
};

/*Aux function to find element in memory pages*/
bool MemoryPaging::memory_contains(std::vector< std::pair<int, int> > &_memory_pages,
    const int _element)
{
    for(auto it = _memory_pages.begin(); it != _memory_pages.end(); ++it)
        if((*it).first == _element) return true;
    return false;
}

/*Aux function to present vector elements*/
void MemoryPaging::print_vector(const std::vector< std::pair< int, int> > &_v)
{
    for_each(_v.begin(), _v.end(),
        [&](const std::pair<int, int> _element)
        {
            std::cout << "     " << _element.first << " : " << _element.second;
        }
    );
    std::cout << std::endl;
}

int MemoryPaging::FIFOAlgorithm(const std::vector<int> &_memory_ref_sequence,
    const int _qt_memory_pages)
{
    std::vector< std::pair<int, int> > _memory_pages;
    result = 0;

    for_each(_memory_ref_sequence.begin(), _memory_ref_sequence.end(),
        [&](int element)
        {

            for_each(_memory_pages.begin(), _memory_pages.end(),
                [&](std::pair<int, int> &_element)
                {
                    _element.second++;
                }
            );

            sort(_memory_pages.begin(), _memory_pages.end(),
                [&](const std::pair<int, int> &_this,
                    const std::pair<int, int> &_that) -> bool
                {
                    return _this.second < _that.second;
                }
            );

            if(!MemoryPaging::memory_contains(_memory_pages, element))
            {

                if(_memory_pages.size() >= _qt_memory_pages)
                {
                    _memory_pages.pop_back();
                }

                _memory_pages.emplace_back(std::make_pair(element, 0));
                result++;

            }

        }
    );

    return result;

}

/* Aux for OptimumAlgorithm */
int get_last_used_index(std::vector< std::pair< int, int> > __memory_pages,
    const std::vector<int> &__memory_ref_sequence, const int _curr_index)
{

    for(int i = 0; i < __memory_pages.size(); ++i)
    {

        for(int j = _curr_index; j < __memory_ref_sequence.size(); ++j)
        {
            if(__memory_pages[i].first == __memory_ref_sequence[j])
            {
                __memory_pages[i].second++;
                break;
            }
            else
            {
                __memory_pages[i].second++;
            }
        }
    }

    int maximum_index(INT_MIN);
    int maximum_value(INT_MIN);
    for(int i = 0; i < __memory_pages.size(); ++i)
    {
        if(__memory_pages[i].second > maximum_value)
        {
            maximum_value = __memory_pages[i].second;
            maximum_index = i;
        }

    }

    return maximum_index;

}

int MemoryPaging::OptimumAlgorithm(const std::vector<int> &_memory_ref_sequence,
    const int _qt_memory_pages)
{

    std::vector< std::pair<int, int> > _memory_pages;
    result = 0;
    int curr_index(0);
    for(auto it = _memory_ref_sequence.begin(); it != _memory_ref_sequence.end(); ++it)
    {
        ++curr_index;
        int curr_element = *it;

        if(_memory_pages.size() < _qt_memory_pages)
        {

            if(!MemoryPaging::memory_contains(_memory_pages, curr_element))
            {
                _memory_pages.emplace_back(std::make_pair(curr_element, 0));
                ++result;
            }
            else
            {
                continue;
            }

        }
        else
        {

            if(!MemoryPaging::memory_contains(_memory_pages, curr_element))
            {
                int index = get_last_used_index(_memory_pages, _memory_ref_sequence, curr_index);
                _memory_pages[index].first = *it;
                ++result;
            }

        }

    }

    return result;

}

/* Aux for LRUAlgorithm */
int get_last_recently_used_index(std::vector< std::pair< int, int> > &__memory_pages)
{

    int maximum_index(INT_MIN);
    int maximum_value(INT_MIN);
    for(int i = 0; i < __memory_pages.size(); ++i)
    {
        if(__memory_pages[i].second > maximum_value)
        {
            maximum_value = __memory_pages[i].second;
            maximum_index = i;
        }

    }

    return maximum_index;

}

int MemoryPaging::LRUAlgorithm(const std::vector<int> &_memory_ref_sequence,
    const int _qt_memory_pages)
{

    std::vector< std::pair<int, int> > _memory_pages;
    result = 0;
    int curr_index;

    for(auto it = _memory_ref_sequence.begin(); it != _memory_ref_sequence.end(); ++it, ++curr_index)
    {

        int curr_element = *it;

        for(int i = 0; i < _memory_pages.size(); ++i)
        {
            _memory_pages[i].second++;
        }

        if(_memory_pages.size() < _qt_memory_pages)
        {

            if(!MemoryPaging::memory_contains(_memory_pages, curr_element))
            {
                _memory_pages.emplace_back(std::make_pair(curr_element, 0));
                ++result;
            }
            else
            {
                _memory_pages[curr_index].second = 0;
                continue;
            }

        }
        else
        {

            if(!MemoryPaging::memory_contains(_memory_pages, curr_element))
            {
                int index = get_last_recently_used_index(_memory_pages);
                _memory_pages[index].first = *it;
                _memory_pages[index].second = 0;
                ++result;
            }
            else
            {

                for(int i = 0; i < _memory_pages.size(); i++)
                {
                    if(_memory_pages[i].first == curr_element)
                    {
                        _memory_pages[i].second = 0;
                        break;
                    }
                }

                continue;

            }

        }

    }

    return result;

}

int main(int argc, char const *argv[])
{

    if(argc > 1)
    {
        std::string filename = argv[1];
        std::ifstream input_file(filename);

        if(input_file.is_open())
        {
            int qt_memory_pages;
            input_file >> qt_memory_pages;

            int curr_sequence_item;
            std::vector<int> memory_ref_sequence;
            std::vector<int> memory_pages(qt_memory_pages);

            while(input_file >> curr_sequence_item)
            {
                memory_ref_sequence.push_back(curr_sequence_item);
            }

            PRINT("FIFO", MemoryPaging::FIFOAlgorithm(memory_ref_sequence, qt_memory_pages));
            PRINT("OTM", MemoryPaging::OptimumAlgorithm(memory_ref_sequence, qt_memory_pages));
            PRINT("LRU", MemoryPaging::LRUAlgorithm(memory_ref_sequence, qt_memory_pages));

            return 0;
        }
        else
        {
            std::cerr << "Error opening file named " << filename << std::endl;
            std::cerr << "Exiting now." << std::endl;
            exit(0);
        }
    }
    else
    {
        std::cerr << "Usage error: Incorrect arguments" << std::endl;
        std::cerr << "Usage: ./a.out filename.txt" << std::endl;
    }

    return 0;

}