/*Header file of the PStep_PricingProblem class

Implementation can be found in PStep_PricingProblem.cpp
Implementation of PStep_LayeredPricingProblem can be found in PStep_LayeredPricingProblem.cpp
Implementation of PStep_LocalSearchPricingProblemFixedArcs can be found in PStep_LocalSearchPricingProblemFixedArcs.cpp
Implementation of PStep_LocalSearchPricingProblemVaryingArcs can be found in PStep_LocalSearchPricingProblemVaringArcs.cpp

This class represents a model and solution approach for the pricing problem.

This file also includes derived classes of PStep_PricingProblem.

*/

#ifndef _PSTEP_PRICINGPROBLEM_H
#define _PSTEP_PRICINGPROBLEM_H

#include "PStep_Extender.h"
#include "PStep_Dominator.h"
#include "PStep.h"
#include "PStep_MergeLabel.h"

//Class used to represent the pricing problem
class PStep_PricingProblem{
public:
	
	//Number of locations and customers
	short int  NumberOfLocations;
	short int  NumberOfCustomers;

	//Maximum number of arcs on a p-step
	//This is usually p but for depot-customer p-steps this could be less.
	short int  MaxNumberOfArcs;

	//Source node, 0 is the depot
	short int  Source;

	//Sink node, 0 is the depot
	short int  Sink;

	//Demand
	//Demand[i] is the demand of customer i, i=0 is the first customer.
	double* Demand;

	//Capacity
	double Capacity;

	//OutArcs[i][j] is the (j+1)'th cheapest arc out of location i,
	//i=0 is the depot, and OutArcs[i][0] is the cheapest arc out of location i.
	//They are sorted with respect to arc costs (not ReducedArcCosts!).
	std::list < std::list<PStep_Arc>> OutArcs;

	//InArcs[i][j] is the (j+1)'th cheapest arc into location i,
	//i=0 is the depot, and InArcs[i][0] is the cheapest arc into location i.
	//They are sorted with respect to arc costs (not ReducedArcCosts!).
	std::list < std::list<PStep_Arc>> InArcs;

	//Array indicating whether a location can (demand-)feasibly be reached on an elementary
	//path from source to sink.
	//Reachable[i]=true indicates customer i can be reached, i=0 is the first customer.
	//Note that reachability of the source is set to false.
	bool *Reachable;

	//Array indicating whether an arc is relevant,
	//meaning it can (demand-)feasibly be used on an elementary path from source to sink.
	bool **ArcIsRelevant;

	//Indicator indicating whether it is allowed to extend to the sink in all layers
	bool AllowedToReachSinkEarly;

	//Reduced costs
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	//The total reduced costs should equal the total arc costs of the selected arcs plus the constant

	//Reduced arc costs
	//ReducedArcCosts[PStep_Arc::StartNode][Pstep_Arc::EndNode] should correspond to the costs of PStep_Arc.
	double** ReducedArcCosts;

	//Reduced cost constant
	double ReducedCostConstant;

	//Members used to store output shortest path algorithms.
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//Candidate labels, as output of a Labeling Algorithm,
	//representing all identified p-steps with negative reduced costs
	std::forward_list<PStep_FinalLabel> CandidateLabels;

	//Candidate p-steps, representing identified p-steps with nonegative reduced costs.
	std::forward_list<PStep> CandidatePSteps;

	//Candidate merge labels, as output of a bidirectional labeling algorithm
	//representing all identified p-steps with negative reduced costs
	std::forward_list<PStep_MergeLabel> CandidateMergeLabels;

	//Members used to store the output of PStep_LayeredLabelingAlgorithm
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//Labels, as output of Layered Labeling Algorithm
	//Label[0][0][j] gives the j-th initial label at the source node.
	//Label[l][i][j] is the j-th label of customer i in layer 0<l<p, i=0 is the first customer.
	std::list<Label>** LayeredLabels;

