UNGPathFinder.cpp

// UNGPathFinder.cpp : implementation file
//

#include "stdafx.h"
#include "MapEditor.h"
#include "UNGPathFinder.h"

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

/////////////////////////////////////////////////////////////////////////////
// CUNGPathFinder

CUNGPathFinder::CUNGPathFinder()
{
	lpReportListBegin = lpReportListEnd = NULL;
}

CUNGPathFinder::~CUNGPathFinder()
{
	// Destroy all TEIR and ADJ records
	if(lpReportListBegin != NULL)
		DestroyAdj(lpReportListBegin);
}

/////////////////////////////////////////////////////////////////////////////
// CUNGPathFinder message handlers

void CUNGPathFinder::InitPathFinder(LPMAP pMap)
{	
	lpMap = pMap;
	lpTeirListBegin = lpTeirListEnd = NULL;
	lpFFIncidenceIndex = NULL;
	lpTHCurrent = NULL;
	nTHBuildingNumber = 0;
		if(lpReportListBegin != NULL)
		{
			DestroyAdj(lpReportListBegin);
			lpReportListBegin = lpReportListEnd = NULL;
		}
}

/////////////////////////////////////////////////////////////////////////////
//															Service
/////////////////////////////////////////////////////////////////////////////

void CUNGPathFinder::AddAdjToTeir(LPADJSTATION lpAdjStation, LPTEIRSTHOLDER lpTH)
{
	if(lpTH != NULL && lpAdjStation != NULL)	//	if Teir and AdjStation Exists
	{
		// We will add it to the teir
		if(lpTH->lpFstAdjStation == NULL)	// The List is empty
			lpTH->lpFstAdjStation = lpTH->lpLstAdjStation = lpAdjStation;
		else	// We have some existing records
		{
			// And we will update the pointers
			lpTH->lpLstAdjStation->pNextObject = lpAdjStation;
			lpAdjStation->pPrevObject = lpTH->lpLstAdjStation;
			lpTH->lpLstAdjStation = lpAdjStation;
		}
	}
}

BOOL CUNGPathFinder::AddTeirRecord(LPTEIRSTHOLDER lpTH)
{
	if(lpTH != NULL)	// It is exists
	{
		if(lpTeirListBegin == NULL)	// No teirs
			lpTeirListBegin = lpTeirListEnd = lpTH;
		else	// If we have some
		{
			lpTeirListEnd->pNextObject = lpTH;
			lpTH->pPrevObject = lpTeirListEnd;
			lpTeirListEnd = lpTH;
		}
		lpTH->nTeir = (++nTHBuildingNumber);
		return TRUE;	
	}
	return FALSE;
}

void CUNGPathFinder::AddAdjToReport(LPADJSTATION lpAdj)
{
	LPADJSTATION lpCurAdj;
	if((lpCurAdj = CreateAdjRecord()) == NULL)
		ASSERT(FALSE);
	//else (if new worked)
		lpCurAdj->dwLabel = lpAdj->dwLabel;
		lpCurAdj->lpStation = lpAdj->lpStation;
	// Then we will add it
		if(lpReportListBegin == NULL)	// Create the list
			lpReportListBegin = lpReportListEnd	= lpCurAdj;
		else
		{	
			lpReportListEnd->pNextObject = lpCurAdj;
			lpCurAdj->pPrevObject = lpReportListEnd;
			lpReportListEnd = lpCurAdj;
		}	
}

// Find a minimal temp label and consider it as PERMANENT
LPADJSTATION CUNGPathFinder::UpdateTempLabels()
{
	LPTEIRSTHOLDER lpTH = lpTeirListBegin;
	LPADJSTATION lpAdj;
	LPADJSTATION lpAdjFound = NULL;
	DWORD	dwMinimalTime;	
	BOOL bInitDone = FALSE;	// We need to get the initial value somewhere
// Loop thru teirs
	if(lpTH != NULL)	// We have some teirs
	{
		// Init MinimalTime
		while(lpTH != NULL)
		{
			lpAdj = lpTH->lpFstAdjStation;
			while(lpAdj != NULL)	// We have some adj entries
			{
				if(lpAdj->bTemp == FALSE)
				{
					// we've found  a station with the temp label
					// If the time is not initialize
					if(!bInitDone)
					{
						dwMinimalTime = lpAdj->dwLabel;
						bInitDone = TRUE;
					}
					// Let's compare
					if(lpAdj->dwLabel <= dwMinimalTime)
						lpAdjFound = lpAdj;
				}
				lpAdj = lpAdj->pNextObject;
			}
		lpTH = lpTH->pNextObject;
		}
	}
	if(lpAdjFound != NULL)	//we found the station 
		lpAdjFound->bTemp = TRUE;

	return lpAdjFound;
}

