#ifndef LagBaBCoverH
#define LagBaBCoverH

//#include "AuraCover.h"
#include "CovMatrix.h"
#include "Cover.h"

#define NEG_INFINITY -100000000.0/0.0000001f
#define POS_INFINITY +100000000.0/0.0000001f
#define NG_INFINITY -2147483647
#define PS_INFINITY +2147483647


#ifndef AuraCoverH

/** \brief Structure where is kept linkt to set of columns included to solution */
struct header_of_solution_UCP {

	/** \brief Summary cost of columns in solution */
	long Cost;

	/** \brief Columns of solution */
	struct CLink *SetC;
};

/** \brief Structure representing one row or column in matrix */
struct CLink {

	/** \brief Previous link (row/column) */
	struct CLink *Previous;

	/** \brief Next link (row/column)*/
	struct CLink *Next;

	/** \brief ID of row/column */
	int ID;

	//int Offset; //Offset to jump from one item to next

	/** \brief Cost of column */
	int Cost;

	/** \brief Count of 1 in this row/column */
	int NumberOf1;
};

/** \brief Structure where row an column links are kept */
struct CoveringMatrix {

	/** \brief Rows of matrix */
	struct CLink *RowLink;
	
	/** \brief Columns of matrix */
	struct CLink *ColLink;

	/** \brief Cost of columns added to solution from original matrix */
	long Cost;

	/** \brief Used for dominance solving */
	int Dirty;

	/** \brief Count of columns */
	int countOfCols;

	/** \brief Count of rows */
	int countOfRows;

	//pridano pro tvoreni doplnkove matice MSIR k matici, kde radky MSIR chybi
	//int MSIR;		

	/** \brief Count of ones in whole matrix */
	int countOfOnes;

	/** \brief Representation of matrix */
	char * *Array;    //Matice
	
	//int lbound;
};

#endif

/** \brief Structure representing part of problem matrix.
*	
*/
class SCPView {

	/** Pointer to the underlying problem */
	CovMatrix* matrix_all;
	/** Number of rows */
	int row_count;
	/** Number of columns */
	int column_count;
	/** Column mapping to the original problem columns */
	int* column_map;
	/** Row mapping to the original problem rows */
	int* row_map;

	friend class LagrangeSolver;

public:

	SCPView(CovMatrix* matrix_all,CoveringMatrix* matrix);
	~SCPView();

	/** \brief Get value from SCP's matrix
	*  \param row Row
	*  \param column Column
	*  \return 0 or 1
	*/
	unsigned char get(int row,int column);

	/** \brief Get cost of column
	*  \param column Column
	*/
	int get_cost(int column);


	/** \brief Get number of rows */
	unsigned int get_row_count() {return row_count;};
	/** \brief Get number of columns */
	unsigned int get_column_count() {return column_count;};

	/** \brief Get ID of row in original problem
	*  \param row Row index in view
	*/
	int get_row_map(int row) { return row_map[row];};
	
	/** \brief Get ID of column in original problem
	*  \param column Column index in view
	*/
	int get_column_map(int column) { return column_map[column];};

	/** \brief Print debugging info to standard output */
	void print();

};

/** \brief Lagrangean relaxation */
class LagrangeSolver {
	
private:

	/** \brief View to the underlying problem */
	SCPView* problemView;

	/** \brief Best feasible solution */
	float ZUB;

	/** \brief Current cost of lagrangean relaxation */
	float ZLP;

	/** \brief Current best cost of lagrangean relaxation */
	float ZLB;

	/** \brief Current integer best cost of lagrangean relaxation */
	int lbound;

	/** \brief Current heuristic solution cost */
	float heur_value;

	/** \brief Current best heuristic solution cost */
	int best_heur_value;

	/** \brief Vector of lagrangian multipliers */
	float* t;

	/** \brief Vector of dual lagrangian multipliers */
	float* n;

	/** \brief Vector indicating changes of lagrangean multipliers */
	unsigned char* primal_delta;

	/** \brief Vector indicating changes of dual lagrangean multipliers */
	unsigned char* dual_delta;

