C - circular shift array

Author

circular shift array

Bint

2007-07-31, 3:57 am

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

2007-07-31, 3:57 am

On Mon, 30 Jul 2007 22:04:42 -0500, "Bint" <bint@csgs.com> wrote:

>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

2007-07-31, 3:57 am

On Jul 30, 7:36 pm, Barry Schwarz <schwa...@doezl.net> wrote:
> On Mon, 30 Jul 2007 22:04:42 -0500, "Bint" <b...@csgs.com> wrote:
>
>
>
> 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

2007-07-31, 3:57 am

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 <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

Richard Heathfield

2007-07-31, 3:57 am

Richard Heathfield said:

<snip>

> (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>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

Chris Torek

2007-07-31, 7:57 am

In article <N_adnSlUjZ1NczPb4p2dnAA@bt.com>,
Richard Heathfield <rjh@see.sig.invalid> wrote:
>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.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

Richard

2007-07-31, 7:57 am

dan <dagoldman@yahoo.com> writes:

> On Jul 30, 7:36 pm, Barry Schwarz <schwa...@doezl.net> wrote:
>
> 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

2007-07-31, 7:57 am

Chris Torek said:

> In article <N_adnSlUjZ1NczPb4p2dnAA@bt.com>,
> Richard Heathfield <rjh@see.sig.invalid> wrote:
>
> 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>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

Sponsored Links