	//Members used to store the output of PStep_DoubleLayeredLabelingAlgorithm
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//Labels, as output of Layered Labeling Algorithm
	//Label[0][0][0][j] gives the j-th initial label at the source node.
	//Label[q][l][i][j] is the j-th label of customer i in layer 0<l<p, with load q, i=0 is the first customer.
	std::list<Label>*** DoubleLayeredLabels;

	//Members used to store the output of PStep_BiDirectionalLayeredLabelingAlgorithm
	//Also used to store the output of functions like PStep_BiDirectionalLayeredLabelingAlgorithmWithCompletionBounds
	//when completion bounds are used.
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//ForwardLabels, as output of the bi-directional Layered Labeling Algorithm.
	//LayeredForwardLabels[0][0][j] gives the j-th initial label at the source node.
	//LayeredForwardLabels[l][i][j] is the j-th label of customer i in layer 0<l<NumberOfForwardLayers, i=0 is the first customer.
	std::list<ForwardLabel>** LayeredForwardLabels;

	//The number of forward layers.
	//In case of PStep_BiDirectionalLayeredLabelingAlgorithm it is set to MaxNumberOfForwardArcs+1.
	short int  NumberOfForwardLayers;

	//ForwardLabels, as output of the bi-directional Layered Labeling Algorithm.
	//BackwardLabels[0][0][j] gives the j-th initial label at the source node.
	//BackwardLabels[l][i][j] is the j-th label of customer i in layer 0<l<NumberOfBackwardLayers, i=0 is the first customer.
	std::list<BackwardLabel>** LayeredBackwardLabels;

	//The number of backward layers.
	//In case of PStep_BiDirectionalLayeredLabelingAlgorithm it is set to MaxNumberOfBackwardArcs+1.
	short int  NumberOfBackwardLayers;

	//Members used to store information that correspond to a particular node in the branching tree
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//CurrentTreeNodeOutArcs are the feasible OutArcs in the current tree node.
	//CurrentTreeNodeOutArcs[i][j] is the (j+1)'th cheapest arc out of location i,
	//i=0 is the depot, and CurrentTreeNodeOutArcs[i][0] is the cheapest arc out of location i.
	//They are sorted with respect to arc costs (not ReducedArcCosts!).
	std::list < std::list<PStep_Arc>> CurrentTreeNodeOutArcs;

	//CurrentTreeNodeInArcs are the feasible InArcs in the current tree node.
	//CurrentTreeNodeInArcs[i][j] is the (j+1)'th cheapest arc into location i,
	//i=0 is the depot, and CurrentTreeNodeInArcs[i][0] is the cheapest arc into location i.
	//They are sorted with respect to arc costs (not ReducedArcCosts!).
	std::list < std::list<PStep_Arc>> CurrentTreeNodeInArcs;

	//Array indicating whether an arc is relevant in the current tree node,
	//meaning it can (demand-)feasibly be used on an elementary path from source to sink.
	bool **CurrentTreeNodeArcIsRelevant;

	//CurrentTreeNodeLimitedOutArcs is a limited set of feasible OutArcs in the current tree node.
	//CurrentTreeNodeLimitedOutArcs[i][j] is the (j+1)'th cheapest arc out of location i,
	//i=0 is the depot, and CurrentTreeNodeLimitedOutArcs[i][0] is the cheapest arc out of location i.
	//They are sorted with respect to arc costs (not ReducedArcCosts!).
	std::list < std::list<PStep_Arc>> CurrentTreeNodeLimitedOutArcs;

	//CurrentTreeNodeLimitedInArcs is a limited set of feasible InArcs in the current tree node.
	//CurrentTreeNodeLimitedInArcs[i][j] is the (j+1)'th cheapest arc into location i,
	//i=0 is the depot, and CurrentTreeNodeLimitedInArcs[i][0] is the cheapest arc into location i.
	//They are sorted with respect to arc costs (not ReducedArcCosts!).
	std::list < std::list<PStep_Arc>> CurrentTreeNodeLimitedInArcs;

	//Members of use for the BiDirectionalLayeredLabelingAlgorithm
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//The maximum number of arcs on a partial path obtained through forward labeling
	short int  MaxNumberOfForwardArcs;

