// SADlg.cpp : implementation file
//

#include "stdafx.h"
#include "SA.h"
#include "SADlg.h"
#include <math.h>
#include <stdlib.h>
#include <random>

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
double fRand(double fMin, double fMax)
{
	double f = (double)rand() / RAND_MAX;
	return fMin + f * (fMax - fMin);
}
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CSADlg dialog

CSADlg::CSADlg(CWnd* pParent /*=NULL*/)
	: CDialog(CSADlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CSADlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CSADlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CSADlg)
	DDX_Control(pDX, IDC_CITY_FRAME, m_CityFrame);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CSADlg, CDialog)
	//{{AFX_MSG_MAP(CSADlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_START, OnStart)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CSADlg message handlers

BOOL CSADlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon


	srand((unsigned)time(NULL));

	CRect r;
	m_CityFrame.GetClientRect(&r);

	m_memDC.CreateCompatibleDC(GetDC());
	m_bmp.CreateCompatibleBitmap(GetDC(), r.Width(), r.Height());
	m_font.CreatePointFont(110, "Arial");
	m_pen.CreatePen(PS_SOLID, 1, RGB(255, 0, 0));
	m_brush.CreateSolidBrush(RGB(255, 255, 255));

	m_memDC.SelectObject(&m_bmp);
	m_memDC.SelectObject(&m_font);
	m_memDC.SelectObject(&m_pen);
	m_memDC.SelectObject(&m_brush);

	m_CityFrame.GetClientRect(&r);
	m_memDC.Rectangle(&r);

	m_memDC.SetBkMode(TRANSPARENT);

	COLORREF oldTxtCol = (m_memDC.SetTextColor(RGB (0, 100, 10)));

	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CSADlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CSADlg::OnPaint()
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CPaintDC dc(this); // device context for painting

		CRect r;
		m_CityFrame.GetWindowRect(&r);
		ScreenToClient(r);

		dc.BitBlt(r.left, r.top, r.right - r.left, r.bottom - r.top, &m_memDC, 0, 0, SRCCOPY);

		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CSADlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

/**************************************************************************}
{ODCZYT MAPY Z PLIKU, WYZNACZENIE TEMPERATURY POCZATKOWEJ                  }
{**************************************************************************/
BOOL CSADlg::InitializeMap()
{

	int i, j, k;

	int stop;

	CFile f;
	if (!f.Open("tsp-c.dat", CFile::modeRead | CFile::shareDenyWrite))
	{
		MessageBox("Proszę umieścić plik tsp-c.dat w katalogu, w którym znajduje się program.");
		return FALSE;
	}

	float fBuf;

	for (i = 0; i < NCITIES; i++)
	{
		f.Read(&fBuf, sizeof(float));
		loc[i][0] = (double)fBuf;
		f.Read(&fBuf, sizeof(float));
		loc[i][1] = (double)fBuf;
	};

	f.Close();
	for (j = 0; j < NCITIES; j++)
	{
		do
		{
			stop = 1;
			route[j] = rand() % NCITIES;
			k=0;

			while (k<j)
			{
				if (route[k] == route[j]) stop = 0;
				k++;
			};
		}
		while (!stop);
	 };

	 T = 15.0;
	 energy = 0;

	 return TRUE;
}

/**************************************************************************}
{RYSOWANIE AKTUALNEJ TRASY, WYSWIETLANIE ENERGII                           }
{**************************************************************************/
void CSADlg::Draw()
{

	int i, x, y, x1, y1;
	char s[10];
	CString sEn = "Energia: ";

	CRect r;
	m_CityFrame.GetClientRect(&r);
	m_memDC.Rectangle(&r);

	if (energy == 0.0)
	{
		sEn = "Oblicz wartość energii!";
	}
	else
	{
		_gcvt_s(s, sizeof(s), energy,5);
		sEn += CString(s);
	}

	m_memDC.TextOut(10, r.Height()-20, sEn);

	for (i = 0; i < NCITIES; i++)
	{
		x = 10 + (int)((r.Width()-20)*loc[i][0]);
		y = 10 + (int)((r.Height()-20)*loc[i][1]);
		m_memDC.Ellipse(x-5, y-5, x+5, y+5);
	}

	for (i = 0; i < NCITIES-1; i++)
	{
		x = 10 + (int)((r.Width()-20)*loc[route[i]][0]);
		y = 10 + (int)((r.Height()-20)*loc[route[i]][1]);
		x1 = 10 + (int)((r.Width()-20)*loc[route[i+1]][0]);
		y1 = 10 + (int)((r.Height()-20)*loc[route[i+1]][1]);
		m_memDC.MoveTo(x, y);
		m_memDC.LineTo(x1, y1);
	};

	x = 10 + (int)((r.Width()-20)*loc[route[NCITIES-1]][0]);
	y = 10 + (int)((r.Height()-20)*loc[route[NCITIES-1]][1]);
	x1 = 10 + (int)((r.Width()-20)*loc[route[0]][0]);
	y1 = 10 + (int)((r.Height()-20)*loc[route[0]][1]);
	m_memDC.MoveTo(x, y);
	m_memDC.LineTo(x1, y1);

	CDC* pDC = GetDC();
	m_CityFrame.GetWindowRect(&r);
	ScreenToClient(r);

	pDC->BitBlt(r.left, r.top, r.right - r.left, r.bottom - r.top, &m_memDC, 0, 0, SRCCOPY);

	ReleaseDC(pDC);
}

