in api/model.cpp [92:417]
void Model::gcd( ComboCollection &vecCombo )
{
if( m_parameters.empty() ) return;
processExclusions( vecCombo );
fixRowSeeds();
int maxRange = -1;
for( ComboCollection::iterator iterC = vecCombo.begin(); iterC != vecCombo.end(); ++iterC )
{
if( ( *iterC )->GetRange() > maxRange )
{
maxRange = ( *iterC )->GetRange();
}
}
if( maxRange <= 0 ) return;
GetTask()->AllocWorkbuf( maxRange );
m_totalCombinations = GlobalZerosCount;
// main loop: repeat until we've found all required parameter value combinations
while( GlobalZerosCount > 0 )
{
DOUT( L"Main loop: GlobalZerosCount " << GlobalZerosCount << L"\n" );
if( GetTask()->AbortGeneration() )
{
// tear down all the combinations
for( ComboCollection::iterator i = vecCombo.begin(); i != vecCombo.end(); ++i )
{
delete *i;
}
throw GenerationError( __FILE__, __LINE__, ErrorType::GenerationCancelled );
}
// initialize all parameters to unbound, not on work list
for( vector<Parameter*>::iterator iter = m_parameters.begin(); iter != m_parameters.end(); ++iter )
{
( *iter )->InitBinding();
}
int unbound = static_cast<int>( m_parameters.size() );
// init all combinations bound, counts to zero
for( ComboCollection::iterator iterC = vecCombo.begin(); iterC != vecCombo.end(); ++iterC )
{
( *iterC )->InitBinding();
}
// initialize work list to empty
WorkList worklist;
// do we have unused seed data?
// if yes: bind those values, make sure combinations get marked, zero counts (including global) updated
if( !m_rowSeeds.empty() )
{
RowSeed &rowSeed = m_rowSeeds.front();
for( RowSeed::iterator ir = rowSeed.begin(); ir != rowSeed.end(); ++ir )
{
( ir->first )->MarkPending();
}
for( RowSeed::iterator ir = rowSeed.begin(); ir != rowSeed.end(); ++ir )
{
// find the parameter in the collection
Parameter* param = ir->first;
vector<Parameter*>::iterator found = find( m_parameters.begin(), m_parameters.end(), param );
assert( found != m_parameters.end() );
if( found != m_parameters.end() )
{
unbound -= param->Bind( ir->second, worklist );
}
}
m_rowSeeds.pop_front();
}
for( int cidx = 0; cidx < static_cast<int>( vecCombo.size() ); ++cidx )
{
vecCombo[ cidx ]->Print();
}
// Approximate mode must be handled differently from the other modes
if( m_task->GetGenerationMode() == GenerationMode::Approximate )
{
// it's a row not an exclusion but Exclusion is a perfect data structure for it
typedef Exclusion CandidateRow;
CandidateRow candidateRow;
size_t attempt = 0;
bool stop = false;
while( 1 )
{
candidateRow = generateRandomRow();
if( !rowViolatesExclusion( candidateRow ) )
break;
if( ++attempt >= m_task->GetMaxRandomTries() )
{
stop = true;
break;
}
};
if( stop ) break; // out of "GlobalZerosCount > 0" loop
for( CandidateRow::iterator ir = candidateRow.begin(); ir != candidateRow.end(); ++ir )
{
( ir->first )->MarkPending();
}
for( CandidateRow::iterator ir = candidateRow.begin(); ir != candidateRow.end(); ++ir )
{
// find the parameter in the collection
Parameter* param = ir->first;
vector<Parameter*>::iterator found = find( m_parameters.begin(), m_parameters.end(), param );
assert( found != m_parameters.end() );
if( found != m_parameters.end() )
{
unbound -= param->Bind( ir->second, worklist );
}
}
}
// non Approximate aka regular mode
else
{
// loop to build one result vector: while some parameters remain unbound
while( unbound > 0 )
{
if( worklist.IsEmpty() )
{
DOUT( L"Empty worklist: finding a seed combination.\n" );
// pick a zero from feasible combination with the most zeros, bind corresponding values
int maxZeros = 0;
int maxMatch = 0;
int ties = 0;
int choice = -1;
for( int cidx = 0; cidx < static_cast<int>( vecCombo.size() ); ++cidx )
{
if( !vecCombo[ cidx ]->IsFullyBound() )
{
int open = 0;
int match = 0;
// Make sure there's a feasible value set
for( int vidx = 0; vidx < vecCombo[ cidx ]->GetRange(); ++vidx )
{
ComboStatus status = vecCombo[ cidx ]->Feasible( vidx );
if( ComboStatus::Open == status )
{
++open;
}
else if( ComboStatus::CoveredMatch == status )
{
++match;
}
}
// if combo has the most zeros
if( open > maxZeros )
{
choice = cidx;
ties = 1;
maxZeros = open;
}
// if number of zeros ties up with some previous choice, pick randomly
else if( open == maxZeros
&& maxZeros > 0
&& !( rand() % ++ties ) )
{
choice = cidx;
}
// no zeros were found anywhere yet, pick the best matching one
else if( maxZeros == 0
&& match > maxMatch )
{
choice = cidx;
ties = 1;
maxMatch = match;
}
// if there's a tie in match, pick randomly
else if( maxZeros == 0
&& match > 0
&& match == maxMatch
&& !( rand() % ++ties ) )
{
choice = cidx;
}
}
} // for cidx
assert( choice != -1 );
if( -1 == choice )
{
throw GenerationError( __FILE__, __LINE__, ErrorType::GenerationFailure );
}
// no combo had any uncovered combinations in it
if( 0 == maxZeros )
{
int totalWeight = 0;
int bestValue = -1;
// For each non-excluded value in the bitvec, find total weight
for( int vidx = 0; vidx < vecCombo[ choice ]->GetRange(); ++vidx )
{
if( ComboStatus::Excluded != vecCombo[ choice ]->Feasible( vidx ) )
{
// Pick a value using weighted random choice
int weight = vecCombo[ choice ]->Weight( vidx );
totalWeight += weight;
if( rand() % totalWeight < weight )
{
bestValue = vidx;
}
}
}
unbound -= vecCombo[ choice ]->Bind( bestValue, worklist );
}
else
{
// OK, we picked a combination, now pick a value set
vector<int> candidates;
for( int vidx = 0; vidx < vecCombo[ choice ]->GetRange(); ++vidx )
{
if( ComboStatus::Open == vecCombo[ choice ]->Feasible( vidx ) )
{
candidates.push_back( vidx );
}
}
#if (0)
if (candidates.empty())
{
for (int vidx = 0; vidx < vecCombo[choice]->GetRange(); ++vidx)
{
if (CoveredMatch == vecCombo[choice]->Feasible(vidx))
{
candidates.push_back(vidx);
}
}
}
#endif
assert( !candidates.empty() );
int zeroVal = candidates[ rand() % candidates.size() ];
DOUT( L"Chose value " << zeroVal << L", unbound count was " << unbound << L".\n" );
// Bind the values corresponding to the zero
unbound -= vecCombo[ choice ]->Bind( zeroVal, worklist );
DOUT( L"After combo bind, unbound count was " << unbound << L".\n" );
}
}
// worklist is NOT empty
else
{
// pull a parameter from the work list and pick a value
Parameter *param = worklist.GetItem();
assert( !param->GetBoundCount() );
DOUT( L"From worklist " );
param->Bind( param->PickValue(), worklist );
--unbound;
}
} // end: unbound > 0
} // end: non-Approximate
}
m_remainingCombinations = GlobalZerosCount;
// tear down all the combinations
for( ComboCollection::iterator i = vecCombo.begin(); i != vecCombo.end(); ++i )
{
delete *i;
}
resolvePseudoParams();
// put parameter vector back into original sequence
sort( m_parameters.begin(), m_parameters.end(), LessThanBySequence() );
// move results from parameters into this Model
size_t results = 0;
for( ParamCollection::iterator ip = m_parameters.begin(); ip != m_parameters.end(); ++ip )
{
( *ip )->GetFirst();
if( results )
{
assert( ( *ip )->GetTempResultCount() == results );
}
else
{
results = ( *ip )->GetTempResultCount();
}
}
for( size_t n = 0; n < results; ++n )
{
ResultRow resultRow;
for( ParamCollection::iterator ip = m_parameters.begin(); ip != m_parameters.end(); ++ip )
{
resultRow.push_back( ( *ip )->GetNext() );
}
// remove violating cases, it's needed for preview mode of
// generation as in that mode, m_result contains some invalid cases
bool violatesExclusion = false;
if( GetTask()->GetGenerationMode() == GenerationMode::Preview )
{
violatesExclusion = rowViolatesExclusion( resultRow );
}
if( !violatesExclusion )
{
m_results.push_back( resultRow );
}
}
for( ParamCollection::iterator ip = m_parameters.begin(); ip != m_parameters.end(); ++ip )
{
( *ip )->CleanUp();
}
// process all result parameters: mark unknown all result values
// that are under or over-specified.
// only run it on the root; result params should not be part of
// any user-defined submodels anyway.
if( this->GetTask()->GetRootModel() == this )
{
markUndefinedValuesInResultParams();
}
}