void CUNGPathFinder::HighLightWay(LPADJSTATION lpAdjEndPoint)
{
	LPADJSTATION lpAdj;
	LPTEIRSTHOLDER lpTH;
	LPINCIDENCE lpCurrentInc;
	lpTH = GetTeirByStation(lpAdjEndPoint->lpStation, &lpAdj);
	LPADJSTATION lpPrevAdj;
	// Add the start point
	while(lpTH != NULL)
	{
		lpPrevAdj = lpTH->lpFstAdjStation;
		while(lpPrevAdj != NULL)
		{
			// If they are incident
			if((lpCurrentInc = IsConnectionExists(lpAdjEndPoint->lpStation, lpPrevAdj->lpStation)) != NULL)
			{
				// If Deikstra was right
				if(lpPrevAdj->dwLabel == (lpAdjEndPoint->dwLabel - TransformTime(lpCurrentInc)))
				{
				// Highlight the station
					lpPrevAdj->lpStation->bHighlight = TRUE;
				// Add to the report list
					AddAdjToReport(lpAdjEndPoint);				
					lpAdjEndPoint = lpPrevAdj;
				}
			}
			lpPrevAdj = lpPrevAdj->pNextObject;
		}
		lpTH = lpTH->pPrevObject;
	}
	AddAdjToReport(lpAdjEndPoint);	// Add the first station
}

DWORD CUNGPathFinder::AddTime(DWORD dwFirst, DWORD dwSecond)
{
	return 0;
}

/////////////////////////////////////////////////////////////////////////////
//															Creation
/////////////////////////////////////////////////////////////////////////////

LPADJSTATION CUNGPathFinder::CreateAdjRecord()
{
	LPADJSTATION lpAdjStation;
		if((lpAdjStation = new(ADJSTATION)) == NULL)
			return NULL;	// Couldnt create
	// New worked
		lpAdjStation->dwLabel = 0;
		lpAdjStation->bTemp = FALSE;
		lpAdjStation->lpStation = NULL;
		lpAdjStation->pNextObject = lpAdjStation->pPrevObject = NULL;
	return lpAdjStation;
}

LPTEIRSTHOLDER CUNGPathFinder::CreateTeirRecord()
{
	LPTEIRSTHOLDER lpBldTeir;
		if((lpBldTeir = new(TEIRSTHOLDER)) == NULL)
			return NULL;
	// New Worked
		lpBldTeir->lpFstAdjStation = lpBldTeir->lpLstAdjStation = NULL;
		lpBldTeir->nTeir = 0;
		lpBldTeir->pNextObject = lpBldTeir->pPrevObject = NULL;
	return lpBldTeir;
}

/////////////////////////////////////////////////////////////////////////////
//															Destruction
/////////////////////////////////////////////////////////////////////////////
void CUNGPathFinder::DestroyAdj(LPADJSTATION lpAdjStation)
{
	if(lpAdjStation->pNextObject != NULL)	// If we have the next record we will
		DestroyAdj(lpAdjStation->pNextObject); // Destroy it at first
	delete(lpAdjStation);
}

void CUNGPathFinder::DestroyTeir(LPTEIRSTHOLDER lpTH)
{
	if(lpTH->pNextObject != NULL)		// If we have the next record we will
		DestroyTeir(lpTH->pNextObject);	// Destroy it at first
	if(lpTH->lpFstAdjStation != NULL)	// Destroy AdjRecords if exist
		DestroyAdj(lpTH->lpFstAdjStation);
	delete(lpTH);
}

BOOL CUNGPathFinder::DestroyTeirs()
{
	if(lpTeirListBegin != NULL)	// We have teirs
		DestroyTeir(lpTeirListBegin);
	lpTeirListBegin = lpTeirListEnd = NULL;	// Null the pointers
	nTHBuildingNumber = 0;
	return TRUE;
}

/////////////////////////////////////////////////////////////////////////////
//															Search
/////////////////////////////////////////////////////////////////////////////

LPINCIDENCE CUNGPathFinder::IsConnectionExists(LPSTATION lpStationA, LPSTATION lpStationB)
{
	LPINCIDENCE lpIncLocalVar = lpMap->pIncidence;
		while(lpIncLocalVar != NULL)
		{
			if(((lpIncLocalVar->lpAlpha == lpStationA) && (lpIncLocalVar->lpBeta == lpStationB)) ||
				 ((lpIncLocalVar->lpAlpha == lpStationB) && (lpIncLocalVar->lpBeta == lpStationA)))	
				 return lpIncLocalVar;
			lpIncLocalVar = lpIncLocalVar->pNextEntry;
		}
	return NULL;
}

