// Kurs_LipinDlg.cpp : implementation file

#include "stdafx.h"
#include "Kurs_LipinDlg.h"
#include "math.h"
#include "Setting.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)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CKurs_LipinDlg dialog

CKurs_LipinDlg::CKurs_LipinDlg(CWnd* pParent /*=NULL*/)
: CDialog(CKurs_LipinDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CKurs_LipinDlg)
m_len = _T("");
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CKurs_LipinDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CKurs_LipinDlg)
DDX_Control(pDX, IDC_LIST1, m_list1);
DDX_Control(pDX, IDC_STATIC1, m_label);
DDX_Text(pDX, IDC_STATIC1, m_len);
//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CKurs_LipinDlg, CDialog)
//{{AFX_MSG_MAP(CKurs_LipinDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_WM_LBUTTONDOWN()
ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
ON_BN_CLICKED(IDC_BUTTON4, OnButton4)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CKurs_LipinDlg message handlers

BOOL CKurs_LipinDlg::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

name_city[0] = "С.-Петербург";
name_city[1] = "Псков";
name_city[2] = "Новгород";
name_city[3] = "Смоленск";
name_city[4] = "Тверь";
name_city[5] = "Вологда";
name_city[6] = "Ярославль";
name_city[7] = "Кострома";
name_city[8] = "Москва";
name_city[9] = "Брянск";
name_city[10] = "Калуга";
name_city[11] = "Иваново";
name_city[12] = "Орел";
name_city[13] = "Тула";
name_city[14] = "Владимир";
name_city[15] = "Курск";
name_city[16] = "Рязань";
name_city[17] = "Белгород";
name_city[18] = "Липецк";
name_city[19] = "Н.Новгород";
name_city[20] = "Воронеж";
name_city[21] = "Тамбов";
name_city[22] = "Чебоксары";
name_city[23] = "Саранск";
name_city[24] = "Пенза";
name_city[25] = "Ульяновск";
name_city[26] = "Саратов";
name_city[27] = "Самара";
name_city[28] = "Волгоград";
 
x0=10;y0=50;// смещение карты относительно левого верхнего угла окна
koord[0][0]=x0+225;// Санкт-Петербург
koord[0][1]=y0+54;
koord[1][0]=x0+148; //Псков
koord[1][1]=y0+60;
koord[2][0]=x0+195;  // Новгород
koord[2][1]=y0+92;
koord[3][0]=x0+93;  // Смоленск
koord[3][1]=y0+171;
koord[4][0]=x0+191; //Тверь
koord[4][1]=y0+193;
koord[5][0]=x0+340;  //Вологда
koord[5][1]=y0+200;
koord[6][0]=x0+235;  //Ярославль
koord[6][1]=y0+221;
koord[7][0]=x0+320;//Кострома
koord[7][1]=y0+238;
koord[8][0]=x0+181;//Москва
koord[8][1]=y0+241;
koord[9][0]=x0+76;//Брянск
koord[9][1]=y0+240;
koord[10][0]=x0+133;//Калуга
koord[10][1]=y0+245;
koord[11][0]=x0+256;//Иваново
koord[11][1]=y0+250;
koord[12][0]=x0+88;//Орел
koord[12][1]=y0+275;
koord[13][0]=x0+139;//Тула
koord[13][1]=y0+272;
koord[14][0]=x0+227;//Владимир
koord[14][1]=y0+274;
koord[15][0]=x0+55;//Курск
koord[15][1]=y0+297;
koord[16][0]=x0+176;//Рязань
koord[16][1]=y0+297;
koord[17][0]=x0+29;//Белгород
koord[17][1]=y0+328;
koord[18][0]=x0+121;//Липецк
koord[18][1]=y0+338;
koord[19][0]=x0+276;//Нижний Новгород
koord[19][1]=y0+322;
koord[20][0]=x0+70;//Воронеж
koord[20][1]=y0+370;
koord[21][0]=x0+149;//Тамбов
koord[21][1]=y0+364;
koord[22][0]=x0+307;//Чебоксары
koord[22][1]=y0+373;
koord[23][0]=x0+237;//Саранск
koord[23][1]=y0+388;
koord[24][0]=x0+212;//Пенза
koord[24][1]=y0+420;
koord[25][0]=x0+280;//Ульяновск
koord[25][1]=y0+429;
koord[26][0]=x0+184;//Саратов
koord[26][1]=y0+456;
koord[27][0]=x0+292;//Самара
koord[27][1]=y0+491;
koord[28][0]=x0+91;//Волгоград
koord[28][1]=y0+506;

