5.zad

#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;
mutex term_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 printaj() {
        unique_lock<mutex> l(term_m);

        cout << "--------------------------------------------------------------------" << endl;
        for (Komat k : komati)
        {
            cout << "Komat: " << pow(2,k.velicina) << "KB, zauz: " << k.zauzeto << ", kuj: " << k.kuj << endl;
        }
        cout << "--------------------------------------------------------------------" << endl;
    }

    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 - 1, false, komati[j].kuj));
                    noviKomati.push_back(Komat(komati[j].velicina - 1, 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>();
            bool flag = false;
            for (int i = 0; i < komati.size(); ++i)
            {
                if ((i != komati.size() - 1) && (komati[i].velicina == komati[i + 1].velicina) && (!komati[i].zauzeto) && (!komati[i + 1].zauzeto) && !flag)
                {
                    novi.push_back(Komat(komati[i].velicina + 1, false, komati[i].kuj));
                    i++;
                    flag = true;
                }
                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)
    {
        printaj();
        int stepen = odrediStepen(potrebno);
        int step = stepen;
        bool found = false;
        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) - 1);

        komati[indeks].zauzeto = true;
        komati[indeks].kuj = id_procesa;
        printaj();
    }
    void oslobodi(int id_procesa)
    {
        printaj();
        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);
        }
        printaj();
    }
};


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;
    }
}

const 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();

    cout << "Press enter to continujes: ";
    cin.get();
}