Clean, efficient algorithm for wrapping integers i

Question

/**
  * Returns a number between kLowerBound and kUpperBound
  * e.g.: Wrap(-1, 0, 4); // Returns 4
  * e.g.: Wrap(5, 0, 4); // Returns 0      
  */
int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
    // Suggest an implementation?
}

Answer 1

The sign of a % b is only defined if a and b are both non-negative.

int Wrap(int kX, int const kLowerBound, int const kUpperBound)
{
    int range_size = kUpperBound - kLowerBound + 1;

    if (kX < kLowerBound)
        kX += range_size * ((kLowerBound - kX) / range_size + 1);

    return kLowerBound + (kX - kLowerBound) % range_size;
}

Answer 2

Why not using Extension methods.

public static class IntExtensions
{
    public static int Wrap(this int kX, int kLowerBound, int kUpperBound)
    {
        int range_size = kUpperBound - kLowerBound + 1;

        if (kX < kLowerBound)
            kX += range_size * ((kLowerBound - kX) / range_size + 1);

        return kLowerBound + (kX - kLowerBound) % range_size;
    }
}

Usage: currentInt = (++currentInt).Wrap(0, 2);

Answer 3

An answer that has some symmetry and also makes it obvious that when kX is in range, it is returned unmodified.

int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
    int range_size = kUpperBound - kLowerBound + 1;

    if (kX < kLowerBound)
        return kX + range_size * ((kLowerBound - kX) / range_size + 1);

    if (kX > kUpperBound)
        return kX - range_size * ((kX - kUpperBound) / range_size + 1);

    return kX;
}

Answer 4

I've faced this problem as well. This is my solution.

template <> int mod(const int &x, const int &y) {
    return x % y;
}
template <class T> T mod(const T &x, const T &y) {
    return ::fmod((T)x, (T)y);
}
template <class T> T wrap(const T &x, const T &max, const T &min = 0) {
    if(max < min)
        return x;
    if(x > max)
        return min + mod(x - min, max - min + 1);
    if(x < min)
        return max - mod(min - x, max - min + 1);
    return x;
}

I don't know if it's good, but I'd thought I'd share since I got directed here when doing a Google search on this problem and found the above solutions lacking to my needs. =)

Answer 5

Please do not overlook this post. :)

Is this any good?

int Wrap(N,L,H){
  H=H-L+1; return (N-L+(N<L)*H)%H+L;
}

This works for negative inputs, and all arguments can be negative so long as L is less than H.

Background... (Note that H here is the reused variable, set to original H-L+1).

I had been using (N-L)%H+L when incrementing, but unlike in Lua, which I used before starting to learn C a few months back, this would NOT work if I used inputs below the lower bound, never mind negative inputs. (Lua is built in C, but I don't know what it's doing, and it likely wouldn't be fast...)

I decided to add +(N<L)*H to make (N-L+(N<L)*H)%H+L, as C seems to be defined such that true=1 and false=0. It works well enough for me, and seems to answer the original question neatly. If anyone knows how to do it without the MOD operator % to make it dazzlingly fast, please do it. I don't need speed right now, but some time I will, no doubt.

EDIT:

That function fails if N is lower than L by more than H-L+1 but this doesn't:

int Wrap(N,L,H){
  H-=L; return (N-L+(N<L)*((L-N)/H+1)*++H)%H+L;
}

I think it would break at the negative extreme of the integer range in any system, but should work for most practical situations. It adds an extra multiplication and a division, but is still fairly compact.

(This edit is just for completion, because I came up with a much better way, in a newer post in this thread.)

Crow.

Answer 6

The following should work independently of the implementation of the mod operator:

int range = kUpperBound - kLowerBound + 1;
kx = ((kx-kLowerBound) % range);
if (kx<0)
  return kUpperBound + 1 + kx;
else
  return kLowerBound + kx;

An advantage over other solutions is, that it uses only a single % (i.e. division), which makes it pretty efficient.

Note (Off Topic):

It's a good example, why sometimes it is wise to define intervals with the upper bound being being the first element not in the range (such as for STL iterators...). In this case, both "+1" would vanish.