/*Implementation of PStep_ShortestPathAlgorithm.h

It contains the member functions of PStep_LocalSearchVaryingArcs

*/

#include "PStep_ShortestPathAlgorithm.h"

//PStep_LocalSearchVaryingArcs:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Solve the shortest path problem
//------------------------------------------------------------------------------------
//Use local search algorithm to solve the pricing problem.
//The number of arcs can vary between 1 and a maximum number of arcs and elementarity is respected.
//It applies in case a p-step is created which starts at the depot.
//All identified p-steps with nonegative reduced costs are stored in the forward list CandidatePSteps.
//NOTE:	The function RemoveDoublesCurrentPStep is available to facilitate initializing with a cyclic p-step.
void PStep_LocalSearchVaryingArcs::Run(){

	//Obtain Locations
	std::list<short int>& Locations = CurrentPStep.Locations;

	//Initialize the number of arcs on the current p-step
	short int CurrentNumberOfArcs;

	//Check whether an initial p-step was provided
	if (InitialPStepProvided){
		//An initial p-step is provided, count the number of arcs.
		CurrentNumberOfArcs = Locations.size() - 1;
	}
	//Check whether the arc source-sink is in use
	else if (ArcInUse[Source][Sink]){

		//No initial p-step was provided.
		//Initialize a p-step including only the source and sink.

		//Add source and sink:
		Locations.push_back(Source);
		Locations.push_back(Sink);
		//Initialize current demand
		CurrentDemand = 0;
		if (Source > 0){
			CurrentDemand += Demand[Source - 1];
		}
		if (Sink > 0){
			CurrentDemand += Demand[Sink - 1];
		}
		//Update the reduced cost constant by adding the reduced arc cost from source to sink
		CurrentReducedCosts = ReducedCostConstant + ReducedArcCosts[Source][Sink];

		//Set the current number of arcs
		CurrentNumberOfArcs = 1;

	}
	else{

		//TODO: the algorithm does not work for the 0-0 pricing problem

		//We failed to initialize
		return;
	}

	//Check whether the maximum number of arcs is greater than 1
	if (MaxNumberOfArcs > 1){

		//Initialize the outside customers
		InitializeOutsideCustomers();

		//Initialize local search:

		//Initialize the current best customer to be inserted by Swap
		std::vector<short int>::iterator BestSwapInsertCustomer;
		//Initialize the current best customer to be removed by Swap,
		//the customer after this iterator is removed
		std::list<short int>::iterator BestSwapRemoveCustomer;

		//Initialize the current best customer to be inserted by SwapIntraPStep
		std::list<short int>::iterator BestSwapIntraPStepFirstCustomer;
		//Initialize the current best customer to be removed by Swap,
		//the customer after this iterator is removed
		std::list<short int>::iterator BestSwapIntraPStepSecondCustomer;

		//Initialize the current best customer to be inserted
		std::vector<short int>::iterator BestInsertCustomer;
		//Initialize best insert position, the current best customer is inserted before this position
		std::list<short int>::iterator BestInsertPosition;

		//Initiliaze the current best customer ot be removed
		std::list<short int>::iterator BestRemoveCustomer;

		//Initialize the current best cost increase is
		double CurrentBestCostIncrease;
		//Initialize the best cost increase of a move
		double MoveBestCostIncrease;

		//Initialize best found move type
		//0: no best type move found.
		//1: The best found move is an insert.
		//2: The best found move is a remove.
		//3: The best found move is a swap.
		//4: The best found move is an intra p-step swap.
		short int BestFoundMoveType;

		//Initialize indicator indicating whether an improvement is found
		bool ImprovementFound = true;

		//Initialize indicator indicating whether the source and sink are not both the depot.
		bool SourceAndSinkAreNotTheDepot = true;
		if (Source == 0 && Sink == 0){
			SourceAndSinkAreNotTheDepot = false;
		}

		//Perform local search until a termination criterion is met
		while (CurrentReducedCosts >= -Tolerance && ImprovementFound){

			//Reset best found move type for this iteration
			BestFoundMoveType = 0;
			//Reset ImprovementFound
			ImprovementFound = false;

			//Check whether the current p-step only has one arc
			if (CurrentNumberOfArcs == 1){
				//The current p-step has only one arc.
				//The only possible move is an insert.

				//Find best insert
				if (Insert(BestInsertCustomer, BestInsertPosition, CurrentBestCostIncrease)){
					//Set best cost move type.
					//Note that the CurrentBestCostIncrease is already set (see third argument of Insert above).
					BestFoundMoveType = 1;
				}

			}
			else{
				//The current p-step contains more than one arc.

				//If the number of arcs is greater than 2 or the source and the sink are not
				//both the depotthe source and sink are, find best remove
				if (CurrentNumberOfArcs > 2 || SourceAndSinkAreNotTheDepot){
					//Find the best remove.
					if (Remove(BestRemoveCustomer, CurrentBestCostIncrease)){
						//Set best found move type to remove
						BestFoundMoveType = 2;
					}
				}

				//Find best swap.
				if (Swap(BestSwapInsertCustomer, BestSwapRemoveCustomer, MoveBestCostIncrease)){
					//Check if the best swap is better than the best move found so far
					if (BestFoundMoveType == 0 || MoveBestCostIncrease < CurrentBestCostIncrease){
						//Set swap as current best
						CurrentBestCostIncrease = MoveBestCostIncrease;
						BestFoundMoveType = 3;
					}
				}

				//If the number of arcs is more than 2, perform an intra p-step swap
				if (CurrentNumberOfArcs > 2 && SwapIntraPStep(BestSwapIntraPStepFirstCustomer, BestSwapIntraPStepSecondCustomer, MoveBestCostIncrease)){
					//Check if the best intra p-step swap is the best move found so far
					if (BestFoundMoveType == 0 || MoveBestCostIncrease < CurrentBestCostIncrease){
						//Set intra p-step swap as current best
						CurrentBestCostIncrease = MoveBestCostIncrease;
						BestFoundMoveType = 4;
					}
				}

				//If the number of arcs is less than the maximum, perform an insert
				if (CurrentNumberOfArcs < MaxNumberOfArcs && Insert(BestInsertCustomer, BestInsertPosition, MoveBestCostIncrease)){
					//Check if the best insert is the best move found so far
					if (BestFoundMoveType == 0 || MoveBestCostIncrease < CurrentBestCostIncrease){
						//Set insert as current best
						CurrentBestCostIncrease = MoveBestCostIncrease;
						BestFoundMoveType = 1;
					}
				}

			}//end check whether the current p-step has more than one arc

			//Check whether an improvement has been found
			if (BestFoundMoveType > 0 && CurrentBestCostIncrease < -Tolerance){

				//Check which type of move is the best
				if (BestFoundMoveType == 1){
					//The best move is an insert.

					//Add the best customer at the insert position
					Locations.insert(BestInsertPosition, *BestInsertCustomer);
					//Update the corresponding load
					CurrentDemand += Demand[(*BestInsertCustomer) - 1];
					//Update the remaining customers
					OutsideCustomers.erase(BestInsertCustomer);

					//Update the current number of arcs
					++CurrentNumberOfArcs;

				}
				else if (BestFoundMoveType == 2){
					//The best move is a remove.

					//Update the remaining customers
					OutsideCustomers.push_back(*BestRemoveCustomer);
					//Update load
					CurrentDemand -= Demand[*BestRemoveCustomer - 1];
					//Remove the customer
					Locations.erase(BestRemoveCustomer);

					//Update the current number of arcs
					--CurrentNumberOfArcs;

				}
				else if (BestFoundMoveType == 3){
					//The best move is a swap.

					//Obtain customer to be inserted
					short int InsertedCustomer = *BestSwapInsertCustomer;
					//Remove customer
					*BestSwapInsertCustomer = *BestSwapRemoveCustomer;
					//Insert customer
					*BestSwapRemoveCustomer = InsertedCustomer;
					//Update demand, note that BestSwapInsertedCustomer now points to the removed customer
					CurrentDemand += DemandIncrease[InsertedCustomer - 1][*BestSwapInsertCustomer - 1];

				}
				else if (BestFoundMoveType == 4){
					//The best move is an intra p-step swap.

					//Obtain first customer
					short int FirstCustomer = *BestSwapIntraPStepFirstCustomer;
					//Put second customer in the position of the first
					*BestSwapIntraPStepFirstCustomer = *BestSwapIntraPStepSecondCustomer;
					//Put first customer in the position of the second
					*BestSwapIntraPStepSecondCustomer = FirstCustomer;

				}

				//Update reduced costs
				CurrentReducedCosts += CurrentBestCostIncrease;
				//Update indicator indicating that an improvement has been found
				ImprovementFound = true;

			}//end check whether an improvement has been found

		}//end local search

	}//end check whether the maximum number of arcs is greater than 1

	//Check whether a negative reduced cost p-step is found
	if (CurrentReducedCosts < -Tolerance){
		//A negative reduced cost p-step is found

		//Set costs, starting load and total load of the current p-step
		SetCurrentPStepCostAndLoads();

		//Check whether a candidate p-step has already been identified for the current pricing problem
		if (CandidatePSteps.begin() == CandidatePSteps.end()){
			//Add the current pricing problem to the list of solved pricing problems
			SolvedPricingProblems.push_front(&PricingProblem);
		}

		//Add p-step to list of candidates
		CandidatePSteps.push_front(CurrentPStep);

	}

}

