/*
    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 "Kmedoids.h"
#include <boost/date_time.hpp>

using namespace smartcomparator::compare;
using namespace Matrices;
using namespace std;

namespace clustering
{
	namespace kmedoids
	{
		Kmedoids::Kmedoids(size_t medoids_no, SuperMatrixPtr matrix, CompareFunctionPtr cmp_fun, size_t seed):
				_seed(seed), _medoids_no(medoids_no), _matrix(matrix)
		{
			_rows = matrix->NumberOfRows();
			_isMedoid = std::vector<bool>(_rows);
			_cmp_function = cmp_fun;
		}

		void Kmedoids::StartClustering()
		{
			cout << "Clustering in progress..." << endl;
			cout << "No of medoids: " << _medoids_no << endl;
			NormalizeMatrix();
			InitMedoids();
			PrintVector(_medoids_indices);
			double best_similarity = this->CountSimilarity(_medoids_indices);
			size_t best_medoid, old_medoid;
			bool wasChange = true;

			size_t iteration = 1;

			while(wasChange)
			{
				wasChange = false;
				for(size_t i = 0; i < _medoids_no; ++i)
				{
					old_medoid = best_medoid = _medoids_indices[i]; //copy of medoid
//					cout << "start i: " << i << " medoids: ";
//					PrintVector(medoids_indices);
//					cout << endl;
					for(size_t j = 0; j < _rows; ++j)
					{
						if(!_isMedoid[j])
						{
							_medoids_indices[i] = j; //try current row as medoid
//							cout << "i: " << i << " j: " << j << " medoids: ";
//							PrintVector(medoids_indices);
							double similarity = CountSimilarity(_medoids_indices);
							if(similarity > best_similarity)
							{
								best_similarity = similarity;
								best_medoid = j;
								wasChange = true;
							}
						}
					}
					_medoids_indices[i] = best_medoid;
					if(old_medoid != best_medoid)
					{
						_isMedoid[old_medoid] = false;
						_isMedoid[best_medoid] = true;
					}
				}
				iteration++;
				wasChange = false;
			}//while(wasChange)
			cout << "Result medoids: ";
			PrintVector(_medoids_indices);
			cout << endl <<  "Similarity: " << best_similarity << endl;
			cout << "Done" << endl;
		}

		void Kmedoids::NormalizeMatrix()
		{
			//weight matrix
			//<zmiany wprowadzone przez Jacka przy zmianie metody TransformMatrix>
			this->_cmp_function->WeightMatrixCopy();
			this->_matrix = this->_cmp_function->GetMatrix();
			//</zmiany wprowadzone przez Jacka przy zmianie metody TransformMatrix>

			using namespace smartcomparator::weights;

			//normalize matrix
			WeightFeaturePtr weight = WeightFeaturePtr(new NormalizeWeight(this->_matrix));
			MatrixTransformer transformer(weight);
			transformer.Transform();
		}

		void Kmedoids::InitMedoids()
		{
			srand(_seed);

			for(size_t i = 0; i < _medoids_no; i++)
			{
				size_t index = rand() % _rows;
				while(_isMedoid[index])
				{
					index = rand() % _rows;
				}
				_medoids_indices.push_back(index);
				_isMedoid[index] = true;
			}
		}

		double Kmedoids::CountSimilarity(const vector<size_t> & medoids)
		{
			ClusterMap clusters;
			for(size_t i = 0; i < _medoids_no; ++i)
				clusters.insert( std::make_pair(i, std::vector<ClusterMember>() ) );

			double sum = 0, max = 0;
			size_t i, j, index;

			using namespace boost::posix_time;
			ptime start = microsec_clock::local_time();
			time_duration total_time;

			cout << "Searching for group" << endl;
			for(i = 0; i < _rows; i++)
			{
				if(_isMedoid[i])
					continue; //ok?
				max = index = 0;
				for(j = 0; j < medoids.size(); j++)
				{
					double sim;
					SimilarityMap::iterator iter = _simMatrix.find(make_pair(i, medoids[j]));
					if(iter == _simMatrix.end())
					{
						iter = _simMatrix.find(make_pair(medoids[j], i));
						if(iter == _simMatrix.end())
						{
							//sim = 0.1;
							//cout << "Compare " << i << " " << medoids[j] << endl;
							sim = _cmp_function->Compare(i, medoids[j]);
							_simMatrix.insert(std::make_pair( std::make_pair(i, medoids[j]), sim ));
						}
						else
						{
							//cout << "Nothing to compare 2 " << i << " " << medoids[j] << endl;
							sim = iter->second;
						}
					}
					else
					{
						//cout << "Nothing to compare 1 " << i << " " << medoids[j] << endl;
						sim = iter->second;
					}

					if(sim > max)
					{
						max = sim;
						index = j;
					}
				}
				clusters[index].push_back(ClusterMember(i, max));

				//Print progress every 5 sec.
//				ptime end = microsec_clock::local_time();
//				time_duration len = end-start;
//				if(len.total_milliseconds() > 5000)
//				{
//					total_time += len;
//					long total_ms = total_time.total_milliseconds();
//					start = microsec_clock::local_time();
//					cout << "Row: " << i << " assigned to cluster" << endl;
//					std::cout.flush();
//				}
			}
			cout << "Found" << endl;
			sum = this->CountSquareErrors(clusters);
			return sum;
		}

		double Kmedoids::CountSquareErrors(ClusterMap & clusters)
		{
			ClusterMap::iterator iter = clusters.begin();

			using namespace boost::posix_time;
			ptime start = microsec_clock::local_time();
			time_duration total_time;

			double result = 0;
			for(; iter != clusters.end(); ++iter)
			{
				double sum = 0;
				vector<ClusterMember>::iterator iter2 = iter->second.begin();
//				cout << "Entering the loop for: " << ++i << " time" << endl;
				for( ; iter2 != iter->second.end(); ++iter2)
				{
					sum += (*iter2).similarity * (*iter2).similarity;
				}
				if (iter->second.size() > 0)
				{
					sum /= iter->second.size();
//				cout << "Similarity for cluster " << iter->first << " counted, no of rows in cluster: " << iter->second.size() << endl;
					result += sum;
				}
			}
			return result;
		}

		size_t Kmedoids::GetClusterNumber(size_t row) const
		{
			if(row < 0 || row > _matrix->NumberOfRows()-1)
				throw runtime_error("Wrong row number");

			//if(_isMedoid[row])
			//	return row; //correct to: indeks wartosci row w tablicy medoids_indices

			double max = 0;
			size_t index = 0;
			for(size_t j = 0; j < _medoids_indices.size(); j++)
			{
				double sim = _cmp_function->Compare(row, _medoids_indices[j]);
				if(sim > max)
				{
					max = sim;
					index = j;
				}
			}
			return index;
		}

		size_t Kmedoids::GetRows() const
		{
			return _rows;
		}

		void Kmedoids::PrintVector(vector<size_t> & v)
		{
			std::copy(v.begin(), v.end(), std::ostream_iterator<size_t>(std::cout," "));
			cout << endl;
		}
	}
}
