#include <iostream>
#include <mutex>
#include <condition_variable>
#include <vector>
#include <thread>
#include <map>
#include <algorithm>

#include "math.h"

using namespace std;
using namespace chrono;
mutex m;
class Kompir {
	public:
		int id;
		int velicina;
		Kompir(int _id, bool _velicina) : id(_id), velicina(_velicina) {}
};
bool wayToSort(Kompir i, Kompir j) { return i.velicina > j.velicina; }

int odrediStepen(int i)
{
	int brojac = 0;
	while(true){
		if(pow(2,brojac) >= i)
			return brojac;
		brojac++;

	}
}


class cv_tag {
	private:
		struct cv_data {
			condition_variable c;
			bool fulfilled;
			cv_data(): fulfilled(false) {}
		};
		map<size_t, cv_data*> waiting;
	public:
		cv_tag() {}
		~cv_tag();
		void wait(unique_lock<mutex>& ,size_t);
		void notify(size_t tag);
		void notify_all();
};

cv_tag::~cv_tag() {
    for (auto i = waiting.begin(); i!=waiting.end(); ++i)
        delete (*i).second;
}

void cv_tag::wait(unique_lock<mutex>& l, size_t tag) {
    waiting.insert(pair<size_t,cv_data*>{tag,new cv_data});
	while (!waiting[tag]->fulfilled)
		waiting[tag]->c.wait(l);
    delete waiting[tag];
    waiting.erase(tag);
}

void cv_tag::notify(size_t tag) {
    if (waiting.find(tag) != waiting.end()) {
        waiting[tag]->fulfilled = true;
        waiting[tag]->c.notify_one();
    }
}

void cv_tag::notify_all() {
	for (auto i = waiting.begin(); i!=waiting.end(); ++i) {
            (*i).second->fulfilled = true;
            (*i).second->c.notify_one();
    }
}

class Komat {
	public:
		int velicina;
		bool zauzeto;
		int kuj;
		Komat(int _velicina, bool _zauzeto, int _kuj) : velicina(_velicina), zauzeto(_zauzeto), kuj(_kuj) {}
};


inline bool operator==(const Komat& lhs, const Komat& rhs) {return lhs.velicina == rhs.velicina;}
class RadnaMemorija {
	private:
		vector<Komat> komati;
		int U;

		vector<Kompir> kompiri;
		cv_tag red;

		void namakni(int i, int kolikoGodina) // 22, '90 godiste
		{
			vector<Komat> noviKomati;
			for(int k = 0; k < kolikoGodina; ++k){
				noviKomati = vector<Komat>();

				for(int j = 0; j < komati.size(); ++j)
				{
					if(j != i)
						noviKomati.push_back(komati[j]);
					else
					{
						noviKomati.push_back(Komat(komati[j].velicina / 2, false, komati[j].kuj));
					}
				}

				komati = noviKomati;
			}
		}

		void razapni(bool& fnd, int& ind, int& step)
		{
			while(step < U && !fnd){
			   	for(int i = 0; i < komati.size(); i++)
			   	{
			   		if(komati[i].velicina == step && !komati[i].zauzeto)
			   		{

						fnd = true;
						ind = i;
						break;
			   		}
		   		}
		   		step++;
		   	}
		}

		void razjebi()
		{
			vector<Komat> novi = komati;

			do
			{
				komati = novi;
				novi = vector<Komat>();
				for(int i = 0; i < komati.size(); ++i)
				{
					if(komati[i].velicina = komati[i+1].velicina && !komati[i].zauzeto && !komati[i+1].zauzeto)
					{
						novi.push_back(Komat(komati[i].velicina * 2, false, komati[i].kuj));
						i++;
					}else{
						novi.push_back(komati[i]);
					}
				}

			}while(novi != komati);
		}
    public:
        RadnaMemorija(int _U) : U(_U)
        {
        	komati.push_back(Komat(_U, false, 0));
        }

        //Zauzimanje memorije
	   //Parametar id_procesa - identifikator procesa koji se smesta u memoriju
	   //Parametar potrebno - koja kolicina memorije je potrebna da se proces smesti (broj potrebnih kilobajta, a ne stepen broja 2)
	   void zauzmi(int id_procesa, int potrebno)
	   {
	   		int stepen = odrediStepen(potrebno);
	   		int step = stepen;
	   		bool found;
	   		int indeks = -1;
	   		unique_lock<mutex> l(m);
	   		razapni(found, indeks, step);
		   	while(!found)
		   	{
		   		kompiri.push_back(Kompir(id_procesa, stepen));
		   		red.wait(l, id_procesa);
	   			razapni(found, indeks, step);
		   	}

		   	if(step != stepen)
				namakni(indeks, step - stepen);

			komati[indeks].zauzeto = true;
			komati[indeks].kuj = id_procesa;

	   }
       void oslobodi(int id_procesa)
       {
       		unique_lock<mutex> l(m);
       		for(Komat k : komati)
       		{
       			if(k.kuj == id_procesa)
       				k.zauzeto = false;
       		}

       		razjebi();

       		sort(kompiri.begin(), kompiri.end(), wayToSort);
       		for(Kompir krkr : kompiri){
       			red.notify(krkr.id);
       		}

       }
};

mutex term_m;

void proces(RadnaMemorija& rm, int id_procesa, int potrebno, int kasnjenje, int trajanje) {
    this_thread::sleep_for(chrono::seconds(kasnjenje));
    {
        unique_lock<mutex> l(term_m);
        cout << "Proces " << id_procesa << " zeli da zauzme " << potrebno << " KB memorije." << endl;
    }
    rm.zauzmi(id_procesa, potrebno);
    {
        unique_lock<mutex> l(term_m);
        cout << "Proces " << id_procesa << " zauzeo " << potrebno << " KB memorije." << endl;
    }
    this_thread::sleep_for(chrono::seconds(trajanje));
    {
        unique_lock<mutex> l(term_m);
        cout << "Proces " << id_procesa << " oslobadja memoriju." << endl;
    }
    rm.oslobodi(id_procesa);
    {
        unique_lock<mutex> l(term_m);
        cout << "Proces " << id_procesa << " zavrsio." << endl;
    }
}

int BROJ_PROCESA = 5;

int main() {
    RadnaMemorija rm(10);
    vector<int> velicine = {100, 240, 64, 256, 75};
    vector<int> kasnjenje = {0, 1, 2, 3, 6};
    vector<int> trajanje = {5, 3, 5, 6, 2};
    thread procesi[BROJ_PROCESA];

    for (int i = 0; i < BROJ_PROCESA; ++i)
        procesi[i] = thread(proces, ref(rm), i+1, velicine[i], kasnjenje[i], trajanje[i]);

    for (int i = 0; i < BROJ_PROCESA; ++i)
        procesi[i].join();
}