/*
    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 "Kmeans.h"

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

namespace clustering
{
	namespace kmeans
	{
		Kmeans::Kmeans(size_t clusters_no, Matrices::SuperMatrixPtr matrix, CompareFunctionPtr cmp_fun, size_t seed, double epsilon):
				_seed(seed), _clusters_no(clusters_no), _epsilon(epsilon), _matrix(matrix), _simFun(true, false) //check initialization of simFun
		{
			_rows = _matrix->NumberOfRows();
			_columns = _matrix->NumberOfColumns();
			_cmp_function = cmp_fun;
			_clustersToSave = vector<int>(_rows);
		}

		void Kmeans::StartClustering()
		{
			cout << "Clustering in progress..." << endl;
			cout << "No of clusters: " << _clusters_no << " epsilon: " << _epsilon << endl;
			if (_cmp_function != NULL)
				WeightMatrix();
			NormalizeMatrix();
			InitClusters();

			double sim= 0, oldSim = 0;

			bool clusteringFinished = false;

			size_t iteration = 0;
			while(!clusteringFinished)
			{
				cout << "Iteration " << ++iteration << endl;
				oldSim = sim;
				sim = CountSimilarities();
				cout << "New sim: " << sim << " oldSim " << oldSim << " diff: " << (sim-oldSim) << endl;
				if (sim - oldSim > _epsilon)
					FindNewCentroids();
				else
					clusteringFinished = true;
			}
			cout << "Finished" << endl;
		}

		void Kmeans::WeightMatrix()
		{
			//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>
		}

		void Kmeans::NormalizeMatrix()
		{
			using namespace smartcomparator::weights;

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

		void Kmeans::InitClusters()
		{
			srand(_seed);
			vector<size_t> indices;
			for(size_t i = 0; i < _clusters_no; i++)
			{
				size_t index = rand() % _rows;
				while ( find(indices.begin(), indices.end(), index) != indices.end() )
				{
					index = rand() % _rows;
				}
				_centroids.push_back(_matrix->GetRow(index));
				indices.push_back(index);
			}
			cout << "Clusters init finished" << endl;
		}

		double Kmeans::CountSimilarities()
		{
			_clusters.clear();
			for(size_t i = 0; i < _clusters_no; ++i)
				_clusters.insert( std::make_pair(i, std::vector<ClusterMember>() ) );
			vector<double> squares = vector<double>(_clusters_no); //sums of squares of similarities for each cluster
			double maxSim;
			int index; //index of most similar centroid

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

			for(size_t i = 0; i < _rows; ++i)
			{
				CompressedVectorPtr currentRow = _matrix->GetRow(i);
				CentroidsVector::iterator iter = _centroids.begin();
				index = 0;
				maxSim = 0;
				double sim;
				for(size_t j = 0; iter != _centroids.end(); ++iter, ++j)
				{
					sim = _simFun.CountSimilarity(*currentRow, **iter);

					if(sim > maxSim)
					{
						maxSim = sim;
						index = j;
					}
				}
				squares[index] += maxSim * maxSim;
				_clusters[index].push_back(ClusterMember(i, maxSim));
				_clustersToSave[i] = index;

				//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 no: " << i << " time: " << total_ms << endl;
//					std::cout.flush();
//				}
			}
			ptime end = microsec_clock::local_time();
			time_duration len = end-start;
			cout << "Similarities count in " << len.total_milliseconds() << " ms" <<  endl;
			return CountSquareError(squares);
		}

		double Kmeans::CountSquareError(vector<double> & errors)
		{
			double sum = 0;
			ClusterMap::iterator iter = _clusters.begin();
			for (; iter != _clusters.end(); ++iter)
			{
				if (iter->second.size() > 0)
				{
					errors[iter->first] /= iter->second.size(); //divide each sum of squares by no of items in cluster
					sum += errors[iter->first];
				}
			}
			return sum;
		}

		void Kmeans::FindNewCentroids()
		{
			ClusterMap::iterator iter = _clusters.begin();

			for (; iter != _clusters.end(); ++iter)
			{
				size_t clusterNo = iter->first;
				vector<ClusterMember>::iterator iter2 = iter->second.begin();

				CompressedVectorPtr meanVector = CompressedVectorPtr(new CompressedVector(this->_columns));

				for (; iter2 != iter->second.end(); ++iter2)
				{
					CompressedVectorPtr currentRow = _matrix->GetRow(iter2->row_index);
					*meanVector += *currentRow;
				}

				*meanVector /= iter->second.size();

				Measures::NormalizeVector(meanVector);
				_centroids[clusterNo] = meanVector;
			}
			cout << "New centroids found" << endl;
		}

		vector<int> Kmeans::GetClusters() const
		{
			return _clustersToSave;
		}
	}
}
