/*Implementation of PStep_Algorithm.h

It contains the arc functions of PStep_Algorithm

*/

#include "PStep_Algorithm.h"

//Arc functions:
//------------------------------------------------------------------------------------

//Set available arcs.
//This function updates the arc members of all relevant PricingProblems to reflect
//which arcs are available in AlgorithmMembers.CurrentTreeNode. In particular it updates
//CurrentTreeNodeOutArcs, CurrentTreeNodeInArcs, CurrentTreeNodeArcIsRelevant,
//and potentially CurrentTreeNodeLimitedOutArcs and CurrentTreeNodeLimitedInArcs.
void PStep_Algorithm::SetAvailableArcs(){

	//Obtain EdgeInUse of the current tree node
	bool* (&EdgeInUse) = AlgorithmMembers.CurrentTreeNode->EdgeInUse;

	//Obtain pricing problems
	PStep_PricingProblem** (&PricingProblems) = AlgorithmMembers.PricingProblems;

	//Set the CurrentTreeNodeOutArcs, CurrentTreeNodeInArcs and CurrentTreeNodeArcIsRelevant:
	//---------------------------------------------------------------------------------------

	//Check whether the depot-depot pricing problem is relevant
	if (AlgorithmMembers.AlgorithmSettings.p > 1){
		//Obtain pricing problem
		PStep_PricingProblem &DepotDepotPricingProblem = PricingProblems[0][0];
		//Set CurrentTreeNodeOutArcs
		FilterArcsByEdgeInUse(DepotDepotPricingProblem.OutArcs, DepotDepotPricingProblem.CurrentTreeNodeOutArcs, EdgeInUse);
		//Set CurrentTreeNodeInArcs
		FilterArcsByEdgeInUse(DepotDepotPricingProblem.InArcs, DepotDepotPricingProblem.CurrentTreeNodeInArcs, EdgeInUse);
		//Set CurrentTreeNodeArcIsRelevant
		FilterArcIsRelevantByEdgeInUse(DepotDepotPricingProblem.ArcIsRelevant, DepotDepotPricingProblem.CurrentTreeNodeArcIsRelevant, EdgeInUse);
	}

	//Obtain depot-customer pricing problems
	std::list<PStep_PricingProblem*>& RelevantDepotCustomerPP = AlgorithmMembers.RelevantDepotCustomerPricingProblems;
	//Go over all depot-customer pricing problems
	for (auto CurrentPP = RelevantDepotCustomerPP.begin(); CurrentPP != RelevantDepotCustomerPP.end(); ++CurrentPP){
		//Set CurrentTreeNodeOutArcs
		FilterArcsByEdgeInUse((*CurrentPP)->OutArcs, (*CurrentPP)->CurrentTreeNodeOutArcs, EdgeInUse);
		//Set CurrentTreeNodeInArcs
		FilterArcsByEdgeInUse((*CurrentPP)->InArcs, (*CurrentPP)->CurrentTreeNodeInArcs, EdgeInUse);
		//Set CurrentTreeNodeArcIsRelevant
		FilterArcIsRelevantByEdgeInUse((*CurrentPP)->ArcIsRelevant, (*CurrentPP)->CurrentTreeNodeArcIsRelevant, EdgeInUse);
	}

	//Obtain customer-depot pricing problems
	std::list<PStep_PricingProblem*>& RelevantCustomerDepotPP = AlgorithmMembers.RelevantCustomerDepotPricingProblems;
	//Go over all customer-depot pricing problems
	for (auto CurrentPP = RelevantCustomerDepotPP.begin(); CurrentPP != RelevantCustomerDepotPP.end(); ++CurrentPP){
		//Set CurrentTreeNodeOutArcs
		FilterArcsByEdgeInUse((*CurrentPP)->OutArcs, (*CurrentPP)->CurrentTreeNodeOutArcs, EdgeInUse);
		//Set CurrentTreeNodeInArcs
		FilterArcsByEdgeInUse((*CurrentPP)->InArcs, (*CurrentPP)->CurrentTreeNodeInArcs, EdgeInUse);
		//Set CurrentTreeNodeArcIsRelevant
		FilterArcIsRelevantByEdgeInUse((*CurrentPP)->ArcIsRelevant, (*CurrentPP)->CurrentTreeNodeArcIsRelevant, EdgeInUse);
	}

	//Obtain customer-customer pricing problems
	std::list<PStep_PricingProblem*>& RelevantCustomerCustomerPP = AlgorithmMembers.RelevantCustomerCustomerPricingProblems;
	//Go over all customer-customer pricing problems
	for (auto CurrentPP = RelevantCustomerCustomerPP.begin(); CurrentPP != RelevantCustomerCustomerPP.end(); ++CurrentPP){
		
		//Set CurrentTreeNodeOutArcs
		FilterArcsByEdgeInUse((*CurrentPP)->OutArcs, (*CurrentPP)->CurrentTreeNodeOutArcs, EdgeInUse);
		//Set CurrentTreeNodeInArcs
		FilterArcsByEdgeInUse((*CurrentPP)->InArcs, (*CurrentPP)->CurrentTreeNodeInArcs, EdgeInUse);
		//Set CurrentTreeNodeArcIsRelevant
		FilterArcIsRelevantByEdgeInUse((*CurrentPP)->ArcIsRelevant, (*CurrentPP)->CurrentTreeNodeArcIsRelevant, EdgeInUse);

		//Obtain the pricing problem with reverse source and sink, it should be relevant
		short int Source = (*CurrentPP)->Source;
		short int Sink = (*CurrentPP)->Sink;
		PStep_PricingProblem& ReversePP = PricingProblems[Sink][Source];

		//Set CurrentTreeNodeOutArcs
		FilterArcsByEdgeInUse(ReversePP.OutArcs, ReversePP.CurrentTreeNodeOutArcs, EdgeInUse);
		//Set CurrentTreeNodeInArcs
		FilterArcsByEdgeInUse(ReversePP.InArcs, ReversePP.CurrentTreeNodeInArcs, EdgeInUse);
		//Set CurrentTreeNodeArcIsRelevant
		FilterArcIsRelevantByEdgeInUse(ReversePP.ArcIsRelevant, ReversePP.CurrentTreeNodeArcIsRelevant, EdgeInUse);

	}

	//Set CurrentTreeNodeLimitedOutArcs and CurrentTreeNodeLimitedInArcs if required:
	//-------------------------------------------------------------------------------
	
	//Check whether limited arcs are used
	if (AlgorithmMembers.LimitedArcsUsed){

		//Check whether the depot-depot pricing problem is relevant
		if (AlgorithmMembers.AlgorithmSettings.p > 1){
			//Obtain pricing problem
			PStep_PricingProblem &DepotDepotPricingProblem = AlgorithmMembers.PricingProblems[0][0];
			//Set CurrentTreeNodeLimitedOutArcs
			SelectFirstArcs(DepotDepotPricingProblem.CurrentTreeNodeOutArcs, DepotDepotPricingProblem.CurrentTreeNodeLimitedOutArcs);
			//Set CurrentTreeNodeLimitedInArcs
			SelectFirstArcs(DepotDepotPricingProblem.CurrentTreeNodeInArcs, DepotDepotPricingProblem.CurrentTreeNodeLimitedInArcs);
		}

		//Go over all depot-customer pricing problems
		for (auto CurrentPP = RelevantDepotCustomerPP.begin(); CurrentPP != RelevantDepotCustomerPP.end(); ++CurrentPP){
			//Set CurrentTreeNodeLimitedOutArcs
			SelectFirstArcs((*CurrentPP)->CurrentTreeNodeOutArcs, (*CurrentPP)->CurrentTreeNodeLimitedOutArcs);
			//Set CurrentTreeNodeLimitedInArcs
			SelectFirstArcs((*CurrentPP)->CurrentTreeNodeInArcs, (*CurrentPP)->CurrentTreeNodeLimitedInArcs);
		}

		//Go over all customer-depot pricing problems
		for (auto CurrentPP = RelevantCustomerDepotPP.begin(); CurrentPP != RelevantCustomerDepotPP.end(); ++CurrentPP){
			//Set CurrentTreeNodeLimitedOutArcs
			SelectFirstArcs((*CurrentPP)->CurrentTreeNodeOutArcs, (*CurrentPP)->CurrentTreeNodeLimitedOutArcs);
			//Set CurrentTreeNodeLimitedInArcs
			SelectFirstArcs((*CurrentPP)->CurrentTreeNodeInArcs, (*CurrentPP)->CurrentTreeNodeLimitedInArcs);
		}

		//Go over all customer-customer pricing problems
		for (auto CurrentPP = RelevantCustomerCustomerPP.begin(); CurrentPP != RelevantCustomerCustomerPP.end(); ++CurrentPP){
			
			//Set CurrentTreeNodeLimitedOutArcs
			SelectFirstArcs((*CurrentPP)->CurrentTreeNodeOutArcs, (*CurrentPP)->CurrentTreeNodeLimitedOutArcs);
			//Set CurrentTreeNodeLimitedInArcs
			SelectFirstArcs((*CurrentPP)->CurrentTreeNodeInArcs, (*CurrentPP)->CurrentTreeNodeLimitedInArcs);

			//Obtain the pricing problem with reverse source and sink, it should be relevant
			short int Source = (*CurrentPP)->Source;
			short int Sink = (*CurrentPP)->Sink;
			PStep_PricingProblem& ReversePP = PricingProblems[Sink][Source];

			//Set CurrentTreeNodeLimitedOutArcs
			SelectFirstArcs(ReversePP.CurrentTreeNodeOutArcs, ReversePP.CurrentTreeNodeLimitedOutArcs);
			//Set CurrentTreeNodeLimitedInArcs
			SelectFirstArcs(ReversePP.CurrentTreeNodeInArcs, ReversePP.CurrentTreeNodeLimitedInArcs);

		}

	}

}

