CODEWITHSUNDEEP
c++
Nick____9
Nick____9

Reputation: 71

Cleanest way to avoid accessng an array out of bounds?

Say I have a 5x5 2D Array. For a given position in the array, I need to check if the adjacent positions contains a certain value. How do I handle elements that are on the edge of the array?

For example, my immediate thought to handle something like this would be; 

if(array[i-1][j] != 'A' && array[i][j-1] != 'A' && array[i+1][j] != 'A' && array[i][j+1] != 'A')

but given any element where i or j is 0/4, one (or two) of those statements will attempt to check something that is out of bounds of the dimension of the array. Is there a clean way to do this without nesting a bunch of if statements to check if the element is at the edge?

Upvotes: 1

Views: 1131

Answers (4)

quetzalcoatl
quetzalcoatl

Reputation: 33556

Is there a clean way to do this without nesting a bunch of if statements to check if ...

Yes. That is called NOT nesting. Focus on the checking part, and notice that you don't need nesting. For any part of the test to be done, a partial result may define the total outcome, and you can use it to break the code into parts.

Instead of

// using short-cut evaluation to build a HUGE if
if(x > 0 && y > 0 && data[x][y-1] != 'A' ...)
{
   do something1;
   do something2;
}

or

// using nesting to guarantee some conditions "from now onwards"
if(x > 0 && y > 0)
{
    do something1;
    if(data[x][y-1] != 'A' ...)
        do something2;
}

just write

bool Check1(...)
{
    if(x < 0) return false; // A*
    if(y < 0) return false;
    ...

    return true;
}

bool Check2(...)
{
    if(data[x][y-1] != 'A') return false; // A*
    ...

    return true;
}

and at the original place

bool sidesOk = Ćheck1(....);
bool neighboursOk = Ćheck2(....);

// first case
if(sidesOk && neighboursOk)
{
   do something1;
   do something2;
}

// second case
if(sidesOk)
   do something1;

if(sidesOk && neighboursOk)
   do something2;

// or even - depending on your algorithm
if(!sidesOk)
   return;

But then, it's down to aesthetics and your personal preferences. Both this and your code works. There might be minor performance differences (measure it if you need!) but the overall logic and the result are the same.

Notabene - A* - note that there are some "good coding rules" that discourage constructing code that have multiple return paths, and that promote a "single function single return" rule. As if tracing when/where the function exists is a hard thing. If you ever heard this rule, forget it, and your life will be easier. This rule was invented when we were writing assembly by hand and when the assembly was at pre-MacroAssembler stage, and contained no macros and no functions and you wrote function-like code manually by conditions and jumps. Adapting that rule to current tools and needs, it should say "keep branching and return paths easy to comprehend". And yes, the if(x)return false block is what the compiler would do when you are using short-cut evaluation if(x&&y&&..) "so why dont we keep it one-line already" - it's more important for the code to be easy for humans to read.

Upvotes: 0

john
john

Reputation: 87997

You can use boolean logic, and short circuit evaluation

if ((i == 0 || array[i-1][j] != 'A') &&
    (j == 0 || array[i][j-1] != 'A') &&
    (i == 4 || array[i+1][j] != 'A') &&
    (j == 4 || array[i][j+1] != 'A'))
{
    ...
}

I'm assuming that you want to consider array[-1][j] != 'A' etc as true. If not then the expression would change.

Upvotes: 1

MSalters
MSalters

Reputation: 180020

This is a common problem in image processing. As molbdnilo notes in the comments, a common solution is to add some padding; since you use a 3x3 neighborhood you need to add just a single pixel on all sides.

Another solution that's sometimes used is to mirror accesses beyond the image bound. That is to say, if x>bound you use (2*bound-x) instead, and the same for y. Alternatively, you can use if (x>bound) x=bound. A common factor here is that you limit the number of if-statements by handling x and y separately.

Upvotes: 1

ShadowMitia
ShadowMitia

Reputation: 2533

You can try splitting the algorithm in two parts:

  • first do all the cases in the 3x3 array inside the 5x5 which doesn't have the edge cases
  • finish up with all the remaining edges

In each situation you know in what condition you are, so you can minimise ìf` checks

Upvotes: 0

Related Questions