/**------------------------------------------------------------------------
 * @file
 *
 * Copyright 2001 by the University of Toronto (UT).
 *
 *                       All Rights Reserved
 * 
 * Permission to copy and modify this software and its documentation 
 * only for internal use in your organization is hereby granted, 
 * provided that this notice is retained thereon and on all copies.  
 * UT makes no representations as to the suitability and operability 
 * of this software for any purpose.  It is provided "as is" without 
 * express or implied warranty.
 *
 * UT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
 * SHALL UT BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA
 * OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 *
 * No other rights, including for example, the right to redistribute 
 * this software and its documentation or the right to prepare 
 * derivative works, are granted unless specifically provided in a 
 * separate license agreement.
 *
 * Author: Diego Macrini
 * 
 * $Log: Matching.cpp,v $
 * Revision 1.6  2002/06/18 00:39:56  dmac
 * Improved display of SG skeleton.
 *
 * Revision 1.5  2002/06/13 21:50:06  dmac
 * Cmd line args added.
 *
 * Revision 1.4  2002/06/10 18:43:19  dmac
 * More cmd line params added.
 *
 * Revision 1.3  2002/05/17 00:26:39  dmac
 * Modification to make the code work with any kind of DAG.
 *
 * Revision 1.2  2002/03/12 18:23:07  dmac
 * ShowResults() was splited into SaveResults() and a new ShowResults()
 *
 * Revision 1.1.1.1  2002/03/10 07:38:08  dmac
 * Imported sources
 *
 *
 *-----------------------------------------------------------------------*/
#include "ShapeMatcher.h"
#include "Matching.h"
#include "viewpoints.h"
#include "ImgPreprocess.h"

#ifndef WIN32
#include <unistd.h>
#include <getopt.h>
#include <signal.h>
#include <sys/wait.h>
#endif //no WIN32

using namespace std;

//#define TIMEOUT (60 * 3)

fstream g_logFile;	//!< Global log stream

#ifndef WIN32
pid_t	g_pid;		//!< Global child process ID
int g_nTimeout;   //!< Global timeout, used only to log the timeout val.
#endif

// Function definitions

/*!
	@brief Occludes part of the given graph

	@param dMaxOcclusionRate Maximum percentage of occlusion allowed

	@todo The DeleteSubDAG() function does not work for DAGs with loops.
*/
double OccludeDAG(DAGPtr& ptrDag, double dMaxOcclusionRate)
{
	leda_node v;
	double dOcclusionRate = 0;
	double nNodeMass, nTotalMass = ptrDag->GetNodeCount(); //must be double for division
	int i = 0;

	if (nTotalMass <= 3)
		return 0;
	
	do {
		v = ptrDag->choose_node();
		ASSERT(v != nil);
		
		// ptrDag->GetNodeMass(v) is really cummulative mass now
		nNodeMass = ptrDag->GetTransClosMat().RowSum(ptrDag->GetNodeDFSIndex(v));
		dOcclusionRate = nNodeMass / nTotalMass;
		
	} while (dOcclusionRate > dMaxOcclusionRate && i++ < nTotalMass * 2);

	if (dOcclusionRate > dMaxOcclusionRate)
		return 0;

	ptrDag->DeleteSubDAG(v);
	ptrDag->ComputeDerivedValues();
		
	return dOcclusionRate;
}

#ifndef WIN32
int AsyncIndexDAG(const DAG* pQueryDag, DAGDatabase& dagDB, MATCHINFO& info, STATINFO& idxSt)
{
	int* pnCount = new int(0);
	
	if ((g_pid = fork()) != 0)
	{
		int status;	
		waitpid(g_pid, &status, 0);

		if (!(WIFEXITED(status)))
		{
			cerr << "\nSegmentation fault when indexing " << pQueryDag->GetDAGLbl() << endl;
			*pnCount = 0;
		}
			
		int count = *pnCount;
		delete pnCount;
		DBG_MSG1("At parent", count)
		// Parent process is done, function returns normaly
		return count;
	}
	
	// Child process starts here
	*pnCount = dagDB.GetSimilar(*pQueryDag, idxSt.matchList, info.idxrange,
		info.modelSimWeight, info.idxtau);
	DBG_MSG1("At child", *pnCount)	
	_exit(0);
}

