circular shift array

[Bint]

Hi,

What is a simple way to shift the elements in an array, circularly? Is
there a way to do it so that you don't need a separate storage array?

IE I want to shift array A{1,2,3,4,5,6,7,8} by 3 to the right. The result
would be B{6,7,8,1,2,3,4,5)

Thanks!
B

 

[Barry Schwarz]

Hi,

What is a simple way to shift the elements in an array, circularly? Is
there a way to do it so that you don't need a separate storage array?

IE I want to shift array A{1,2,3,4,5,6,7,8} by 3 to the right. The result
would be B{6,7,8,1,2,3,4,5)

You don't need a separate array; one temporary object to hold the
rightmost value is sufficient.

Save rightmost value
Loop through array from right to left starting at next to
rightmost value
Save value in next element to the right
Store saved value in first element
Repeat as often as necessary.

You could make a function out of it (or even a macro)

void rshift_int(int array[], size_t num_elements, int
iterations){...}


Remove del for email

 

[dan]

Hi,

What is a simple way to shift the elements in an array, circularly? Is
there a way to do it so that you don't need a separate storage array?

IE I want to shift array A{1,2,3,4,5,6,7,8} by 3 to the right. The result
would be B{6,7,8,1,2,3,4,5)

You don't need a separate array; one temporary object to hold the
rightmost value is sufficient.

Save rightmost value
Loop through array from right to left starting at next to
rightmost value
Save value in next element to the right
Store saved value in first element
Repeat as often as necessary.

You could make a function out of it (or even a macro)

void rshift_int(int array[], size_t num_elements, int
iterations){...}

Remove del for email

Barry is correct. I did this kind of thing.

One suggestion. If you have a bunch of arrays, instead of a temporary
object, you may want to make each array one longer than needed, and
use the extra element as the temporary object. It may make your code
easier to read and maintain.

Daniel Goldman

 

[Richard Heathfield]

Bint said:

Hi,

What is a simple way to shift the elements in an array, circularly?
Is
there a way to do it so that you don't need a separate storage array?

IE I want to shift array A{1,2,3,4,5,6,7,8} by 3 to the right. The
result would be B{6,7,8,1,2,3,4,5)

If you must shift them at all (see below):

(a) you /can/ get away with temporary storage for a single value, but
this means you have to move every item individually, instead of taking
advantage of memcpy - so get some temporary storage if you can;
(b) minimise the shift. If the array has 8 members and you want to shift
5 to the left, you can reduce this to 8 - 5 = 3 by shifting in the
opposite direction, so you never need temporary storage for more than
half the items in the array;
(c) if you have temporary storage capable of storing a number of
elements at least equal to the amount W of your shift, use it to store
*all* of the W leftmost items (if you're shifting left) or the W
rightmost items (if you're shifting right). That way, you can do the
whole thing in two memcpy's and a memmove.

An easier way, which doesn't involve any shifting at all, is to maintain
an object whose purpose is to store the index of the first item. Then
you just process the array as follows:

idx = head;
for(i = 0; i < n; i++)
{
if(idx++ == n) /* idx = (head + i) % n is shorter, but costlier */
{
idx = 0;
}
proc(arr[idx]);
}

and there is no need to shift anything at all!

Also investigate circular linked lists.

 

[Richard Heathfield]

Richard Heathfield said:

(a) you /can/ get away with temporary storage for a single value, but
this means you have to move every item individually, instead of taking
advantage of memcpy

Er, I meant memmove

<snip>

 

[Chris Torek]

An easier way [to deal with circular queues], which doesn't involve
any shifting at all, is to maintain an object whose purpose is to
store the index of the first item. Then you just process the array
as follows:

idx = head;
for(i = 0; i < n; i++)
{
if(idx++ == n) /* idx = (head + i) % n is shorter, but costlier */

I believe you mean "if (++idx == n)" here. (The post-increment
version can be made to work by changing other values, but it is
then not equivalent to the "idx = (head + i) % n" method.)

Or, one could say:

idx = (head + i) % n; /* if (idx++ == n) is faster, but less correct */

which suggests perhaps you are doing premature optimization.

{
idx = 0;
}
proc(arr[idx]);
}

Also, usually one wants to process first, then test ++idx against n.
(Again, "increment before processing" can be made to work, but is
more complicated.)

 

[Richard]

Hi,

What is a simple way to shift the elements in an array, circularly? Is
there a way to do it so that you don't need a separate storage array?

IE I want to shift array A{1,2,3,4,5,6,7,8} by 3 to the right. The result
would be B{6,7,8,1,2,3,4,5)

You don't need a separate array; one temporary object to hold the
rightmost value is sufficient.

Save rightmost value
Loop through array from right to left starting at next to
rightmost value
Save value in next element to the right
Store saved value in first element
Repeat as often as necessary.

You could make a function out of it (or even a macro)

void rshift_int(int array[], size_t num_elements, int
iterations){...}

Remove del for email

Barry is correct. I did this kind of thing.

One suggestion. If you have a bunch of arrays, instead of a temporary
object, you may want to make each array one longer than needed, and
use the extra element as the temporary object. It may make your code
easier to read and maintain.

Daniel Goldman

or just have the array double its normal size with duplicate copies and
merely shuffle a pointer to the first element .... no Memory move at all
then.

 

[Richard Heathfield]

Chris Torek said:

An easier way [to deal with circular queues], which doesn't involve
any shifting at all, is to maintain an object whose purpose is to
store the index of the first item. Then you just process the array
as follows:

idx = head;
for(i = 0; i < n; i++)
{
if(idx++ == n) /* idx = (head + i) % n is shorter, but costlier */

I believe you mean "if (++idx == n)" here.

Er, kind of. What I really meant was:

proc(arr[idx]);
if(++idx == n)
{
idx = 0;
}

(The post-increment
version can be made to work by changing other values, but it is
then not equivalent to the "idx = (head + i) % n" method.)

Or, one could say:

idx = (head + i) % n; /* if (idx++ == n) is faster, but less
correct */

which suggests perhaps you are doing premature optimization.

Well, it does avoid a division. Had I got it right, I think it would
have been a reasonable thing to do.

<snip>