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

#include "stdafx.h"

#ifdef _MSC_VER
#pragma hdrstop
#endif

using namespace std;

#include "../../Kernel/myExcept.h"
//#include "stdlib.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 < rownum; i++ ) rows.push_back(i);
	for ( i = 0; i < colnum; i++ ) columns.push_back(i);
	validcontrib = false;
	autocontrib = false;
	considercost = true;
	solution = new list<unsigned int>;
	colptrs.reserve(colnum);
	colptrs2.reserve(colnum);
}

/*HeurCover::~HeurCover(void)
{
}*/

list<unsigned int>::iterator HeurCover::DeleteRow( list<unsigned int>::iterator row_it )
// Deletes a row pointed by an iterator
// Returns iterator to the next row
{
	list<unsigned int>::iterator row_it1;
	list<unsigned int>::iterator col_it;

	if ( autocontrib && validcontrib ) {
		for ( col_it = columns.begin(); col_it != columns.end(); col_it++ )
			if ( CM->GetValue(*row_it, *col_it) ) colcontrib[*col_it]--;
	} else validcontrib = false;
	rownum--;
	row_it1 = rows.erase(row_it);
	if ( autocontrib && !validcontrib ) RecomputeContributions();
	return row_it1;
}

list<unsigned int>::iterator HeurCover::DeleteColumn( list<unsigned int>::iterator col_it )
// Deletes a column pointed by an iterator
// Returns iterator to the next column
{
	list<unsigned int>::iterator col_it1;
	list<unsigned int>::iterator row_it;

	if ( autocontrib && validcontrib ) {
		for ( row_it = rows.begin(); row_it != rows.end(); row_it++ )
			if ( CM->GetValue(*row_it, *col_it) ) rowcontrib[*row_it]--;
	} else validcontrib = false;
		
	colnum--;
	col_it1 = columns.erase(col_it);
	if ( autocontrib && !validcontrib ) RecomputeContributions();
	return col_it1;
}

list<unsigned int>::iterator HeurCover::MoveToSolution( list<unsigned int>::iterator col_it )
// Moves a column pointed by an iterator to the solution, removes covered rows
// Returns iterator to the next row
{
	list<unsigned int>::iterator row_it;

	solution->push_back( *col_it );
	row_it = rows.begin();
	while ( row_it != rows.end() ) {
		if ( CM->GetValue( *row_it, *col_it ) )
			row_it = DeleteRow(row_it);
		else row_it++;
	}
	return DeleteColumn(col_it);
}

bool HeurCover::RowDominanceRemoval(void)
// solves the row dominance
// Returns true if some change was made
{
	list<unsigned int>::iterator row_it1, row_it2;
	list<unsigned int>::iterator col_it;
	bool flag1, flag2;					// if true, it is dominated
	bool changed = false;
	
	if ( rows.empty() ) return false;
	if ( columns.empty() ) 
		throw RuntimeException( "HeurCover::RowDominanceRemoval: Something's wrong. Some rows are not covered." );

		// for 1-row case
	if ( rows.size() == 1 ) return false;

	row_it1 = rows.begin();
	while ( row_it1 != rows.end() ) {
		row_it2 = row_it1;
		row_it2++;
		flag1 = true;
		flag2 = true;
		while ( row_it2 != rows.end() ) {
			flag1 = true;
			flag2 = true;
			for ( col_it = columns.begin(); col_it != columns.end(); col_it++ ) {
				if ( CM->GetValue(*row_it1, *col_it) && !CM->GetValue(*row_it2, *col_it) ) flag2 = false;
				if ( !CM->GetValue(*row_it1, *col_it) && CM->GetValue(*row_it2, *col_it) ) flag1 = false;
				if ( !flag1 && !flag2 ) break;
			}
			if ( flag1 || flag2 ) changed = true;
			if ( flag2 )
				row_it2 = DeleteRow(row_it2);		// 2nd is dominated
			else if ( flag1 ) {
				row_it1 = DeleteRow(row_it1);		// 1st is dominated
				break;
			} else row_it2++;
		}
		if ( flag2 || !flag1 ) row_it1++;		// do not increment, when 1st was dominated
	}
	return changed;
}

