//---------------------------------------------------------------------------

/*
kurs:
- ETE7013L Optymalizacja procesow dyskretnych

termin:
- CZW/P 09:15

autorzy:
- Dominik Chalupczynski
- Stanislaw Kozuchowicz
- Lukasz Fajdek
*/

//---------------------------------------------------------------------------

#pragma hdrstop
#include <iostream.h>
#include <conio.h>
using namespace std;

//---------------------------------------------------------------------------

int n;                                     //liczba zadan
int lineN = 0;                             //indeks wiersza wykozystywany przy tablicy N[][]
int lineLTS = 0;                           //indeks wiersza wykozystywany przy tablicy LTS[][]

int N[1225][50];                           //tablica przechowujaca aktualne otoczenie
long int F_N[1225];                        //tablica przechowująca wartosci funkcji celu wszystkich permutacji wchodzacych w sklad otoczenia
int LTS[100][50];                          //lista tabu

//---------------------------------------------------------------------------

void drukuj(const int *pi, const int n)    //funkcja funkcja zapisujaca otoczenie do tablicy
{
  if (pi != 0)
  {
    for (int k = 0; k < n; k++)
    {
      N[lineN][k] = pi[k];
    }
    lineN++;
  }
}

//---------------------------------------------------------------------------

void otoczenie(int n, int *pi)              //funkcja generujaca otoczenie rozwiazania
        {
        int tmp = 0;
        for (int i=0; i<(n * (n - 1))/2; i++)
        {
          for(int j=i+1; j<=n-1; j++)
          {
            tmp = pi[i];
            pi[i] = pi[j];
            pi[j] = tmp;
            drukuj(pi, n);
            tmp = pi[i];
            pi[i] = pi[j];
            pi[j] = tmp;
          }
        }
lineN = 0;
}

//---------------------------------------------------------------------------

int maks(int T)
        {
          if (T > 0)
            return T;
          else
            return 0;
        }

//---------------------------------------------------------------------------

void Fcelu(int n, int *t, int *d, int *w)                //funkcja obliczajaca i zapisujaca w tablicy wartosci funkcji celu dla wszystkich permutacji wchodzacych w sklad otoczenia
        {
          long int c = 0;                                //zmienna przechowujaca czas zakonczenia zadania
          long int T;                                    //zmienna przechowujaca czas opuznienia zadania
          long int F = 0;                                //zmienna przechowujaca wartosc funkcji celu

          for (int a = 0; a < n*(n-1)/2; a++)
          {
            for (int b = 0; b < n; b++)
            {
              c = c + t[N[a][b]];
              T = maks(c - d[N[a][b]]);
              F = F + T * w[N[a][b]];
            }
            F_N[a] = F;
            c = 0;
            F = 0;
           }
        }

//---------------------------------------------------------------------------

int lepszy(long int F_piBest, long int F_pi)             // funkcja zwraca 1 gdy drugi z parametrow jest mniejszy,
        {                                                //w przeciwnym pryzpadku 0
          if(F_piBest > F_pi)
            return 1;
          else
            return 0;
        }

//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{

  int t[50];                                //tablica przechowujaca czasy wkonywania poszczegolonych zadan
  int w[50];                                //tablica przechowujaca wagi poszczegolnych zadan
  int d[50];                                //tablica przechowujaca deadline`y poszczegolnych zadan
  int pi[50];                               //tablica przechowujaca rozwiazanie poczatkowe
  int piBest[50];                           //tablica przechowujaca najlepsza permutacje
  long int F_piBest = 0;                    //zmienna przechowujaca wartosc funkcji celu najlepszej permutacji
  int licznik = 0;

