# Repetitive 'if' statements with same action and different conditions

This topic is 3904 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a 2d grid of objects (crystals), of different colours, and I have a function whose job it is, is to start with the 2d index of a crystal and recursively check the neghbours (adjacent crystals) that are the same colour as the start crystal, as defined by 'm_currentGroupColour'. Info:
• 'm_checkedList' is a list of the indices of the crystals that have already been examined, so we don't go on a recursive stack kill.
• 'm_groupList' is a list of the indices of the crystals that are in the current group (have the same colour and are adjacent to the start crystal, or to one of it's neighbours, or to one of it's neighbours, etc, etc)
• This does work, albiet with only a couple of small tests, but it will be tested more intensively later (when I get back home after the weekend), but I can't see any major problems.
• The checking function wraps left and right, so a crystal at (0,1) is adjacent to a crystal at ([width of array],1), but it does not wrap up and down.
/**
* A function to start with a crystal and check all of it's neighbours. If the neighbours are the same
* colour as the start crystal, it checks the neighbours of those blocks and comes up with a group of the
* same coloured blocks that are connected by edges (horizontally or vertically, not diagonally).
*
* NB. The checking will wrap around left and right, but not up and down.
*
*/
void Cylinder::findMatchingCrystalGroup(const Index2d& index)
{
// Check Crystal Above
Index2d next_index(index.x, index.y+1);
// If we're not at the top row of crystals
if( next_index.y < m_levelSettings.rows &&
// If the colour of the crystal above is the same colour as the current group of crystals
getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&
// if the index we're looking at has not been looked at before
std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(),
next_index) == m_checkedList.end() &&
// if the block is not already in the current group
std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){

// add the index of the crystal to the group list
m_groupList.insert(next_index);

// add the new index to the 'looked at' list
m_checkedList.insert(next_index);

// check the neighbours of the next crystal
findMatchingCrystalGroup( next_index );
}

// Check Crystal Below
next_index = Index2d(index.x, index.y-1);
// If we're not on the bottom row of crystals
// NB. Needs to be 'index.y', because it is unsigned, if we try to test 'next_index.y' after the assignment,
// it will wrap around from 0 to large positive values.
if( index.y > 0 &&
// If the crystal below is the same colour as the current group of crystals
getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&
// if the index we're looking at has not been looked at before
std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(),
next_index) == m_checkedList.end() &&
// if the block is not already in the current group
std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){

// add the index of the crystal to the group list
m_groupList.insert(next_index);

// add the new index to the 'looked at' list
m_checkedList.insert(next_index);

// check the neighbours of the next crystal
findMatchingCrystalGroup( next_index );
}

// Check Crystal Right
next_index = Index2d(index.x+1, index.y);
// wrap around to the other side if necessary
if( next_index.x >= m_levelSettings.columns )
next_index.x = 0;

// If the crystal to the right is the same colour as the current group of crystals
if( getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&
// if the index we're looking at has not been looked at before
std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(),
next_index) == m_checkedList.end() &&
// if the block is not already in the current group
std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){

// add the index of the crystal to the group list
m_groupList.insert(next_index);

// add the new index to the 'looked at' list
m_checkedList.insert(next_index);

// check the neighbours of the next crystal
findMatchingCrystalGroup( next_index );
}

// Check Crystal Left
next_index = Index2d(index.x-1, index.y);
// wrap around to the other side if necessary
// NB. Needs to be 'index.x', because it is unsigned, if we try to test 'next_index.x' after the assignment,
// it will wrap around from 0 to large positive values.
if( index.x <= 0 )
next_index.x = m_levelSettings.columns-1;

// If the crystal to the left is the same colour as the current group of crystals
if( getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&
// if the index we're looking at has not been looked at before
std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(),
next_index) == m_checkedList.end() &&
// if the block is not already in the current group
std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){

// add the index of the crystal to the group list
m_groupList.insert(next_index);

// add the new index to the 'looked at' list
m_checkedList.insert(next_index);

// check the neighbours of the next crystal
findMatchingCrystalGroup( next_index );
}

}


My problem is that I feel that the 4 major if statements are really unwieldy, because they all do the exact same thing, it's just that the if statements have 1-2 different conditions, and 2 conditions that are exactly the same. It just feels like bad coding. Ideas on how to get this down to something more readable?

##### Share on other sites
Factor out identical or nearly identical function into an auxiliary function, which is then called from the main code with different parameters. Judging from your code, this function would start with two or three distinct conditions, with an early return when they fail, and then execute the associated code.