//Filter arcs by EdgeInUse
//It copies all InputArcs and stores them in OutputArcs, while filtering out all arcs
//that are not in use as indicated by EdgeInUse.
//EdgeInUse[(j-1)(j)/2+i] indicates whether edge (i,j), i<j, is still in use.
void PStep_Algorithm::FilterArcsByEdgeInUse(std::list<std::list<PStep_Arc>>& InputArcs, std::list<std::list<PStep_Arc>>& OutputArcs, bool* (&EdgeInUse)){

	//Empty output arcs
	OutputArcs.clear();

	//Go over all lists of arcs in InputArcs
	for (auto CurrentInputArcs = InputArcs.begin(); CurrentInputArcs != InputArcs.end(); ++CurrentInputArcs){

		//Initialize new list of output arcs
		OutputArcs.emplace_back();
		//Obtain list
		std::list<PStep_Arc>& CurrentOutputArcs = OutputArcs.back();

		//Go over all arcs in the current input list
		for (auto CurrentInputArc = CurrentInputArcs->begin(); CurrentInputArc != CurrentInputArcs->end(); ++CurrentInputArc){

			//Check whether the edge corresponding to the current input arc is in use.

			//Obtain StartNode and EndNode
			short int StartNode = CurrentInputArc->StartNode;
			short int EndNode = CurrentInputArc->EndNode;

			//Check whether startnode is smaller than endnode
			if (StartNode < EndNode){
				//Check whether the corresponding edge is in use
				if (EdgeInUse[(EndNode - 1)*EndNode / 2 + StartNode]){
					//The edge is in use, copy the arc
					CurrentOutputArcs.push_back(*CurrentInputArc);
				}
			}
			else{
				//Check whether the corresponding edge is in use
				if (EdgeInUse[(StartNode - 1)*StartNode / 2 + EndNode]){
					//The edge is in use, copy the arc
					CurrentOutputArcs.push_back(*CurrentInputArc);
				}
			}

		}

	}

}

