/*
    Copyright (C) 2012 Bartosz Broda, Jacek Bochenek, Łukasz Biłeńkij, 
    Damian Jaworski, Wojciech Mazur, Dominik Piasecki, Maciej Piasecki, 
    Radosław Ramocki
    
    This program is free software; you can redistribute it and/or modify it
under the terms of the GNU Lesser General Public License as published by the Free
Software Foundation; either version 3 of the License, or (at your option)
any later version.

    This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. 

    See the LICENSE and COPYING files for more details.
*/

#include "Cluster.h"
#include <queue>
#include <iostream>
#include <map>


namespace ClusteringBase
{
	size_t Cluster::m_LastID = 0;

	Cluster::Cluster()	:m_ID(m_LastID++)
	{
		m_pDataPointsID = new IdSet();
	}

	Cluster::Cluster(size_t id) : m_ID(id)
	{
		m_pDataPointsID = new IdSet();
		if(m_ID >= m_LastID)
			m_LastID = m_ID+1;
	}

	size_t Cluster::GetID() const
	{
		return m_ID;
	}

	void Cluster::AddPoint(size_t pointID)
	{
		m_pDataPointsID->insert(pointID);
	}

	IdSet& Cluster::GetPointsID()
	{
		return *m_pDataPointsID;
	}

	Cluster::~Cluster()
	{
		if(m_pDataPointsID)
		{
			delete m_pDataPointsID;
			m_pDataPointsID = NULL;
		}
	}
	std::vector<boost::shared_ptr<Cluster> >& Cluster::GetChildren()
	{
		return m_vChildren;
	}
	boost::shared_ptr<Cluster> Cluster::GetParent()
	{
		return m_pParent;
	}
	void Cluster::SetParent(boost::shared_ptr<Cluster> parent)
	{
		m_pParent = parent;
	}

	bool Cluster::operator < (Cluster &c) const
	{
		return GetID() < c.GetID();
	}

	bool lessClusterPtr::operator()(const ClusterPtr c1, const ClusterPtr c2) const
	{
		return ( *c1 < *c2);
	}

	ClusterPtr MergeClusters(ClusterPtr c1, ClusterPtr c2)
	{
		ClusterPtr ret(new Cluster());
		for(IdSet::iterator i = c1->GetPointsID().begin(); i != c1->GetPointsID().end(); i++)
			ret->AddPoint( *i );
		for(IdSet::iterator i = c2->GetPointsID().begin(); i != c2->GetPointsID().end(); i++)
			ret->AddPoint( *i );

		c1->SetParent(ret);
		c2->SetParent(ret);

		ret->GetChildren().push_back(c1);
		ret->GetChildren().push_back(c2);

		return ret;
	}

	bool IsFlat(ClusterSetPtr clusterset)
	{
		for(ClusterSet::iterator i = clusterset->begin(); i != clusterset->end(); i++)
			if( (*i)->GetChildren().size() > 0 || (*i)->GetParent() != NULL)
				return false;
		return true;
	}

	void GetLeafs(ClusterSetPtr clusterset, ClusterSet &leafs)
	{
		for(ClusterSet::iterator i = clusterset->begin(); i != clusterset->end(); i++)
			if( (*i)->GetChildren().size() == 0)
				leafs.insert( *i );
	}
	void GetRoots(ClusterSetPtr clusterset, ClusterSet &roots)
	{
		for(ClusterSet::iterator i = clusterset->begin(); i != clusterset->end(); i++)
			if( (*i)->GetParent() == NULL)
				roots.insert( *i );
	}

	void AssertNotExists(int id, std::map<int, ClusterPtr> elems)
	{
		if(elems.find(id) != elems.end() )
			throw std::runtime_error("Element is in more then one cluster, fuzzy solutions not supported!");
	}//AssertNotExists

	ClusterPtr GetFirstNonSingeltionParent(ClusterPtr cluster)
	{
		ClusterPtr parent = cluster->GetParent();
		if( parent == NULL )
			return parent;
		IdSet &elems = cluster->GetPointsID();
		if(elems.size() > 1)
			return parent;
		return GetFirstNonSingeltionParent( parent );
	}

