/*Implementation of PStep_Merger

It contains the member functions of PStep_Merger and all derived classes

*/

#include "PStep_Merger.h"

//PStep_Merger:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Check whether the CurrentForwardLabel and CurrentBackwardLabel have visited the same locations,
//This is accomplished by backtracking and forward tracking both labels.
bool PStep_Merger::CheckVisited(ForwardLabel &CurrentForwardLabel, BackwardLabel &CurrentBackwardLabel){

	//Obtain the number of customers
	short int NumberOfCustomers = CurrentForwardLabel.NumberOfCustomers;

	//Initialize visited
	bool* Visited = new bool[NumberOfCustomers];
	for (short int i = 0; i < NumberOfCustomers; ++i){
		Visited[i] = false;
	}

	//Backtrack forward label
	//-------------------------------------------------------------------------------------

	//Initialize backtracking of the forward label:
	//Obtain the next forward location
	short int NextForwardLocation = CurrentForwardLabel.LastLocation - 1;

	//Check whether the next forward location is not the depot
	if (NextForwardLocation >= 0){

		//Set the initial locations as visited
		Visited[NextForwardLocation] = true;

		//Perform backtracking of the forward label:
		//Initialize next forward label
		ForwardLabel* NextForwardLabel = &CurrentForwardLabel;
		//Backtrack until all locations will have been forgotten anyway, or the start (or the depot) is found
		while (NextForwardLabel->PreviousLabel != 0 && NextForwardLabel->PreviousLabel->LastLocation != 0){

			//Backtrack, update indicators
			NextForwardLabel = NextForwardLabel->PreviousLabel;
			Visited[NextForwardLabel->LastLocation - 1] = true;

		}//end backtrack when the start is found

	}//end check whether the initial forward location is not the depot

	//Backtrack backwards label
	//-------------------------------------------------------------------------------------

	//Initialize backtracking of the forward label:
	//Obtain the next backward location
	short int PreviousBackwardLocation = CurrentBackwardLabel.FirstLocation - 1;

	//Check whether the previous backward location is not the depot
	if (PreviousBackwardLocation >= 0){

		//Check whether this location has already been visited
		if (Visited[PreviousBackwardLocation]){
			//clean
			delete[]Visited;

			return false;
		}
		//Otherwise this location has not yet been visited

		//Perform backtracking of the backward label:
		//Initialize previous backward label
		BackwardLabel* PreviousBackwardLabel = &CurrentBackwardLabel;
		//Backtrack until all locations will have been forgotten anyway, or the end (or the depot) is found
		while (PreviousBackwardLabel->NextLabel != 0 && PreviousBackwardLabel->NextLabel->FirstLocation != 0){

			//Backtrack, update indicators
			PreviousBackwardLabel = PreviousBackwardLabel->NextLabel;
			if (Visited[PreviousBackwardLabel->FirstLocation-1]){
				//clean
				delete[]Visited;

				return false;
			}

		}//end backtrack until the start is found

	}//end check whether the initial backward location is not the depot

	//clean
	delete[]Visited;

	return true;

}

//PStep_ZeroLoadMerger:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Merge functions:

//This merge function checks whether the combined load of the forward and backward labels 
//do not exceed capacity and whether there is no location visited by both labels.
//If this is indeed not the case, a new PStep_MergLabel is created and added to the list MergeLabels.
//The starting load is set to 0.
void PStep_ZeroLoadMerger::Merge(ForwardLabel &CurrentForwardLabel, BackwardLabel &CurrentBackwardLabel){

	//Compute combined load
	double CombinedLoad = CurrentForwardLabel.Load + CurrentBackwardLabel.Load;
	//Check whether the combined load does not exceed capacity
	if (CombinedLoad <= CapacityPlusTolerance && CheckVisited(CurrentForwardLabel, CurrentBackwardLabel)){
		//Merge
		MergeLabels.emplace_front(CurrentForwardLabel, CurrentBackwardLabel, 0, CombinedLoad);
		++NumberOfMergeLabels;
	}

}

//PStep_MaxLoadMerger:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Merge functions:

//This merge function checks whether the combined load of the forward and backward labels 
//do not exceed capacity and whether there is no location visited by both labels.
//If this is indeed not the case, a new PStep_MergLabel is created and added to the list MergeLabels.
//The starting load is set to its maximum.
void PStep_MaxLoadMerger::Merge(ForwardLabel &CurrentForwardLabel, BackwardLabel &CurrentBackwardLabel){

	//Compute combined load
	double CombinedLoad = CurrentForwardLabel.Load + CurrentBackwardLabel.Load;
	//Check whether the combined load does not exceed capacity
	if (CombinedLoad <= CapacityPlusTolerance && CheckVisited(CurrentForwardLabel, CurrentBackwardLabel)){
		//Merge
		MergeLabels.emplace_front(CurrentForwardLabel, CurrentBackwardLabel, Capacity - CombinedLoad, CombinedLoad);
		++NumberOfMergeLabels;
	}

}

//PStep_NGZeroLoadMerger:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Merge functions:

