InputSet.cpp

#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());
		}
	}
}