void CSADlg::OnStart()
{

	if (!InitializeMap())
		return;

	Draw();
	maxTrialN=NCITIES*100;
	maxAcceptN=NCITIES*10;
	stopTolerance=0.005;

	minE=1e20;
	maxE=-1;

  /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}
  {TU WSTAWIC PETLE WYZARZANIA                                               }
  {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}
  Z pliku została wczytana mapa miast. Jest ich NCITIES. Ich współrzędne
  zawiera tablica loc[NCITIES][2]. Każdy wiersz tej tablicy to współrzędne
  (x,y) jednego miasta.

  Losowo wybrana trasa jest umieszczona w tablicy route[NCITIES].
  Trasa to ciąg liczb oznaczających miasta i jednocześnie wskazujących wiersze
  tablicy 'loc' (aby można było odczytywać współrzędne miast).

  Procedura 'Draw' wyświetla trasę zawartą w 'route' i wartość zmiennej
  'energy' (o ile jest wyznaczona).
  Temperatura początkowa jest ustawiona w zmiennej 'T'.

  Zmienne minE i maxE służą do przechowywania energii najlepszego
  i najgorszego rozwiązania, zaakceptowanego w danym kroku (czyli przy
  tej samej temperaturze). Sprawdzając wartość różnicy maxE-minE
  można podejmować decyzję o zakończeniu bądź kontynuowaniu wyżarzania.

  Zmienne są zdefiniowane w pliku SADlg.h.

  ---Algorytm symulowanego wyżarzania---

  Poniższe kroki należy powtarzać, dopóki (maxE-minE)/maxE nie spadnie
  poniżej progu określonego przez stopTolerance.

1. Ustaw licznik prób i licznik zaakceptowanych prób na 0.
2. Oblicz energię E aktualnego rozwiązania.
3. Wyznacz nowe rozwiązanie (np. zamieniając miejscami dwa miasta w trasie).
4. Oblicz energię En nowego rozwiązania.
5. Zaakceptuj nowe rozwiązanie z prawdopodobieństwem 1/(1+exp(dE/T)), gdzie
   (dE = En-E). W przypadku zaakceptowania zwiększ licznik zaakceptowanych prób.
6. Uaktualnij maxE i minE, jeśli jest to konieczne.
7. Zwiększ licznik prob. Jeżeli licznik prób lub licznik zaakceptowanych prób
   osiągnęły maksymalną wartość (maxTrialN, maxAcceptN), idź do kroku 8. W przeciwnym razie wróć do kroku 3.
8. Uaktualnij zawartość zmiennych 'route' i 'energy', tak by opisywały ostatnią zaakceptowaną trasę.
9. Wywołaj funkcję 'Draw', aby uzyskać podgląd aktualnego rozwiązania.
10.Obniż temperaturę.

  {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
	srand(time(NULL));
	double E = 0;
	double En = 0;
	int TrialN = 0;
	int AcceptN = 0;
	int tmproute[NCITIES];



	while ((maxE - minE) / maxE>stopTolerance) {
		E = 0;
		for (int i = 0; i < NCITIES - 1; i++)
		{
			E += sqrt(pow((loc[route[i]][0] - loc[route[i + 1]][0]), 2) + pow((loc[route[i]][1] - loc[route[i + 1]][1]), 2));
		}
		E += sqrt(pow((loc[route[NCITIES - 1]][0] - loc[route[0]][0]), 2) + pow((loc[route[NCITIES - 1]][1] - loc[route[0]][1]), 2));
			int index = rand() % NCITIES;
			int index2 = rand() % NCITIES;
			double temp = route[index];
			route[index] = route[index2];
			route[index2] = temp;

		En = 0;
		for (int i = 0; i < NCITIES - 1; i++)
		{
			En += sqrt(pow((loc[route[i]][0] - loc[route[i + 1]][0]), 2) + pow((loc[route[i]][1] - loc[route[i + 1]][1]), 2));
		}
		En += sqrt(pow((loc[route[NCITIES - 1]][0] - loc[route[0]][0]), 2) + pow((loc[route[NCITIES - 1]][1] - loc[route[0]][1]), 2));
		double prawdopodobienstwo = 1 / (1 + exp((En - E) / T))/5;
		double tmp = fRand(0,1);
		if (En < E) {
			AcceptN++;
		for (int i = 0; i < NCITIES; i++)
			tmproute[i] = route[i];
		}
		if (minE > En)
			minE = En;
		else if (maxE < En)
			maxE = En;
		TrialN++;
		if (TrialN == maxTrialN || AcceptN == maxAcceptN)
			break;
	}
	for (int i = 0; i < NCITIES; i++)
		route[i] = tmproute[i];
	energy = En;
	Draw();
	T = T * 0.7;
}