double AsyncMatchDAG(const DAG* pQueryDag, const DAG* pModelDag, DAGNodeMap& nodeMap)
{
	double* pdSim = new double(0);
	
	if ((g_pid = fork()) != 0)
	{
		int status;	
		waitpid(g_pid, &status, 0);

		if (!(WIFEXITED(status)))
		{
			cerr << "\nSegmentation fault when matching " << pQueryDag->GetDAGLbl()
				<< " against " << pModelDag->GetDAGLbl() << endl;
				
			*pdSim = 0;
		}
			
		double sim = *pdSim;
		delete pdSim;
		
		// Parent process is done, function returns normaly
		return sim;
	}
	
	// Child process starts here
	*pdSim = pQueryDag->Similarity(*pModelDag, nodeMap);
	_exit(0);
}
#endif //no WIN32

//! Match one SG against ALL the SGs in the given db

time_t MatchDAG(const DAG* pTargetDag, DAGDatabase& dagDB, MATCHINFO& info, 
			  STATINFO& idxSt, STATINFO& matSt)
{
	double dSim;
	DAGNodeMap nodeMap;
	DAGPtr ptrDag;
	int i;
	time_t startTime, endTime;

	startTime = time(NULL);

	// Index with target DAG
	int count;
	
	/*if (info.asyncCompu)
		count = AsyncIndexDAG(pTargetDag, dagDB, info, idxSt);
	else*/
		count = dagDB.GetSimilar(*pTargetDag, idxSt.matchList, info.idxrange,
			info.modelSimWeight, info.idxtau);

	matSt.matchList.resize(count);

	// Match DAGs returned by the index
	for (i = 0; i < count; i++)
	{
		dSim = idxSt.matchList[i].dSimilarity;
		
		if (dSim < info.idxtau)
			break;

		// Only retrive the K best allowing multiplicity of the last k one.

		if (i > info.idxKBest && dSim < idxSt.matchList[info.idxKBest].dSimilarity)
			break;

		ptrDag = dagDB.ReadDAG(idxSt.matchList[i].nDAGId, true);

		if (ptrDag.IsNull())
		{
			cerr << "Can't read DAG" << idxSt.matchList[i].nDAGId << endl;
			break;
		}

		// Match DAGs retrive by the indexer as long as the similarity thresholds for
		// the matcher is achivable, ie <= 1. If matchtau > 1, then we just want indexing stats.
		if (info.matchtau <= 1)
		{
			/*if (info.asyncCompu)
				dSim = AsyncMatchDAG(pTargetDag, ptrDag, nodeMap);
			else*/
				dSim = pTargetDag->Similarity(ptrDag, nodeMap);

			if (dSim >= info.matchtau)
				matSt.matchList[i].Set(ptrDag, dSim);
		}
		
		idxSt.matchList[i].ptrDAG = ptrDag;
	}

	// Sort best matches
	matSt.matchList.sort();

	endTime = time(NULL);

	if (info.computeStats)
	{
		idxSt.ComputeStats(pTargetDag);
		matSt.ComputeStats(pTargetDag);
		if (info.matchtau <= 1)
			idxSt.ComputeCrossRankingIdxStats(matSt);
	}

	return endTime - startTime;
}

//! Match one SG against another ONE in the given database

void MatchDAG(const DAG* pImgDag, DAGDatabase& dagDB, MATCHINFO& info, 
			  streamoff nModelDagOffset, STATINFO& matSt)
{
	double dSim;
	DAGNodeMap nodeMap;
	DAGPtr ptrDag;

	matSt.matchList.resize(1);

	// Match model DAG
	ptrDag = dagDB.ReadDAG(nModelDagOffset, pImgDag->ClassName());

	if (ptrDag.IsNull())
	{
		cerr << "Can't read DAG with offset " << nModelDagOffset << endl << flush;
		return;
	}

	dSim = pImgDag->Similarity(*ptrDag, nodeMap);

	matSt.matchList[0].Set(ptrDag, dSim);
}