bool HeurCover::ColDominanceRemoval(void)
// Solves the column dominance
// Returns true if any change was made
{
	list<unsigned int>::iterator col_it1, col_it2;
	list<unsigned int>::iterator row_it;
	bool flag1, flag2;					// if true, it is dominated
	bool changed = false;
	
	if ( rows.empty() ) return false;
	if ( columns.empty() ) 
		throw RuntimeException( "HeurCover::ColDominanceRemoval: Something's wrong. Some rows are not covered." );

	// for 1-column case
	col_it1 = columns.begin();
	if ( columns.size() == 1 ) {
		for ( row_it = rows.begin(); row_it != rows.end(); row_it++ )
			if ( CM->GetValue(*row_it, *col_it1) ) {
				MoveToSolution(col_it1);		// it is a non-zero column
				break;
			}
		columns.clear();
		return true;
	}

	for (col_it1 = columns.begin(); col_it1 != columns.end(); ++col_it1)
		colptrs.push_back(&(*col_it1));
	int n = colptrs.size(), i, j;
	colptrs2 = colptrs;

	#pragma omp parallel for default(none) schedule(static, 10) \
		shared(n, changed) private(i, j, flag1, flag2, row_it)
	for (i = 0; i < n; i++) {
		if (colptrs[i] == NULL) continue;
		unsigned int c1 = *colptrs2[i];
		for ( j = i + 1; j < n; j++) {
			if (colptrs[i] == NULL) break;
			if (colptrs[j] == NULL) continue;
			flag1 = flag2 = true;
			unsigned int c2 = *colptrs2[j], a;
			bool v1, v2;
			for (row_it = rows.begin(); row_it != rows.end(); ++row_it) {
					a = *row_it;
					v1 = CM->GetValue(a, c1);
					v2 = CM->GetValue(a, c2);
					if ( v1 && !v2 ) flag1 = false;
					if ( !v1 && v2 ) flag2 = false;
					if ( !flag1 && !flag2 ) break;
			}
			if ( flag1 || flag2 ) changed = true;
			if ( flag2 ) colptrs[j] = NULL;		// 2nd is dominated
			else if ( flag1 ) {
				colptrs[i] = NULL;			// 1st is dominated
				break;
			}
		}
	}
	for (i = 0, col_it1 = columns.begin(); i < n && col_it1 != columns.end(); ++i)
		if (colptrs[i] == NULL) col_it1 = DeleteColumn(col_it1);
		else ++col_it1;
	colptrs.clear();
	colptrs2.clear();
	return changed;
}

bool HeurCover::Essentials(void)
// Moves essential columns to the solution
// Returns true if any
{
	list<unsigned int>::iterator col_it, col;
	list<unsigned int>::iterator row_it;
	set<unsigned int> essentials;
	unsigned short count;

	if ( rows.empty() ) return false;
	if ( columns.empty() ) 
		throw RuntimeException( "HeurCover::Essentials: Something's wrong. Some rows are not covered." );
	//CM->DumpMatrix("CM");
	for ( row_it = rows.begin(); row_it != rows.end(); row_it++ ) {
		count = 0;
		for ( col_it = columns.begin(); col_it != columns.end(); col_it++ ) {
			if ( CM->GetValue( *row_it, *col_it ) ) {
				count++;
				if ( count > 1 ) break;
				col = col_it;
			}
		}
		if ( count == 0 )
			throw RuntimeException( "Cover::Essentials:: A row that cannot be coverered found" );
		if ( count == 1 ) essentials.insert( *col );
	}
	col_it = columns.begin();
	while ( col_it != columns.end() )
		if ( essentials.find(*col_it) != essentials.end() )
			col_it = MoveToSolution(col_it);
		else col_it++;
	return !essentials.empty();
}

void HeurCover::ComputeContributions(void)
// Computes row and column contributions for the whole matrix
{
	unsigned int r, c;

	if ( validcontrib ) return;
	if ( colcontrib.empty() ) colcontrib.resize( CM->GetColNum(), 0 );
	else colcontrib.assign( CM->GetColNum(), 0 );
	if ( rowcontrib.empty() ) rowcontrib.resize( CM->GetRowNum(), 0 );
	else rowcontrib.assign( CM->GetRowNum(), 0 );
	if ( colcontrib.size() != CM->GetColNum() || rowcontrib.size() != CM->GetRowNum() ) 
		throw RuntimeException( "HeurCover:: ComputeContributions: Bad contribution vector size" );
	for ( r = 0; r < CM->GetRowNum(); r++ )
		for ( c = 0; c < CM->GetColNum(); c++ )
			if ( CM->GetValue( r, c ) ) {
				colcontrib[c]++;
				rowcontrib[r]++;
			}
	validcontrib = true;
}

