// Sel.cpp

#include <vector>
#include <list>
#include "Sel.h"

namespace az
{
namespace mea
{
namespace sel
{
	//!\brief	sort population, the first 'size' are best ones
	//!\param	pop population
	//!\param	size size of best ones
	//!\return	population
	CPopulationMO& SCrowd::SelectSort(CPopulationMO& pop, unsigned int size)
	{
		if(pop.Size()<=size) return pop;

		unsigned int start, end;

		//Step 1: rank sort
		pop.RankSort();

		//Step 2: find the sub set which "cover" the cut point
		start = end = 0;
		while(end<size)
		{
			start = end;
			while(end<pop.Size() && pop[end].Rank() == pop[start].Rank()) end++;
		}

		//Step 3: sort the sub set
		if(pop[start].IsFeasible() && end > start + 2 && start < size-2)
		{
			unsigned int i,j,k; double interval;

			std::vector<double>			share(end-start);
			std::vector<unsigned int>	index(end-start);
			
			for(i=0; i<(unsigned int)share.size(); i++) share[i] = 0.0;
			
			//calculate the share values
			for(i=0; i<pop.P().FSize(); i++)
			{
				for(j=start; j<end; j++) index[j-start] = j;

				for(j=0; j<(unsigned int)index.size()-1; j++)
					for(k=j+1; k<(unsigned int)index.size(); k++)
						if(pop[index[j]].F(i) > pop[index[k]].F(i))
							std::swap(index[j], index[k]);

				interval =  pop[index[index.size()-1]].F(i) - pop[index[0]].F(i) ;
				for(j=1; j<(unsigned int)index.size()-1; j++) share[index[j]-start] += (pop[index[j+1]].F(i) - pop[index[j-1]].F(i))/interval;
				share[index[0]-start] = MAXDOUBLE;
				share[index[index.size()-1]-start] = MAXDOUBLE;
			}
			
			//sort the sub-population according to the share value
			for(i=start; i<end; i++)
				for(j=i+1; j<end; j++)
					if(share[i-start] < share[j-start])
						pop.Swap(i, j);

			share.clear();
			index.clear();
		}

		return pop;
	}

	//!\brief	select from current population and offspring population
	//!\param	pop combined population
	//!\param	size population size
	//!\return	population
	CPopulationMO& SCrowd::Select(CPopulationMO& pop, unsigned int size)
	{
		if(pop.Size()>size) SelectSort(pop, size).Erase(size);

		return pop;
	}

	/////////////////////////////////////////////////////////////////////////////////////////////////
	//!\brief	sort population, the first 'size' are best ones
	//!\param	pop population
	//!\param	size size of best ones
	//!\return	population
	CPopulationMO& SCrowd2::SelectSort(CPopulationMO& pop, unsigned int size)
	{
		if(pop.Size()<=size) return pop;

		unsigned int start, end;

		//Step 1: rank sort
		pop.RankSort();

		//Step 2: find the sub set which "cover" the cut point
		start = end = 0;
		while(end<size)
		{
			start = end;
			while(end<pop.Size() && pop[end].Rank() == pop[start].Rank()) end++;
		}

		//Step 3: sort the sub set
		if(pop[start].IsFeasible() && end > start + 2 && start < size-2)
		{
			unsigned int i,j,k,de; double interval;

			while(end>size)
			{
				std::vector<double>			share(end-start);
				std::vector<unsigned int>	index(end-start);
				
				for(i=0; i<(unsigned int)share.size(); i++) share[i] = 0.0;
				
				//calculate the share values
				for(i=0; i<pop.P().FSize(); i++)
				{
					for(j=start; j<end; j++) index[j-start] = j;

					for(j=0; j<(unsigned int)index.size()-1; j++)
						for(k=j+1; k<(unsigned int)index.size(); k++)
							if(pop[index[j]].F(i) > pop[index[k]].F(i))
								std::swap(index[j], index[k]);

					interval =  pop[index[index.size()-1]].F(i) - pop[index[0]].F(i) ;
					for(j=1; j<(unsigned int)index.size()-1; j++) share[index[j]-start] += (pop[index[j+1]].F(i) - pop[index[j-1]].F(i))/interval;
					share[index[0]-start] = MAXDOUBLE;
					share[index[index.size()-1]-start] = MAXDOUBLE;
				}
				
				//find the one to delete 
				de = start;
				for(i=start+1; i<end; i++) if(share[i-start] < share[de-start]) de=i;

				//move the one to the end
				pop.Swap(de, end-1);

				share.clear();
				index.clear();

				end--;
			}
		}

		return pop;
	}

	//!\brief	select from current population and offspring population
	//!\param	pop combined population
	//!\param	size population size
	//!\return	population
	CPopulationMO& SCrowd2::Select(CPopulationMO& pop, unsigned int size)
	{
		if(pop.Size()>size) SelectSort(pop, size).Erase(size);

		return pop;
	}

}//namespace sel
} //namespace mea
} //namespace az