#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <search.h>
#include <windows.h>
#include <algorithm>

using namespace std;

const int n = 500;

class zadanie{

public:
    double nczas, liniowy, prog, d;

    void wylosuj(int n)                             //losowanie wartosci dla zadania z przedzialow
    {
        nczas = ((11.0)*(double)rand()/RAND_MAX) + 10;
        liniowy = ((10.0)*(double)rand()/RAND_MAX) + 1;
        prog = (((5.0)*(double)rand()/RAND_MAX) + 1) * 0.1 *n;
        d = (((nczas + liniowy*n)*(double)rand()/RAND_MAX) + nczas/n) * 0.25;
    }
};

int compare(const void *arg1, const void *arg2)     //funkcja porownujaca do qsorta
{
    zadanie *z1 = (zadanie*) arg1;
    zadanie *z2 = (zadanie*) arg2;
    return (int)(z1->d - z2->d);
}

double GetTime()                                    //funkcja mierzaca czas
{
  long long f,t;
  QueryPerformanceFrequency((PLARGE_INTEGER)&f);
  QueryPerformanceCounter((PLARGE_INTEGER)&t);
  return (double)t/(double)f;
}

void main()
{
    int instancje=50;
    double czas=0;
    double srednia=0;

    srand(time(0));                             //aby losowane liczby losowane byly rozne przy
    zadanie x[n];                               //kazdym dzialaniu programu
    for(int i=0; i<n; i++)
    {
        x[i].wylosuj(n);                        //wypelnianie tabeli klasy zadanie
    }

    for(int i=0; i<instancje; i++)              //mierzenie czasu dla liczby instancji
    {
        double t1=GetTime();
        qsort(x, n, sizeof(zadanie), compare);  //sortowanie po niemalejacym elemencie d
        double t2=GetTime();
        czas=t2-t1;
        srednia=srednia+czas;
    }
    cout<<"Sredni czas EDD: "<<srednia/instancje<<"s"<<endl;

    double p[n];
    double c[n];

    //Algorytm Moore'a
    double temp=0;
    double czasmax=0;
    int i_opoznione=0;
    double ostatni=-1;
    zadanie opoznione;

    czas=0;
    srednia=0;
    /*
    for(int i=0; i<instancje; i++)
    {
        double t3=GetTime();

        //w petli for dodatkowy warunek, aby po dojsciu do wczesniej przeniesionego zadania
        //zakonczyc prace algorytmu
        for(int i=0; i<n && x[i].nczas!=ostatni; i++)
        {
            if(i-x[i].prog>0) p[i]=x[i].nczas + (x[i].liniowy*(i-x[i].prog));
            else p[i]=x[i].nczas;                   //czas wykonania kolejnego zadania
            c[i] = p[i] + temp;
            temp = c[i];
            //tablica c zawiera kolejne czasy kolejno zakonczonych zadan

            if(c[i]>x[i].d)                         //gdy C>d wez zadanie
            {
                for(int j=0; j<i; j++)
                {
                    if(x[j].nczas>czasmax)
                    {
                        czasmax=x[j].nczas; //...znajdz najwieksze a z przedzialu [1,zadanie]
                        i_opoznione=j;
                    }
                }
                opoznione=x[i_opoznione];
                for(int j=i_opoznione; j<n-1; j++)  //przenies je na koniec
                {
                    x[j]=x[j+1];            //reszte przenies
                }
                x[n-1]=opoznione;

                if(ostatni==-1)             //warunek, ktory pomoze zakonczyc algorytm
                {
                    ostatni=x[n-1].nczas;
                }
            }
        }
        double t4=GetTime();
        czas=t4-t3;                         //sredni czas dla odpowiedniej liczby instancji
        srednia=srednia+czas;
    }
    cout << "Sredni czas  MA: " << srednia/instancje <<"s"<<endl;
    */

    //NEH
    int il_opoz=0;
    int naj_opoz=0;
    zadanie y[n];
    zadanie pom[n];
    zadanie last;
    y[0]=x[0];
    for(int i=0; i<instancje; i++)          //petla wykonujaca ilosc instancji
    {
        double t3=GetTime();

        for(int j=1; j<n; j++)          //dodawanie kolejnego zadania
        {
            y[j]=x[j];
            for(int k=j; k>0; k--)      //przesuwanie ostatniego elementu w lewa strone o jeden element
            {
                for(int i=0; i<n; i++)  //liczenie opoznien
                {
                    if(i-y[i].prog>0) p[i]=y[i].nczas + (y[i].liniowy*(i-y[i].prog));
                    else p[i]=y[i].nczas;                   //czas wykonania kolejnego zadania
                    c[i] = p[i] + temp;
                    temp = c[i];
                    //tablica c zawiera kolejne czasy kolejno zakonczonych zadan

                    if(c[i]>y[i].d) il_opoz++;
                }
                if(il_opoz<naj_opoz)    //jezeli nowe szeregowanie ma mniej opoznien przepisz je do tablicy pomocniczej
                {
                    naj_opoz=il_opoz;
                    for(int m=0; m<j; m++)
                    {
                        pom[m]=y[m];
                    }
                }
                last=y[k];      //przesuniecie elementu o jedna pozycje w lewo
                y[k]=y[k-1];
                y[k-1]=last;
            }
            naj_opoz=j;         //ustawienie maksymalnej liczby opoznien dla przebiegu po zwiekszeniu liczby elementow
            il_opoz=0;
        }
        for(int i=0; i<n; i++) x[i]=pom[i]; //przepisanie najlepszego szeregowania do tablicy pierwotnej
        double t4=GetTime();
        czas=t4-t3;                         //sredni czas dla odpowiedniej liczby instancji
        srednia=srednia+czas;
    }
    cout << "Sredni czas  NEH: " << srednia/instancje <<"s"<<endl;
}