Shifting A Circular Array

Question

I have a homework assignment that requires having to shift a circular array -n places in memory.

I have accomplished the task with the following C++ Syntax:

while ( r < 0 )  // rotate negatively.
{
    if ( i == top+1 )
    {
        current->n = items[top+1].n;  
        items[top+1].n = items[back-1].n;
    }
    midPtr->n  = items[++i].n;
    items[i].n = current->n;

    if ( i == back-1 )
    {
            items[back-1].n = current->n;
            i = 0;
            r++; continue;
    }
    else
    {
            current->n = items[++i].n;
            items[i].n = midPtr->n;
            if ( i == back-1 )
            {
                    i = 0;
                    r++; continue;
            }
    }
}

I was wondering if anyone has a better, more efficient method of shifting a circular array by -n units.

Because I seem to be performing unnecessary transfers between ptr variables.

Answer 1

Without giving you code (this is after all a homework assignment) consider this ... a circular array is just an allocation of n units in memory and a pointer to the "start" of the array. The first item in the array need not be the lowest address in the allocated memory, but just a pointer/index to the item in the array that represents the logical first element. Shifting the array is simply shifting the index of the first element. It can be done without loops, simply calculate how far the index needs to move - taking into account the circular nature of the data structure.

Answer 2

Finnicky, but, I guess, OK (there are just too many places that MIGHT have off-by-1 errors to make sure about them all -- just make sure you have a ton of unit tests;-). Personally, whenever faced with such problems (in a real-work context -- alas, the time of homework is far in the past for me;-) I tend to focus on something I learned from Gries a long time ago...: any "swap two blocks" task inside an array can be performed quite effectively (linear time, 0 extra memory) with a single primitive -- "invert a block". Visualizing the array as a normal compact piece of memory, say you have...:

start
  .
  .
beg1
  .
  .
end1
  .
  .
beg2
  .
  .
end2
  .
  .
finis

and your task is to swap the block (beg1..end1) with the block (beg2..end2). The Gries solution is (in each case a block's given (begin..end) with extremes included):

1. invert (beg1..end2)
2. invert (end2..beg2)
3. invert (end2+1..end1-1)
4. invert (end1..beg1)

...that's all!-) Since invert(X..Y) takes (Y-X+1) elementary moves, the Gries solution takes 2*(end2-beg1+1) such moves -- the relative overhead compared to a "minimal possible elementary moves" solution can be high in some special cases (beg2 much larger than end1 AND the two blocks exactly of the same length, for example), but the generality and lack of finnicky worries about off-by-one issues makes it worth to me more often than not.

"Rotation" is a special case of "swap two blocks", of course. So my instinct would be to ensure I have the "invert" primitive (much easier to program anyway;-) and then use that.

But then, I DO have to worry only about my code being clear, correct, and fast, NOT on how a TA will evaluate it, admittedly;-).