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

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

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

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

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".

Collectives™ on Stack Overflow

Using the mod operator to rotate an array in-place

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related