Using the mod operator to rotate an array in-place

Question

Without using any stls, boosts, and the like I have been trying to rotate the elements in my array. I've been trying to use the mod operator, to be efficient:

void stack::rotate(int r)
{
 r = ( r % maxSize + maxSize ) % maxSize;
 for ( int first_index = 0; first_index < r; ++first_index )
 {
  int mem = items[first_index].n;
  int index = ( first_index + r ) % maxSize, index_prev = first_index;
  while ( index != first_index )
  {
   items[index_prev] = items[index];
   index_prev = index;
   index = ( index + r ) % maxSize;
  }
  items[index_prev].n = mem;
 }

Where items is an allocated array to an item struct. Although it is a little weird the item struct has an integer 'n' member so that i may use it with integer type varaibles.

But its still not comming out right =( . Im losing the contents of my second element. I think its break time ;)

Why you'd want to do this rather than just using std::rotate makes no sense to me. — Jesper Juhl
– Jesper Juhl, Commented Sep 1, 2023 at 12:03

Jeremy Friesner · Accepted Answer · 2009-10-26 02:27:29Z

4

In-place array rotation is trickier than it looks. You might be interested in this article:

http://www.azillionmonkeys.com/qed/case8.html

answered Oct 26, 2009 at 2:27

Jeremy Friesner

73.9k17 gold badges147 silver badges258 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Daniel Daranas · Accepted Answer · 2009-10-26 08:43:08Z

2

Tips:

Add assertions (r is positive, nonzero?, less than maxsize, maxsize is nonzero, etc.)

Write tests for this function, starting from an easy array and going up. Do not throw them away - keep them written and run all of them in a row.

Give clear names to variables.

Do not reuse r.

Your code looks a bit too obscure for me. At first sight it is crying "Off by one errors here! Come see!". Assert each and every possible boundary error.

For any more detailed answers, you should expand a bit on "its still not comming out right".

answered Oct 26, 2009 at 8:43

Daniel Daranas

22.7k10 gold badges66 silver badges122 bronze badges

Collectives™ on Stack Overflow

Using the mod operator to rotate an array in-place

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related