/*
    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.
*/

#ifndef K_MEANS_H
#define K_MEANS_H

#include "matrices_all.h"
#include "comparator_all.h"

namespace clustering
{
	namespace kmeans
	{
		/**
		  * Struct describing cluster member. It contains index of row identifying member and similarity to centroid
		  */
		struct ClusterMember
		{
			size_t row_index;
			/**
			  * Similarity to centroid
			  */
			double similarity;

			ClusterMember(size_t in, double sim):row_index(in), similarity(sim)
			{}
		};

		typedef std::map<size_t, std::vector<ClusterMember> > ClusterMap;
		typedef std::vector<Matrices::CompressedVectorPtr> CentroidsVector;

		/**
		  * Implementation of kmeans clustering algotithm.
		  */
		class Kmeans
		{
		public:

			/**
			  * Constructor. It requires number of medoids, shared pointer to SuperMatrix, seed number
			  */
			Kmeans(size_t clusters_no, Matrices::SuperMatrixPtr matrix, smartcomparator::compare::CompareFunctionPtr cmp_fun, size_t seed, double epsilon);

			/**
			  * Starts clustering process.
			  */
			void StartClustering();

			/**
			  * Returns vector containing numbers of cluster for each row
			  */
			std::vector<int> GetClusters() const;

		private:

			/**
			  * Weight matrix
			  */
			void WeightMatrix();

			/**
			  * Normalizes matrix
			  */
			void NormalizeMatrix();

			/**
			  * Inits centroids vector. It uses random generator with predefined seed.
			  */
			void InitClusters();

			/**
			  * Finds the most similar cetroid for each row
			  */
			double CountSimilarities();

			/**
			  * Counts sum of square errors of each cluster
			  */
			double CountSquareError(std::vector<double> & errors);

			/**
			  * Finds new centroids (mean vectors of all cluster members)
			  */
			void FindNewCentroids();

			//fields

			/**
			  * Seed used to random numbers generation
			  */
			size_t _seed;

			/**
			  * Number of clusters
			  */
			size_t _clusters_no;

			/**
			  * Minimal difference between iterations
			  */
			double _epsilon;

			/**
			  * Vector containing compressed rows representing centroids
			  */
			CentroidsVector _centroids;

			/**
			  * Number of rows in SuperMatrix object
			  */
			size_t _rows;

			/**
			  * Number of columns in SuperMatrix object
			  */
			size_t _columns;

			/**
			  * Shared pointer to SuperMatrix object
			  */
			Matrices::SuperMatrixPtr _matrix;

			/**
			  * Shared pointer to CompareFunction object (used just to weight matrix)
			  */
			smartcomparator::compare::CompareFunctionPtr _cmp_function;

			/**
			  * Map containing pair: number of cluster and vector of it's members
			  */
			ClusterMap _clusters;

			//should this be hardcoded?
			/**
			  * Similarity function used to compare compressed vectors (matrix row with centroid)
			  */
			smartcomparator::simfunctions::LocalCosineSimilarity _simFun;

			/**
			  * vector containing numbers of cluster for each row
			  */
			std::vector<int> _clustersToSave;
		};
	}
}

#endif //K_MEANS_H
