// SADlg.cpp : implementation file
//

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

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// 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, L"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)));

	alpha = 1.0;
	beta = 0.5;
	rho = 0.5;

	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                 }
{************************************/
BOOL CSADlg::InitializeMap()
{

	int i, j, k;

	int stop;

	CFile f;
	if (!f.Open(L"tsp-c.dat", CFile::modeRead | CFile::shareDenyWrite))
	{
		MessageBox(L"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);
	 };

	 distance = 0;

	for (i = 0; i < NCITIES; i++)
		for (j = 0; j < NCITIES; j++)
			intens[i][j] = 0.01;

	for (i = 0; i < NCITIES; i++)
		for (j = 1; j < NCITIES; j++)
			ants[i][j] = -1;

	for (i = 0; i < NCITIES; i++)
		ants[i][0] = 0;

	for (i = 0; i < NCITIES; i++)
		for (int j = 0; j < NCITIES; j++)
		{
			delta[i][j] = 0.0;

			double d = Dst(i,j);

			if (d == 0.0)
				d = -1;

			visibility[i][j] = 1/d;
		}

	return TRUE;
}

double CSADlg::Dst(int i, int j)
{
	double xi = loc[i][0];
	double yi = loc[i][1];
	double xj = loc[j][0];
	double yj = loc[j][1];

	double res = sqrt((xi-xj)*(xi-xj) + (yi-yj)*(yi-yj));

	return res;
}

bool CSADlg::IsCityInAnt(int city, int ant)
{
	bool bRes = false;

	for (int i = 0; i < NCITIES; i++)
	{
		if (ants[ant][i] == city)
		{
			bRes = true;
			break;
		}
	}

	return bRes;
}


/**************************************************************************}
{RYSOWANIE AKTUALNEJ TRASY, WYSWIETLANIE JEJ DŁUGOŚCI                      }
{**************************************************************************/
void CSADlg::Draw()
{

	int i, x, y, x1, y1;
	char s[10];
	CString sEn = "Długość trasy: ";

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

	if (distance == 0.0)
	{
		sEn = "Wyznacz długość aktualnej trasy!";
	}
	else
	{
		_gcvt_s(s, sizeof(s), distance, 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();

	/*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}
	{TU WSTAWIC ALGORYTM MRÓWKOWY                                              }
	{!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}

	Z pliku została wczytana mapa miast. Jest ich NCITIES.

	Liczba mrówek to NANTS. Każda mrówka jest reprezentowana przez jeden wiersz w tablicy ants[NANTS][NCITIES].
	Każdy wiersz ma zawierać indeksy miast, odwiedzanych kolejno przez mrówkę.
	Każda mrówka startuje z miasta 0, dlatego pierwszy element wiersza to 0,
	a pozostałe elementy wiersza są początkowo ustawione na -1.

	Tablica intens[NCITIES][NCITIES] służy do przechowywania intensywności "feromonu";
	intens[i][j] oznacza siłę "zapachu" połączenia między miastami i oraz j.
	Początkowo wszystkie połączenia mają przypisaną tę samą wagę.

	W tablicy visibility[NCITIES][NCITIES] przechowywane są wartości opisujące, jak dobrze "widać" miasto j z miasta i.
	Element visibility(i,j) zawiera wartość	1/d(i,j), gdzie d(i,j) jest odległością między miastami i oraz j.

	Tablica delta[NCITIES][NCITIES], wypełniona na początku zerami, będzie służyć do odnotowywania przejść mrówek
	pomiędzy poszczególnymi miastami.

	Wartości alpha, beta i rho używane w algorytmie są już ustawione.

	Procedura 'Draw' wyświetla trasę zawartą w 'route' i wartość zmiennej
    'distance' (o ile jest wyznaczona).

	Funkcja Dst(i,j) oblicza odległość między miastami i oraz j.

	Funkcja IsCityInAnt(city, ant) zwraca 'true', gdy miasto 'city' znajduje się już w trasie mrówki 'ant'.

	Zmienne są zdefiniowane w pliku SADlg.h.


	---Algorytm mrówkowy---



	-------------------------------------------------------------------------------------
	WAŻNE! Atrakcyjność przejścia z miasta i-tego do miasta j-tego wyznaczamy następująco:
	(intens[i][j]^alpha * visibility[i][j]^beta)
	-------------------------------------------------------------------------------------

	Podane kroki powtórz 100 razy.
	1. Poniższą czynność wykonaj (NCITIES-1) razy.
	   Dla każdej mrówki wyznacz kolejne miasto w trasie:
	   - oblicz sumę S atrakcyjności przejść do wszystkich możliwych miast
	   - przejdź do kolejnego miasta z prawdopodobieństwem równym
			0, jeśli mrówka już była w tym mieście,
			(atrakcyjność_przejścia / S)  w przeciwnym razie.
	2. Dla każdej k-tej mrówki wyznacz długość trasy dist(k).
	3. Przepisz najkrótszą trasę do 'route', jej długość do 'distance'
	   i wywołaj 'Draw'.
    4. Wypełnij tablicę 'delta':
	   dla każdej k-tej mrówki, jeśli w jej trasie jest przejście z
	   miasta 'i' do miasta 'j', to
		 delta[i][j] += a/dist(k);
       gdzie a = 10 dla najlepszej mrówki, a = 1 dla pozostałych,
    5. Uaktualnij tablicę 'intens' (po wszystkich i,j):
	    intens[i][j] = rho*intens[i][j] + delta[i][j];
	6. Wyzeruj tablicę 'delta'.
	7. Wyczyść trasę każdej mrówki (wszystkie elementy z wyjątkiem
	   pierwszego ustaw na -1).

   {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
	double S;
	double dummy_rand;
	for (int loop = 0; loop < 100; loop++) {
		//1
		for (int i = 0; i < NCITIES - 1; i++) {
			for (int j = 0; j < NANTS; j++) {
				S = 0;
				for (int h = 0; h < NCITIES; h++) {
					S += pow(intens[h][i], alpha) * pow(visibility[h][i] , beta);
				}

				//przejscie
				dummy_rand = (double)rand() / RAND_MAX;
				for (int h = 0; h < NCITIES; h++) {
					if (IsCityInAnt(h, j) == false) {
						if (dummy_rand < (intens[i][h] / S)){
							ants[j][i + 1] = h;
							break;
						}
					}
				}

			}

		}

		//2
		double min_dist = MAXINT;
		int min_ant = 0;
		double ant_dist[NANTS];

		for (int k = 0; k < NANTS; k++) {
			ant_dist[k] = 0;
			for (int i = 0; i < NCITIES-1; i++) {
				ant_dist[k] += Dst(ants[k][i], ants[k][i + 1]);
			}
			if (ant_dist[k] < min_dist) {
				min_ant = k;
				min_dist = ant_dist[k];
			}

		}

		//3
		distance = min_dist;
		for (int i = 0; i < NCITIES; i++) {
			route[i] = ants[min_ant][i];
		}
		Draw();


		//4
		for (int j = 0; j < NANTS; j++) {
			for (int k = 1; k < NCITIES-1; k++) {
				if (j == min_ant) {
					delta[ants[j][k]][ants[j][k + 1]] += 10.0/ant_dist[j];
				}
				else {
					delta[ants[j][k]][ants[j][k + 1]] += 1.0/ant_dist[j];
				}
			}
		}

		//5
		for (int i = 0; i < NCITIES; i++) {
			for (int j = 0; j < NCITIES; j++) {
				intens[i][j] = rho*intens[i][j] + delta[i][j];
			}
		}

		//6
		for (int i = 0; i < NCITIES; i++) {
			for (int j = 0; j < NCITIES; j++) {
				delta[i][j] = 0;
			}
		}
		//7
		for (int i = 0; i < NANTS; i++) {
			ants[i][0] = 0;
			for (int j = 0; j < NCITIES; j++) {
				ants[i][j] = -1;
			}
		}
	}





}