/*
 *  MWSCP.h
 *  Fix
 *
 *  Created by Andrei Lopatenko on 3/4/06.
 *  Copyright 2006 __MyCompanyName__. All rights reserved.
 *
 */
#include <list>
#include <vector>
#include <queue>
//#include "ADT.h"
using namespace std;
 
template <class W> 
class WeightedSet {
  public:
	int identifier; // must be replaced by parameter class latter
  WeightedSet(W, int);
  ~WeightedSet();
  W weight; // the weight
  W rweight; // the "real" or "effective" weight, this field is intended to store information for MWSCP algorithms
  int els;    // the number of elements
  int *elements;  // elements, we assume that integers represent elements of the set
  bool operator <(const WeightedSet<W>&);
  bool operator ==(const WeightedSet<W>&);
  bool operator >(const WeightedSet<W>&);
  
};

template <class W>
 struct solution {
 W cost;
 int size;
 list<WeightedSet<W> > collections;
 };
 
template  <class W> 
class MWSCP {
public:
   MWSCP(int pels, int pcolls);
	~MWSCP();	
   int els; // the total number of elements
   int colls; //the total number of collections
   int* covered;  //covered[element]=0 if element is covered by a current choice of collections
   WeightedSet<W> *collections;  // 
   void reset() {
	   for (int i=0; i < els; i++) covered[i] = 0;
   }
   solution<W> solveGreedy();
   solution<W> solveLayered();
   bool check();
};

/*
template <class  W>
class MWSVPHeap : public MWSCP<W> {
public:
	MWSCPHeap(int, int);
	priority_queue< vector<W> > pq_collections;
};
*/



class MWSCPHeap {
	//  implementation of heapified version of MWSCP, we assume that all elements are ints
	// the first version for WeightedSet<float>
protected:
	//map<int, I> map; // maps elleme
	//PQHeap<WeightedSet<float> > sets;
};