	/** \brief Vector of the LP solution */
	unsigned char* x;

	/** \brief Vector of the dual solution */
	float* y;

	/** \brief Vector of the current feasible heuristic solution */
	unsigned char* x_heur;

	/** \brief Vector of the best feasible heuristic solution known */
	unsigned char* x_best;

	/** \brief count of columns selected by solving LP */
	int selected_columns;

	/** \brief array containing indexes of columns selected by solving LP */
	int* help_indexes;

	/** \brief array containing costs of columns selected by solving LP */
	float* help_costs;

	/** \brief array containing count of rows covered by columns selected by solving LP */
	int* help_number_of_ones;

	/** \brief number of rows covered by solving LP */
	int covered_rows;

	/** \brief Vector of rows covered by solving LP */
	bool* row_is_covered;

	/** \brief Vector indicating whether given column's reduced cost was recounted
	* when solving dual problem 
	*/
	unsigned char* column_is_recounted;

	/** \brief Vector indicating whether given row's dual reduced cost was recounted
	* when solving dual problem 
	*/
	unsigned char* row_is_recounted;

	/** \brief Vector of costs of columns */
	float* costs;

	/** \brief Vector of reduced costs of columns */
	float* reduced_costs;

	/** \brief Temporary vector of modified or normal reduced costs */
	float* modified_reduced_costs;

	/** \brief Vector of lowest costs of columns covering given row */
	float* min_costs;

	/** \brief Vector of dual reduced costs of rows */
	float* dual_reduced_costs;

	/** \brief Vector of slacks */
	int* primal_slack;

	/** \brief Vector of dual slacks */
	float* dual_slack;
	
	/** \brief Iteration counter */
	int iterations;

	/** \brief Supplementary iteration counter */
	int sup_iterations;

	/** \brief Supplementary dual iteration counter */
	int sup_dual_iterations;

	/** \brief Step coefficient */
	float step_coefficient;

	/** \brief Dual step coefficient */
	float dual_step_coefficient;

	/** \brief Minimal step coefficient */
	float step_coefficient_min;

	/** \brief Number of iterations before step coefficient is halved */
	int step_coefficient_iter;

	/** \brief Supplementary ZLB */
	float sup_ZLB;

	/** \brief Supplementary ZUB */
	float sup_ZUB;

	/** \brief Array with indexes of rows covered by columns */
	int** rows_covered_by_column;

	/** \brief Number of rows covered by given column */
	int* rows_covered_by_column_count;

	/** \brief Array with indexes of columns covered by rows */
	int** columns_covered_by_row;

	/** \brief Number of columns covered by given row */
	int* columns_covered_by_row_count;

	/** \brief Subgradient */
	int primal_subgradient;
	
	/** \brief Dual subgradient */
	float dual_subgradient;
	
	/** \brief Step */
	float primal_step;
	
	/** \brief Dual step */
	float dual_step;

	/** \brief Indicates whether primal step coefficient is lower then minimal step coefficient */
	int primal_step_change_stop;
	
	/** \brief Indicates whether dual step coefficient is lower then minimal step coefficient */
	int dual_step_change_stop;

	/** \brief Column with lowest reduced cost */
	int recommended_column;

	/** \brief Initialize variables and arrays */
	void initialize(int randomizeMultipliers,float stepCoef, float stepCoefMin, int stepCoefIter);
	
	/** \brief Finds simple feasible solution with simple greedy heuristic */
	int find_heur_ub();

	/** \brief Randomizes initial lagrangean multipliers */
	void randomize_multipliers(int minCost, int maxCost);

	/** \brief Solve lagrangean problem (LP) */
	void solve_lp();

	/** \brief Solve first iteration of dual lagrangean problem */
	void solve_dlp();

	/** \brief Solve next iterations of dual lagrangean problem */
	void solve_dlp_next();

	/** \brief Heuristic - creates feasible solution
	* Uses reduced cost
	*/
	void ha(int removeType);

	/** \brief Heuristic - creates feasible solution 
	* Uses modified reduced cost
	*/
	void ha_modified(int removeType);