//Filter ArcIsRelevant by EdgeInUse
//It copies InputArcIsRelevant, where InputArcIsRelevant[i][j] indicates whether arc (i,j) is relevant,
//and stores it in OutputArcs, while filtering out all arcs that are not in use as indicated by EdgeInUse.
//EdgeInUse[(j-1)(j)/2+i] indicates whether edge (i,j), i<j, is still in use.
//NumberOfLocations should correspond to the size of InputArcIsRelevant (and OutputArcIsRelevant).
void PStep_Algorithm::FilterArcIsRelevantByEdgeInUse(bool** (&InputArcIsRelevant), bool** &(OutputArcIsRelevant), bool* (&EdgeInUse)){

	//Obtain number of customers and locations
	short int NumberOfCustomers = AlgorithmMembers.Instance.NumberOfCustomers;
	short int NumberOfLocations = NumberOfCustomers + 1;

	//Empty OutputArcIsRelevant
	if (OutputArcIsRelevant != 0){
		for (short int i = 0; i < NumberOfLocations; ++i){
			delete[] OutputArcIsRelevant[i];
		}
		delete[] OutputArcIsRelevant;
	}

	//Initialize OutPutArcIsRelevant
	OutputArcIsRelevant = new bool*[NumberOfLocations];
	for (short int i = 0; i < NumberOfLocations; ++i){
		OutputArcIsRelevant[i] = new bool[NumberOfLocations];
		OutputArcIsRelevant[i][i] = false;
	}

	//Go over all locations
	for (short int i = 0; i < NumberOfCustomers; ++i){

		//Go over all locations
		for (short int j = i + 1; j < NumberOfLocations; ++j){

			//Check whether the corresponding edge is in use
			if (EdgeInUse[(j - 1)*j / 2 + i]){
				//The edge is in use, copy ArcIsRelavant
				OutputArcIsRelevant[i][j] = InputArcIsRelevant[i][j];
				OutputArcIsRelevant[j][i] = InputArcIsRelevant[j][i];
			}
			else{
				OutputArcIsRelevant[i][j] = false;
				OutputArcIsRelevant[j][i] = false;
			}

		}
	}

}

