current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 6 down vote favorite

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++)
  {
    int adj = wrapAroundArray(i, words);
    std::cout << "i: " << i;
    std::cout << ", adjusted index: " << adj;
    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?

share|improve this question
    
Yes, that's also the actual output. I edited the question based on your comment. –  hoosierEE yesterday

2 Answers 2

up vote 6 down vote accepted

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

the solution will be:

return i % N;

this should produce the same results for your adjusted index.

When I ran a few calculations on the modulo operator through wolfram-alpha, I got 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 concern. We can thus assume, we need to actually do the switching of negative numbers ourselves. this leads to 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 what we need to do now is: eliminate the sign in our modulo calculations to have the same behavior, regardless of implementation.

if (i < 0) {
    wasNegative = true;
    i = -i; //there's definitely a bithack for this. I just don't know it ;)
}
int offset = i % N
return (wasNegative) ? N - offset : offset;

so here's your mathematical solution ;)

share|improve this answer
    
Could you expound on "count the absolute from the last index backwards"? It doesn't read that clearly to me. Could you also directly address the case when i < 0? –  Schism yesterday
    
That's mathematical modulus. Unfortunately C++ is special and, depending on implementation, -1 % 3 == -1. –  Schism yesterday
    
This worked for me. I was probably trying to do it in too few steps. Thanks! –  hoosierEE yesterday
    
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. –  Brilliand yesterday
    
@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. –  hoosierEE 21 hours ago
up vote 3 down vote

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" };
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.