void SaveResults(const DAG* pTarget, DAGDatabase& dagDB, 
				 STATINFO& idxSt, STATINFO& matSt, ostream& os)
{
	const int RANK = 8;
	const int DAGID = 15;
	const int OBJNAME = 25;
	const int VIEWNUM = 10;
	const int SIMIL = 10;
	int i;
	
	os.flags(ios::left);

	os << "\nChoosen graph: " << pTarget->GetDAGLbl();
	os << "\nDAG ID: " << pTarget->GetDAGId() << endl;

	os << "\nINDEXING RESULTS\n\n";
	os << setw(RANK) << "Rank" << setw(DAGID) << "DAG ID" << setw(OBJNAME) << "Object Name" 
		<< setw(VIEWNUM) << "View #" << setw(SIMIL) << "Similarity" << endl;
	
	for(i = 0; i < idxSt.matchList.size() && i < matSt.matchList.size(); i++)
	{
		const MatchInfo& info = idxSt.matchList[i];
		
		if (info.dSimilarity == 0.0)
			break;

		const DAGPtr ptrDAG = (info.ptrDAG.IsNull()) ? dagDB.ReadDAG(info.nDAGId, true):info.ptrDAG;

		os << endl; 
		os << setw(RANK)    << i;
		os << setw(DAGID)   << ptrDAG->GetDAGId();
		os << setw(OBJNAME) << ptrDAG->GetObjName();
		os << setw(VIEWNUM) << ptrDAG->GetViewNumber();
		os << setw(SIMIL)   << info.dSimilarity;
	}

	os << "\n\nMATCHING RESULTS\n\n";
	os << setw(RANK) << "Rank" << setw(DAGID) << "DAG ID" << setw(OBJNAME) << "Object Name" 
		<< setw(VIEWNUM) << "View #" << setw(SIMIL) << "Similarity" << endl;

	for(i = 0; i < matSt.matchList.size(); i++)
	{
		const MatchInfo& info = matSt.matchList[i];

		if (info.dSimilarity == 0.0)
			break;

		os << endl;
		os << setw(RANK)    << i;
		os << setw(DAGID)   << info.ptrDAG->GetDAGId();
		os << setw(OBJNAME) << info.ptrDAG->GetObjName();
		os << setw(VIEWNUM) << info.ptrDAG->GetViewNumber();
		os << setw(SIMIL)   << info.dSimilarity;
	}

	if (matSt.bCompViewStats)
	{
		int v1 = 0, v2 = 0, v3 = 0;
		GetClosestViews(pTarget->GetViewNumber(), 3, v1, v2, v3);
		
		SmartArray<int> secLevClosViews(0, 9);
		GetClosestViews2(pTarget->GetViewNumber(), 3, secLevClosViews, false);

		os << endl;
		os << "\n\nStatistics:\n";
		os << "\n\nClosest views: " << v1 << ' ' << v2 << ' ' << v3;
		os << "\n\nClosest 2nd level views: ";
		secLevClosViews.Print(os);
		os << endl;
	}
}

bool ShowResults(const DAG* pTarget, STATINFO& matSt, 
	DAGDatabase& queryDB, DAGDatabase& modelDB, int nTgtID /*=-1*/) 
{
	int i;

	cout << endl << "Query DAG: " << pTarget->GetDAGLbl() << endl;

	for (i = 0; i < matSt.matchList.size() && AskBool("\nShow next matching result"); i++)
		if (matSt.matchList[i].dSimilarity > 0.0)
		{
			if (nTgtID == -1)
				ShowMatch(pTarget, matSt.matchList[i].ptrDAG);
			else
				ShowMatch(queryDB, nTgtID, modelDB, matSt.matchList[i].nDAGId);
		}

	// If answered NO...
	if (i < matSt.matchList.size()) 
		return AskBool("\nKeep showing matches for other queries");

	return true;
}

void AddSubsamplingInfo(ViewSubsampler& vs, const DAG* pTarget, STATINFO& matSt, int kBest)
{	
	SmartArray<int> closestViews(0, 9);
	
	GetClosestViews2(pTarget->GetViewNumber(), 3, closestViews, true);
	vs.AddViewWeights(128, pTarget, matSt.matchList, closestViews, kBest);	
}

void SaveSubsamplingInfo(ViewSubsampler& vs, String strDBFileName)
{
	char szFileName[MAX_PATH_SIZE];
	
	DirWalker::ChangeFileExt(strDBFileName, NULL, szFileName);
	strcat(szFileName, "_subsampling.inf");

	vs.SaveViewWeights(szFileName);
}