//This merge function checks whether the combined load of the forward and backward labels 
//do not exceed capacity and whether there is no location visited by both labels.
//If this is indeed not the case, a new PStep_MergLabel is created and added to the list MergeLabels.
//The starting load is set to 0.
void PStep_NGZeroLoadMerger::Merge(ForwardLabel &CurrentForwardLabel, BackwardLabel &CurrentBackwardLabel){

	//Compute combined load
	double CombinedLoad = CurrentForwardLabel.Load + CurrentBackwardLabel.Load;
	//Check whether the combined load does not exceed capacity
	if (CombinedLoad <= CapacityPlusTolerance && CheckVisited(CurrentForwardLabel,CurrentBackwardLabel)){
		//Merge
		MergeLabels.emplace_front(CurrentForwardLabel, CurrentBackwardLabel, 0, CombinedLoad);
		++NumberOfMergeLabels;
	}

}

//Check whether the CurrentForwardLabel and CurrentBackwardLabel have visited the same locations,
//in the ng sense. This is accomplished by backtracking and forward tracking both labels.
bool PStep_NGZeroLoadMerger::CheckVisited(ForwardLabel &CurrentForwardLabel, BackwardLabel &CurrentBackwardLabel){

	//Obtain the number of customers
	short int NumberOfCustomers = CurrentForwardLabel.NumberOfCustomers;

	//Initialize list of forward and backward visited locations (in the ng sense)
	bool* ForwardVisited = new bool[NumberOfCustomers];
	bool* BackwardVisited = new bool[NumberOfCustomers];
	for (short int i = 0; i < NumberOfCustomers; ++i){
		ForwardVisited[i] = false;
		BackwardVisited[i] = false;
	}

	//Backtrack forward label
	//-------------------------------------------------------------------------------------

	//Initialize backtracking of the forward label:
	//Obtain the next forward location
	short int NextForwardLocation = CurrentForwardLabel.LastLocation - 1;
	//Initialize not in neighbourhood of the next forward location
	bool* NextForwardNotInNeighbourhood;

	//Check whether the next forward location is not the depot
	if (NextForwardLocation >= 0){

		//Set the initial locations as visited
		ForwardVisited[NextForwardLocation] = true;
		//Obtain not in neighbourhood of the next forward location
		NextForwardNotInNeighbourhood = NotInNeighbourhood[NextForwardLocation];

		//Initialize list of forward and backward locations that will not be forgotten 
		//(in the ng sense), or are already visited.
		std::list<short int> ForwardNotForgottenLocations;
		std::list<short int> BackwardNotForgottenLocations;
		for (short int i = 0; i < NumberOfCustomers; ++i){
			//Check whether i is in the neighborhood of the next forward location
			if (!NextForwardNotInNeighbourhood[i]){
				//Do not yet forget i
				ForwardNotForgottenLocations.push_back(i);
			}
		}

		//Perform backtracking of the forward label:
		//Initialize next forward label
		ForwardLabel* NextForwardLabel = &CurrentForwardLabel;
		//Backtrack until all locations will have been forgotten anyway, or the start (or the depot) is found
		while (!ForwardNotForgottenLocations.empty() && NextForwardLabel->PreviousLabel != 0 && NextForwardLabel->PreviousLabel->LastLocation != 0){

			//Backtrack, update indicators
			NextForwardLabel = NextForwardLabel->PreviousLabel;
			NextForwardLocation = NextForwardLabel->LastLocation - 1;
			NextForwardNotInNeighbourhood = NotInNeighbourhood[NextForwardLocation];

			//Initialize start and end of ForwardNotForgottenLocations
			auto CurrentNotForgottenLocation = ForwardNotForgottenLocations.begin();
			auto ForwardNotForgottenLocationsEnd = ForwardNotForgottenLocations.end();
			//Go over the not forgotten locations
			while (CurrentNotForgottenLocation != ForwardNotForgottenLocationsEnd){

				//Check whether the current forgotten location is the next forward location
				if (*CurrentNotForgottenLocation == NextForwardLocation){
					//Set this location as visited
					ForwardVisited[NextForwardLocation] = true;
					//Erase the location from the not forgotten list
					CurrentNotForgottenLocation = ForwardNotForgottenLocations.erase(CurrentNotForgottenLocation);
				}
				//Otherwise check whether the location is not in the neighborhood
				else if (NextForwardNotInNeighbourhood[*CurrentNotForgottenLocation]){
					//Erase the location from the not forgotten list
					CurrentNotForgottenLocation = ForwardNotForgottenLocations.erase(CurrentNotForgottenLocation);
				}
				else{
					//Otherwise iterate the current forgotten location
					++CurrentNotForgottenLocation;
				}

			}//end go over the not forgotten locations

		}//end backtrack while not all locations will have been forgotten anyway, or the start is found

	}//end check whether the initial forward location is not the depot

	//Backtrack backwards label
	//-------------------------------------------------------------------------------------

	//Initialize backtracking of the forward label:
	//Obtain the next backward location
	short int PreviousBackwardLocation = CurrentBackwardLabel.FirstLocation - 1;
	//Initialize not in neighbourhood of the next backward location
	bool* PreviousBackwardNotInNeighbourhood;

	//Check whether the previous backward location is not the depot
	if (PreviousBackwardLocation >= 0){

		//Set the initial locations as visited
		BackwardVisited[PreviousBackwardLocation] = true;
		//Obtain not in neighbourhood of the previous backward locations
		PreviousBackwardNotInNeighbourhood = NotInNeighbourhood[PreviousBackwardLocation];

		//Initialize list of backward locations that will not be forgotten 
		//(in the ng sense), or are already visited.
		std::list<short int> BackwardNotForgottenLocations;
		for (short int i = 0; i < NumberOfCustomers; ++i){
			//Check whether i is not in the neighborhood of the next backward location
			if (!PreviousBackwardNotInNeighbourhood[i]){
				//Do not yet forget i
				BackwardNotForgottenLocations.push_back(i);
			}
		}

		//Perform backtracking of the backward label:
		//Initialize previous backward label
		BackwardLabel* PreviousBackwardLabel = &CurrentBackwardLabel;
		//Backtrack until all locations will have been forgotten anyway, or the end (or the depot) is found
		while (!BackwardNotForgottenLocations.empty() && PreviousBackwardLabel->NextLabel != 0 && PreviousBackwardLabel->NextLabel->FirstLocation != 0){

			//Backtrack, update indicators
			PreviousBackwardLabel = PreviousBackwardLabel->NextLabel;
			PreviousBackwardLocation = PreviousBackwardLabel->FirstLocation - 1;
			PreviousBackwardNotInNeighbourhood = NotInNeighbourhood[PreviousBackwardLocation];

			//Initialize start and end of BackwardNotForgottenLocations
			auto CurrentNotForgottenLocation = BackwardNotForgottenLocations.begin();
			auto BackwardNotForgottenLocationsEnd = BackwardNotForgottenLocations.end();
			//Go over the not forgotten locations
			while (CurrentNotForgottenLocation != BackwardNotForgottenLocationsEnd){

				//Check whether the current forgotten location is the previous backward location
				if (*CurrentNotForgottenLocation == PreviousBackwardLocation){
					//Set this location as visited
					BackwardVisited[PreviousBackwardLocation] = true;
					//Erase the location from the not forgotten list
					CurrentNotForgottenLocation = BackwardNotForgottenLocations.erase(CurrentNotForgottenLocation);
				}
				//Otherwise check whether the location is not in the neighborhood
				else if (PreviousBackwardNotInNeighbourhood[*CurrentNotForgottenLocation]){
					//Erase the location from the not forgotten list
					CurrentNotForgottenLocation = BackwardNotForgottenLocations.erase(CurrentNotForgottenLocation);
				}
				else{
					//Otherwise iterate the current forgotten location
					++CurrentNotForgottenLocation;
				}

			}//end go over the not forgotten locations

		}//end backtrack while not all locations will have been forgotten anyway, or the start is found

	}//end check whether the initial backward location is not the depot

	//Check whether the current forward and backward label do not visit the same locations:
	//-------------------------------------------------------------------------------------
	
	//Obtain end point
	bool* ForwardVisitedEnd = &ForwardVisited[CurrentForwardLabel.NumberOfCustomers];
	//Initialize pointer to Visited of Backwardlabels
	bool* CurrentBackwardVisited = BackwardVisited;
	//Go over all customers
	for (bool* CurrentForwardVisited = ForwardVisited; CurrentForwardVisited != ForwardVisitedEnd; ++CurrentForwardVisited){
		//Check if both labels have visited the same location
		if (*CurrentForwardVisited && *CurrentBackwardVisited){
			//clean
			delete[]ForwardVisited;
			delete[]BackwardVisited;
			
			return false;
		}
		//Update pointer to Visited of BackwardLabel
		++CurrentBackwardVisited;
	}

	//clean
	delete[]ForwardVisited;
	delete[]BackwardVisited;

	return true;

}

//PStep_NGMaxLoadMerger:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Merge functions:

//This merge function checks whether the combined load of the forward and backward labels 
//do not exceed capacity and whether there is no location visited by both labels.
//If this is indeed not the case, a new PStep_MergLabel is created and added to the list MergeLabels.
//The starting load is set to its maximum.
void PStep_NGMaxLoadMerger::Merge(ForwardLabel &CurrentForwardLabel, BackwardLabel &CurrentBackwardLabel){

	//Compute combined load
	double CombinedLoad = CurrentForwardLabel.Load + CurrentBackwardLabel.Load;
	//Check whether the combined load does not exceed capacity
	if (CombinedLoad <= CapacityPlusTolerance && CheckVisited(CurrentForwardLabel, CurrentBackwardLabel)){
		//Merge
		MergeLabels.emplace_front(CurrentForwardLabel, CurrentBackwardLabel, Capacity - CombinedLoad, CombinedLoad);
		++NumberOfMergeLabels;
	}

}