/**------------------------------------------------------------------------
 * @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.h,v $
 *
 *
 *-----------------------------------------------------------------------*/

#ifndef __VIEW_CLUSTERING_H__
#define __VIEW_CLUSTERING_H__

#include <vector>
#include <LEDA/core/p_queue.h>
#include <newmatap.h>
#include <newmatio.h>
#include <HelperFunctions.h>

/*!
	A bounded bin is a sorted sequence, <sorted_data, other_inf>, whose length
	is at all times smaller or equal to nMaxSize.
*/
class NearestNeighborsList : public leda::p_queue<double, int> 
{
	int nMaxSize;

public:
	NearestNeighborsList(int sz = 1) { SetMaxSize(sz); }

	void SetMaxSize(int sz) { nMaxSize = sz; }
	int GetMaxSize() const  { return nMaxSize; }
	void Clear()            { clear(); }

	void Push(const double& weight, int id)
	{
		ASSERT(size() <= nMaxSize);

		// Keep the size <= nMaxSize
		if (size() == nMaxSize)
		{
			leda::pq_item min = find_min(); //O(1)

			if (prio(min) < weight)
				del_item(min); //O(log nMaxSize)
			else
				return; // nothing to insert
			
		}

		insert(weight, id); //O(log nMaxSize)
	}

	bool PopMin(double& weight, int& id)
	{
		if (empty())
			return false;
		
		leda::pq_item min = find_min();
		weight = prio(min);
		id = inf(min);
		del_item(min);

		return true;
	}

	friend std::ostream& operator<<(std::ostream& os, const NearestNeighborsList& nnl) 
	{ 
		leda::pq_item it;

		forall_items(it, nnl)
			os << '(' << nnl.prio(it) << ',' << nnl.inf(it) << ") ";

		return os; 
	}
};

class ViewClustering
{
	std::vector<NearestNeighborsList> m_nnla;
	NEWMAT::Matrix m_simMat;
	NEWMAT::Matrix m_dagIds;
	int m_numShapes;
	int m_maxNNCount;
	float m_groupSizeTau;

public:
	int ReadSimilarityMatrix(const char* szFilename);
	void ClusterFromSimilarityMatrix(const char* szFilename, int K, float tau = 500);
	void InitializeConnections();
	void FindPrototypes();
};

#endif //__VIEW_CLUSTERING_H__

