C++ idiom for loop edges

Question

Problem 1: suppose you have an array of n floats and you want to calculate an array of n running averages over three elements. The middle part would be straightforward:

for (int i=0; i<n; i++)
    b[i] = (a[i-1] + a[i] + a[i+1])/3.

But you need to have separate code to handle the cases i==0 and i==(n-1). This is often done with extra code before the loop, extra code after the loop, and adjusting the loop range, e.g.

b[0] = (a[0] + a[1])/2.
for (int i=1; i<n-1; i++)
    b[i] = (a[i-1] + a[i] + a[i+1])/3.;
b[n-1] = (a[n-1] + a[n-2])/2.

Even that is not enough, because the cases of n<3 need to be handled separately.

Problem 2. You are reading a variable-length code from an array (say implementing a UTF-8 to UTF-32 converter). The code reads a byte, and accordingly may read one or more bytes to determine the output. However, before each such step, it also needs to check if the end of the input array has been reached, and if so, perhaps load more data into a buffer, or terminate with an error.

Both of these problems are cases of loops where the interior of the loop can be expressed neatly, but the edges need special handling. I find these sort of problems the most prone to error and to messy programming. So here's my question: Are there any C++ idioms which generalize wrapping such loop patterns in a clean way?

question from:https://stackoverflow.com/questions/65878868/c-idiom-for-loop-edges

Answer 1

Efficiently and elegantly handling boundary conditions is troublesome in any programming language -- C++ has no magic hammer for this. This is a common problem with applying convolution filters to signals / images -- what do you do at the image boundaries where your kernel goes outside the image support?

There are generally two things you are trying to avoid:

• out of bounds array indexing (which you must avoid), and
• special computation (which is inelegant and results in slower code due to extra branching).

There are usually three approaches:

• Avoid the boundaries -- this is the simplest approach and is often sufficient since the boundary case make up a tiny slice of the problem and can be ignored.
• Extend the bounds of your buffer -- add extra columns/rows of padding to the array so the same code used in the general case can be used at the edges. Of course this raises the problem of what values to place in the padding -- this often depends on the problem you are solving and is considered in the next approach.
• Special computation at the boundary -- this is what you do in your example. Of course how you do this is problem dependent and raises a similar issue as the previous approach -- what is the correct thing to do when my filter (in your case an averaging filter) extends beyond the array support? What should I consider the values to be outside the array support? Most image filter libraries provide some form of extrapolation options -- for example:
  • assume a value zero or some other constant (define a[i] = 0 if i < 0 || i >= n),
  • replicate the boundary value (e.g. a[i] = a[0] if i < 0 and a[i] = a[n-1] if i >= n)
  • wrap the value (define a[i] = a[(i + n) % n] -- makes sense of some cases -- e.g, texture filters)
  • mirror the border ((e.g. a[i] = a[abs(i+1)] if i < 0 and a[i] = a[2n - i -1] if i >= n)
  • other special case (what you do)

When reasonable, its best to separate the special case from the general case (like you do) to avoid inelegant and slow general cases. One could always wrap/hide the special case and general case in a function or operator (e.g., overload operator[]) , but this only sugar coats the problem like any contrived C++ idiom would. In a multi-threaded environment (e.g. CUDA / SIMD) you can do some other tricks be preloading out-of-bounds values, but you are still stuck with the same problem.

This is why programmers use the phrase "edge case" in referring any kind of special case programming and is often a time sink and a source for annoying errors. Some languages that efficiently support exception handling for out of bounds array indexing (e.g. Ada) can make for prettier code, but still cause the same pain.