/*Implementation of PStep_ShortestPathAlgorithm.h

It contains the member functions of PStep_DoubleLayeredLabelingAlgorithm

*/

#include "PStep_ShortestPathAlgorithm.h"

//PStep_DoubleLayeredLabelingAlgorithm:
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

//Solve the pricing problem
//------------------------------------------------------------------------------------

//Solve the pricing problem
void PStep_DoubleLayeredLabelingAlgorithm::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;
	int IntegerCapacity = int(PricingProblem.Capacity);
	short int MaxNumberOfArcs = PricingProblem.MaxNumberOfArcs;
	bool AllowedToReachSinkEarly = PricingProblem.AllowedToReachSinkEarly;

	//Convert double demand to integer demand
	int* Demand = new int[NumberOfCustomers];
	for (short int i = 0; i < NumberOfCustomers; ++i){
		Demand[i] = int(PricingProblem.Demand[i]);
	}

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

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

	//Obtain Labels
	std::list<Label>*** Labels = PricingProblem.DoubleLayeredLabels;
	std::forward_list<PStep_FinalLabel> &CandidateLabels = PricingProblem.CandidateLabels;

	//Create initial label:
	//Initialize label
	Labels[0][0][0].emplace_front();
	//Obtain label
	Label& InitialLabel = Labels[0][0][0].front();
	//Set values of label
	InitialLabel.NumberOfCustomers = NumberOfCustomers;
	InitialLabel.LastLocation = Source;
	InitialLabel.Cost = PricingProblem.ReducedCostConstant;
	InitialLabel.Reachable = new bool[NumberOfCustomers];
	for (short int i = 0; i < NumberOfCustomers; ++i){
		InitialLabel.Reachable[i] = PricingProblem.Reachable[i];
	}
	if (Source == 0){
		InitialLabel.Load = 0;
	}
	else{
		InitialLabel.Load = PricingProblem.Demand[Source - 1];
	}

	//Extend the initial Label:
	//*************************

	//Obtain initial location
	short int InitialLocation = InitialLabel.LastLocation;
	//Initialize out arcs of the initial location
	std::list<std::list<PStep_Arc>>::iterator InitialOutArcs = Arcs.begin();
	//Initalize support
	short int Counter = 0;
	//Obtain the out arcs of the initial location
	while (Counter < InitialLocation){
		++Counter;
		++InitialOutArcs;
	}

	//Go over all arcs out of the initial customer
	for (auto CurrentArc = InitialOutArcs->begin(); CurrentArc != InitialOutArcs->end(); ++CurrentArc){
		//Obtain next node
		short int NextNode = CurrentArc->EndNode;
		//Check whether the next node is the sink
		if (NextNode == Sink){
			//Check whether the sink may be reached from this layer
			if (MaxNumberOfArcs == 1 || AllowedToReachSinkEarly){
				//Extend to sink
				ExtenderToSink.Extend(InitialLabel, *CurrentArc, CandidateLabels);

			}
		}
		//The next node is not the sink, check whether it is not the depot and MaxNumberOfArcs is not 1
		else if (NextNode>0 && InitialLabel.Reachable[NextNode - 1] && MaxNumberOfArcs > 1){
			//Compute next load
			int NextLoad = Demand[NextNode - 1];
			//Check whether this load is not already in use
			if (Labels[NextLoad] == 0){
				//Initialize Labels[NextNode]
				Labels[NextLoad] = new std::list<Label>*[MaxNumberOfArcs];
				for (short int Layer = 0; Layer < MaxNumberOfArcs; ++Layer){
					Labels[NextLoad][Layer] = new std::list<Label>[NumberOfCustomers];
				}
			}
			//Extend
			Extender.Extend(InitialLabel, *CurrentArc, Labels[NextLoad][1][NextNode - 1]);
		}

	}

	//Go over all loads
	for (int q = 1; q <= IntegerCapacity; ++q){
		//Check whether this load is in use
		if (Labels[q] != 0){

			//Extend the labels in the layers after the initial layer and prior to the last layer:
			//************************************************************************************

			//Go over all layers after the initial layer and prior to the last layer
			for (short int Layer = 1; Layer < MaxNumberOfArcs - 1; ++Layer){
				//Initialize current customer
				short int CurrentNode = 0;
				//Go over all customers
				for (auto OutArcs = ++Arcs.begin(); OutArcs != Arcs.end(); ++OutArcs){
					//Update current customer
					++CurrentNode;
					//Go over all arcs
					for (auto CurrentArc = OutArcs->begin(); CurrentArc != OutArcs->end(); ++CurrentArc){
						//Obtain next node
						short int NextNode = CurrentArc->EndNode;
						//Check whether the next node is the sink
						if (NextNode == Sink){
							//Check whether the sink may be reached from this layer
							if (AllowedToReachSinkEarly){

								//Obtain current list of Labels
								std::list<Label>& CurrentListOfLabels = Labels[q][Layer][CurrentNode - 1];
								//Extend all labels to the sink
								for (auto CurrentLabel = CurrentListOfLabels.begin(); CurrentLabel != CurrentListOfLabels.end(); ++CurrentLabel){
									//Check whether the sink is reachable
									if (NextNode == 0 || CurrentLabel->Reachable[NextNode - 1]){
										//Extend to sink
										ExtenderToSink.Extend(*CurrentLabel, *CurrentArc, CandidateLabels);
									}
								}//end go over all labels

							}
						}
						//The next node is not the sink, check whether it is not the depot
						else if (NextNode > 0 && NextNode != InitialLocation){

							//Obtain current list of Labels
							std::list<Label>& CurrentListOfLabels = Labels[q][Layer][CurrentNode - 1];
							//Check whether there are labels to extend.
							if (!(CurrentListOfLabels.empty())){
								//Compute next load
								int NextLoad = q + Demand[NextNode - 1];
								//Check whether the extension to the next node does not violate the capacity
								if (NextLoad < IntegerCapacity){
									//Check whether this load is not already in use
									if (Labels[NextLoad] == 0){
										//Initialize Labels[NextNode]
										Labels[NextLoad] = new std::list<Label>*[MaxNumberOfArcs];
										for (short int Layer = 0; Layer < MaxNumberOfArcs; ++Layer){
											Labels[NextLoad][Layer] = new std::list<Label>[NumberOfCustomers];
										}
									}
									//Obtain the target list of labels
									std::list<Label>& TargetListOfLabels = Labels[NextLoad][Layer + 1][NextNode - 1];
									//Extend all labels to the the next node
									for (auto CurrentLabel = CurrentListOfLabels.begin(); CurrentLabel != CurrentListOfLabels.end(); ++CurrentLabel){
										//Check whether the next node is reachable
										if (CurrentLabel->Reachable[NextNode - 1]){

											//Initialie new label
											Label NewLabel;

											//Extend
											Extender.Extend(*CurrentLabel, *CurrentArc, NewLabel);

											//Perform dominance:

											//Initialize indicator indicating that the new label itself is not yet dominated
											bool NewLabelIsNotDominated = true;
											//Initialize iterators
											std::list<Label>::iterator NextLabel = TargetListOfLabels.begin();
											//Go over all labels with lower reduced costs and check whether the new label is dominated
											while (NewLabelIsNotDominated && NextLabel != TargetListOfLabels.end() && NextLabel->Cost < NewLabel.Cost - Tolerance){
												//Check if the next label dominates the new label
												if (Dominator.Dominate(*NextLabel, NewLabel)){
													//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 != TargetListOfLabels.end() && NextLabel->Cost <= NewLabel.Cost + Tolerance){
												//Check whether the new label dominates the next label
												if (Dominator.Dominate(NewLabel, *NextLabel)){
													//Remove the next label
													NextLabel = TargetListOfLabels.erase(NextLabel);
												}
												//The new label does not dominate, check whether the new label is dominated by the next
												else if (Dominator.Dominate(*NextLabel, NewLabel)){
													//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 = TargetListOfLabels.emplace(NextLabel, NewLabel);
												//Update NextLabel
												++NextLabel;

												//Go over all labels with higher reduced costs and check whether the new label dominates
												while (NextLabel != TargetListOfLabels.end()){
													//Check whether the new label dominates the next label
													if (Dominator.Dominate(NewLabel, *NextLabel)){
														//Remove the next label
														NextLabel = TargetListOfLabels.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

			//Extend the labels from the last layer to the sink:
			//************************************************************************************
			//Check whether the last layer is not the same as the first layer
			if (MaxNumberOfArcs > 1){
				//Initialize current node
				short int CurrentNode = 0;
				//Go over all customers
				for (auto OutArcs = ++Arcs.begin(); OutArcs != Arcs.end(); ++OutArcs){
					//Update current customer
					++CurrentNode;
					//Go over all arcs
					for (auto CurrentArc = OutArcs->begin(); CurrentArc != OutArcs->end(); ++CurrentArc){
						//Obtain next node
						short int NextNode = CurrentArc->EndNode;
						//Check whether the next node is the sink
						if (NextNode == Sink){
							//Obtain current list of Labels
							std::list<Label>& CurrentListOfLabels = Labels[q][MaxNumberOfArcs - 1][CurrentNode - 1];
							//Extend all labels to the sink
							for (auto CurrentLabel = CurrentListOfLabels.begin(); CurrentLabel != CurrentListOfLabels.end(); ++CurrentLabel){
								//Check whether the sink is reachable
								if (NextNode == 0 || CurrentLabel->Reachable[NextNode - 1]){
									//Extend to sink
									ExtenderToSink.Extend(*CurrentLabel, *CurrentArc, CandidateLabels);
								}
							}//end go over all labels
						}
					}//end go over all out arcs
				}//end go over all customers
			}

		}//end check whether the load is in use
	}//end go over all loads

	//Add the current pricing problem to the list of solved pricing problems
	SolvedPricingProblems.push_front(&PricingProblem);

	//clean
	delete[] Demand;

}