#include "InputSet.h" #define MAX_BUF 0xF std::set InputSet::universe; std::set InputSet::allSets; std::map > InputSet::matrix; std::set InputSet::chosen; void InputSet::deleteAll() { chosen.clear(); matrix.clear(); universe.clear(); std::set::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 &owners = InputSet::matrix[el]; owners.insert(elSet); } size_t InputSet::getMinCoverage() { size_t minSize = 0; std::map >::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 &inpSet = InputSet::matrix[el]; std::set::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 >::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 &sets = matrix[el]; std::set::iterator itr; for (itr = sets.begin(); itr != sets.end(); ) { InputSet* iSet = *itr; std::set &elems = iSet->elems; itr++; elems.erase(el); } return true; } bool InputSet::removeChildsOfChosen(InputSet* chosen) { std::set &els = chosen->elems; for (std::set::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 &inpSet, FILE *outFile) { std::set::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()); } } }