	/** \brief Calculates subgradient and updates Lagrangean multiplicatiors 
	*  \return 0 if subgradient is 0 or step coefficient is too small
	* else return 1
	*/
	int compute_subgradient();

	/** \brief Calculates reduced cost of column
	*  \param columnIndex Index of column
	*/
	float get_primal_reduced_cost(int columnIndex);

	/** \brief Calculates dual reduced cost of row
	*  \param rowIndex Index of row
	*/
	float get_dual_reduced_cost(int rowIndex);

	/** \brief Updates best solution with it's cost*/
	void update_best_solution(float candZUB);

	


public:
	
	LagrangeSolver(SCPView* pv);
	~LagrangeSolver();
	
	/** \brief Returns the cost of best heuristic solution found*/
	int get_lgsolution_cost() { return best_heur_value;};

	/** \brief Returns the vector with best heuristic solution found*/
	unsigned char* get_best_solution() {return x_best;};

	/** \brief Returns the value of lower bound found by solving LP*/
	int get_lower_bound() { return lbound;};

	/** \brief Returns ID with lowest reduced cost*/
	int get_recommended_column() { return recommended_column;};

	/** \brief Solve the SCP using lagrangian heuristic
	*  \param iterations max number of iterations
	*  \param heuristic which heuristic will be used
	*  \param heurIterations number of iterations between running heuristic
	*  \param stepCoef initial step coefficient
	*  \param stepCoefMin minimal step coefficient
	*  \param stepCoefIter number of iteration without change of LB before step coefficient is halved
	*  \param maxLowerBound Desired maximum lower bound. If that bound is reached, algorithm is stopped
	*/
	void solve(int iterations,int randomizeCosts, int heuristic, int heurIterations, float stepCoef, float stepCoefMin,int stepCoefIter,int maxLowerBound);
	
	/** \brief Solve the SCP using dual lagrangian heuristic
	*  \param iterations max number of iterations
	*  \param heuristic which heuristic will be used
	*  \param heurIterations number of iterations between running heuristic
	*  \param stepCoef initial step coefficient
	*  \param stepCoefMin minimal step coefficient
	*  \param stepCoefIter number of iteration without change of LB before step coefficient is halved
	*  \param maxLowerBound Desired maximum lower bound. If that bound is reached, algorithm is stopped
	*  \param stepCoef initial dual step coefficient
	*  \param stepCoefMin minimal dual step coefficient
	*  \param stepCoefIter number of iteration without change of UB before dual step coefficient is halved
	*/
	void solve_dual(int iterations, int heuristic, int heurIterations,float stepCoef, float stepCoefMin,int stepCoefIter, int maxLowerBound,
		float stepCoefDual, float stepCoefMinDual,int stepCoefIterDual);

};

/** \brief compares columns by costs, if those are equal then by number of covered rows
*  \param costs array with costs of columns
*  \param number_of_ones array eith counts of covers of columns
*  \param c1 index of first compared column
*  \param c2 index of second compared column
*  \return -1,0 or 1
*/
int  compare_three_arrays(float costs[],int number_of_ones[],int c1, int c2);

/** \brief swaps two columns
*  \param columns array with indexes of columns
*  \param costs array with costs of columns
*  \param number_of_ones array eith counts of covers of columns
*  \param c1 index of first swapped column
*  \param c2 index of second swapped column
*/
void swap_in_arrays(int columns[], float costs[],int number_of_ones[],int left, int right);

/** \brief sort given part of arrays representing columns
*  \param columns array with indexes of columns
*  \param costs array with costs of columns
*  \param number_of_ones array eith counts of covers of columns
*  \param l index of last column to be sorted
*  \param r index of last column to be sorted
*/
void quick_sort_three_arrays(int columns[], float costs[],int number_of_ones[], int l, int r);

/** \brief compares columns by costs, if those are equal then by number of covered rows
*  \param links array with links to columns
*  \param c1 index of first compared column
*  \param c2 index of second compared column
*  \return -1,0 or 1
*/
int compare_column_links(CLink* links[],int c1, int c2);