LPINCIDENCE CUNGPathFinder::FindFirstIncidence(LPSTATION lpStation)
{
	lpFFIncidenceIndex = lpMap->pIncidence;
		if(lpFFIncidenceIndex != NULL)
			lpFFIncidenceIndex = SearchIncidence(lpFFIncidenceIndex, lpStation);
	return lpFFIncidenceIndex;
}

LPINCIDENCE CUNGPathFinder::FindNextIncidence(LPSTATION lpStation)
{
	LPINCIDENCE lpLocalIncVar = lpFFIncidenceIndex->pNextEntry;
		if(lpLocalIncVar != NULL)
		{
			lpLocalIncVar = SearchIncidence(lpFFIncidenceIndex->pNextEntry, lpStation);
			lpFFIncidenceIndex = lpLocalIncVar;
		}
	return lpLocalIncVar;
	
}

LPINCIDENCE CUNGPathFinder::SearchIncidence(LPINCIDENCE lpCurrentInc, LPSTATION lpStation)
{
	if(lpStation != NULL)	// Current pointers are not NULL
	{
		LPINCIDENCE lpLocalIncVar = lpCurrentInc;
		while(lpLocalIncVar != NULL)
		{
			if((lpLocalIncVar->lpAlpha == lpStation) ||
				 (lpLocalIncVar->lpBeta == lpStation))
			return lpLocalIncVar;
			lpLocalIncVar = lpLocalIncVar->pNextEntry;
		}
	}
	return NULL;
}

LPTEIRSTHOLDER CUNGPathFinder::GetTeirByStation(LPSTATION lpStation, LPADJSTATION *lppAdj)
{
	LPTEIRSTHOLDER lpTH = lpTeirListBegin;
	LPADJSTATION	lpAdj;
	*lppAdj = NULL;
	if(lpTH != NULL)	// We have some teirs
	{
		while(lpTH != NULL)
		{
			lpAdj = lpTH->lpFstAdjStation;
			while(lpAdj != NULL)	// We have some adj entries
			{
				if(lpAdj->lpStation == lpStation)
				{
					*lppAdj = lpAdj;
					return lpTH;	// Oh yeah, we did it
				}
				lpAdj = lpAdj->pNextObject;
			}
		lpTH = lpTH->pNextObject;
		}
	}
	return lpTH;
}

LPSTATION CUNGPathFinder::GetOppositeStation(LPINCIDENCE lpIncidence, LPSTATION lpStation)
{
	if(lpIncidence != NULL)
	{
		if(lpIncidence->lpAlpha == lpStation)
			return lpIncidence->lpBeta;
		return lpIncidence->lpAlpha;
	}
	return NULL;
}

DWORD CUNGPathFinder::TransformTime(LPINCIDENCE lpIncidence)
{
	WORD wViceVersaTime = 0;
	DWORD dwTransformed = 0;
	// Get the route time	
	if(lpIncidence->wRouteTime != 0)
	{
	// Exchange Two Values
	BYTE bTimeMin = LOBYTE(lpIncidence->wRouteTime);
	BYTE bTimeSec = (HIBYTE(lpIncidence->wRouteTime) & 0x3F);

	wViceVersaTime = MAKEWORD(bTimeSec, bTimeMin);	
		return(dwTransformed = (DWORD)wViceVersaTime);
	}
	return 0;
}