//Local search functions
//------------------------------------------------------------------------------------

//Remove double customers from the current p-step.
//For customers that are visited multiple times, the first is maintained and
//the others are removed, unless a customer is visited as sink, in this case,
//the sink is maintained and the others are removed.
//It returns false if the current p-step could not be transformed into an elementary path.
//In that case, the current p-step might be altered.
bool PStep_LocalSearchVaryingArcs::RemoveDoublesCurrentPStep(){

	//Check whether there are customers to be removed
	if (MaxNumberOfArcs < 3){
		return true;
	}

	//Obtain current locations
	std::list<short int>& Locations = CurrentPStep.Locations;
	//Obtain Source and Sink
	Source = PricingProblem.Source;

	//Initialize indicators indicating whether a location has been visited already
	bool* Visited = new bool[NumberOfLocations];
	//Set all indicators to false
	for (short int i = 0; i < NumberOfLocations; ++i){
		Visited[i] = false;
	}

	//Set source and sink to visited
	Visited[Source] = true;
	Visited[Sink] = true;

	//Obtain iterator to previous and current and next location.
	auto PreviousLocation = Locations.begin();
	auto CurrentCustomer = PreviousLocation;
	++CurrentCustomer;
	auto NextLocation = CurrentCustomer;
	++NextLocation;

	//Go over all locations
	for (; NextLocation != Locations.end(); ++NextLocation){
		//Check if the location has already been visited or it is the depot
		if (Visited[*CurrentCustomer]){
			//Remove the current customer from the p-step:

			//Check whether the customer can be removed,
			//i.e., whether the required arc is in use
			if (ArcInUse[*PreviousLocation][*NextLocation]){
				//Update demand
				CurrentDemand -= Demand[*CurrentCustomer - 1];
				//Update costs
				CurrentReducedCosts += ReducedArcCosts[*PreviousLocation][*NextLocation] - ReducedArcCosts[*PreviousLocation][*CurrentCustomer] - ReducedArcCosts[*CurrentCustomer][*NextLocation];
				//Remove customer
				Locations.erase(CurrentCustomer);
			}
			else{
				//The location cannot be removed
				return false;
			}

		}
		else{
			//Update Visited
			Visited[*CurrentCustomer] = true;
			//Update indicators
			PreviousLocation = CurrentCustomer;
		}
		//Update indicators
		CurrentCustomer = NextLocation;
	}

	//clean
	delete[]Visited;

	return true;
}

