/*Implementation of PStep_ShortestPathAlgorithm.h

It contains the member functions of PStep_CompleteBiDirectionalLayeredLabeling

*/

#include "PStep_ShortestPathAlgorithm.h"

//PStep_CompleteBiDirectionalLayeredLabeling:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Continue labeling
//------------------------------------------------------------------------------------

//Continue forward and backward labeling to make a complete forward and backward pass,
//after having run the bi-directional layered labeling algorithm. As such, Labels should
//not be altered before running this algorithm. It makes use of (the second half of the)
//completion bounds. In this labeling algorithm, dominance is only applied between labels
//that have the same end node and have visited exactly the same amount of locations.
//Labels are stored in PricingProblem.
void PStep_CompleteBiDirectionalLayeredLabeling::Run(){

	//Initialization:
	//*************************

	//Obtain Tolerance
	double Tolerance = Dominator.Tolerance;

	//Obtain pricing problem info for easy reference
	short int NumberOfCustomers = PricingProblem.NumberOfCustomers;
	short int Source = PricingProblem.Source;
	short int Sink = PricingProblem.Sink;
	short int MaxNumberOfForwardArcs = PricingProblem.MaxNumberOfForwardArcs;
	short int MaxNumberOfBackwardArcs = PricingProblem.MaxNumberOfBackwardArcs;
	short int NumberOfForwardLayers = PricingProblem.NumberOfForwardLayers;
	short int NumberOfForwardLayersMinusOne = NumberOfForwardLayers - 1;
	short int NumberOfBackwardLayers = PricingProblem.NumberOfBackwardLayers;
	short int NumberOfBackwardLayersMinusOne = NumberOfBackwardLayers - 1;
	bool AllowedToReachSinkEarly = PricingProblem.AllowedToReachSinkEarly;
	double** (&ReducedArcCosts) = PricingProblem.ReducedArcCosts;
	double** (&ForwardCompletionBounds) = PricingProblem.ForwardCompletionBounds;
	double** (&BackwardCompletionBounds) = PricingProblem.BackwardCompletionBounds;

	//Obtain arcs:
	//Initialize support
	std::list<std::list<PStep_Arc>>* TempOutArcs;
	std::list<std::list<PStep_Arc>>* TempInArcs;
	//Check whether a limited set of arcs should be used
	if (UseLimitedArcs){
		//Limited arcs should be used
		TempOutArcs = &PricingProblem.CurrentTreeNodeLimitedOutArcs;
		TempInArcs = &PricingProblem.CurrentTreeNodeLimitedInArcs;
	}
	else{
		//All arcs should be used
		TempOutArcs = &PricingProblem.CurrentTreeNodeOutArcs;
		TempInArcs = &PricingProblem.CurrentTreeNodeInArcs;
	}
	//Set arcs
	std::list<std::list<PStep_Arc>> &OutArcs = *TempOutArcs;
	std::list<std::list<PStep_Arc>> &InArcs = *TempInArcs;

	//Reset Output/Labels
	PricingProblem.ResetSecondHalfBiDirectionalLayerMembers();

	//Obtain Labels
	std::list<ForwardLabel>** ForwardLabels = PricingProblem.LayeredForwardLabels;
	std::list<BackwardLabel>** BackwardLabels = PricingProblem.LayeredBackwardLabels;

	//Forward Labeling:
	//*************************************************************************************

	//Go over all remaining layers
	for (short int Layer = MaxNumberOfForwardArcs; Layer < NumberOfForwardLayersMinusOne; ++Layer){
		//Initialize current customer
		short int CurrentNode = 0;
		//Go over all customers
		for (auto CurrentOutArcs = ++OutArcs.begin(); CurrentOutArcs != OutArcs.end(); ++CurrentOutArcs){
			//Update current customer
			++CurrentNode;
			//Go over all arcs
			for (auto CurrentArc = CurrentOutArcs->begin(); CurrentArc != CurrentOutArcs->end(); ++CurrentArc){
				//Obtain next node
				short int NextNode = CurrentArc->EndNode;
				//Check whether the next node is not the sink, nor the depot
				if (NextNode != Sink && NextNode > 0){

					//Obtain current list of Labels
					std::list<ForwardLabel>& CurrentListOfForwardLabels = ForwardLabels[Layer][CurrentNode - 1];
					//Obtain the target list of labels
					std::list<ForwardLabel>& TargetListOfForwardLabels = ForwardLabels[Layer + 1][NextNode - 1];
					//Obtain the completion bound at the next node and subtract the current arc costs
					double Bound = ForwardCompletionBounds[Layer + 1][NextNode - 1] - ReducedArcCosts[CurrentArc->StartNode][CurrentArc->EndNode];
					//Extend all labels of which the costs do not exceed the bound, to the the next node
					for (auto CurrentForwardLabel = CurrentListOfForwardLabels.begin(); CurrentForwardLabel != CurrentListOfForwardLabels.end() && CurrentForwardLabel->Cost < Bound; ++CurrentForwardLabel){
						//Check whether the next node is reachable
						if (CurrentForwardLabel->Reachable[NextNode - 1]){

							//Initialize new label
							ForwardLabel NewForwardLabel;

							//Extend
							Extender.Extend(*CurrentForwardLabel, *CurrentArc, NewForwardLabel);

							//Perform dominance:

							//Initialize indicator indicating that the new label itself is not yet dominated
							bool NewLabelIsNotDominated = true;
							//Initialize iterators
							std::list<ForwardLabel>::iterator NextLabel = TargetListOfForwardLabels.begin();
							//Go over all labels with lower reduced costs and check whether the new label is dominated
							while (NewLabelIsNotDominated && NextLabel != TargetListOfForwardLabels.end() && NextLabel->Cost < NewForwardLabel.Cost - Tolerance){
								//Check if the next label dominates the new label
								if (Dominator.Dominate(*NextLabel, NewForwardLabel)){
									//Update indicators
									NewLabelIsNotDominated = false;
								}
								//Otherwise, no dominance is observed
								else{
									//Update indicator
									++NextLabel;
								}
							}//end go over all labels to check dominance over new label

							//Go over all labels with "the same" reduced costs and check whether the new label dominates
							while (NewLabelIsNotDominated && NextLabel != TargetListOfForwardLabels.end() && NextLabel->Cost <= NewForwardLabel.Cost + Tolerance){
								//Check whether the new label dominates the next label
								if (Dominator.Dominate(NewForwardLabel, *NextLabel)){
									//Remove the next label
									NextLabel = TargetListOfForwardLabels.erase(NextLabel);
								}
								//The new label does not dominate, check whether the new label is dominated by the next
								else if (Dominator.Dominate(*NextLabel, NewForwardLabel)){
									//Update indicator
									NewLabelIsNotDominated = false;
								}
								else{
									//Neither labels dominate, update NextLabel
									++NextLabel;
								}
							}//end go over all labels to check dominance of new label

							//Check whether the new label is not dominated
							if (NewLabelIsNotDominated){

								//Add the NewLabel at the current position in the list
								NextLabel = TargetListOfForwardLabels.emplace(NextLabel, NewForwardLabel);
								//Update NextLabel
								++NextLabel;

								//Go over all labels with higher reduced costs and check whether the new label dominates
								while (NextLabel != TargetListOfForwardLabels.end()){
									//Check whether the new label dominates the next label
									if (Dominator.Dominate(NewForwardLabel, *NextLabel)){
										//Remove the next label
										NextLabel = TargetListOfForwardLabels.erase(NextLabel);
									}
									//Otherwise, no dominance is observed
									else{
										++NextLabel;
									}
								}//end go over all labels to check dominance of new label

							}//end check whether the new label was dominated

						}//end check whether the next node is reachable
					}//end go over all labels

				}//end check whether the next node is not the depot

			}//end go over all out arcs
		}//end go over all customers
	}//end go over all layers after the initial layer and prior to the last layer

	//Backward Labeling:
	//*************************************************************************************

	//Go over all remaining layers
	for (short int Layer = MaxNumberOfBackwardArcs; Layer < NumberOfBackwardLayersMinusOne; ++Layer){
		//Initialize current customer
		short int CurrentNode = 0;
		//Go over all customers
		for (auto CurrentInArcs = ++InArcs.begin(); CurrentInArcs != InArcs.end(); ++CurrentInArcs){
			//Update current customer
			++CurrentNode;
			//Go over all arcs
			for (auto CurrentArc = CurrentInArcs->begin(); CurrentArc != CurrentInArcs->end(); ++CurrentArc){
				//Obtain next node
				short int NextNode = CurrentArc->StartNode;
				//Check whether the nest node is not the source, nor the depot
				if (NextNode != Source && NextNode > 0){

					//Obtain current list of Labels
					std::list<BackwardLabel>& CurrentListOfBackwardLabels = BackwardLabels[Layer][CurrentNode - 1];
					//Obtain the target list of labels
					std::list<BackwardLabel>& TargetListOfBackwardLabels = BackwardLabels[Layer + 1][NextNode - 1];
					//Obtain the completion bound at the next node and subtract the current arc costs
					double Bound = BackwardCompletionBounds[Layer + 1][NextNode - 1] - ReducedArcCosts[CurrentArc->StartNode][CurrentArc->EndNode];
					//Extend all labels of which the costs do not exceed the bound, to the the next node
					for (auto CurrentBackwardLabel = CurrentListOfBackwardLabels.begin(); CurrentBackwardLabel != CurrentListOfBackwardLabels.end() && CurrentBackwardLabel->Cost < Bound; ++CurrentBackwardLabel){
						//Check whether the next node is reachable
						if (CurrentBackwardLabel->Reachable[NextNode - 1]){

							//Initialize new label
							BackwardLabel NewBackwardLabel;

							//Extend
							Extender.Extend(*CurrentBackwardLabel, *CurrentArc, NewBackwardLabel);

							//Perform dominance:

							//Initialize indicator indicating that the new label itself is not yet dominated
							bool NewLabelIsNotDominated = true;
							//Initialize iterators
							std::list<BackwardLabel>::iterator NextLabel = TargetListOfBackwardLabels.begin();
							//Go over all labels with lower reduced costs and check whether the new label is dominated
							while (NewLabelIsNotDominated && NextLabel != TargetListOfBackwardLabels.end() && NextLabel->Cost < NewBackwardLabel.Cost - Tolerance){
								//Check if the next label dominates the new label
								if (Dominator.Dominate(*NextLabel, NewBackwardLabel)){
									//Update indicators
									NewLabelIsNotDominated = false;
								}
								//Otherwise, no dominance is observed
								else{
									//Update indicator
									++NextLabel;
								}
							}//end go over all labels to check dominance over new label

							//Go over all labels with "the same" reduced costs and check whether the new label dominates
							while (NewLabelIsNotDominated && NextLabel != TargetListOfBackwardLabels.end() && NextLabel->Cost <= NewBackwardLabel.Cost + Tolerance){
								//Check whether the new label dominates the next label
								if (Dominator.Dominate(NewBackwardLabel, *NextLabel)){
									//Remove the next label
									NextLabel = TargetListOfBackwardLabels.erase(NextLabel);
								}
								//The new label does not dominate, check whether the new label is dominated by the next
								else if (Dominator.Dominate(*NextLabel, NewBackwardLabel)){
									//Update indicator
									NewLabelIsNotDominated = false;
								}
								else{
									//Neither labels dominate, update NextLabel
									++NextLabel;
								}
							}//end go over all labels to check dominance of new label

							//Check whether the new label is not dominated
							if (NewLabelIsNotDominated){

								//Add the NewLabel at the current position in the list
								NextLabel = TargetListOfBackwardLabels.emplace(NextLabel, NewBackwardLabel);
								//Update NextLabel
								++NextLabel;

								//Go over all labels with higher reduced costs and check whether the new label dominates
								while (NextLabel != TargetListOfBackwardLabels.end()){
									//Check whether the new label dominates the next label
									if (Dominator.Dominate(NewBackwardLabel, *NextLabel)){
										//Remove the next label
										NextLabel = TargetListOfBackwardLabels.erase(NextLabel);
									}
									//Otherwise, no dominance is observed
									else{
										++NextLabel;
									}
								}//end go over all labels to check dominance of new label

							}//end check whether the new label was dominated

						}//end check whether the next node is reachable
					}//end go over all labels

				}//end check whether the next node is not the depot

			}//end go over all in arcs
		}//end go over all customers
	}//end go over all layers after the initial layer and prior to the last layer

}