int wrap(int x, int max) {  if (x < 0) return max - 1;  if (x == max) return 0;  return x;}void Cylinder::findMatchingCrystalGroup(const Index2d& index){  // Check Crystal Above  if( next_index.y < m_levelSettings.rows)    ExploreCrystal(Index2d(index;x,index.y+1));  // Check Crystal Below  if (index.y > 0)     ExploreCrystal(Index2d(index.x,index.y-1));  // Check Crystal Right  ExploreCrystal(Index2d(    wrap(index.x + 1, m_levelSettings.columns),index.y));  // Check Crystal Left  ExploreCrystal(Index2d(    wrap(index.x - 1, m_levelSettings.columns),index.y));}void Cylinder::ExploreCrystal(const Index2d& next_index) {  // Different color  if (!getCrystal(next_index)->isColourMatch(m_currentGroupColour))   {    return;   }  // if the index we're looking at has been looked at before  if (std::find(m_checkedList.begin(), m_checkedList.end(),next_index)        != m_checkedList.end())   {    return;  }  // if the block is already in the current group  if (std::find(m_groupList.begin(), m_groupList.end(), next_index)        != m_groupList.end())  {    return;  }  // add the index of the crystal to the group list  m_groupList.insert(next_index);  // add the new index to the 'looked at' list  m_checkedList.insert(next_index);  // check the neighbours of the next crystal  findMatchingCrystalGroup( next_index );}

##### Share on other sites
	Index2D test_and_adjust( Index2D &index, int dx, int dy ){	Index2D next_index( index.x + dx, index.y + dy);	if (index.x <= 0) next_index.x = m_levelSettings.columns-1;	if (index.x > m_levelSettings.columns) next_index.x = 0;		if( getCrystal(next_index)->isColourMatch(m_currentGroupColour) &&		// if the index we're looking at has not been looked at before		std::find<IndexList::iterator, Index2d>(m_checkedList.begin(), m_checkedList.end(),		next_index) == m_checkedList.end() &&		// if the block is not already in the current group		std::find<IndexList::iterator, Index2d>(m_groupList.begin(), m_groupList.end(), next_index) == m_groupList.end() ){		// add the index of the crystal to the group list		m_groupList.insert(next_index);		// add the new index to the 'looked at' list		m_checkedList.insert(next_index);		// check the neighbours of the next crystal		findMatchingCrystalGroup( next_index );	}	}void Cylinder::findMatchingCrystalGroup(const Index2d& index){	test_and_adjust( index,  1,  0 );	test_and_adjust( index, -1,  0 );	test_and_adjust( index,  0, -1 );	test_and_adjust( index,  0,  1 );}

I don't guarantee the code is still correct, make sure to check the conditions are really the same, and that there aren't any other hidden conditions or similar.

But this is the most trivial refactoring. You perform 1 - 2 redundant tests for each test_and_adjust, that could be solved with templates, but I don't think it's necessary.

##### Share on other sites
Ah, good old flood fill.

1) Simplify the recursion. Instead of checking whether the neighbours are part of the group, check whether the *current* node is part of the group; and if it is, always recurse to the neighbours (because they might be).

2) (Actually, I'm doubting myself about this one. ToohrVyk also has a good idea with the wrap() function.) Take advantage of the wrapping of the unsigned values. Since this will produce a large positive value - certainly larger than the rows/columns of the grid - you can actually use the exact same checking condition.

3) Don't specify the template parameters for std::find. One of the nice things about C++ is that templated functions can infer their template types from the parameters.

4) The checked list and group list are actually completely redundant with each other (I assume you clear both in a helper function before starting the recursion, the same place that m_currentGroupColour gets set): each time you add to one, you add the same node to the other, so they'll always have the same contents. After all, the nodes that you know are in the group (group list) are the same as the ones that you already checked and know to be in the group (checked list), yeah?

void Cylinder::findMatchingCrystalGroupVertical(int x, int y) {	Index2d index(x, y);	if (index.y < m_levelSettings.rows) {		findMatchingCrystalGroup(index);	}}void Cylinder::findMatchingCrystalGroupHorizontal(int x, int y) {	Index2d index(x, y);	// If strictly greater, we must have wrapped around the left side...	if (index.x > m_levelSettings.cols) { index.x = m_levelSettings.cols - 1; }	else if (index.x == m_levelSettings.cols) { index.x = 0; }	findMatchingCrystalGroup(index);}void Cylinder::findMatchingCrystalGroup(const Index2d& index) {	// If the colour matches...	if (getCrystal(index)->isColourMatch(m_currentGroupColour) &&	    // and we don't already know about this one,	    std::find(m_groupList.begin(), m_groupList.end(), index) ==	    m_groupList.end()) {		// add it,		m_groupList.insert(index);		// and consider its neighbours.		findMatchingCrystalGroupVertical(index.x, index.y + 1);		findMatchingCrystalGroupVertical(index.x, index.y - 1);		findMatchingCrystalGroupHorizontal(index.x + 1, index.y);		findMatchingCrystalGroupHorizontal(index.x - 1, index.y);	}}

5) The packing with Index2d's seems a bit unwieldy. It might be easier to create them within the main recursive function, like this:

void Cylinder::findMatchingCrystalGroupVertical(int x, int y) {	if (y < m_levelSettings.rows) {		findMatchingCrystalGroup(x, y);	}}void Cylinder::findMatchingCrystalGroupHorizontal(int x, int y) {	// If strictly greater, we must have wrapped around the left side...	if (x > m_levelSettings.cols) { x = m_levelSettings.cols - 1; }	else if (x == m_levelSettings.cols) { x = 0; }	findMatchingCrystalGroup(x, y);}void Cylinder::findMatchingCrystalGroup(int x, int y) {	Index2d index(x, y);	// If the colour matches...	if (getCrystal(index)->isColourMatch(m_currentGroupColour) &&	    // and we don't already know about this one,	    std::find(m_groupList.begin(), m_groupList.end(), index) ==	    m_groupList.end()) {		// add it,		m_groupList.insert(index);		// and consider its neighbours.		findMatchingCrystalGroupVertical(x, y + 1);		findMatchingCrystalGroupVertical(x, y - 1);		findMatchingCrystalGroupHorizontal(x + 1, y);		findMatchingCrystalGroupHorizontal(x - 1, y);	}}

##### Share on other sites

This topic is 3904 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.