Index into array as if it is circular

The problem:

Treat an array as if it is circular; out-of-bounds indices "wrap around" the array to become in-bounds.

Current solution:

// roudedArray.cpp
#include <iostream>

template <typename T, int N>
int wrapAroundArray(int i, T(&ThisArray)[N])
{
// "wrap" i around ThisArray, landing on a valid index
while (i < 0) { i += N; }
while (i >= N) { i -= N; }
return i;
}

std::string words[] = { "this", "and", "that" };

int main()
{
for (int i = -9; i < 10; i++)
{
std::cout << "i: " << i;
std::cout << ", word: " << words[adj] << std::endl;
}
}


Output (compile with g++ roundedArray.cpp):

i: -9, adjusted index: 0, word: this
i: -8, adjusted index: 1, word: and
i: -7, adjusted index: 2, word: that
i: -6, adjusted index: 0, word: this
i: -5, adjusted index: 1, word: and
i: -4, adjusted index: 2, word: that
i: -3, adjusted index: 0, word: this
i: -2, adjusted index: 1, word: and
i: -1, adjusted index: 2, word: that
i: 0, adjusted index: 0, word: this
i: 1, adjusted index: 1, word: and
i: 2, adjusted index: 2, word: that
i: 3, adjusted index: 0, word: this
i: 4, adjusted index: 1, word: and
i: 5, adjusted index: 2, word: that
i: 6, adjusted index: 0, word: this
i: 7, adjusted index: 1, word: and
i: 8, adjusted index: 2, word: that
i: 9, adjusted index: 0, word: this


I'd prefer an arithmetic (constant-time) solution that produces the same results. Any suggestions?

The arithmetic solution to this is relatively simple as we're talking modulo here:

return i % N;


When I ran a few calculations on the modulo operator through WolframAlpha, I got the following results:

for $F(x) = x \mod 3$

$5 \mapsto 2$
$4 \mapsto 1$
$3 \mapsto 0$
$2 \mapsto 2$
$1 \mapsto 1$
$0 \mapsto 0$
$-1 \mapsto 2$
$-2 \mapsto 1$
$-3 \mapsto 0$

The pattern we see here is exactly what you describe.

@Schism pointed out that this behavior is only that of "mathematical modulo". It seems that some implementations are unfriendly in that regard. We can thus assume that we need to actually do the switching of negative numbers ourselves.

This leads to the following implementation:

if (i < 0) {
//assuming the behavior described by Schism (-1 % 3 = -1)
i = N + (i % N);
} else {
i = i % n;
}


Unfortunately this is still implementation-dependent, so now we need to eliminate the sign in our modulo calculations to have the same behavior, regardless of implementation:

bool wasNegative = false;
if (i < 0) {
wasNegative = true;
i = -i; //there's definitely a bithack for this.
}
int offset = i % N;
return (wasNegative) ? (N - offset) : (offset);

• That's mathematical modulus. Unfortunately C++ is special and, depending on implementation, -1 % 3 == -1. Jul 24, 2014 at 14:03
• This worked for me. I was probably trying to do it in too few steps. Thanks! Jul 24, 2014 at 16:42
• I would suggest checking for negativity after the modulus, rather than before. That way your "if negative" rule will only apply to the implementations that leave it negative. Jul 24, 2014 at 20:08
• @Brilliand, that's not a bad suggestion, but at the moment I'm willing to be a little slower in order to be more consistent. Jul 25, 2014 at 2:10
• @Schism: The sign of the result of the % operator is guaranteed to be equal to the sign of the first argument since C++11. Jun 19, 2015 at 20:17

Stumbled upon a simpler solution here (notice the %% operator):

template <typename T, int N>
int betterModulo(int i, T(&)[N])
{
return (i % N + N) % N;
}


Further searching turned up this, which helped me feel like I was not crazy for wanting to think of things as circular... :)

You shouldn't have words in global scope. As you're just passing it to another function from main(), initialize it within main(). It should also be const since it's not being modified anywhere.

const std::string words[] = { "this", "and", "that" };


Also, if you have C++11, use std::array instead. C-arrays should be avoided in C++.

constexpr std::array<std::string, 3> words { "this", "and", "that" };