interclasare

#include <iostream>
#include <list>
#include <vector>
#include "Profiler.h"

using namespace std;

Profiler profiler("average");

list <int> lista_interclasta;

struct Heap
{
    list<int> v;
    int size;
};

void print(list<int> const& list)
{
    for (auto it = list.cbegin(); it != list.cend(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

void generare_liste(vector<list <int>> &lista ,int n, int k)
{
    for (int i = 0; i < k - 1; i++)
    {
        int r = rand() % (n);
        while (r == 0 || (n - r) < k - i - 1)
            r = rand() % (n);
        n -= r;
        int* v = (int*)malloc(r * sizeof(int));
        FillRandomArray(v, r, 1, 100, false, 1);
        for (int j = 0; j < r; j++)
        {
            lista[i].push_back(v[j]);
        }
        free(v);
    }
    if (n > 0) {
        int* v = (int*)malloc(n * sizeof(int));
        FillRandomArray(v, n, 1, 100, false, 1);
        for (int j = 0; j < n; j++)
        {
            lista[k - 1].push_back(v[j]);
        }
        free(v);
    }
}

void test_generare()
{
    vector<list <int>> lista(4);
    generare_liste(lista, 20, 4);
    for (int i = 0; i < 4; i++)
        print(lista[i]);
}

int parent(int i)
{
    return (i - 1) / 2;
}

int left(int i)
{
    return 2 * i + 1;
}

int right(int i)
{
    return 2 * (i + 1);
}


void minHeapify(Heap* h, int i, int n, int k)
{
    Operation opComp1 = profiler.createOperation("k1Total", k);
    Operation opComp2 = profiler.createOperation("k2Total", k);
    Operation opComp3 = profiler.createOperation("k3Total", k);

    int mini = 0, ok = 0;

    int l = left(i);
    int r = right(i);

    list<int>::iterator it_i = h->v.begin();
    advance(it_i, i);

    if (k == 5)
        opComp1.count();
    else
        if (k == 10)
            opComp2.count();
        else
            if (k == 100)
                opComp3.count();
    if (l < h->size)
    {
        list<int>::iterator it_l = h->v.begin();
        advance(it_l, l);

        if (k == 5)
            opComp1.count();
        else
            if (k == 10)
                opComp2.count();
            else
                if (k == 100)
                    opComp3.count();
        if (l < h->size && *it_l < *it_i)
        {
            mini = l;
            ok = 1;
        }
        else
        {
            mini = i;
            ok = 1;
        }
    }

    list<int>::iterator it_min = h->v.begin();
    advance(it_min, mini);

    if (k == 5)
        opComp1.count();
    else
        if (k == 10)
            opComp2.count();
        else
            if (k == 100)
                opComp3.count();
    if (r < h->size)
    {
        list<int>::iterator it_r = h->v.begin();
        advance(it_r, r);

        if (k == 5)
            opComp1.count();
        else
            if (k == 10)
                opComp2.count();
            else
                if (k == 100)
                    opComp3.count();
        if (r < h->size && *it_r < *it_min)
        {
            mini = r;
            it_min = h->v.begin();
            advance(it_min, mini);
            ok = 1;
        }
    }
    if (mini != i && ok)
    {
        if (k == 5)
            opComp1.count(3);
        else
            if (k == 10)
                opComp2.count(3);
            else
                if (k == 100)
                    opComp3.count(3);
        swap(*it_i, *it_min);
        minHeapify(h, mini, n, k);
    }
}

void buildMinHeap_bottomUp(Heap* h, int n, int k)
{
    for (int i  = h->size / 2 - 1; i >= 0; i--)
    {
        minHeapify(h, i, n, k);
    }
}

int heapExtractMin(Heap* h, int k)
{
    int min = *h->v.begin();
    list<int>::iterator it_ultimul = h->v.begin();
    advance(it_ultimul, h->size-1);
    *h->v.begin() = *it_ultimul;
    h->v.pop_back();
    h->size--;
    minHeapify(h, 0, h->size, k);
    return min;
}

void interclasare_k(vector<list <int>>& lista, int k, int n)
{
    Operation opComp1 = profiler.createOperation("k1Total", n);
    Operation opComp2 = profiler.createOperation("k2Total", n);
    Operation opComp3 = profiler.createOperation("k3Total", n);

    Heap h;
    h.size = k;

    int* vec = (int*)malloc(k * sizeof(int));

    int j = 0;
    for (int i = 0; i < k; i++) {
        if (k == 5)
            opComp1.count();
        else
            if (k == 10)
                opComp2.count();
            else
                if (k == 100)
                    opComp3.count();
        if (!lista[i].empty()) {
            if (k == 5)
                opComp1.count();
            else
                if (k == 10)
                    opComp2.count();
                else
                    if (k == 100)
                        opComp3.count();
            h.v.push_back(*lista[i].begin());
            vec[i] = *lista[i].begin();
            lista[i].pop_front();
            j++;
        }
    }
    //print(h.v);
    h.size = j;
    buildMinHeap_bottomUp(&h, h.size, k);

    while (lista_interclasta.size() < n)
    {
        int i = 0, c;
        while(i<k) {
            if (k == 5)
                opComp1.count();
            else
                if (k == 10)
                    opComp2.count();
                else
                    if (k == 100)
                        opComp3.count();
            if (!h.v.empty() && h.size > 0) {
                c = heapExtractMin(&h,k);
                if (k == 5)
                    opComp1.count();
                else
                    if (k == 10)
                        opComp2.count();
                    else
                        if (k == 100)
                            opComp3.count();
                lista_interclasta.push_back(c);
            }
            int ok = 0;
            for (int m = 0; ok == 0 && m < k; m++)
            {
                if (k == 5)
                    opComp1.count();
                else
                    if (k == 10)
                        opComp2.count();
                    else
                        if (k == 100)
                            opComp3.count();
                if (vec[m] == c && !lista[m].empty())
                {
                    ok = 1;
                    vec[m] = *lista[m].begin();
                    h.v.push_back(*lista[m].begin());
                    h.size++;
                    buildMinHeap_bottomUp(&h, h.size, k);
                    lista[m].pop_front();
                }
            }
            if (!ok) {
                if (k == 5)
                    opComp1.count();
                else
                    if (k == 10)
                        opComp2.count();
                    else
                        if (k == 100)
                            opComp3.count();
                i = 0;
                while (i < k && lista[i].empty())
                    i++;
                if (k == 5)
                    opComp1.count();
                else
                    if (k == 10)
                        opComp2.count();
                    else
                        if (k == 100)
                            opComp3.count();
                if (i < k && !lista[i].empty()) {
                    h.v.push_back(*lista[i].begin());
                    h.size++;
                    buildMinHeap_bottomUp(&h, h.size, k);
                    lista[i].pop_front();
                }
            }
            i++;
        }
    }
}

void test_interclasare()
{
    vector<list <int>> lista(4);
    generare_liste(lista, 8, 4);
    for (int i = 0; i < 4; i++)
        print(lista[i]);
    interclasare_k(lista, 4,8);
    print(lista_interclasta);
}

void average()
{
    for (int n = 100; n <= 10000; n += 100)
    {
        //vector<list <int>> lista1(5);
        //generare_liste(lista1, n, 5);
        //interclasare_k(lista1, 5, n);

        //vector<list <int>> lista2(10);
        //generare_liste(lista2, n, 10);
        //interclasare_k(lista2, 10, n);

        vector<list <int>> lista3(100);
        generare_liste(lista3, n, 100);
        interclasare_k(lista3, 100, n);
    }

    /*for (int k = 10; k <= 500; k += 10)
    {
        vector<list <int>> lista(k);
        generare_liste(lista, 10000, k);
        interclasare_k(lista, k, 10000);
    }*/

    profiler.createGroup("Total k-const", "k1Total", "k2Total", "k3Total");
    profiler.createGroup("Total n-const", "nTotal");

    profiler.showReport();
}

int main()
{
    //test_generare();
    //test_interclasare();
    average();
}