Coda_di_priorità_Min-Heap

#include "Coda_di_priorita.h"


Coda_di_priorita::Coda_di_priorita()
{
    string nome;
    int input;
    cout<<"Dimmi quanti elementi vuoi inserire: ";
    cin>>n_oggetti;

    ogg=new Oggetto[n_oggetti];

        for(int i=0;i<n_oggetti;i++)
        {
            cout<<"Inserire nome oggetto: ";
            cin>>nome;
            (ogg+i)->set_nome(nome);
            cout<<"Inserire peso oggetto: ";
            cin>>input;
            (ogg+i)->set_peso(input);
            cout<<"Inserire valore oggetto: ";
            cin>>input;
            (ogg+i)->set_valore(input);
            (ogg+i)->set_priorita();
        }
}

Coda_di_priorita::Coda_di_priorita(Oggetto *ogg,int n_oggetti)
{
    this->ogg=ogg;
    this->n_oggetti=n_oggetti;
}

Coda_di_priorita::~Coda_di_priorita()
{
    delete []ogg;
}

void Coda_di_priorita::HeapSort()
{
    Build_Min_Heap();
    for(int j=n_oggetti-1;j>0;j--)
        {
            swap(*(ogg+0),*(ogg+j));
            heap_size--;
            Heapify(0);
        }
}

void Coda_di_priorita::Build_Min_Heap()
{
    heap_size = n_oggetti;
    for (int i=n_oggetti/2; i>=0; i--)
        Heapify(i);
}

void Coda_di_priorita::Heapify(int i)
{
    int l,r,minimo;
    l=Left(i);
    r=Right(i);

    if(l < heap_size && ((ogg+l)->get_priorita() < (ogg+i)->get_priorita()))
        minimo = l;
    else
        minimo = i;

    if( r < heap_size && ((ogg+r)->get_priorita() < (ogg+minimo)->get_priorita()))
        minimo = r;

    if(minimo!=i)
    {
        swap(*(ogg+i),*(ogg+minimo));
        Heapify(minimo);
    }
}

void Coda_di_priorita::Heap_Decrease_priority(int i,int val)
{
    if(val>((ogg+i)->get_valore()))
        cout<<"Errore. Il nuovo valore e' maggiore dell'attuale"<<endl;
    else
        {
            (ogg+i)->set_valore(val);
            (ogg+i)->set_priorita();

            while(i>0 && (ogg+Padre(i))->get_valore() > (ogg+i)->get_valore())
                {
                    swap(*(ogg+i),*(ogg+Padre(i)));
                    i=Padre(i);
                }
        }
}

Oggetto Coda_di_priorita::Heap_Minimum()
{
    return *(ogg);
}

Oggetto Coda_di_priorita::Heap_Extract_Min()
{
    if(heap_size<=0)
        {cout<<"Errore."<<endl;exit(1);}
    Oggetto minimo;
    minimo=*(ogg);
    swap(*(ogg+0),*(ogg+heap_size-1));
    heap_size=heap_size-1;
    resize_oggetti(heap_size);
    Heapify(0);
    return minimo;
}

void Coda_di_priorita::Insert(Oggetto x)
{
    n_oggetti=n_oggetti+1;
    resize_oggetti(n_oggetti);
    *(ogg+n_oggetti-1)=x;
}

void Coda_di_priorita::resize_oggetti(int newsize)
{
    Oggetto* newArr = new Oggetto[newsize];

    if(newsize>n_oggetti)
    {
        for(int i=0;i<n_oggetti;i++)
            *(newArr+i)=*(ogg+i);
    }
    else
    {
        for(int i=0;i<newsize;i++)
            *(newArr+i)=*(ogg+i);
    }
    delete [] ogg;
    ogg = newArr;
    n_oggetti=newsize;
}

int Coda_di_priorita::Left(int i) { return 2*i+1;}
int Coda_di_priorita::Right(int i) { return 2*i+2;}
int Coda_di_priorita::Padre(int i) {return i/2;}


void Coda_di_priorita::stampa()
{
        for(int i=0;i<n_oggetti;i++)
        {
            cout<<i+1<<") "<<(ogg+i)->get_nome()<<"\t";
            cout<<"Peso: "<<(ogg+i)->get_peso()<<"\t";
            cout<<"Valore: "<<(ogg+i)->get_valore()<<"\t";
            cout<<"Priorita': "<<(ogg+i)->get_priorita()<<endl;
        }
}