void ShowMatch(DAGDatabase& dagDB1, int nDag1Id, DAGDatabase& dagDB2, int nDag2Id) 
{
	ShowMatch(dagDB1.ReadDAG(nDag1Id), dagDB2.ReadDAG(nDag2Id));
}

void ShowMatch(const DAG* pDag1, const DAG* pDag2)
{
	DAGNodeMap nodeMap;

	pDag1->Similarity(*pDag2, nodeMap);

	/*DAGPtr ptrCpDag1 = pDag1->CreateObject();
	DAGPtr ptrCpDag2 = pDag2->CreateObject();

	ShowGraph(*ptrCpDag1 = *pDag1);
	ShowGraph(*ptrCpDag2 = *pDag2);*/

	if (pDag1->ClassName() == "ShockGraph")
		ShowSkeletonMatch(pDag1, pDag2, nodeMap);
	else if (pDag1->ClassName() == "GestureGraph") {
		cout << "This is Fatih's job." << endl;
		// Fatih, cast to const GGNode*. Then use pNode->GetSimilarity()
		// to get the similarity assigned to a node after matching.
	}
}

void ShowSkeletonMatch(const DAG* pDag1, const DAG* pDag2, DAGNodeMap& nodeMap)
{
	const ShockGraph* pSG1 = dynamic_cast<const ShockGraph*>(pDag1);
	const ShockGraph* pSG2 = dynamic_cast<const ShockGraph*>(pDag2);

	if (pSG1 && pSG2)
	{
		SGMatchWnd wnd;
		wnd.SetMatchMap(nodeMap);
		wnd.Create(pSG1, pSG2);
	}
}

void ShowSkeleton(const DAG* pDag)
{
	const ShockGraph* pSG = dynamic_cast<const ShockGraph*>(pDag);

	if (pSG)
	{
		ShockGraph dummy;
		SGMatchWnd wnd;
		wnd.Create(pSG, &dummy);
	}
}

/*double SGNodeDistance(const SGNode& n1, const SGNode& n2)
{
	int i, j;
	double total = 0, subtotal, d;

	for (i = 0; i < n1.GetShockCount(); i++)
	{
		subtotal = 1000000;

		for (j = 0; j < n2.GetShockCount(); j++)
		{
			d = abs(abs(n1.m_shocks[i].dr_ds) - abs(n2.m_shocks[j].dr_ds));

			if (d < subtotal)
				subtotal = d;
		}

		total += subtotal;
	}

	return total;
}*/