/** \brief compares rows by number of covered columns
*  \param links array with links to rows
*  \param r1 index of first compared row
*  \param r2 index of second compared row
*  \return -1,0 or 1
*/
int compare_row_links(CLink* links[],int r1, int r2);

/** \brief swaps two links
*  \param links array with links to rows or columns
*  \param left index of first link to be swapped
*  \param right index of second link to be swapped
*/
void swap_in_links(CLink* links[],int left, int right);


/** \brief sort given part of array with links to columns
*  \param links array with links to columns
*  \param l index of first column link to be sorted
*  \param r index of last column link to be sorted
*/
void quick_sort_column_links(CLink* links[], int l, int r);

/** \brief sort given part of array with links to rows
*  \param links array with links to rows
*  \param l index of first row link to be sorted
*  \param r index of last row link to be sorted
*/
void quick_sort_row_links(CLink* links[], int l, int r);


/** \brief Recursive UCP solver using Lagrangean relaxation */
class LagBaBCover {

private:
	
	/** \brief Cost of best feasible solution found */
	long uBound;

	/** \brief Cost of all columns */
	long MaxCost;

	/** \brief Count of calls of B&B method */
	long NumCalls;

	/** \brief Total time spent by solving lagrange computations */
	float lagrangeTime;

	/** \brief Representation of problem (used by B&B alghoritm)*/
	struct CoveringMatrix *covering_matrix;

	/** \brief Representation of B&B solution */
	struct header_of_solution_UCP *solution_UCP;

	/** \brief Representation of problem (used by Lagrange alghoritms)*/
	CovMatrix* covMatrix;

	/** \brief Representation of lagrangean solution */
	int *bestLgSolution;

	/** \brief Cost of best lagrangean solution */
	long bestLgSolutionCost;

	/** \brief Indicates whether best solution is obtained by lagrange algh. or B&B */
	char bestLgSolutionUsed;

	/** \brief state with best solution found by Lagrangean heuristic*/
	long double  bestLgState;

	/** \brief options of solving (domination, relaxation parameters...) */
	CoverOpts* options;

	//bool isAllCovered;

	/** \brief creates new covering matrix from CovMatrix structure
	*  \param CVM data matrix
	*/
	struct CoveringMatrix *rebuild_matrix (CovMatrix *CVM);

	/** \brief duplicates links to rows and cols of covering matrix 
	*  \param CM matrix to be duplicated
	*  \return clone of the matrix 
	*/
	struct CoveringMatrix* duplicate ( struct CoveringMatrix *CM);
	
	/** \brief creates row and column links of covering matrix 
	*  \param Cm structure where links will be created
	*  \param Costs array with costs of columns
	*/
	void create_matrix ( struct CoveringMatrix *Cm,int *Costs );
	
	/** \brief sorts columns of matrix according to costs and sorts rows by count of covered columns
	*  \param Cm sorted matrix
	*/
	void sort_matrix ( struct CoveringMatrix *Cm);
	
