//---------------------------------------------------------------------------

#include "stdafx.h"

#ifdef _MSC_VER
#pragma hdrstop
#endif

using namespace std;

#include "../../Kernel/myExcept.h"

#include "CovMatrix.h"
#include "HeurCover.h"

HeurCover::HeurCover( const CovMatrix *_matrix )
{
	unsigned int i;

	CM = _matrix;
	rownum = CM->GetRowNum();
	colnum = CM->GetColNum();
	for ( i = 0; i < colnum; i++ ) columns.push_back(i);

	initialize();
}

HeurCover::~HeurCover(void)
{
}

void HeurCover::DeleteRow( int row ) {
	
	unsigned int i;
	unsigned int column;

	if(row_is_covered[row]==false) {

		row_is_covered[row] = true;
		covered_rows = covered_rows+1;
		row_contrib[row] = 0;
		
		for(i=0;i<columns_covered_by_row_count[row];i++) {
			
			column = columns_covered_by_row[row][i];
			if(x[column]== false) {

				col_contrib[column]--;
				float_col_contrib[column]-= float_row_contrib[row];
			}
		}
	} else {

	}
}

list<unsigned int>::iterator HeurCover::MoveToSolution( list<unsigned int>::iterator col_it ) {
	
	list<unsigned int>::iterator col_it1;
	unsigned int row,i;


	cout << "Cover::MoveToSolution:: Adding to solution column" << *col_it << endl;
	solution.push_back( *col_it );
	x[*col_it] = true;

	for(i=0;i<rows_covered_by_column_count[*col_it];i++) {
		row = rows_covered_by_column[*col_it][i];
		if(row_is_covered[row]==false) {
			DeleteRow(row);
		}
	}
	return columns.erase(col_it);
}


void HeurCover::Essentials() {

	cout << "Essentials" << endl;

	list<unsigned int>::iterator col_it;
	set<unsigned int> essentials;
	unsigned int i;
	unsigned int column;

	if ( columns.empty() ) throw RuntimeException( "Essentials: Something's wrong. Some rows are not covered." );

	for(i=0;i<rownum;i++) {
		
		if(row_contrib[i]==0) {
			cout << "Essentials:: uncoverable row found: " << i << endl;
		}
		if(row_contrib[i]==1) {
			
			column = columns_covered_by_row[i][0];
			cout << "Essentials:: essential column found:" << column << endl;
			essentials.insert( column );
		}


	}

	//cout << "Cover::Essentials:: Adding essentials" << endl;
	col_it = columns.begin();
	while ( col_it != columns.end() ) {
		//cout << *col_it << endl;
		if ( essentials.find(*col_it) != essentials.end() )
			col_it = MoveToSolution(col_it);
		else  {
			col_it++;
		}
	}

	cout << "Essentials done" << endl;

}

void HeurCover::Contrib_SelectColumn(void) {
	

	list<unsigned int>::iterator col_it;
	list<unsigned int>::iterator candidate;
	float contrib, maxcontrib;
	vector< list<unsigned int>::iterator > c_candidates;

	// Find columns with maximum contribution
	maxcontrib = 0.;

	cout << "Contrib_SelectColumn" << endl;

	for ( col_it = columns.begin(); col_it != columns.end(); col_it++ ) {

		contrib = (float)float_col_contrib[*col_it]/(float)costs[*col_it];
		if ( contrib > maxcontrib ) {
			maxcontrib = contrib;
			c_candidates.clear();
			c_candidates.push_back(col_it);
		}
	}
	if ( c_candidates.empty() ) throw RuntimeException( "HeurCover::Contrib_SelectColumn:: Something's wrong. No candidate column found." );

	col_it = c_candidates[0];

	MoveToSolution( col_it );

	cout << "Contrib_SelectColumn done" << endl;
}


list<unsigned int> HeurCover::Run(void)
{

	return solution;

}

list<unsigned int> HeurCover::RunServit(void) {
	
	unsigned int i,j,row,column;
	
	cout << "Running Servit " << endl;
	//cout << "float row contribs" << endl;

	for(i=0;i<rownum;i++) {
		float_row_contrib[i]=0.;
		for(j=0;j<columns_covered_by_row_count[i];j++) {
			column = columns_covered_by_row[i][j];
			float_row_contrib[i] +=  (float) (1. / costs[column]);

		}
		//cout << "float row contrib for row " << i << " is " << float_row_contrib[i] << endl;
	}
	
	//cout << "float column contribs" << endl;

	for(i=0;i<colnum;i++) {
		float_col_contrib[i]=0.;
		for(j=0;j<rows_covered_by_column_count[i];j++) {
			row = rows_covered_by_column[i][j];
			//cout << float_col_contrib[i] << " to ";
			float_col_contrib[i]+=float_row_contrib[row];
			//cout << float_col_contrib[i] << endl;
		}
		//cout << "float column contrib for column " << i << " is " << float_col_contrib[i] << endl;
	}
	
	Essentials();
	do {
		
		if ( covered_rows==rownum ) 
			return solution;

		Contrib_SelectColumn();
	} while ( true );
}