//---------------------------------------------------------------------------

  Etykieta:

  clrscr();
  cout << "Prosze wprowadzic liczbe zadan (2-50):";
  cin >> n ;
  cout << endl ;

  if (n<51)
  {
    for (int l = 0; l<n; l++)
    {
     cout << "Prosze wprowadzic czas wykonania zadania nr." << l + 1 << ": ";
     cin >> t[l];
     cout <<endl;

     cout << "Prosze wprowadzic wage zadnia nr." << l + 1 << ": ";
     cin >> w[l];
     cout <<endl;

     cout << "Prosze wprowadzic deadline zadania nr." << l + 1 << ": ";
     cin >> d[l];
     cout <<endl;

     clrscr();
    }
  }
  else
  {
    cout << endl;
    cout << "Wprowadzona liczba zadan jest za duza!!" << endl;
    cout << "Wcisnij dowolny klawisz..." << endl;
    getch();
    goto Etykieta;
  }

  for(int m=0; m<n; m++)
  {
    cout << "Zadanie nr." << m+1 << ": " << endl;
    cout << "     - czas wykonania t" << m + 1 << ": " << t[m] << endl;
    cout << "     - waga w" << m + 1 << ": " << w[m] << endl;
    cout << "     - deadline d" << m + 1 << ": " << d[m] << endl;
    cout << endl;
  }

//---------------------------------------------------------------------------

  for (int a = 0; a < 50; a++)              //wypelnienie tabicy pi[] pierwszym rozwiazaniem: 1,2,3,....,n
  {
    pi[a] = a;
  }

  for (int b = 0; b < 1225; b++)            //wyzerowanie tablicy przechowujacej bierzace otoczenie
  {
    for(int c = 0; c < 50; c++)
    {
      N[b][c] = 0;
    }
  }

  for (int d = 0; d < 100; d++)             //wypelnienie zerami listy tabu search
  {
    for(int e = 0; e < 50; e++)
    {
      LTS[d][e] = 0;
    }
  }

  for (int f = 0; f < 50; f++)              
  {
    piBest[f] = pi[f];
    LTS[lineLTS][f] = piBest[f];
  }
  lineLTS++;

  long int c_piBest = 0;
  long int T_piBest;

  for (int z = 0; z < n; z++)               //inicjalizacja wartosci funkcji celu rozwiazania poczatkowego
  {
    c_piBest = c_piBest + t[piBest[z]];
    T_piBest = maks(c_piBest - d[piBest[z]]);
    F_piBest = F_piBest + T_piBest * w[piBest[z]];
  }

//---------------------------------------------------------------------------

  for (int r = 0; r < (n); r++)
  {
    otoczenie(n, pi);
    Fcelu(n, t, d, w);

    for (int k = 0; k < (n*(n-1)/2); k++)         // blok usuwajacy z otoczenia permutacje
    {                                             //znajdujace sie juz na liscie tabu
      for (int j=0; j < lineLTS; j++)             //
      {                                           //
        for(int i = 0; i < n; i++)                //
        {                                         //
          if (N[k][i] == LTS[j][i]) licznik += 1; //
        }                                         //
        if (licznik == n)                         //
        {                                         //
          if (!lepszy(F_piBest, F_N[k]))          //
          {                                       //
            F_N[k] = 2147483647;                  // przypisanie permutaji znalezionej na LTS wartosci
          }                                       //funkcji celu ktora wykluczy jej udzial w dalszych poszukiwaniach
        }                                         //
        licznik = 0;                              //
      }                                           //
    }                                             //

    int best = F_N[0];
    int indeks = 0;

    for (int l = 1; l < (n*(n-1)/2); l++)         //wyszukanie najlepszej permutacji w bierzacym otoczeniu
    {
      if(lepszy(best, F_N[l]))
      {
        best = F_N[l];
        indeks = l;
      }
    }

    if (lepszy(F_piBest, F_N[indeks]))            // sprawdzenie czy najlepsza permutacja
    {                                             //z aktualnego otoczenia jest lepsza od piBest
      for (int m = 0; m < n; m++)
      {
        piBest[m] = N[indeks][m];
      }
    F_piBest = F_N[indeks];
    }

    for (int p = 0; p < n; p++)                   //dodanie atrybutow ruchu do LTS
      {
        pi[p] = N[indeks][p];
        LTS[lineLTS][p] = pi[p];
      }
    lineLTS++;
  }

  cout << endl;
  cout << "Optymalna kolejnosc wykonania zadan to:" << endl;

  for(int o = 0; o < n; o++)
  {
    cout << piBest[o] +1 << "  ";
  }

//---------------------------------------------------------------------------

      cout << endl;
      cout << "Wcisnij dowolny klawisz..." << endl;
      getch();
      return 0;
}
//---------------------------------------------------------------------------
