/***
Implementation of algorithms solving Minimum Weighted Set Cover Problem

*/



#include <stdlib.h>
#include <iostream>
#include  <list>

#include "MWSCP.h"


template <class W>
  WeightedSet<W>::WeightedSet(W w, int n) {
   // w is the weight, n is the number of elements
   weight = w;
   els = n;
   elements = new int[n];
  } 

template   <class W>
WeightedSet<W>::~WeightedSet(){
//	delete [] elements;
}


template <class W>
bool WeightedSet<W>::operator <(const WeightedSet<W>& sOperand)
{
  return this.rweight < sOperand.rWeight;
}

template <class W>
bool WeightedSet<W>::operator >(const WeightedSet<W>& sOperand)
{
  return this.rweight > sOperand.rWeight;
}

template <class W>
bool WeightedSet<W>::operator ==(const WeightedSet<W>& sOperand)
{
  return this.rweight == sOperand.rWeight;
}



template <class W> 
   MWSCP<W>::MWSCP(int pels, int pcolls) {
     // pels is the total number of elements, pcolls is the number of collections
     els = pels;
     covered = new int[els];
     for (int i=0; i < els; i++) covered[i] = 0;
     colls = pcolls;
     collections = (WeightedSet<W> *)malloc(colls * sizeof(WeightedSet<W>));
   } 
  
template <class  W>
MWSCP<W>::~MWSCP(){
	delete [] covered;
	delete [] collections;
}

template <class W>  
solution<W> MWSCP<W>::solveGreedy(){
   // solves this instance of the MWSCP 
      W totalcost = 0; int executions = 0;
	  solution<W> solution;
      while (!check() && executions++ < els) {
         // choose the lowers price
         W mincost = 0;
#ifdef DEBUG
		  cout << executions << endl;
#endif 		  
		  
         int collection = 0;
         for (int i = 0; i< colls; i++ ){
             // check all collections to find a collection with the minimal cost per uncovered element 
             W cost;
             int notcovered = 0;
             WeightedSet<W> *c  = &collections[i];
             for  (int j = 0; j < c->els; j++)  if (covered[c->elements[j]] == 0 ) notcovered++;
             if (notcovered > 0) cost = c->weight/(static_cast<W>(notcovered));
             else continue; // all elements of a given collection are covered already
             if (mincost == 0 /*the first execution*/ || mincost > cost ) {mincost = cost; collection = i; continue;}
         }
		 WeightedSet<W> *c  = &collections[collection];
         totalcost += c->weight;
         for (int j = 0; j < c->els; j++) covered[c->elements[j]] = 1;
		 solution.collections.push_back(*c);
      }
	  solution.size = executions+1;
	  solution.cost = totalcost;
	  cout << endl << totalcost << endl;
	  return solution;
   }
   
template <class W>
solution<W> MWSCP<W>::solveLayered(){
      W residue[colls]; // coefficient of the large-degree function
	  W coeff; // coefficient of the largest-degree function
	  solution<W> solution;
	  for (int i=0; i < colls; i++) residue[i] = collections[i].weight;
	  list<WeightedSet<W> > SetCover; // a list of collections which will be chosen at this layer
      W totalcost = 0; int executions = 0;
      while (!check() && executions++ < els) {
         // choose the lowers price
         W mincost = 0; 
#ifdef  DEBUG
		  cout << executions << endl;
#endif		  
		  
		  int collection = 0;
         for (int i = 0; i< colls; i++ ){
             // check all collections to find a collection with the minimal cost per uncovered element 
             W cost;
             int notcovered = 0;
             WeightedSet<W> *c  = &collections[i];
             for  (int j = 0; j < c->els; j++)  if (covered[c->elements[j]] == 0 ) notcovered++;
             if (notcovered > 0) cost = (residue[i])/(static_cast<W>(notcovered));
             else continue; // all elements of a given collection are covered already
			 if (mincost == cost) SetCover.push_back(*c);
             if (mincost == 0 /*the first execution*/ || mincost > cost ) 
			   {mincost = cost; collection = i; coeff = cost/notcovered;
			   SetCover.clear(); SetCover.push_back(*c);
				 continue;}
            }
		 WeightedSet<W> *c  = &collections[collection];
		 // before update we have to compute new residue...it can be postponed to the next step
		 for (int i = 0; i < colls; i++){
		    WeightedSet<W> *c = &collections[i];
			int notcovered = 0;
			for  (int j = 0; j < c->els; j++)  if (covered[c->elements[j]] == 0 ) notcovered++;
			residue[i] -= notcovered * coeff;
			solution.collections.push_back(*c);
		 }
		 typename list<WeightedSet<W> >::iterator iter;
		 for (iter = SetCover.begin(); iter != SetCover.end(); iter++){
         totalcost += iter->weight;
	     solution.size +=1;
         for (int j = 0; j < iter->els; j++) covered[iter->elements[j]] = 1;}

      }
	  solution.cost = totalcost;
	  cout << endl << totalcost << endl;
    return solution;
}   


template <class W>   
bool MWSCP<W>::check() {
   // check if all elements are covered
       for (int i=0; i<els; i++) if (covered[i] == 0)  return 0;
       return 1;
   }