/**------------------------------------------------------------------------
 * @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: ViewClustering.cpp,v $
 *
 *-----------------------------------------------------------------------*/
#include "ViewClustering.h"
#include "../FHImgSegment/segment-graph.h"

using namespace std;

/*!
	@brief Reads the similarity matrix created with the "-matrix" option of
	ShapeMatcher. I.e., sm -matrix "matrix.m" obj.db

	returns the number of columns in 'id' == cols and rows in 'm'
*/
int ViewClustering::ReadSimilarityMatrix(const char* szFilename)
{
	fstream is;
	int sz;

	try {
		is.open(szFilename, ios::in);

		char c;
		int i, j;

		// Read: n = X;
		is >> c >> c >> sz >> c;

		// Read: id = [ X X ... ];
		m_dagIds.ReSize(1, sz);
		is >> c >> c >> c >> c;
		for (i = 1; i <= sz; i++)
			is >> m_dagIds(1, i);
		is >> c >> c;

		//cout << sz << "->" << id << endl;

		// Read: m = [ X X ... ];
		m_simMat.ReSize(sz, sz);
		is >> c >> c >> c;
		for (i = 1; i <= sz; i++)
			for (j = 1; j <= sz; j++)
				is >> m_simMat(i, j);
		is >> c >> c;

		//cout << c << "->" << m << endl;
	}
	catch(...)
	{
		ShowError1("Cannot read similarity matrix file:", szFilename);
		return 0;
	}

	return sz;
}

/*!
	@brief Clusters views using the information in the similarity matrix
	created with the "-matrix" option of ShapeMatcher.
*/
void ViewClustering::ClusterFromSimilarityMatrix(const char* szFilename, int K, float tau /*=500*/)
{
	m_maxNNCount = K;
	m_groupSizeTau = tau;
	m_numShapes = ReadSimilarityMatrix(szFilename);

	if (m_numShapes > 0)
	{
		InitializeConnections();
		FindPrototypes();
	}

	// Save prototypes
}

/*!
	@brief Initializes array of nearest neighbor lists
*/
void ViewClustering::InitializeConnections()
{
	int i, j;

	m_nnla.clear();
	m_nnla.resize(m_numShapes);

	for (i = 0; i < m_numShapes; i++)
		m_nnla[i].SetMaxSize(m_maxNNCount);

	for (i = 0; i < m_numShapes; i++)
		for (j = 0; j < m_numShapes; j++)
			if (i != j)
				m_nnla[i].Push(m_simMat(i + 1, j + 1), j);

	// Check how things look
	//for (i = 0; i < m_numShapes; i++)
	//	cout << m_nnla[i] << endl;	
}

void ViewClustering::FindPrototypes()
{
	int i, j, numEdges;
	double sim;

	// 1. Create Graph
	edge* edges = new edge[m_numShapes * m_maxNNCount];

	for (i = 0, numEdges = 0; i < m_numShapes; i++)
	{
		while (m_nnla[i].PopMin(sim, j))
		{
			edges[numEdges].a = i;
			edges[numEdges].b = j;
			edges[numEdges].w = float((1 - sim) * 255); // ie, like pixel intensity diff
			numEdges++;
		}
	}

	ASSERT(numEdges <= m_numShapes * m_maxNNCount);

	// 2. Cluster graph
	cout << "\t- clustering graph with " << m_numShapes << " nodes and " 
		<< numEdges << " edges (tau = " << m_groupSizeTau << ")..." << endl;

	universe* u = segment_graph(m_numShapes, numEdges, edges, m_groupSizeTau);

	// 3. Find prototypes
	int group, numSets = u->num_sets();

	cout << "\t- finding one prototypes for each of the " 
		<< numSets << " groups" << endl;

	std::vector<NearestNeighborsList> prots(m_numShapes), groups(m_numShapes);
	double cumSim, groupSize;

	// Init. the priority queues to a size of 1 (ie, a prototype per group)
	for (i = 0; i < m_numShapes; i++)
	{
		prots[i].SetMaxSize(1);
		groups[i].SetMaxSize(m_numShapes);
	}

	// Compute average distance betweeen each shape and all the 
	// other shapes in the same group
	for (i = 0; i < m_numShapes; i++)
	{
		group = u->find(i);
		groupSize = u->size(group);

		//cout << "Processing shape " << i << " in group " << group 
		//	<< " of size " << groupSize << endl;

		ASSERT(group >= 0 && group < m_numShapes);
		ASSERT(groupSize > 0 && groupSize <= m_numShapes);

		cumSim = 0;

		for (j = 0; j < m_numShapes; j++)
			if (i != j && u->find(j) == group)
				cumSim += m_simMat(i + 1, j + 1);

		prots[group].Push(cumSim / groupSize, i);

		cout << '.' << flush;
	}

	// Print info/stats
	cout << "Number of sets: " << numSets << endl;
	cout << "Prototypes: " << flush;

	for (i = 0; i < m_numShapes; i++)
		if (!prots[i].empty())
			cout << prots[i] << endl;

	delete[] edges;
	delete u;
}