/////////////////////////////////////////////////////////////////////////////
//															Search
/////////////////////////////////////////////////////////////////////////////
// Here is the main subroutine in this program
int CUNGPathFinder::FindPath(LPSTATION lpAlpha, LPSTATION lpBeta)
{
	// Create Teir 0 and insert there the Alpha station
	// With the permanent label 0;
		// CurrentTeir is 0;
	if((lpTHCurrent = CreateTeirRecord()) == NULL)
		return PF_ERROR;	// We couldnt create a record;
		AddTeirRecord(lpTHCurrent);
	// New worked and we can Insert Alpha to the first teir
	//	At first lets create a structure for it
	LPADJSTATION lpAdjAlpha;
	if((lpAdjAlpha = CreateAdjRecord()) == NULL)
		return PF_ERROR;	// We couldnt create a record;
	// Fill in the information
	lpAdjAlpha->bTemp = TRUE;	// Label is permanent
	lpAdjAlpha->lpStation = lpAlpha;
	// Lets add it to the first teir;
	AddAdjToTeir(lpAdjAlpha, lpTHCurrent);
		
	// Now lets create the second teir and search incidence Station
	// for the Alpha station
	if((lpTHCurrent = CreateTeirRecord()) == NULL)
		return PF_ERROR;	// We couldnt create a record;
		AddTeirRecord(lpTHCurrent);
	int iCResult = 0;
	LPADJSTATION lpLocalAdj = NULL;
	while((iCResult = CreateAndAddTemp(lpAdjAlpha, lpTHCurrent)) != PF_NOTFOUND)
	{
		// Lets found a station with the minimal TEMPORARY label
		if((lpAdjAlpha = UpdateTempLabels()) != NULL)	//We cannot add anymore
		{
			if(lpAdjAlpha->lpStation == lpBeta)	// We found our last station
			{
				HighLightWay(lpAdjAlpha);	// We will highlight the way
					DestroyTeirs();
				return PF_ALLOK;
			}

			// It the station already exists somewhere in the teirs
			if((lpTHCurrent = GetTeirByStation(lpAdjAlpha->lpStation, &lpLocalAdj)) != NULL)
				if(lpTHCurrent->pNextObject == NULL) // it is the last
				{
					// Create the new teir
					if((lpTHCurrent = CreateTeirRecord()) == NULL)
						return PF_ERROR;	// We couldnt create a record;
					AddTeirRecord(lpTHCurrent);
				}
				else
					lpTHCurrent = lpTHCurrent->pNextObject;
		}
		else
		{
			// We couldnt find a way
					DestroyTeirs();
				return PF_NOTFOUND;
					
		}
	}
		DestroyTeirs(); // Destroy Teirs and Exit
	return PF_NOTFOUND;

}

// 
int CUNGPathFinder::CreateAndAddTemp(LPADJSTATION lpAdj, LPTEIRSTHOLDER lpTH)
{
	int iExistsCount = 0;
	int iIterateCount = 0;
	// Find the first Incident Station
	if(lpAdj->lpStation != NULL)	// If it is exists
	{
		LPINCIDENCE lpLocalIncVar;
		if((lpLocalIncVar = FindFirstIncidence(lpAdj->lpStation)) != NULL)
		{
			// We found Incidence
			if(ProcessStation(lpLocalIncVar, lpAdj, lpTH) == PF_ALREADYEXISTS)
				iExistsCount++;
			iIterateCount++;
			// Lets look forward..
			while ((lpLocalIncVar = FindNextIncidence(lpAdj->lpStation)) != NULL)
			{
				if(ProcessStation(lpLocalIncVar, lpAdj, lpTH) == PF_ALREADYEXISTS)
					iExistsCount++;
					iIterateCount++;
			}
		}
	}
	if(iIterateCount == 0)	// No Iterations
		return PF_NOTFOUND;
	if(iExistsCount == iIterateCount)	// if we couldnt create anything
		return PF_ALREADYEXISTS;
	return PF_ALLOK;
}

int CUNGPathFinder::ProcessStation(LPINCIDENCE lpCurInc, LPADJSTATION lpAdj, LPTEIRSTHOLDER lpTH)
{
	LPSTATION lpConnectedSt = GetOppositeStation(lpCurInc, lpAdj->lpStation);
	// We found it let's check if it is already exists
	LPTEIRSTHOLDER lpCurTH;
	LPADJSTATION lpCurAdjSt;
		if((lpCurTH = GetTeirByStation(lpConnectedSt, &lpCurAdjSt)) == NULL)
		{
			// this station is the first-chance
			if((lpCurAdjSt = CreateAdjRecord()) == NULL)
				return PF_ERROR;
			// We have the new Adj Record
			// Lets's add our station to the AdjRecord
			lpCurAdjSt->lpStation = lpConnectedSt;
			AddAdjToTeir(lpCurAdjSt, lpTH); // Add the station to the teir
			// Insert the new label
			InsertLabel(lpCurAdjSt, (lpAdj->dwLabel + TransformTime(lpCurInc)));
		}
		else	// the connected station exists
		{
			if(!lpCurAdjSt->bTemp)	// If the label is TEMPORARY
			{
				InsertLabel(lpCurAdjSt, (lpAdj->dwLabel + TransformTime(lpCurInc)));
				return PF_ALREADYEXISTS;
			// If it is PERMANENT we will just exit
			}
		}
	return PF_ALLOK;
}

// Inserts the new label
void CUNGPathFinder::InsertLabel(LPADJSTATION lpAdj, DWORD dwNewTime)
{
	// At first we will get the last time;
	DWORD dwLastTime;
	// The lets compare like Deikstra did
	if((dwLastTime = lpAdj->dwLabel) != 0)	// The station already has a label
	{
		lpAdj->dwLabel = min(dwNewTime, dwLastTime);
	}
	else
	  lpAdj->dwLabel = dwNewTime;
}