	//The maximum number of arcs on a partial path obtained through backward labeling
	short int  MaxNumberOfBackwardArcs;

	//Members of use for the BiDirectionalLayeredLabelingAlgorithmWithCompletionBounds
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//Forward Completion bounds
	//The forward completion bound is an upper bound on the reduced costs of a forward label.
	//If the forward label has a reduced cost that are equal or higher, extension cannot result
	//in a path with negative reduced costs.
	//It is good practice to subtract Tolerance.
	//ForwardCompletionBound[l][i] is the completion bound of location i (0 is the depot)
	//in layer 0 <=l < MaxNumberOfForwardArcs.
	//Note that the value l=0 is a dummy value for consistency with ForwardLabels.
	double** ForwardCompletionBounds;

	//Backward Completion bounds
	//The backward completion bound is an upper bound on the reduced costs of a backward label.
	//If the backward label has reduced costs that are equal or higher, extension cannot result
	//in a path with negative reduced costs.
	//It is good practice to subtract Tolerance.
	//BackwardCompletionBound[l][i] is the completion bound of location i (0 is the depot)
	//in layer 0 <=l < MaxNumberOfBackwardArcs.
	//Note that the value l=0 is a dummy value for consistency with BackwardLabels.
	double** BackwardCompletionBounds;

	//Old DSSR neighbourhoods.
	//It is used to store the neighbourhoods before decrementing the state, which are needed
	//to compute completion bounds.
	//OldDSSRNeighbourhoods.at(i).at(j) represents neighbour j of customer i (0 is the first customer)
	//in the current state space relaxation.
	std::vector<std::vector<short int >> OldDSSRNeighbourhoods;
	
	//Old DSSRNotInNeighbourhood
	//It is used to store the neighbourhoods before decrementing the state, which are needed
	//to compute completion bounds.
	//Not in neighborhood indicates whether a customer is not in the neighborhoud for the depot to depot pricing problem
	//in the current state space relaxation.
	//OldDSSRNotInNeighbourhood.at(i).at(j)=true if customer j is not a neighbor of customer i (0 is the first customer).
	bool** OldDSSRNotInNeighbourhood;

	//Members used for decremental state space relaxation
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//CurrentDSSRNeighbourhoods.at(i).at(j) represents neighbour j of customer i (0 is the first customer)
	//in the current state space relaxation.
	std::vector<std::vector<short int >> CurrentDSSRNeighbourhoods;
	//Not in neighborhood indicates whether a customer is not in the neighborhoud for the depot to depot pricing problem
	//in the current state space relaxation.
	//CurrentDSSRNotInNeighbourhood.at(i).at(j)=true if customer j is not a neighbor of customer i (0 is the first customer).
	bool** CurrentDSSRNotInNeighbourhood;

	//ToAdd[i][j] indicates whether customer j should be added to the CurrentDSSRNeighborhoods[i].
	//i=0 and j=0 represent the first customers.
	//WARNING: the memory of this member is not freed upon destruction of this object!!!
	bool** ToAdd;

	//Indicator indicating whether a forbidden cycle was found for this particular pricing problem,
	//meaning ToAdd can be used to update at least one neighborhood.
	bool ForbiddenCycleFound;

	//Indicator to indicate whether this pricing problem needs to be resolved, basically meaning the
	//state space was decremented in the previous iteration.
	bool RerunRequired;

	//Constructor functions
	//------------------------------------------------------------------------------------

	//Basic constructor
	PStep_PricingProblem()
		: Demand(0), Reachable(0), ArcIsRelevant(0), ReducedArcCosts(0), LayeredLabels(0), DoubleLayeredLabels(0), LayeredForwardLabels(0), LayeredBackwardLabels(0), CurrentTreeNodeArcIsRelevant(0), ForwardCompletionBounds(0), BackwardCompletionBounds(0), OldDSSRNotInNeighbourhood(0), CurrentDSSRNotInNeighbourhood(0), ToAdd(0)
		{};

