#include "POSeqSel.h"

Individual::Individual()
{

}

void POSeqSel::SetConstraint(int k)
{
	constraint = k;
}

void POSeqSel::SetIterationTime(long num)
{
	iterationTime = num;
}
void POSeqSel::SetSize(int n)
{
	this->n = n;
}
void POSeqSel::DOPOSeqSel()
{
	Individual individual;
	tempOptimum.clear();
	int iter = 0;
	population.push_back(individual);//initiate the population with empty action.
	for (int i = 0; i < iterationTime; i++)
	{
		iter++;
		if (iter == constraint*n)
		{
			iter = 0;
			tempOptimum.push_back(FindCurrentOptimum(population));
		}
		//select one individual from population uniformly
		Individual s = population[rand() % population.size()];
		vector<int> s_temp;
		if (replicatedElement)
		{
			s_temp = Mutation_Repetition(s.itemString);
		}
		else
		{
			s_temp = Mutation_NonRepetition(s.itemString);
		}
		Individual currentIndividual;

		currentIndividual.fitness = EvaluateObjective(s_temp);
		currentIndividual.itemString = s_temp;
		vector<Individual> Q;
		vector<int> deleteIndex;
		bool isAddIn = true;
		for (unsigned int j = 0; j < population.size(); j++)
		{
			if (IsDominate(population[j], currentIndividual))
			{
				isAddIn = false;
				break;
			}
		}
		if (isAddIn)
		{
			for (unsigned int k = 0; k < population.size(); k++)
			{
				if (currentIndividual.fitness >= population[k].fitness&&currentIndividual.itemString.size() <= population[k].itemString.size())
				{
					deleteIndex.push_back(k);
				}
			}
			if (deleteIndex.size() > 0)
			{
				int index = 0;
				for (unsigned int p = 0; p < population.size(); p++)
				{
					if (index < deleteIndex.size() && p == deleteIndex[index])
					{
						index++;

					}
					else
					{
						Q.push_back(population[p]);
					}
				}
				population = Q;
				Q.clear();
			}
			population.push_back(currentIndividual);
		}
	}
	//Individual optimum = FindCurrentOptimum(population);
	tempOptimum.push_back(FindCurrentOptimum(population));
	solution=tempOptimum[tempOptimum.size() - 1].itemString;
}

vector<int> POSeqSel::DeleteOneItem(vector<int> itemString, int position)
{
	vector<int>::iterator iteration = itemString.begin();
	for (int i = 0; i < position; i++)
	{
		iteration++;
	}
	itemString.erase(iteration);
	return itemString;
}

vector<int> POSeqSel::InsertOneItem(vector<int> itemString, int position, int item)
{
	vector<int> tempitemString;
	for (unsigned int i = 0; i < itemString.size(); i++)
	{
		if (i == position)
		{
			tempitemString.push_back(item);
		}
		tempitemString.push_back(itemString[i]);
	}
	if (position == itemString.size())
	{
		tempitemString.push_back(item);
	}
	return tempitemString;
}

bool POSeqSel::IsDominate(Individual individual1, Individual individual2)
{
	bool isDominated = false;
	if (individual1.fitness > individual2.fitness&&individual1.itemString.size() <= individual2.itemString.size())
	{
		isDominated = true;
	}
	if (individual1.fitness >= individual2.fitness&&individual1.itemString.size() < individual2.itemString.size())
	{
		isDominated = true;
	}
	return isDominated;
}

Individual POSeqSel::FindCurrentOptimum(vector<Individual> population)
{
	float maxFitness = -1;
	int index = 0;
	for (unsigned int i = 0; i < population.size(); i++)
	{
		if (population[i].fitness > maxFitness&&population[i].itemString.size() <= constraint)
		{
			index = i;
			maxFitness = population[i].fitness;
		}
	}
	return population[index];
}

int POSeqSel::PoissonDistribution()
{
	int k = 0;
	long double p = 1.0, l = exp(-1.0), u = 1.0;
	do
	{
		u = (rand() % 10001) / 10000.0;
		p *= u;
		k++;
	} while (p > l);
	return k - 1;
}

vector<Individual> POSeqSel::ReturnResult()
{
	return tempOptimum;
}

vector<int> POSeqSel::Mutation_Repetition(vector<int> s_temp)
{
	int r = PoissonDistribution();
	for (int k = 0; k < r; k++)
	{
		int isInsert = rand() % 2;
		if (s_temp.size() == 0)
		{
			isInsert = 1;//There is no action in s,just can insert one action.
		}
		if (isInsert == 0)//delete one action from s uniformly
		{
			int deletePosition = rand() % s_temp.size();
			s_temp = DeleteOneItem(s_temp, deletePosition);
		}
		else//insert one action into s uniformly
		{
			int insertActionOrder = rand() % n;
			int insertPosition = rand() % (s_temp.size() + 1);
			s_temp = InsertOneItem(s_temp, insertPosition, insertActionOrder);
		}
	}
	return s_temp;
}

vector<int> POSeqSel::Mutation_NonRepetition(vector<int> s_temp)
{
	vector<int> leftNodes;
	int r = PoissonDistribution();
	for (int k = 0; k < r; k++)
	{
		int isInsert = rand() % 2;
		if (s_temp.size() == 0)
		{
			isInsert = 1;//There is no action in s,just can insert one action.
		}
		if (isInsert == 0)//delete one action from s uniformly
		{
			int deletePosition = rand() % s_temp.size();
			s_temp = DeleteOneItem(s_temp, deletePosition);
		}
		else//insert one action into s uniformly
		{
			leftNodes.clear();
			for (int i = 0; i < n; i++)
			{
				if (!IsAppearedInVector(s_temp, i))
				{
					leftNodes.push_back(i);
				}
			}
			int insertActionOrder = rand() % leftNodes.size();
			int insertPosition = rand() % (s_temp.size() + 1);
			s_temp = InsertOneItem(s_temp, insertPosition, leftNodes[insertActionOrder]);
		}
	}
	return s_temp;
}
//float POSeqSel::EvaluateObjective(vector<int> itemString)
//{
//	//write you code to evaluate the objective.
//	return 0;
//}
//} 
bool POSeqSel::IsAppearedInVector(vector<int> myVector, int num)
{
	for (unsigned int i = 0; i < myVector.size(); i++)
	{
		if (num == myVector[i])
		{
			return true;
		}
	}
	return false;
}

void POSeqSel::SetIsRepetition(bool flag)
{
	replicatedElement = flag;
}
Edge::Edge()
{
	head = 0;
	tail = 0;
}
Edge::Edge(int head, int tail)
{
	this->head = head;
	this->tail = tail;
}