	void ProcessLeafs(ClusterSetPtr clusters, std::map<size_t, ClusterPtr> &doc2merge2, std::map<size_t, ClusterPtr> &doc2mergeMore)
	{
		ClusterSet leafs;
		GetLeafs(clusters, leafs);

		for(ClusterSet::iterator i = leafs.begin(); i!= leafs.end();i++)
		{
			Cluster& cluster = *(*i);
			IdSet &elems = cluster.GetPointsID();
			size_t size = elems.size();
			switch(size)
			{
			case 1:
				break;
			case 2:
				for(IdSet::iterator iter = elems.begin(); iter != elems.end(); iter++)
					doc2merge2[ *iter ] = *i;
				break;
			default:
				break;
			}
		}

	}
	void PrepareLeafsForParentArray(ClusterSetPtr pClusters, std::map<int, ClusterPtr> &elem2cluster)
	{
		ClusterSet leafs;
		GetLeafs(pClusters, leafs);

		for(ClusterSet::iterator i = leafs.begin(); i!= leafs.end();i++)
		{
			Cluster& cluster = *(*i);
			IdSet &elems = cluster.GetPointsID();
			size_t size = elems.size();
			switch(size)
			{
			case 0://sanity check
				break;
			case 1:// singelton => add link to parent
				{
					size_t id = *(elems.begin());
					AssertNotExists(id, elem2cluster);
					elem2cluster[id] = cluster.GetParent();
				}
				break;
			default:// more then one element => add link to current
				for(IdSet::iterator elemsIter = elems.begin(); elemsIter != elems.end(); elemsIter++)
				{
					AssertNotExists(*elemsIter, elem2cluster);
					elem2cluster[*elemsIter] = *i;
				}
				break;

			}//switch(size)
		}//for each leaf
	}//prepare leafs

	int FindSisterId(ClusterPtr cluster, std::map<ClusterPtr, int> &cluster2parray_id)
	{
		int id = cluster->GetID();
		if(cluster->GetChildren().size() > 0)
		{
			std::vector<ClusterPtr> children ( cluster->GetChildren() );
			while( children.size() )
			{
				ClusterPtr p = children[children.size()-1];
				children.pop_back();

				int child_id = p->GetID();
				if( child_id == id )
					continue;

				std::map<ClusterPtr,int>::iterator find = cluster2parray_id.find(p);
				if( find != cluster2parray_id.end() )
					return find->second;

				std::vector<ClusterPtr> &children2 = p->GetChildren();
				for(size_t i = 0; i < children2.size(); i++)
					children.push_back( children2[i] );

			}
		}
		ClusterPtr parent = cluster->GetParent();
		if(parent == NULL )
			return -1;
		std::vector<ClusterPtr> children ( parent->GetChildren() );
		while( children.size() )
		{
			ClusterPtr p = children[children.size()-1];
			children.pop_back();

			int child_id = p->GetID();
			if( child_id == id )
				continue;

			std::map<ClusterPtr,int>::iterator find = cluster2parray_id.find(p);
			if( find != cluster2parray_id.end() )
				return find->second;

			std::vector<ClusterPtr> &children2 = p->GetChildren();
			for(size_t i = 0; i < children2.size(); i++)
				children.push_back( children2[i] );


		}
		return -1;
	}

	void AddElementsToParentArray( std::map<int, ClusterPtr> &currentElems, Matrices::SuperMatrixPtr pMatrix,
			std::vector<int> &parray, std::map<ClusterPtr, int> &cluster2parray_id)
	{
		Matrices::FeatureVectorPtr row_features = pMatrix->GetRowFeatures();
		size_t row_size = row_features->size();
		size_t next_parray_index = row_size;
		for(size_t row_no = 0; row_no < row_size; row_no++)
		{
			std::map<int, ClusterPtr>::iterator find = currentElems.find(row_no);
			if(find == currentElems.end())
				parray.push_back( -1 );// outlier or not clustered...
			else// not root (or outlier?)
			{
				ClusterPtr pCluster = find->second;
				if(pCluster == NULL )
				{// we do not have parent
					parray.push_back( -1 );
					continue;
				}
				std::map<ClusterPtr, int>::iterator is_added = cluster2parray_id.find( pCluster );
				if( is_added == cluster2parray_id.end() )
				{// new item in parray
					int id = FindSisterId( pCluster, cluster2parray_id );
					if( id == -1 )
					{
						parray.push_back( next_parray_index );
						cluster2parray_id[ pCluster ] = next_parray_index++;
					}
					else
					{
						ClusterPtr fake( new Cluster( (size_t) id ));
						std::map<ClusterPtr, int>::iterator is_added2 = cluster2parray_id.find( fake );
						if( is_added2 == cluster2parray_id.end() )
						{
							parray.push_back( (size_t) id );
							cluster2parray_id[ pCluster ] = (size_t) id;
						}
						else
							parray.push_back( (size_t) id );
					}
				}
				else// has been added before
					parray.push_back( is_added->second );
			}//not root
		}
	}//AddElementsToParentArray

