#include "stdafx.h"
#include "GreedyTSP.h"

#include <math.h>
#include <float.h>

CGreedyTSP::CGreedyTSP(void)
{
	m_pPathGraph = NULL;

	Reset();
}

CGreedyTSP::~CGreedyTSP(void)
{
	Reset();
}

void CGreedyTSP::Reset()
{
	// vector
	m_vecPathData.clear();
	m_vecPathResult.clear();
	m_vecPathAdded.clear();	

	// graph
	if (m_pPathGraph)
	{
		for (int i=0; i<m_nPathCount; i++)
		{
			delete [] m_pPathGraph[i];
		}
		delete [] m_pPathGraph;
	}
	m_pPathGraph = NULL;

	m_nStartIndex = -1;
	m_nPathCount = 0;
	m_dTotalDistance = 0.0;

	m_ptStart.nPosX = -1;
	m_ptStart.nPosY = -1;
}

void CGreedyTSP::SetPathData(const VectorPathData& vecPathData, const SPathData& ptStart)
{
	if (vecPathData.size()<0) return;

	Reset();

	m_nPathCount		= (int)vecPathData.size();
	m_pPathGraph		= new double*[m_nPathCount];

	m_ptStart			= ptStart;

	// path data copy
	m_vecPathData = vecPathData;
	m_vecPathResult.resize(m_nPathCount);
	m_vecPathAdded.resize(m_nPathCount);

	// path graph
	for (int i=0; i<m_nPathCount; i++)
	{
		m_vecPathAdded[i] = false;
		m_pPathGraph[i] = new double [m_nPathCount];
		for (int j=0; j<m_nPathCount; j++)
		{
			if (i==j)
				m_pPathGraph[i][j] = 0.0;
			else
				m_pPathGraph[i][j] = CalculateDistance(m_vecPathData[i], m_vecPathData[j]);
		}
	}

	// path result
	InitPathResult(ptStart);

	m_dTotalDistance = GetTotalDistance();

}

void CGreedyTSP::SetPathData(const VectorPathData& vecPathData, const VectorInteger& vecPathResult)
{
	if (vecPathData.size()<1 || vecPathData.size()!=vecPathResult.size()) return;

	Reset();

	m_nPathCount	= (int)vecPathData.size();
	m_pPathGraph	= new double*[m_nPathCount];

	// path data
	m_vecPathData	= vecPathData;
	m_vecPathResult	= vecPathResult;
	m_vecPathAdded.resize(m_nPathCount);

	// path graph
	for (int i=0; i<m_nPathCount; i++)
	{
		m_vecPathAdded[i] = false;
		m_pPathGraph[i] = new double[m_nPathCount];
		for (int j=0; j<m_nPathCount; j++)
		{
			if (i==j)
				m_pPathGraph[i][j] = 0.0;
			else
				m_pPathGraph[i][j] = CalculateDistance(m_vecPathData[i], m_vecPathData[j]);
		}
	}

	m_dTotalDistance = GetTotalDistance();
}

double CGreedyTSP::CalculateTSP()
{
	if (m_nPathCount<1) return -1.0;

	SortingPathResult();

	return m_dTotalDistance;
}

int CGreedyTSP::GetPathCount() const
{ 
	return m_nPathCount; 
}

int	CGreedyTSP::GetPathResult(int nIndex) const
{
	if (nIndex<0 || nIndex>=m_nPathCount) return -1;
	return m_vecPathResult[nIndex];
}

const SPathData* CGreedyTSP::GetPathData(int nIndex) const
{
	if (nIndex<0 || nIndex>=m_nPathCount) return NULL;
	return &(m_vecPathData[nIndex]);
}

VectorInteger* CGreedyTSP::GetPathResult()
{
	return &m_vecPathResult;
}

VectorPathData* CGreedyTSP::GetPathData()
{
	return &m_vecPathData;
}

double CGreedyTSP::GetPathResult(VectorInteger& vecPathResult)
{
	vecPathResult.resize(m_nPathCount);
	for (int i=0; i<m_nPathCount; i++)
	{
		vecPathResult[i] = m_vecPathResult[i];
	}

	return m_dTotalDistance;
}

double CGreedyTSP::GetTotalDistance()
{
	double distance = 0.0;

	if (m_ptStart.nPosX!=-1 || m_ptStart.nPosX!=-1)
	{
		distance += CalculateDistance(m_ptStart, m_vecPathData[m_vecPathResult[0]]);
	}

	for (int i=1; i<m_nPathCount; i++)
	{
		distance += m_pPathGraph[m_vecPathResult[i-1]][m_vecPathResult[i]];
	}
	return distance;
}

