Implementation of various page replacement algorithms

pageReplacement.cpp

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

template<typename T = int>
class Replacement
{
public:
	static int OPT(list<T> &stream, int FRAME_NUM)
	{
		int PF = 0, fd, d;
		T r;
		list<T> frame(FRAME_NUM);
		for(auto page = stream.begin(); (page != stream.end()) && (fd = stream.size()); page++)
		{
			if(!doesExits(*page, frame))
			{
				for(auto &x : frame)
				{
					d = distance(stream.end(), find(page, stream.end(), x)); //fwdDistance
					if(fd >= d)
						fd = d, r = x;
				}
				replaceWith(r, *page, frame);
				PF++;
			}
			viewMemory(frame);
		}
		return PF;
	}

	static int LRU(list<T> &stream, int FRAME_NUM)
	{
		int PF = 0;
		list<T> frame(FRAME_NUM), hst(FRAME_NUM);

		for(auto page : stream)
			if(!doesExits(page, frame))
			{
				replaceWith(hst.front(), page, frame);
				hst.pop_front(); hst.push_back(page);
				PF++;
			}
			else
				moveFront(page, hst);
			viewMemory(frame);
		return PF;
	}

	static int FIFO(list<T> &stream, int FRAME_NUM)
	{
		int PF = 0;
		list<T> frame(FRAME_NUM);

		for(auto page : stream)
			if(!doesExits(page, frame))
			{
				frame.pop_back();
				frame.push_front(page);
				viewMemory(frame);
				PF++;
			}
		return PF;
	}

	static int LFU(list<T> &stream, int FRAME_NUM)
	{
		int PF = 0;
		list<pair<T, int>> freq(FRAME_NUM); // v, f
		list<T> frame(FRAME_NUM);

		for(auto &page : stream)
		{
			if(!doesExits(page, frame))
			{
				viewMemory(frame);
				replaceWith(rmLeastFreq(freq), page, frame);
				PF++;
			}
			incFreq(page, freq);
		}
		return PF;
	}

	static int CLOCK(list<T> &stream, int FRAME_NUM)
	{
		int PF = 0;
		list<pair<T, bool>> frame(FRAME_NUM); // star: 0
		auto it = frame.begin();

		for(auto &page : stream)
		{
			if(!doesExits(page, frame)) // avoid dangling else
			{
				PF++;
				for(bool f = true; f; it = next(it) == frame.end() ? frame.begin() : next(it))
					if(it->second == true)
					{
						it->first = page;
						it->second = f = false;
					}
					else it->second = true;
			}
			viewMemory(frame); cout << "----------" << endl;
		}
		return PF;
	}
private:
	static bool doesExits(const T &val, list<T> &t)
	{
		return find(t.begin(), t.end(), val) != t.end();
	}

	static bool doesExits(const T &val, list<pair<T, bool>> &f) // for CLOCK only
	{
		// for(auto &x : f)
		// 	if(x.first == val)
		// 	{
		// 		x.second = false; // also set star
		// 		return true;
		// 	}
		// return false;

		auto r = find_if(f.begin(), f.end(), [=](const pair<T, bool> &a){return a.first == val;});
		return r != f.end() ? !(r->second = false) : false; // also sets star
	}

	static void viewMemory(list<T> &t)
	{
		for(auto &x : t)
			cout << x << " ";
		cout << endl;
	}

	static void viewMemory(list<pair<T, bool>> &f)
	{
		for(auto &x : f)
			cout << x.first << ":" << x.second << endl;
	}

	static void replaceWith(const T &a, const T &b, list<T> &t)
	{
		*find(t.begin(), t.end(), a) = b;
	}

	static void moveFront(const T &val, list<T> &t)
	{
		t.remove(val);
		t.push_back(val);
	}

	static T rmLeastFreq(list<pair<T, int>> &f)
	{
		typedef pair<T, int> P;
		auto m = min_element(f.begin(), f.end(), [](const P &a, const P &b){return a.second < b.second;});
		T val = m->first;
		f.erase(m);
		return val;
	}

	static void incFreq(T val, list<pair<T, int>> &f)
	{
		for(auto &x : f)
			if(x.first == val)
			{
				x.second++;
				return;
			}
		f.push_back({val, 1});
	}
};

int main()
{
	list<int> stream1 = {1, 2, 3, 4, 1, 2, 5, 1, 2, 6, 5, 1, 2},
			  stream2 = {2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2};
	list<string> stream3 = {"A", "B", "C", "D", "A", "B", "E", "A", "B", "C", "D", "E"};
	cout << Replacement<>::LFU(stream2, 3) << endl;
	// cout << Replacement<string>::FIFO(stream3, 3) << endl;
	return 0;
}