void HeurCover::RecomputeContributions(void)
// Computes row and column contributions for active (non-removed) rows and columns only
{
	list<unsigned int>::iterator row_it;
	list<unsigned int>::iterator col_it;

	if ( validcontrib ) return;
	if ( colcontrib.empty() || rowcontrib.empty() ) {
		ComputeContributions();
		return;
	}
	if ( colcontrib.size() != CM->GetColNum() || rowcontrib.size() != CM->GetRowNum() ) 
		throw RuntimeException( "HeurCover:: RecomputeContributions: Bad contribution vector size" );
	colcontrib.assign( CM->GetColNum(), 0 );
	rowcontrib.assign( CM->GetRowNum(), 0 );
	for ( row_it = rows.begin(); row_it != rows.end(); row_it++ )
		for ( col_it = columns.begin(); col_it != columns.end(); col_it++ )
			if ( CM->GetValue( *row_it, *col_it ) ) {
				colcontrib[*col_it]++;
				rowcontrib[*row_it]++;
			}
	validcontrib = true;
}

void HeurCover::Random_SelectColumn(void)
// Randomly select one column
{
	list<unsigned int>::iterator col_it;
	unsigned int i;

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

	i = rand() % columns.size();
	col_it = columns.begin();
	while ( i != 0 ) {
		col_it++;
		i--;
	}
	MoveToSolution( col_it );
}

void HeurCover::LCMC_SelectColumn(void)
/*
	LCMC (Least Covered, Most Covering) heuristic.
	First select column covering a row covered by a least number of columns
	From these, select a column covering most of rows
	From these, select a column with the least cost
	Implicitly solves column dominance
	Essential columns should be removed prior to LCMC, for better performance
*/
{
	unsigned int min_c, max_c;
	list<unsigned int>::iterator row_it;
	list<unsigned int>::iterator col_it;
	set <unsigned int> r_candidates;
	set <unsigned int>::iterator r_candidates_it;
	list< list<unsigned int>::iterator > c_candidates;
	list< list<unsigned int>::iterator >::iterator c_candidates_it;
	vector< list<unsigned int>::iterator > c_candidates2;

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

	if ( !validcontrib ) RecomputeContributions();

		// find rows covered by least columns
	min_c = rowcontrib[*(rows.begin())];
	for ( row_it = rows.begin(); row_it != rows.end(); row_it++ ) {
		if ( rowcontrib[*row_it] < min_c ) {
			min_c = rowcontrib[*row_it];
			r_candidates.clear();
			r_candidates.insert( *row_it );
		} else if ( rowcontrib[*row_it] == min_c ) r_candidates.insert( *row_it );
	}
	if ( r_candidates.empty() ) 
		throw RuntimeException( "HeurCover::LCMC_SelectColumn:: Something's wrong. No candidate row." );
	
		// select columns covering above rows and most rows
	max_c = 0;
	for ( col_it = columns.begin(); col_it != columns.end(); col_it++ )
		for ( r_candidates_it = r_candidates.begin(); r_candidates_it != r_candidates.end(); r_candidates_it++ )
			if ( CM->GetValue( *r_candidates_it, *col_it ) ) {
				if ( colcontrib[*col_it] > max_c ) {
					max_c = colcontrib[*col_it];
					c_candidates.clear();
					c_candidates.push_back( col_it );
				} else if ( colcontrib[*col_it] == max_c ) c_candidates.push_back( col_it );
			}
	if ( c_candidates.empty() ) 
		throw RuntimeException( "HeurCover::LCMC_SelectColumn:: Something's wrong. No candidate column." );

		// from the row candidates select the one with the least cost
	min_c = CM->GetCost( **c_candidates.begin() );
	for ( c_candidates_it = c_candidates.begin(); c_candidates_it != c_candidates.end(); c_candidates_it++) {
		if ( CM->GetCost(**c_candidates_it) < min_c ) {
			min_c = CM->GetCost(**c_candidates_it);
			c_candidates2.clear();
			c_candidates2.push_back( *c_candidates_it );
		} else if ( CM->GetCost(**c_candidates_it) == min_c ) c_candidates2.push_back( *c_candidates_it );
	}
	if ( c_candidates2.empty() ) 
		throw RuntimeException( "HeurCover::LCMC_SelectColumn:: Something's wrong. No candidate column." );

		// select one randomly
	col_it = c_candidates2[rand() % c_candidates2.size()];
	MoveToSolution( col_it );
}