	/** \brief recursive function of branch and bound alghoritm
	*  \param CM current representation of problem
	*  \param SolUCP header of current solution
	*  \param instance unique identification of run
	*  \return 1 or 0 
	*/
	int branch_bound_lagrange ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolUCP,long double  instance);
	
	/** \brief releases allocated memory for structure keeping matrix 
	*  \param CM matrix to release
	*/
	void release (struct CoveringMatrix * CM);

	/** \brief releases allocated memory for solution 
	*  \param SolUCP solution to release
	*/
	void release ( struct header_of_solution_UCP *SolUCP );

	/** \brief Creates empty header structure for keeping solution 
	*/
	struct header_of_solution_UCP *create_New_Empty_Solution ( void );
	
	/** \brief Apends columns links from one solution header to another
	*  \param Source solution header with column links that should be added
	*  \param Target target solution header
	*/	
	void append_to_solution (struct header_of_solution_UCP *Source,struct header_of_solution_UCP *Target );

	/** \brief Adds given column link to solution
	*  \param SolutionUCP target solution header
	*  \param Column column link that will be added
	*/	
	void add_to_solution ( struct header_of_solution_UCP *SolutionUCP,struct CLink *Column );

	/** \brief Apends columns links marked in mask array from matrix
	*  \param TargetSolution target solution header
	*  \param Matrix matrix structure containing column links
	*  \param mask binary vector indicating selected columns
	*  \param len length of mask vector
	*/	
	void add_to_solution_masked( struct header_of_solution_UCP *TargetSolution,struct CoveringMatrix* Matrix,unsigned char* mask, int len);
	
	/** \brief creates simple array containing ID's of column links in solution
	*  \param SolutionUCP source solution header
	*  \return array containing solution columns ID's 
	*/	
	list<unsigned int> rebuild_solution (struct header_of_solution_UCP *SolutionUCP);
	
	/** \brief removes given column from covering matrix
	*  \param CM matrix
	*  \param colToRemove column link to remove
	*/	
	void remove_col_from_matrix ( struct CoveringMatrix *CM, struct CLink *colToRemove );

	/** \brief removes given column link from covering matrix
	*  \param CM matrix structure
	*  \param ID id of column to be removed
	*/	
	void remove_col_from_matrix ( struct CoveringMatrix *CM, int ID );

	/** \brief removes given row link from covering matrix 
	*  \param CM matrix structure
	*  \param rowToRemove id of row to be removed
	*/	
	void remove_row_from_matrix ( struct CoveringMatrix *CM, struct CLink *rowToRemove );

	/** \brief removes given column and all rows covered by this column from covering matrix
	*  \param Column column link to be removed
	*  \param CM matrix structure
	*/	
	void remove_col_with_rows ( struct CLink * Column, struct CoveringMatrix *CM );
	
	/** \brief finds number of covers in rows and columns 
	*	also removes columns that don't cover any row
	*  \param CM matrix structure
	*/	
	void find_number_of_ones ( struct CoveringMatrix *CM);
	
	/** \brief reduce the matrix by row dominance
	*  \param CM matrix structure
	*  \param SolutionUCP if matrix contains any essential columns, store their links here
	*/	
	void solve_row_dominance ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolutionUCP );

	/** \brief reduce the matrix by column dominance
	*  \param CM matrix structure
	*/	
	void solve_column_dominance ( struct CoveringMatrix *CM);
	
	/** \brief Reduce matrix with dominance relations
	*  \param CM matrix structure
	*  \param SolutionUCP if matrix contains any essential columns, store their links here
	*  \return 1 or 0 (depending on foun dominance)  
	*/	
	int solve_dominance ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolutionUCP );


	/** \brief checks for essential columns in matrix
	*  \param CM matrix structure
	*  \param SolutionUCP if matrix contains any essential columns, store their links here 
	*/	
	void check_essentiality ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolutionUCP );

	/** \brief Evaluates column - used for selecton of column in B&B alghoritm
	*  \param CM matrix structure
	*  \param ColumnLink evaluated column
	*  \return colun evaluation 
	*/	
	float evaluate_column (struct CoveringMatrix *CM,struct CLink *ColumnLink);

	/** \brief Selects column that should be added to solution in B&B alghoritm
	*  \param CM matrix structure
	*  \return found column 
	*/	
	struct CLink* select_col_contrib (struct CoveringMatrix *CM);


	bool check_coverage ( struct CoveringMatrix *CM,list<unsigned int> solution );

public:

	LagBaBCover( CovMatrix *_matrix );
	~LagBaBCover();

	/** \brief solve UPC using default options
	*  \return list of column ID's 
	*/
	list<unsigned int> Run();

	/** \brief solve UPC
	*  \param opts options for Lagrangean relaxation
	*  \return list of column ID's 
	*/
	list<unsigned int> Run(CoverOpts* opts);

	/** \brief returns time spent on computing Lagrangean relaxations
	*/
	float getLagrangeanTime(){ return lagrangeTime; };

	/** \brief returns count of calls of recursive function
	*/
	unsigned int getExpandedStates(){ return NumCalls; };

	/** \brief check whether all rows are covered by current solution
	*/
	//bool getIsAllCovered(){return isAllCovered;};

};

#endif