	void AddLevelToParentArray( std::map<ClusterPtr, int> &toAdd, std::map<ClusterPtr, int> &next_level, std::vector<int> &parray )
	{
		std::set<int> all;
		for(std::map<ClusterPtr, int>::iterator iter = toAdd.begin(); iter != toAdd.end(); iter++)
			if( iter->second > 0 )
				all.insert( iter->second );
//		std::copy(all.begin(), all.end(), std::ostream_iterator<int>(std::cout, " ") );
//		std::cout << "\n----------------------------" << std::endl;
		for(size_t i = 0; i < all.size(); i++)
			parray.push_back( -2 ); // -2 -> control

		next_level.clear();
		size_t next_parray_id = parray.size();
		for(std::map<ClusterPtr, int>::iterator iter = toAdd.begin(); iter != toAdd.end(); iter++)
		{
			ClusterPtr pCluster = iter->first;
			if( pCluster == NULL )//should not happen
			{
				std::cout << "NULLLLLLLLLLL" << std::endl;
				continue;
			}

			ClusterPtr parent = pCluster->GetParent();
			size_t parray_id = iter->second;

			if( parent == NULL )
			{
				parray[ parray_id ] = -1;
//				std::cout << "PNULL ";
				continue;
			}

			std::map<ClusterPtr, int>::iterator is_added = next_level.find( parent );
			if( is_added == next_level.end() )
			{// ! added
//				std::cout << next_parray_id << " ";
				if( next_parray_id  == 1122 )
				{
					std::cout << "1223: ";
					std::copy(parent->GetPointsID().begin(), parent->GetPointsID().end(),
							std::ostream_iterator<size_t>(std::cout, ", ") );
					std::cout << std::endl;
				}
				next_level[ parent ] = next_parray_id;
				parray[parray_id] = next_parray_id;
				next_parray_id++;
			}
			else//added
				parray[parray_id] = is_added->second;
		}//for(std::map<ClusterPtr, size_t>::iterator iter = toAdd.begin(); iter != toAdd.end(); iter++)
//		std::cout << std::endl;
	}//AddLevelToParentArray

	void ToParentArray(ClusterSetPtr pClusters, Matrices::SuperMatrixPtr pMatrix,  std::vector<int> &parray)
	{
		parray.clear();
		// elementId -> cluster, where cluster is non-singelton singelton cluster
		std::map<int, ClusterPtr> elem2cluster;
		PrepareLeafsForParentArray(pClusters, elem2cluster);

		std::map<ClusterPtr, int> cluster2arrayId, second_one;
		AddElementsToParentArray( elem2cluster, pMatrix, parray, cluster2arrayId );

		std::map<ClusterPtr, int> *current = &cluster2arrayId, *next = &second_one, *temp;
		while( current->size() > 0 )
		{
			AddLevelToParentArray( *current, *next, parray);
			//swap next<->current
			temp = current;
			current = next;
			next = temp;
		}// while next->size() > 0
		// append -1 to the end of parray
		parray.push_back( -1 );
	}//ToParentArray

	void SaveParentArray(std::vector<int> &parray, const std::string &filename)
	{
		std::ofstream file( filename.c_str() ) ;
		if( ! file )
			throw std::runtime_error( "Cannot open file for writing clustering solution: " + filename );

		std::copy( parray.begin(), parray.end(), std::ostream_iterator<int>(file, "\n") );
	}

	void CreateParray(ClusterSetPtr clusters, std::vector<int> &parray)
	{
		ClusterSet roots;
		GetRoots(clusters, roots);
		std::queue< std::pair<ClusterPtr, int> > q;
		for(ClusterSet::iterator i = roots.begin(); i != roots.end(); i++)
		{
			//std::cout << (*i)->GetID() << std::endl;
			q.push( std::pair<ClusterPtr,int>(*i, -1) );
		}


		//std::map<ClusterPtr, int> index; not used?

		while( ! q.empty() )
		{
			std::pair<ClusterPtr, int> c = q.front();
			q.pop();

			parray.push_back( c.second );
			int id = (int) parray.size();

			//std::cout << c.first->GetChildren().size() << std::endl;
			for(size_t i = 0; i < c.first->GetChildren().size(); i++)
				q.push( std::pair<ClusterPtr,int> ( c.first->GetChildren()[i], id ) );
		}

	}

}