//Find the best remove in CurrentPStep
//The best removed customer is stored as the reference CurrentBestCustomer to CurrentPStep.Locations.
//Location 0 is the depot and is never considered for removal, nor are the source and sink.
//The best cost increase is stored in CurrentBestCostIncrease.
//We aim for the lowest cost increase, ideally negative, i.e., a decrease.
//If no feasible insert is found the function outputs false.
//NOTE: It is assumed that the current p-step contains at least 3 locations.
bool PStep_LocalSearchVaryingArcs::Remove(std::list<short int>::iterator& CurrentBestCustomer, double& CurrentBestCostIncrease){

	//Obtain locations
	std::list<short int>& Locations = CurrentPStep.Locations;

	//Initialize indicator indicating whether a feasible remove has not yet been found
	bool FeasibleRemoveNotYetFound = true;

	//Initialize iterator pointing to the current customer considered for removal.
	//It is initialized as the second location on the p-step
	//Obtain iterator of the current location
	std::list<short int>::iterator CurrentCustomer = Locations.begin();
	++CurrentCustomer;
	//Initialize the location visited before the current customer.
	short int PreviousCustomer = Source;
	//Obtain iterator to the location after the current customer
	std::list<short int>::iterator NextLocation = CurrentCustomer;
	++NextLocation;

	//Go over all locations to be removed
	for (; NextLocation != Locations.end(); ++NextLocation){

		//Check whether the required arc for the remove is in use.
		if (ArcInUse[PreviousCustomer][*NextLocation]){

			//Compute the increase in costs of removing the current customer
			double RemoveCost = ReducedArcCosts[PreviousCustomer][*NextLocation] - ReducedArcCosts[PreviousCustomer][*CurrentCustomer] - ReducedArcCosts[*CurrentCustomer][*NextLocation];

			//Check whether the current remove is better than the current best
			if (FeasibleRemoveNotYetFound || RemoveCost < CurrentBestCostIncrease){
				//The current removal is better, update the best
				CurrentBestCostIncrease = RemoveCost;
				CurrentBestCustomer = CurrentCustomer;
				FeasibleRemoveNotYetFound = false;
			}
		}//end check whether the required arc is in use

		//Update previous, current and next locations
		PreviousCustomer = *CurrentCustomer;
		CurrentCustomer = NextLocation;

	}

	return !FeasibleRemoveNotYetFound;

}