#include "InputSet.h"
#define MAX_BUF 0xF
std::set<long> InputSet::universe;
std::set<InputSet*> InputSet::allSets;
std::map<long, std::set<InputSet*> > InputSet::matrix;
std::set<InputSet*> InputSet::chosen;
void InputSet::deleteAll()
{
chosen.clear();
matrix.clear();
universe.clear();
std::set<InputSet*>::iterator itr;
for (itr = allSets.begin(); itr != allSets.end(); itr++ ) {
InputSet* iSet = *itr;
delete iSet;
}
allSets.clear();
}
InputSet* InputSet::parse(std::string filePath, std::string setName)
{
FILE *inpFile = fopen(filePath.c_str(), "r");
if (!inpFile) return NULL;
InputSet *newInp = new InputSet();
newInp->fileName = setName;
char buffer[MAX_BUF];
while (!feof(inpFile)) {
long el = 0;
if (fscanf(inpFile,"%lx",&el) > 0) {
newInp->elems.insert(el);
InputSet::globalAdd(newInp, el);
}
}
fclose(inpFile);
//printf("File = %s size = %d universe = %d\n", newInp->fileName.c_str(), newInp->elems.size(), matrix.size());
return newInp;
}
void InputSet::globalAdd(InputSet *elSet, long el)
{
InputSet::universe.insert(el);
InputSet::allSets.insert(elSet);
std::set<InputSet*> &owners = InputSet::matrix[el];
owners.insert(elSet);
}
size_t InputSet::getMinCoverage()
{
size_t minSize = 0;
std::map<long, std::set<InputSet*> >::iterator itr;
for (itr = matrix.begin(); itr != matrix.end(); itr++ ) {
size_t setSize = itr->second.size();
if (minSize == 0 || setSize < minSize) {
minSize = setSize;
}
}
return minSize;
}
InputSet* InputSet::getTheBiggest(long el)
{
size_t max = 0;
InputSet* maxSet = NULL;
std::set<InputSet*> &inpSet = InputSet::matrix[el];
std::set<InputSet*>::iterator setItr;
for (setItr = inpSet.begin(); setItr != inpSet.end(); setItr++ ) {
size_t size = (*setItr)->elems.size();
if (max == 0 || size > max) {
max = size;
maxSet = *setItr;
}
}
return maxSet;
}
InputSet* InputSet::getCandidateSet()
{
size_t minCovSize = getMinCoverage();
long minEl = 0;
size_t maxSize = 0;
InputSet* maxSet = NULL;
std::map<long, std::set<InputSet*> >::iterator itr;
for (itr = matrix.begin(); itr != matrix.end(); itr++ ) {
size_t setSize = itr->second.size();
if (minCovSize == setSize) {
long el = itr->first;
InputSet* maxContainingSet = InputSet::getTheBiggest(el);
if (maxContainingSet->elems.size() > maxSize) {
maxSize = maxContainingSet->elems.size();
maxSet = maxContainingSet;
minEl = el;
}
}
}
//printf("Candidate el = %ld, in sets: %d\n", minEl, InputSet::matrix[minEl].size());
//InputSet::printSets(InputSet::matrix[minEl]);
return maxSet;
}
bool InputSet::removeFromAllSets(long el)
{
std::set<InputSet*> &sets = matrix[el];
std::set<InputSet*>::iterator itr;
for (itr = sets.begin(); itr != sets.end(); ) {
InputSet* iSet = *itr;
std::set<long> &elems = iSet->elems;
itr++;
elems.erase(el);
}
return true;
}
bool InputSet::removeChildsOfChosen(InputSet* chosen)
{
std::set<long> &els = chosen->elems;
for (std::set<long>::iterator eItr = els.begin(); eItr != els.end(); ) {
long cEl = *eItr;
eItr++;
removeFromAllSets(cEl);
matrix.erase(cEl);
}
return true;
}
bool InputSet::algoStep()
{
InputSet *chosenSet = getCandidateSet();
if (chosenSet == NULL) {
return false;
}
InputSet::chosen.insert(chosenSet);
removeChildsOfChosen(chosenSet);
//InputSet::printSets(InputSet::chosen);
return true;
}
void InputSet::printSets(std::set<InputSet*> &inpSet, FILE *outFile)
{
std::set<InputSet*>::iterator setItr;
for (setItr = inpSet.begin(); setItr != inpSet.end(); setItr++ ) {
if (outFile) {
fprintf(outFile, "%s\n", (*setItr)->fileName.c_str());
} else {
printf("\t%s\n", (*setItr)->fileName.c_str());
}
}
}