//Author: Yusuf Sahillioglu
//Aim: establish cool multiple correspondences over a collection of isometric shapes that guarantees to minimize the overall pairwise distortions for 3 shapes (optimal) and expected to minimize for more shapes (almost-optimal)
//^ rarely x64 release mode not reach its optimum performance; if you feel it is not fast enough, just shutdown computer, delete \x64 and \ipch folders, do ctrl+f5
//^^ most of the files (block.h, Blossom.h, LCA.h, MinCost.h, PerfectMatching.h, PMImplementation.h, PQ.h, timer.h, MinCost.cpp, misc.cpp, PM*.cpp) are just for min-weight perfect matching Blossom which enables large N to be matched

#include "Graph.h"
//#include <windows.h> //for get_time()	//comment-out for full portability of the public release

//these defines are in effect only if you compile and run the code yourself, for the public executable you simply change the command prompt arguments corresponding to these defines
#define SHORTEST_PATH_ALGO			1 //always selects the min-distortion maps as if i solved pairwise correspondences independently; use this as a baseline algo for comparisons
#define DYNAMIC_PROGRAMMING_ALGO_V1	2 //try N! possible maps for each path to be expanded
#define DYNAMIC_PROGRAMMING_ALGO_V2	3 //a similar dynamic programming approach that tries N! possible paths for each map to be appended
#define DYNAMIC_PROGRAMMING_ALGO_V3	4 //a similar dynamic programming approach that tries N! possible paths for each map to be appended and maintains P best-fit paths instead of just 1 best-fit paht as in _V2, hence alleviating the missing maps problem
#define EXPONENTIAL_ALGO			5 //brute force trial of all permutations/compositions of maps and selecting the min-distortion permutation
//#define MESH_TRIPLETS_ONLY			//call alternative main() so as to extract statistics over the matchings of mesh triplets only
//#define SPECTRAL_INIT_TO_MATCH_MORE	//call alternative build() so as to match more (up to 500 but using 80 for consistency w/ PAMI initialization) samples

/*inline double get_time()
{
	LARGE_INTEGER t, frequency;
	QueryPerformanceCounter(&t);
	QueryPerformanceFrequency(&frequency);
	return (double)t.QuadPart/(double)frequency.QuadPart;
}*/

