#include "stdafx.h"
#include<stdio.h>
#include<conio.h>
#include "graphics.h"
#include<fstream>
#include<iostream>
#include <string>
#include <iostream>
#include <thread>

#define MAX 20

using namespace std;

string zestaw_1 = "daneBB.txt";
string zestaw_2 = "daneBB1.txt";

// Mierzenie czasu
LARGE_INTEGER performanceCountStart, performanceCountEnd;
LARGE_INTEGER startTimer()
{
    LARGE_INTEGER start;
    DWORD_PTR oldmask = SetThreadAffinityMask(GetCurrentThread(), 0);
    QueryPerformanceCounter(&start);
    SetThreadAffinityMask(GetCurrentThread(), oldmask);
    return
        start;
}
LARGE_INTEGER endTimer()
{
    LARGE_INTEGER stop;
    DWORD_PTR oldmask = SetThreadAffinityMask(GetCurrentThread(), 0);
    QueryPerformanceCounter(&stop);
    SetThreadAffinityMask(GetCurrentThread(), oldmask);
    return
        stop;
}

// Zmienne algorytmu
float profit[MAX] = { 0 };
float weight[MAX] = { 0 };
float capacityRucksack;
int amountOfElements;

// Struktura węzła
struct node
{
    float lowerBound;
    float upperBound;
    int tag;
    int objno;
};


void load_from_file(string file_name, float (&profit)[MAX], float (&weight)[MAX], float &capacityRucksack, int& amountOfElements)
{

    ifstream odczyt(file_name);
    odczyt >> amountOfElements;
    for (int i = 1; i <= amountOfElements; i++)
    {
        odczyt >> weight[i] >> profit[i];
    }
    odczyt >> capacityRucksack;
    odczyt.close();
}

// Interfejs - menu
void accept()
{
    int what;
    cout << "1. Manualne wprowadzanie danych\n2. Wczytywanie danych z pliku\n\n\tWybor: ";
    cin >> what;
    if (what == 1)
    {
        cout << "\n\nIlosc elementow: ";
        cin >> amountOfElements;

        for (int i = 1; i <= amountOfElements; i++)
        {
            cout << "\nelement " << i;
            cout << "\n\twaga: ";
            cin >> weight[i];
            cout << "\n\tprofit: ";
            cin >> profit[i];

        }
        cout << "\nPojemnosc plecaka: ";
        cin >> capacityRucksack;
    }
    else if (what == 2)
    {
        string file_name = "";
        cout << "\nPodaj nazwe pliku: ";
        cin >> file_name;
        load_from_file(file_name,profit,weight,capacityRucksack,amountOfElements);

        cout << "\nIlosc elementow: " << amountOfElements;
        cout << "\nelement\twaga\tprofit\n";
        for (int i = 1; i <= amountOfElements; i++)
        {
            cout << "   " << i << "\t" << weight[i] << "\t" << profit[i] << endl;
        }
        cout << "\nPojemnosc plecaka: " << capacityRucksack;
    }
    else
    {
        cout << "Blad w wyborze w menu! Dowidzenia!";
        exit(0);
    }
}


float ubound(float cProfit, float cWeight, int k, float capacityRucksack)
{
    for (int i = k + 1; i <= amountOfElements; i++)
    {
        if (cWeight + weight[i] <= capacityRucksack)
        {
            cWeight = cWeight + weight[i];
            cProfit = cProfit - profit[i];
        }
    }
    return cProfit;
}

float bound(float cProfit, float cWeight, int k)
{
    for (int i = k + 1; i <= amountOfElements; i++)
    {
        if (cWeight + weight[i] <= capacityRucksack)
        {
            cWeight = cWeight + weight[i];
            cProfit = cProfit - profit[i];
        }
        else
        {
            return (cProfit - ((capacityRucksack - cWeight) / weight[i])*profit[i]);
        }
    }
    return cProfit;
}

void LCsearch(float profit[MAX], float weight[MAX], float capacityRucksack, int amountOfElements)
{
    int i = 1;
    int k;
    int vector[10] = {};
    float wWeight = 0;
    float pProfit = 0;
    float upper = 999;
    struct node cLeft, cRight, e;

    e.upperBound = ubound(0, 0, 0, capacityRucksack);
    e.lowerBound = bound(0, 0, 0);
    e.tag = -1;
    e.objno = 0;
    upper = e.upperBound;
    while (true)
    {
        k = e.objno + 1;
        cRight.upperBound = ubound(pProfit, wWeight, k, capacityRucksack);
        cRight.lowerBound = bound(pProfit, wWeight, k);
        cRight.tag = 0;
        cRight.objno = k;
        if (cRight.upperBound < upper)
        {
            upper = cRight.upperBound;
        }
        cLeft.tag = 1;
        cLeft.objno = k;
        if (wWeight + weight[k] <= capacityRucksack)
        {
            cLeft.upperBound = ubound(pProfit - profit[k], wWeight + weight[k], k, capacityRucksack);
            cLeft.lowerBound = bound(pProfit - profit[k], wWeight + weight[k], k);
        }
        else
        {

            e.upperBound = pProfit;
            cLeft.lowerBound = pProfit;// bound(pProfit-profit[k],wWeight+weight[k],k);
        }

        if (cLeft.lowerBound <= cRight.lowerBound && cLeft.upperBound <= cRight.upperBound)
        {
            e = cLeft;
        }
        else
        {
            e = cRight;
        }
        vector[i] = e.tag;
        i++;

        if (e.tag == 1)
        {
            pProfit = pProfit - profit[(e.objno)];
            wWeight = wWeight + weight[(e.objno)];
        }

        if (e.objno == amountOfElements)
        {
            break;
        }
    }

    printf("\n\nSolution vector = ");
    for (int i = 1; i <= amountOfElements; i++)
    {
        cout << vector[i]<< "\t";
    }
}

void task1(string zestaw)
{
    // Zmienne algorytmu
    float profit[MAX] = { 0 };
    float weight[MAX] = { 0 };
    float capacityRucksack = 0.0;
    int amountOfElements = 0;

    load_from_file(zestaw, profit, weight, capacityRucksack, amountOfElements);
    LCsearch(profit, weight, capacityRucksack, amountOfElements);
}

void main()
{
/* Na potrzeby testów zakomentowane
TEN KOD DZIAŁA TAK JAK PO STAREMU!
    accept();
    LCsearch(profit,weight,capacityRucksack,amountOfElements);
*/

    // Watek 1
    thread t1(task1, zestaw_1);

    // Wstrzymujemy maina przed zakonczeniem
    t1.join();

    cout << endl;
    system("pause");



















    /*LARGE_INTEGER performanceCountStart, performanceCountEnd;
    ofstream zapis("wyniki1.txt");
    for (int i = 0; i < 100; i++)
    {
    performanceCountStart = startTimer(); //zapami©tujemy czas pocz¥tkowy
    LCsearch();
    performanceCountEnd = endTimer(); //zapami©tujemy koniec czasu
    double tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
    zapis << i+1 << ' ' << tm << endl;
    }
    zapis.close();*/
}