//Select first arcs
//It selects up to the first AlgorithmMember.AlgorithmSettings.CG3NeighbourhoodSize from each list in InputArcs,
//and copies them into OutputArcs
void PStep_Algorithm::SelectFirstArcs(std::list<std::list<PStep_Arc>>& InputArcs, std::list<std::list<PStep_Arc>>& OutputArcs){

	//Empty output arcs
	OutputArcs.clear();

	//Obtain maximum number of arcs that will be copied
	short int MaximumNumberOfArcs = AlgorithmMembers.AlgorithmSettings.CG3NeighbourhoodSize;

	//Go over all lists of arcs in InputArcs
	for (auto CurrentInputArcs = InputArcs.begin(); CurrentInputArcs != InputArcs.end(); ++CurrentInputArcs){

		//Initialize new list of output arcs
		OutputArcs.emplace_back();
		//Obtain list
		std::list<PStep_Arc>& CurrentOutputArcs = OutputArcs.back();

		//Go over all arcs in the current input list
		//Initialize current input arc
		auto CurrentInputArc = CurrentInputArcs->begin();
		//Initialize added arc counter
		int AddedArcCounter = 0;
		//Add arcs
		while ( CurrentInputArc != CurrentInputArcs->end() && AddedArcCounter<MaximumNumberOfArcs ){
			//Add the current arc
			CurrentOutputArcs.push_back(*CurrentInputArc);
			//Update AddedArcCounter
			++AddedArcCounter;
			//Update current arc
			++CurrentInputArc;
		}

	}

}