	//Copy Constructor
	PStep_PricingProblem(const PStep_PricingProblem &OriginalPStep_PricingProblem);

	//Operator functions:
	//------------------------------------------------------------------------------------

	//Assignment operator
	PStep_PricingProblem operator=(PStep_PricingProblem OriginalPStep_PricingProblem);

	//Solve the pricing problem
	//------------------------------------------------------------------------------------
	void virtual Solve(){};

	//Print functions
	//------------------------------------------------------------------------------------

	//Print OutArcs
	void PrintOutArcs();

	//Print InArcs
	void PrintInArcs();

	//Print Reachable Customers
	void PrintReachableCustomers();

	//Print ArcIsRelevant
	void PrintArcIsRelevant();

	//Print Reduced ArcCosts
	void PrintReducedArcCosts();

	//Print CurrentTreeNodeOutArcs
	void PrintCurrentTreeNodeOutArcs();

	//Print CurrentTreeNodeInArcs
	void PrintCurrentTreeNodeInArcs();

	//Print CurrentTreeNodeArcIsRelevant
	void PrintCurrentTreeArcIsRelevant();

	//Print CurrentTreeNodeLimitedOutArcs
	void PrintCurrentTreeNodeLimitedOutArcs();

	//Print CurrentTreeNodeLimitedInArcs
	void PrintCurrentTreeNodeLimitedInArcs();

	//Print ForwardCompletionBounds
	void PrintForwardCompletionBounds();

	//Print BackwardCompletionBounds
	void PrintBackwardCompletionBounds();
	
	//Other functions
	//------------------------------------------------------------------------------------

	//Reset the members that are used by the Layered Labeling Algorithm members to store the output.
	void ResetLayeredLabelingAlgorithmMembers();

	//Reset the members that are used by the Double Layered Labeling Algorithm members to store the output.
	void ResetDoubleLayeredLabelingAlgorithmMembers();

	//Reset the DSSR neighbourhoods
	void ResetDSSRNeighbourhoods();

	//Reset the members that are used by the Bi-Directional Layered Labeling Algorithm members to store the output.
	void ResetBiDirectionalLayeredLabelingAlgorithmMembers();

	//Reset the members that are used for completing the bi-directional labeling algorithm members to store the output.
	void ResetSecondHalfBiDirectionalLayerMembers();

	//Copy the current DSSRNeighbourhoods to old DSSRNeighbourhoods
	void CopyCurrentDSSRNeighbourhoodsToOld();

	//Obtain the "second" half of the completion bounds, based on LayeredForwardLabels and LayeredBackwardLabels.
	//That is, obtain the values of ForwardCompletionBounds[l][i], for all customers i and
	//layers l such that MaxNumberOfForwardArcs < l < NumberOfForwardLayers.
	//Furthermore, obtain the values of BackwardCompletionBounds[l][i] for all customers i
	//and layers l such that MaxNumberOfBackwardArcs < l < NumberOfBackwardLayers.
	//NOTE: It is assumed that ForwardLabels and BackwardLabels are sorted from lowest reduced costs
	//		to highest.
	void ObtainSecondHalfOfCompletionBounds(double MinusTolerance);

	//Obtain the "first" half of the completion bounds, based on LayeredForwardLabels and LayeredBackwardLabels.
	//That is, obtain the values of ForwardCompletionBounds[l][i], for all customers i and
	//layers l such that 0 < l <= MaxNumberOfForwardArcs.
	//Furthermore, obtain the values of ForwardCompletionBounds[l][i] for all customers i
	//and layers l such that 0 < l <= MaxNumberOfBackwardArcs.
	//NOTE: It is assumed that ForwardLabels and BackwardLabels are sorted from lowest reduced costs
	//		to highest.
	void ObtainFirstHalfOfCompletionBounds(double MinusTolerance);

	//Destructor functions
	//------------------------------------------------------------------------------------

	//Default destructor
	virtual ~PStep_PricingProblem();

};

#endif