#ifdef MESH_TRIPLETS_ONLY
int main(int argc, char ** argv)
{
	if (argc != 3)
	{
		cout << "MultipleShapeCorresponder_x64 [whichAlgo: 0 for shortest path, 1 for dynamic programming] [startIdx: integer in [0,72]]\n";
		exit(0);
	}

	//alternative main() that calls computeOptimalMultipleCorrespondence() for 100 SCAPE triplets to demonstrate the optimality of our algorithm on 3 meshes (for 4+ shapes we approximate optimality)
	//where optimality means finding all pairwise maps whose isometric distortion summation, i.e. overall isometric distortion, is minimum
	int algo = (atoi(argv[1]) == 0 ? SHORTEST_PATH_ALGO : DYNAMIC_PROGRAMMING_ALGO_V2), //algorithm selection to get multiple correspondences over mesh collection
		version = 1; //version of the dynamic programming algo to be used
	if (algo == DYNAMIC_PROGRAMMING_ALGO_V2)
		version++;
	else if (algo == DYNAMIC_PROGRAMMING_ALGO_V3)
		version += 2;

	//out of C(72, 3) = 119280, use only the first nMaxTriplets of them
	int nMaxTriplets = 100, m = 72, nIters = 0, startIdx = atoi(argv[2]), overallSymFlips = 0; //make nMaxTriplets=1 to match 1 triplet
	double totalTime = 0.0, overallIsoDistortion = 0.0, overallGrdTruthDistortion = 0.0;
	for (int a = startIdx; a < m; a ++)
		for (int b = a+1; b < m; b++)
			for (int c = b+1; c < m; c++)
			{
				Graph* graph = new Graph(a, b, c); //start, middle, stop idxs to scape dataset to load the current mesh triplet
				//shape collection based on which the graph will be built
				graph->loadMeshTriplets(3, algo != SHORTEST_PATH_ALGO, version);

				//build graph
//				double start_time = get_time();
				graph->build(algo != SHORTEST_PATH_ALGO);
				
				if (algo == SHORTEST_PATH_ALGO)
					//solve shortest paths on this graph to get optimal path of maps whose distortion is minimum which does not necessarily make overall distortion minimum, hence suboptimal
					graph->solve();
				else //dynamic programming
					graph->computeOptimalMultipleCorrespondence(version);
//				totalTime += (get_time() - start_time);
				overallIsoDistortion += graph->overallIsoDistOfTriplet;
				overallGrdTruthDistortion += graph->overallGrdTruthDistOfTriplet;
				overallSymFlips += graph->overallSymFlips;
				if (++nIters == nMaxTriplets)
				{
					a = b = m; //break 2 outer loops
					break; //this inner loop
				}
				//graph->deleteMeshTriplets(); no effect at all
			}
	cout << "\n\noverall isometric & ground-truth distortion of all " << nMaxTriplets << " mesh triplets (= " << nMaxTriplets*3 << " mappings): " << overallIsoDistortion / nMaxTriplets << " & " << overallGrdTruthDistortion / nMaxTriplets
		 << "\noverall # symmetric flips: " << overallSymFlips << " / " << nMaxTriplets*3 << "\n\n>>>>>> ";// << totalTime << " secs for everything (excluding mesh load times)\n";
	FILE* fPtr = fopen("triplets.dat", "a");
	if (algo != SHORTEST_PATH_ALGO)
		fprintf(fPtr, "==================dynamic programming==================\n");
	else
		fprintf(fPtr, "==================shortest path==================\n");
	fprintf(fPtr, "[%d] overall isometric & ground-truth distortion of all %d mesh triplets (= %d mappings): %f & %f\noverall # symmetric flips: %d / %d\n\n", startIdx, nMaxTriplets, nMaxTriplets*3, overallIsoDistortion / nMaxTriplets,
																																							   overallGrdTruthDistortion / nMaxTriplets, overallSymFlips, nMaxTriplets*3);
	fclose(fPtr);

	return 0;
}
#else
int main(int argc, char ** argv)
{
	cout << "\nDynamic Programming Based Distortion Minimization for Multiple Shape Correspondence\n\n";
	cout << "7 parameters expected: MultipleShapeCorresponder_x64.exe $startIdx$ $stopIdx$ $fileExt$ $algorithmID$ $N$ $denseExtension$ $interpCoarseToDense$\n\n";
	if (argc != 8)
	{
		cout << "$start/stopIdx$: use meshes in \\input folder w/ IDs $startIdx$ to $stopIdx$\n";
		cout << "$fileExt$: input mesh file extension: obj, off, ply supported\n";
		cout << "$algorithmID$\t= 1 to execute the optimal exponential algorithm (# shapes better be <9)\n\t\t= 2 to execute the approximation algorithm based on shortest paths\n\t\t= 3 to execute the better approximation algorithm based on dynamic programming (our proposed solution in citation below)\n";
		cout << "$N$: # of samples to be matched on each shape\n";
		cout << "$denseExtension$: 0 to run the original algorithm w/ combinatorial enumeration (for N < 10), 1 to run the version w/ dense enumeration (large N (<500))\n";
		cout << "$interpCoarseToDense$: 1 to interpolate the coarse map of the original algorithm to a 80x80 dense map for all pairs via perfect matching\n";
		exit(0);
	}
	int startIdx = atoi(argv[1]), stopIdx = atoi(argv[2]), theAlgo = atoi(argv[4]), N = atoi(argv[5]);
	char* fileFormat = argv[3];
	bool denseExtension = (atoi(argv[6]) == 1), interpCoarseToDense = (atoi(argv[7]) == 1);
	if (denseExtension && interpCoarseToDense) //interpolation in denseExtension mode does not make sense 'cos enumeration is already dense
		exit(0);

	int algo = DYNAMIC_PROGRAMMING_ALGO_V2, //SHORTEST_PATH_ALGO, //EXPONENTIAL_ALGO, //DYNAMIC_PROGRAMMING_ALGO_V1, //algorithm selection to get multiple correspondences over mesh collection
		version = 1; //version of the dynamic programming algo to be used; ignored for SHORTEST_PATH_ALGO case
	if (theAlgo == 1)
		algo = EXPONENTIAL_ALGO;
	else if (theAlgo == 2)
		algo = SHORTEST_PATH_ALGO;
	if (algo == DYNAMIC_PROGRAMMING_ALGO_V2)
		version++;
	else if (algo == DYNAMIC_PROGRAMMING_ALGO_V3)
		version += 2;
	else if (algo == EXPONENTIAL_ALGO)
		version = 0; //inform loadMeshes() that this is neither shortest path nor dynamic programming solution	

	Graph* graph = new Graph(startIdx, stopIdx);
	graph->N = N; //# of extremes to be matched
	//build graph using shape collection to be loaded
//	double start_time = get_time();
	graph->loadMeshes(fileFormat, algo != SHORTEST_PATH_ALGO, version, denseExtension);
	graph->build(algo != SHORTEST_PATH_ALGO, denseExtension);
//	double intermediate_time = get_time();
//	cout << intermediate_time - start_time << " secs for graph creation\n";

	if (algo == SHORTEST_PATH_ALGO)
	{
		//solve shortest paths on this graph to get optimal path of maps whose distortion is minimum which does not necessarily make overall distortion minimum, hence suboptimal
		if ( graph->solve() )
			;//cout << get_time() - intermediate_time << " secs for graph solving\n";
	}
	else if (algo == EXPONENTIAL_ALGO)
		graph->bruteForceMultipleCorrespondence();
	else //dynamic programming
		graph->computeOptimalMultipleCorrespondence(version, interpCoarseToDense);

//	cout << "\n>>>>>> " << get_time() - start_time << " secs for everything (except mesh load times)\n";

	return 0;
}
#endif