count_selected=0;
myFont.CreateFont(17,0,0,0,500,false,false,false,0,0,0,0,0,"Courier Cyr");
m_len="Выберите несколько городов.";
m_label.SetFont (&myFont);
UpdateData(false);

int i;

for (int i=0; i < 29; i++)
	flag_select[i]=false;
flag_draw=false;
begin_point = -1;
flag_Bpoint=false;


CStdioFile f1;
f1.Open("table.ini",CFile::modeRead);
  for ( i=0; i < 29; i++)
{
	tableAllCity[i][i]=0;

	CString s1;
	f1.ReadString(s1);
	int j=i+1;
	int k=0;
	while (j<29 && k < s1.GetLength())
	{
		CString s2;
		while (s1[k] == ' ') k++;
		while (s1[k] != ' ') 
		{   
			s2 += s1[k];    k++;
		}
		tableAllCity[j][i]=tableAllCity[i][j]=atoi(s2);
		j++;
	}
}

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

void CKurs_LipinDlg::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 CKurs_LipinDlg::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
{
CClientDC pDC(this);
CDC temp;
CBitmap bmp;
bmp.LoadBitmap(IDB_BITMAP1);
temp.CreateCompatibleDC (&pDC);
temp.SelectObject(bmp);

for (int j=0;j<29;j++)
{
	int x=koord[j][0]-x0;
	int y=koord[j][1]-y0;

	if (flag_select[j])
		temp.SelectStockObject (BLACK_BRUSH);
	else
		temp.SelectStockObject (WHITE_BRUSH);

	temp.Ellipse(x-4,y-4,x+4,y+4);
	temp.TextOut( x - 15,y-20, name_city[ j ] );
}

if (begin_point>=0)
{
	int x=koord[begin_point][0]-x0;
	int y=koord[begin_point][1]-y0;
	CBrush br (RGB(255,0,0));
	temp.SelectObject (&br);
	temp.Ellipse(x-4,y-4,x+4,y+4);

}

if (flag_draw)
{
	for (int i = 0; i < n; i++)
	{
		int x1 = koord[sel_city[min_path[i]-1]][0];
		int x2 = koord[sel_city[min_path[i+1]-1]][0];
		int y1 = koord[sel_city[min_path[i]-1]][1];
		int y2 = koord[sel_city[min_path[i+1]-1]][1];

		temp.MoveTo(x1-x0,y1-y0);
		temp.LineTo(x2-x0,y2-y0);
	}

	CString s1;

	int i;
	m_list1.ResetContent();
	for (i=0;i < n; i++)
	{
		s1=name_city[sel_city[min_path[i]-1]];
		s1+=" - "+name_city[sel_city[min_path[i+1]-1]];
		CString s2;
		s2.Format("%d",table[min_path[i]-1][min_path[i+1]-1]);
		s1+=" ->"+s2;
		m_list1.AddString(s1);
	}
	m_len.Format("Длина пути:\n%d км",min_path[n+1]);
	for (i=0;i < n; i++)
	{
		if (i % 2 != 0) m_list1.SetSel(i);
	}
}
else
{
	m_len="Выберите несколько городов.";
}
UpdateData(false);

pDC.BitBlt(x0,y0,638,638,&temp,0,0,SRCCOPY);

CDialog::OnPaint();
}
}

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

void CKurs_LipinDlg::OnLButtonDown(UINT nFlags, CPoint point) 
{
for (int i=0;i<29;i++)
{
int x=point.x-koord[i][0],y=point.y-koord[i][1];
if((x*x+y*y)<=7*7)
{
if (flag_Bpoint)
{
	begin_point=i;
	flag_Bpoint=false;
	if (flag_select[i]==false) count_selected++;

	flag_select[i]=true;
	flag_draw=false;
	Invalidate(false);
}
else
{
	if (flag_select[i]==false) count_selected++;
	else 
	{
	count_selected--;
	if (i == begin_point) 
	{
	begin_point=-1;
	}
	}
	flag_select[i]=!flag_select[i];
	flag_draw=false;
	Invalidate(false);
}
}
}
CDialog::OnLButtonDown(nFlags, point);
}