double CGreedyTSP::GetTotalDistance(const VectorInteger& vecPathResult)
{
	int nPathCount = (int)vecPathResult.size();

	double distance = 0.0;
	for (int i=1; i<nPathCount; i++)
	{
		distance += m_pPathGraph[vecPathResult[i-1]][vecPathResult[i]];
	}
	return distance;
}

double CGreedyTSP::CalculateDistance(const POINT& pt1, const POINT &pt2)
{
	double dx = double(pt1.x-pt2.x) / 1000.0;
	double dy = double(pt1.y-pt2.y) / 1000.0;
	return sqrt(dx*dx + dy*dy);
}

double CGreedyTSP::CalculateDistance(const SPathData& pt1, const SPathData &pt2)
{
	double dx = double(pt1.nPosX-pt2.nPosX) / 1000.0;
	double dy = double(pt1.nPosY-pt2.nPosY) / 1000.0;
	return sqrt(dx*dx + dy*dy);
}

double CGreedyTSP::CalculateDistanceX( const POINT& pt1, const POINT &pt2 )
{
	double dx = double(pt1.x-pt2.x) / 1000.0;
	return fabs(dx);
}

double CGreedyTSP::CalculateDistanceX( const SPathData& pt1, const SPathData &pt2 )
{
	double dx = double(pt1.nPosX-pt2.nPosX) / 1000.0;
	return fabs(dx);
}

double CGreedyTSP::CalculateDistanceY( const POINT& pt1, const POINT &pt2 )
{
	double dy = double(pt1.y-pt2.y) / 1000.0;
	return fabs(dy);
}

double CGreedyTSP::CalculateDistanceY( const SPathData& pt1, const SPathData &pt2 )
{
	double dy = double(pt1.nPosY-pt2.nPosY) / 1000.0;
	return fabs(dy);
}

int CGreedyTSP::SelectPath(int nCurIdx)
{
	int nMinIdx		= -1;
	double dTempMin = DBL_MAX;
	for (int i=0; i<m_nPathCount; i++)
	{
		// Ãß°¡µÈ pathÀÎÁö È®ÀÎ.
		if (m_vecPathAdded[i]==true) continue;

		if (dTempMin > m_pPathGraph[nCurIdx][i])
		{
			dTempMin	= m_pPathGraph[nCurIdx][i];
			nMinIdx		= i;
		}
	}

	if (nMinIdx==-1)
	{
		return -1;
	}

	// Ãß°¡‰çÀ½À» ÀúÀå.
	m_vecPathAdded[nMinIdx] = true;

	return nMinIdx;
}

void CGreedyTSP::InitPathResult(const SPathData& ptStart)
{
	if (m_nPathCount<1) return;

	m_nStartIndex		= -1;
	double dMinDist		= DBL_MAX;
	double dTempDist	= 0.0;

	for (int i=0; i<m_nPathCount; i++)
	{
		dTempDist = CalculateDistance(ptStart, m_vecPathData[i]);
		if (dMinDist>dTempDist)
		{
			m_nStartIndex	= i;
			dMinDist		= dTempDist;
		}
	}

	if (m_nStartIndex==-1) 
	{
		return;
	}

	m_vecPathResult[0] = m_nStartIndex;

	// Ãß°¡‰çÀ½À» ÀúÀå.
	m_vecPathAdded[m_nStartIndex] = true;

	for (int i=1; i<m_nPathCount; i++)
	{
		m_vecPathResult[i] = SelectPath(m_vecPathResult[i-1]);
	}
}

BOOL CGreedyTSP::SortingPathResult()
{
	if (m_nPathCount<1) return FALSE;

	int nStartIndex		= -1;
	double dMinDist		= DBL_MAX;
	double dTempDist	= 0.0;

	for (int i=0; i<m_nPathCount; i++)
	{
		dTempDist = CalculateDistance(m_ptStart, m_vecPathData[i]);
		if (dMinDist>dTempDist)
		{
			nStartIndex	= i;
			dMinDist	= dTempDist;
		}
	}

	for (int i=0; i<m_nPathCount; i++)
	{
		if (nStartIndex==m_vecPathResult[i])
		{
			nStartIndex = i;
			break;
		}
	}
	
	VectorInteger	vecPathResult;
	vecPathResult.reserve(m_nPathCount);

	for (int i=nStartIndex; i<m_nPathCount; i++)
	{
		vecPathResult.push_back(m_vecPathResult[i]);
	}

	for (int i=0; i<nStartIndex; i++)
	{
		vecPathResult.push_back(m_vecPathResult[i]);
	}

	m_vecPathResult = vecPathResult;

	return TRUE;
}