/*************************************************************************
* Project: Library of Evolutionary Algoriths
*************************************************************************
* Author: Changhe Li & Ming Yang
* Email: changhe.lw@google.com Or yangming0702@gmail.com
* Language: C++
*************************************************************************
*  This file is part of EAlib. This library is free software;
*  you can redistribute it and/or modify it under the terms of the
*  GNU General Public License as published by the Free Software
*  Foundation; either version 2, or (at your option) any later version.
*************************************************************************/
// Created: 21 September 2011
// Last modified:
#ifndef CLUSTERING_H
#define CLUSTERING_H

#include "Group.h"

template<class T>
class Cluster{
public:
	Group<T> *mp_group;
	int m_number;
	int m_initialNumber;
	double **mpp_dis;
public:
	Cluster();
	Cluster( T *p,const int num);
	void initialize(const Cluster &clst);
	void initialize( T *p,const int num);
	~Cluster();
	virtual void allocateMemory(const int rNum, const int rInitialNum);
	virtual void freeMemory();

	Cluster &operator =(const Cluster &clst);
	void computeDistMatrix();
	void roughClustering();
	double computerGroupDist(const int from,const int to);
	bool isNearestGroup(int & g1, int & g2);
	void deleteGroup(const int id);

};

// implementation of Clustering class
template<class T>
Cluster<T>::Cluster():m_initialNumber(0){
	m_number=0;
	mp_group=0;
	mpp_dis=0;
}

template<class T>
void Cluster<T>::allocateMemory(const int rNum, const int rInitialNum){
    mp_group=new Group<T>[rNum];
    mpp_dis=new double*[rInitialNum];
	for(int i=0;i<rInitialNum;i++)
		mpp_dis[i]=new double[rInitialNum];
}

template<class T>
Cluster<T>::Cluster(T *p, const int num):m_number(num),m_initialNumber(num){
	m_number=num;
	allocateMemory(m_number,m_initialNumber);

	for(int i=0;i<m_number;i++)
		mp_group[i].initialize(p[i],i);

	computeDistMatrix();
}
template<class T>
void Cluster<T>::initialize( T *p,const int num){
	freeMemory();

	m_initialNumber=num;
	m_number=num;

	allocateMemory(m_number,m_initialNumber);

	for(int i=0;i<m_number;i++)
		mp_group[i].initialize(p[i],i);
	computeDistMatrix();
}
template<class T>
void Cluster<T>::initialize(const Cluster &clst){
	if(clst.m_initialNumber==0) return;

	m_initialNumber=clst.m_initialNumber;
	m_number=clst.m_number;

	allocateMemory(m_number,m_initialNumber);

	for(int i=0;i<m_number;i++)
		mp_group[i].initialize(clst.mp_group[i]);

	for(int i=0;i<m_initialNumber;i++)
		for(int j=0;j<m_initialNumber;j++)
			mpp_dis[i][j]=clst.mpp_dis[i][j];
}
template<class T>
Cluster<T>::~Cluster(){
	freeMemory();
}
template<class T>
void Cluster<T>::computeDistMatrix(){
	// only called by constructor
	for(int i=0;i<m_initialNumber;i++){
		mpp_dis[i][i]=-1; //infinite large
		for(int j=0;j<i;j++)
			mpp_dis[i][j]=mpp_dis[j][i]=mp_group[i].m_center.getDistance(mp_group[j].m_center);
	}

}
template<class T>
void Cluster<T>::roughClustering(){
	while(1){
		int i=0;
		while(i<m_number&&mp_group[i].m_number>1) i++;
		if(i==m_number) break;
		int g1,g2;
		if(!isNearestGroup(g1,g2)) break;
		mp_group[g2].merge(mp_group[g1]);
		deleteGroup(g1);
	}
	for(int i=0;i<m_number;i++) mp_group[i].calculateRadius();
}
template<class T>
void Cluster<T>::deleteGroup(const int id){
	int num=m_number-1;
	if(num<1){
		freeMemory();
		return;
	}
	Group<T> *g=new Group<T>[num];
	for(int i=0,j=0;i<num;i++,j++){
		if(j!=id){
			g[i].initialize(mp_group[j].m_number,i);
			g[i]=mp_group[j];
		}else
			i--;
	}
	delete [] mp_group;
	mp_group=g;
	m_number--;
}
template<class T>
double Cluster<T>::computerGroupDist(const int from,const int to){
	return mp_group[from].m_center.getDistance(mp_group[to].m_center);
}
template<class T>
bool Cluster<T>::isNearestGroup(int & g1, int & g2){
	
	if(m_number<=1) {
	 g1=0;
	 g2=0;
	 return false;
	}
	bool flag_fail=true;
	double l,u,Min_dis=0,dist;
	for(int i=0;i<Global::g_dimNumber;i++){
        Global::gp_problem->getSearchRange<double>(l,u,i);
        Min_dis+=(u-l)*(u-l);
    }
    Min_dis=sqrt(Min_dis);

	for(int i=0;i<m_number;i++){
		//if(mp_group[i].m_number>1) continue;// can't merge two mp_groups whose m_number are both greater than 1
		for(int j=0;j<m_number;j++){
				if(j==i) continue;
				if(mp_group[i].m_number+mp_group[j].m_number>Global::g_subSize) continue;
				dist=computerGroupDist(i,j);
				if(Min_dis>dist){
					Min_dis=dist;
					g1=i;
					g2=j;
					flag_fail=false;
				}
		}
	}

	if(flag_fail) return false;
	else return true;
}
template<class T>
void Cluster<T>::freeMemory(){
	if(m_number>0){
		delete [] mp_group;
		mp_group=0;
		for(int i=0;i<m_initialNumber;i++){
			delete [] mpp_dis[i];
			mpp_dis[i]=0;
		}
		delete[] mpp_dis;
		mpp_dis=0;
		m_number=0;
		m_initialNumber=0;
	}
}
template<class T>
Cluster<T> &Cluster<T>::operator =(const Cluster<T> &clst){
	if(clst.m_initialNumber==0) return *this;
	freeMemory();
	initialize(clst);
	return *this;
}



#endif // CLUSTERING_H