void CKurs_LipinDlg::OnButton1() 
{
m_list1.ResetContent();

for (int i=0; i < 29; i++)
flag_select[i]=true;
/*flag_select[6]=true;
flag_select[8]=true;
flag_select[12]=true;
flag_select[13]=true;
flag_select[15]=true;
flag_select[18]=true;
flag_select[19]=true;
flag_select[20]=true;
flag_select[21]=true;
flag_select[26]=true;
flag_select[27]=true;
flag_select[28]=true;
flag_select[24]=true;*/
count_selected=29;
flag_draw=false;
flag_Bpoint = false;
begin_point = -1;


Invalidate(false);

}

void CKurs_LipinDlg::OnButton2() 
{
m_list1.ResetContent();

for (int i=0; i < 29; i++)
flag_select[i]=false;
flag_Bpoint = false;
begin_point = -1;
count_selected = 0;
flag_draw = false;
Invalidate (false);

}

void CKurs_LipinDlg::OnOK() 
{
	int i;
m_list1.ResetContent();

n = count_selected;

if (n <=1) 
{
MessageBox ("Выберите не менее 2 городов.", "Warrning!");
return;
}
sel_city= new int[n];
int count = 0;
for (int i=0; i < 29; i++)
if (flag_select[i]) sel_city[count++] = i;

for (i=0; i < n; i++)// ставим исходный город на первое место в массиве
if (sel_city[i] == begin_point)
{
	int tmp = sel_city[0];
	sel_city[0] = sel_city[i];
	sel_city[i] = tmp;
}

table = new int *[n];
for (i=0; i<n; i++)
table[i] = new int [n];

for (i=0; i<n; i++)
  for (int j = 0; j < n; j++)
  {
if (i>=j) 
{
table[i][j]=table[j][i]=tableAllCity[sel_city[i]][sel_city[j]];
}
  }

bool *flag = new bool[n];      //  заполнение признаков посещения городов
flag[0] = true;
for (i=1; i < n; i++) flag[i]=false;

unsigned int *cur_path = new unsigned int[n+2];
min_path = new unsigned int[n+2];

//  заполнение матриц минимального пути и текущего пути
min_path[0] = min_path[n]=1;    min_path[n+1]=0;
for (i=1; i < n; i++)
{
min_path[i]=i+1;  min_path[n+1]+=table[i-1][i];
cur_path[i]=0;
}  min_path[n+1] += table [min_path[n-1]-1] [min_path[n]-1 ];

cur_path[n+1] =0;
cur_path[0] = cur_path[n] = 1;

m_len="Подождите:\nидут вычисления...";
UpdateData(false);

recursiv (flag,cur_path, 1);    // вызов рекурсивной функции*/

flag_draw = true;
Invalidate(false);

}

void CKurs_LipinDlg::recursiv (bool flag[],unsigned int cur_path[],int j)   
{

for (int i = 0; i < n; i++)      // для каждой точки
{
if (flag[i] == false)        // где мы еще не были
{
flag[i] = true;          // переходим в нее,
cur_path[j] = i+1;       // вычисляя длину пройденного пути
cur_path[n+1] += table [cur_path[j-1]-1] [cur_path[j]-1];

  //  ***   если длина текущего пути меньше минимальной   ***
  if (cur_path[n+1] < min_path[n+1])
// рассматриваем новую точку, если она не конечная
if (j < n-1) recursiv (flag, cur_path, j+1);
else
{   // или вычисляем длинув сего пути и ...
cur_path[n+1] += table [cur_path[n-1]-1] [cur_path[n]-1];

// ...  сравниваем с минимальным
if (cur_path[n+1] < min_path[n+1])
{
for (int k=0; k <= n+1; k++)
   min_path[k] = cur_path[k];

}
cur_path[n+1] -= table [cur_path[n-1]-1] [cur_path[n]-1];
}
flag[i]=false;
cur_path[n+1] -= table [cur_path[j-1]-1] [cur_path[j]-1];
}
}
return;
}

void CKurs_LipinDlg::OnButton3() 
{
m_list1.ResetContent();
flag_Bpoint=true;
Invalidate(false);
}

void CKurs_LipinDlg::OnButton4() 
{
CSetting dlg1(this);
dlg1.DoModal();

}