void HeurCover::MCLC_SelectColumn(void)
/*
	MCLC (Most Covering, Least Covered) heuristic.
	Select the column covering most rows
	From these, select a column covering a row covered by least columns
*/
{
	unsigned int min_c, max_c;
	list<unsigned int>::iterator row_it;
	list<unsigned int>::iterator col_it;
	list< list<unsigned int>::iterator > c_candidates;
	list< list<unsigned int>::iterator >::iterator c_candidates_it;
	vector< list<unsigned int>::iterator > c_candidates2;

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

	if ( !validcontrib ) RecomputeContributions();

	// Find columns covering most rows
	max_c = 0;
	for ( col_it = columns.begin(); col_it != columns.end(); col_it++ )
		if ( colcontrib[*col_it] > max_c ) {
			c_candidates.clear();
			c_candidates.push_back(col_it);
			max_c = colcontrib[*col_it];
		}
		else if ( colcontrib[*col_it] == max_c ) c_candidates.push_back(col_it);
	if ( c_candidates.empty() ) throw RuntimeException( "HeurCover::MCLC_SelectColumn:: Something's wrong. No candidate column." );
	
	// From these, find a column covering a row covered by least columns
	min_c = UINT_MAX;
	for ( c_candidates_it = c_candidates.begin(); c_candidates_it != c_candidates.end(); c_candidates_it++ )
		for ( row_it = rows.begin(); row_it != rows.end(); row_it++ )
			if ( CM->GetValue( *row_it, **c_candidates_it ) ) {
				if ( rowcontrib[*row_it] < min_c ) {
					c_candidates2.clear();
					c_candidates2.push_back(*c_candidates_it);
					min_c = rowcontrib[*row_it];
				}
				else if ( rowcontrib[*row_it] == min_c ) c_candidates2.push_back(*c_candidates_it);
			}
	if ( c_candidates.empty() ) throw RuntimeException( "HeurCover::MCLC_SelectColumn:: Something's wrong. No candidate column." );

	// select one randomly
	col_it = c_candidates2[rand() % c_candidates2.size()];
	MoveToSolution( col_it );
}

void HeurCover::Contrib_SelectColumn(void)
/*
	Combined contribution heuristic
	Selects a column having the highest contribution,
*/
{
	float contrib, maxcontrib;
	unsigned int mincost;
	list<unsigned int>::iterator row_it;
	list<unsigned int>::iterator col_it;
	vector< list<unsigned int>::iterator > c_candidates, c_candidates2;
	vector< list<unsigned int>::iterator >::iterator c_candidates_it;

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

	if ( !validcontrib ) RecomputeContributions();

		// Find columns with maximum combined contribution
	maxcontrib = 0;
	for ( col_it = columns.begin(); col_it != columns.end(); col_it++ ) {
		contrib = 0;
		for ( row_it = rows.begin(); row_it != rows.end(); row_it++ )
			if ( CM->GetValue( *row_it, *col_it ) ) contrib+= 1/(float)rowcontrib[*row_it];
		if ( contrib > maxcontrib ) {
			c_candidates.clear();
			c_candidates.push_back(col_it);
			maxcontrib = contrib;
		} else if ( contrib == maxcontrib ) c_candidates.push_back(col_it);
	}
	if ( c_candidates.empty() ) throw RuntimeException( "HeurCover::Contrib_SelectColumn:: Something's wrong. No candidate column." );

	if ( considercost && c_candidates.size() > 1 ) {
		c_candidates_it = c_candidates.begin();
		mincost = CM->GetCost(**c_candidates_it);
		for ( c_candidates_it = c_candidates.begin(); c_candidates_it != c_candidates.end(); c_candidates_it++ )
			if ( CM->GetCost(**c_candidates_it) < mincost ) {
				c_candidates2.clear();
				c_candidates2.push_back(*c_candidates_it);
				mincost = CM->GetCost(**c_candidates_it);
			} else if ( CM->GetCost(**c_candidates_it) == mincost ) c_candidates2.push_back(col_it);
			// select one randomly
		col_it = c_candidates2[rand() % c_candidates2.size()];
	}
	else {
			// select one randomly
		col_it = c_candidates[rand() % c_candidates.size()];
	}
	MoveToSolution( col_it );
}

list<unsigned int> *HeurCover::Run(void)
{
//	bool changed;
//	bool changed1;

		// preliminary preprocessing
	autocontrib = false;
	considercost = false;
	Essentials();
	ColDominanceRemoval();
		// main cover loop
	do {
//		do {
//			changed = RowDominanceRemoval();
//			changed1 = ColDominanceRemoval();
//			changed = changed || changed1;
//			Essentials();
//		} while ( changed && !rows.empty() && !columns.empty() );
		if ( rows.empty() ) return solution;

		MCLC_SelectColumn();
	} while ( true );
}