list<unsigned int> HeurCover::RunContribAdd(void){

	cout << "Running contribAdd " << endl;
	unsigned int i,j,row;
	
	for(i=0;i<rownum;i++) {
		float_row_contrib[i] =  (float) (1. / (float) columns_covered_by_row_count[i]);
		//cout << "float row contrib for row " << i << " is " << float_row_contrib[i] << endl;
	}
	
	for(i=0;i<colnum;i++) {
		float_col_contrib[i]=0.;
		for(j=0;j<rows_covered_by_column_count[i];j++) {
			row = rows_covered_by_column[i][j];
			float_col_contrib[i]+=float_row_contrib[row];

		}
		//cout << "float column contrib for column " << i << " is " << float_col_contrib[i] << endl;
	}

	Essentials();
	do {
		
		if ( covered_rows==rownum ) 
			return solution;

		Contrib_SelectColumn();
	} while ( true );
}


void HeurCover::initialize() {

	int j=0;
	int i=0;
	int cols=CM->GetColNum();
	int rows=CM->GetRowNum();
	int cost;

	int* helpMap;
	int rowsCovered;
	int colsCovered;

	costs=new unsigned int[cols];
	x = new int[cols];
	
	row_is_covered=new bool[rows];

	rows_covered_by_column = new unsigned int*[cols];
	rows_covered_by_column_count = new unsigned int[cols];
	columns_covered_by_row = new unsigned int*[rows];
	columns_covered_by_row_count = new unsigned int[rows];
	
	
	col_contrib = new int[cols];
	row_contrib = new int[rows];

	float_col_contrib = new float[cols];
	float_row_contrib = new float[rows];

	// Set number of covered rows to 0
	covered_rows =0;

	// Mark all rows as not covered
	memset(row_is_covered,0,rows);

	//cout << "map 1" << endl;
	helpMap = new int[rows];
	
	for(i=0;i<cols;i++) {
		
		
		//cout <<"column" << i << " :" ;
		// Find minimal cost of columns covering this row
		cost = CM->GetCost(i);
		costs[i]=cost;

		memset(helpMap,0,rows);
		rowsCovered=0;
		
		// Find all rows covered by this column
		// Store their indexes into help array
		for(j=0;j<rows;j++) {
			if (CM->GetValue(j,i)) {
				helpMap[rowsCovered]=j;
				rowsCovered++;
				//cout << j << ",";
			}
		}
		
		// Copy the help array into mapping
		rows_covered_by_column[i] = new unsigned int[rowsCovered];
		memcpy(rows_covered_by_column[i],helpMap,rowsCovered*sizeof(int));
		rows_covered_by_column_count[i] = rowsCovered;
		
		//if ( rowsCovered==0 ) cout << "Column "<< i << " covering 0 rows." << endl;

		col_contrib[i] = rowsCovered;
		//cout << endl;
	}
	
	if (helpMap!=NULL) 
		delete[] helpMap;

	//cout << "map 2" << endl;

	// Create mapping of columns covered by rows
	helpMap = new int[cols];
	

	for(i=0;i<rows;i++) {
		memset(helpMap,0,cols);
		colsCovered=0;
		//cout <<"row" << i << "(" << problemView->row_map[i] << "):";

		// Find all columns covering this row
		// Store their indexes into help array
		for(j=0;j<cols;j++) {
			if (CM->GetValue(i,j)==1) {

				helpMap[colsCovered]=j;
				colsCovered++;
			}
		}

		// Copy the help array into mapping
		columns_covered_by_row[i] = new unsigned int[colsCovered];
		memcpy(columns_covered_by_row[i],helpMap,colsCovered*sizeof(int));
		columns_covered_by_row_count[i] = colsCovered;

		//if ( rowsCovered==0 ) cout << "Row "<< i << " covered by 0 columns." << endl;
		row_contrib[i] = colsCovered;

		
		//cout << endl;

	}
	
	if (helpMap!=NULL) 
		delete[] helpMap;

	
	cout << "Init complete" << endl;

}