/* 
	@brief Computes a shock graph from the given ppm file.

	@param szFileName PPM file name
	@param outFile The SG will be written into this file
	@logFil Log info will be written in this file
	@info Parameters for the SG computation code
	@bAsyncProcessing Whether a TIME OUT must be used to control the SG computation

	Since the SG computation used to fail, the async processing was necessary to
	avoid a batch processing of files getting stuck in a particular file.
*/
void ProcessFile(const char* szFileName, DAGDatabase& dagDB, fstream& logFile,
				 SGRECINFO& info, bool bAsyncProcessing)
{
	logFile << endl << '\t' << szFileName << "... ";
	logFile.flush();

#ifndef WIN32                 
	int status;

	if (bAsyncProcessing)
	{
		if ((g_pid = fork()) != 0)
		{	
			signal(SIGALRM, OnAlarm);
			g_nTimeout = info.timeout;
			alarm(info.timeout);
			waitpid(g_pid, &status, 0);

			if (!(WIFEXITED(status)))
				logFile << "ERROR: Seg. Fault";

			// Parent process is done, function returns normaly
			return; 
		}
	}
#endif // no WIN32

	// Child process executes the following code...
	DAGPtr pDag;
	bool bIsRead;
	const char* szFileExt;

	szFileExt = DirWalker::FindFileExtention(szFileName);

	if (!strcmp(szFileExt, "ppm") || !strcmp(szFileExt, "pgm") ||
		!strcmp(szFileExt, "bmp") || !strcmp(szFileExt, "tif") ||
		!strcmp(szFileExt, "jpg") || !strcmp(szFileExt, "png"))
	{
		ShockGraph* pSG = new ShockGraph;
		pDag = pSG;

		// Do we use the new SG code or the old one?

		if (info.skelcode == 1)
		{
			// The SG code seems to require square images to work properly
			//MakeSquare(szFileName);
			//bIsRead = pSG->ComputeFromPPMFile(szFileName, info.cutoff, info.sigma, info.range);
			bIsRead = false;
			cerr << "\nSG old code is not available anymore!!!\n";
		}
		else if (info.skelcode == 2)
		{
			cout << "\nComputing Flux skeleton from " << szFileName << "..." << endl;
			bIsRead = pSG->ComputeFromPPMFile2(szFileName, info.sgparams);
		}
		else if (info.skelcode == 3) 
		{
			cout << "\nComputing AFMM skeleton from " << szFileName << "..." << endl;
			IMAGEINFO imgInfo;
			bIsRead = AddBumpsAndNotches(szFileName, info, &imgInfo);
			if (bIsRead)
				bIsRead = pSG->ComputeFromPPMFile3(imgInfo, info.sgparams);
		}
		else {
			bIsRead = false;
			cerr << "\nInvalid skeletonization option!!!\n";
		}
	}
	else if (!strcmp(szFileExt, "gg"))
	{
		GestureGraph* pGG = new GestureGraph;
		pDag = pGG;

		bIsRead = pGG->Read(szFileName);
	}
	else
	{
		cerr << "\nUnknown file extension: " << szFileExt << endl;
		bIsRead = false;
	}

	if(bIsRead)
	{
		logFile << "DONE! (" << pDag->GetNodeCount() << " nodes)... " << flush;
		
		dagDB.AddDAG(pDag, true);

		logFile << "WRITTEN!" << flush;
	}
	else
		logFile << "ERROR: Can't read dag." << flush;

#ifndef WIN32
	// If bAsyncProcessing, the child process must finish
	if (bAsyncProcessing)
	{
		dagDB.Close();
		_exit(0); // Warning exit() with no '_' flushes the buffer and we don't want that.
	}
#endif // no WIN32
}

#ifndef WIN32
void OnAlarm(int param)
{
	kill(g_pid, SIGKILL);
	cerr << "\nTIMEOUT (" << g_nTimeout << " sec)" << endl;
	g_logFile << "TIMEOUT (" << g_nTimeout << " sec)";
}
#endif // no WIN32

/*!
	@brief It ensutes that the given PPM file has square dimentions

	The present version of the SG code crashes if the images aren't square
*/
/*void MakeSquare(const char* szPPMFileName)
{
	pixel** img;
	FILE* fp = fopen(szPPMFileName, "r+");
	int rows, cols, row, col, n, i;
	pixval maxval;
	int format;

	if (fp == NULL)
	{
		cerr << "\nERROR: Can't open " << szPPMFileName 
			<< ". Missing or read-only file.\n PPM might not be square." << endl;

		return;
	}

	ppm_readppminit(fp, &cols, &rows, &maxval, &format);

	// If img is already square, there is nothing to do
	if (cols == rows)
		return;

	n = (cols > rows) ? cols:rows;

	img = ppm_allocarray(n, n);

	// Set all the pixels in the new image to white
	for (i = 0; i < n; i++)
		memset(img[i], maxval, sizeof(pixel) * n);

	// Add the old image in the center of the new one
	if (cols > rows)
		for (i = 0, row = (cols - rows) / 2; i < rows; i++, row++)
			ppm_readppmrow(fp, img[row], cols, maxval, format);
	else
		for (i = 0, col = (rows - cols) / 2; i < rows; i++)
			ppm_readppmrow(fp, img[i] + col, cols, maxval, format);

	// Write down the new image
	fseek(fp, 0, SEEK_SET);
	ppm_writeppm(fp, img, n, n, maxval, 0);

	fclose(fp);
}*/

bool AskBool(const char* szQuestion)
{
	char cAnswer;
	
	cout << szQuestion << "?[y/n]: ";
	cin >> cAnswer;

	return (cAnswer == 'y' || cAnswer == 'Y');
}

int AskInt(const char* szQuestion)
{
	int nAnswer;
	
	cout << szQuestion << "?: ";
	cin >> nAnswer;

	return nAnswer;
}

