#ifndef SOLUTION_H
#define SOLUTION_H
#include <vector>
#include "Problem.h"
#include "Control.h"
#include "Random.h"

/*
Solution.h
The class Solution implemets a solution in the VRPSD with the preventive
restocking policy, with methods for computing the objective value and for
exploring the Or-opt neighborhood.

The objective value of a solution is the expected cost under the preventive
restocking policy. A solution is a sequence of customers which starts and ends at the 
depot, to be followed in that order for delivering goods.
Under the preventive restocking policy, to each customer is associated 
a threshold value. When the driver is given a solution, he follows the customers in the
order specified by the sequence.
After serving one customer i and before going to the next one, the driver
goes to the depot to replenish IF the residual amount of goods on the 
vehicle is less than the threshold of customer i, OTHERWISE it proceeds to the next
customer.
*/


class Solution : public vector<int> {
  //A solution is also a vector with a number of elements equal to the
  //number of customers, depot included.
  //Solution[i] is the label of the ith customer
  //of the a priori route. Solution[0] must always be 0 (the depot).


public:
  

  Solution( Random* rnd, Control& control, Problem* ); 
  //Construct with a pointer to problem data and with the control class.
  //The control class is used to know whether approximated or exact moves evaluation
  //functions should be used.

  Random* rg;

  double expectedCost;         

  void perturbTSP();

  void shift(void);
  //Method which shifts a string starting from move[0]+1 of length move[1] 
  //after move[2]th customer.
  //This method *modifies* the current solution, and evaluates the new expected cost.

  void shiftTSP(void);
  //Method which shifts a string starting from move[0]+1 of length move[1] 
  //after move[2]th customer.
  //This method does not compute the new expected cost.
  
  bool firstMove(int k);
  //Set the first move with string length = k.

  bool nextMove(int k);
  //Set the next move[0] in lexicographic order, set move[1]=k and set move[2]
  //chosen at random in the range [move[0]+k+1,...,n-1].

  void initializeRandomSolution(); 
  double computeExpectedCost();
  //Compute the objective function of this solution.

  double computeTourLength();
  //Compute the length of the a priori solution (the tsp objective function).

  double computeExpectedCostAndThresholds(vector<int>& thresholds); 
  //The threshold vector must contain numberOfCustomers elements.      
  //The threshold vector values are filled by this method.
  //thresholds[i] will contain the threshold of the customer whose name is i.

  double computeMoveValue();
  //Computes the value of the solution that would be obtained, if the move would be
  //applied to the current solution. 
  //The value returned is not exact, if the delta has been computed with the 
  //proxy function (computeProxyDelta).

  double computeMoveValueTSP( double l );


  //Utility functions.
  void printOn( ostream& );  //print a solution 
  void printOn( ostream&, const vector<int>& thresholds); //Print also the thresholds.
  void printOn( ostream&, const vector<vector<double> >& costToGoMatrix); 
  void copySolution( const Solution& );
  Problem* getProblem();
  vector<int> getMove();
  void setMove(const vector<int>& m);


protected:
  static Problem* problem; //a pointer to problem data
  bool computedExpectedCost; //Is false if cost has not been computed.
  bool useProxy;

  Control& control_;

  vector<int> move;          
  //Contains a move while using move iterators.
  //A move is a triplet: move = {i,k,j}, where
  //move[0]=i is the position of the customer after which a string to be shifted is considered.
  //move[1]=k is the length of the string of k consecutive nodes (i+1)th, ..., (i+k)th.
  //move[2]=j is the position of the customer after which the string is inserted.

  vector<vector<double> > costToGoMatrix;
  void allocateCostToGoMatrix();
  bool allocatedCostToGoMatrix;
  bool computedCostToGoMatrix;

  double computeExpectedCost(vector<vector<double> >& costToGoMatrix);
  //The costToGo matrix must contain (numberOfCustomers-1) rows
  //and (Capacity+1) columns.
  //The matrix values are filled by this method.
  //CostToGoMatrix[i][q], for i>0, will contain the expected cost-to-go from 
  //the (i)th customer, given that the vehicle has capacity q, after having
  //serviced the (i)th customer.
  //CostToGoMatrix[0][q] will be -1 for q < capacity, and
  //CostToGoMatrix[0][Q] will be the expected cost of the solution.
  //The returned value is the expected cost of the solution.

  double computeProxyDelta( );
  double computeExactDelta( );
  double computeCostIfPreventiveRestock(int j,int succ_j,const vector<double>& );
  double computeCostIfProceed(int q,int j,int succ_j,const vector<double>& );
  double computeProxyDeletionSaving(const vector<double>&, const vector<double>& );
  double computeProxyInsertionCost( const vector<double>&,const vector<double>& );
};

#endif