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

[sam_cit]

On Jul 31, 8:10 am, "Bint" <[e-mail]:

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

In addition, sometimes shifting might not be required, like shifting 8
times on your array gives the same result, so have some kind of logic
like the following,

int no_of_shifts;
no_of_shifts = shift%n;
if(no_of_shifts == 0) return; /* No need to shift */
else if (n <= no_of_shifts/2) right_shift(no_of_shifts);
else left_shift(no_of_shifts);

[Duncan Muirhead]

On Mon, 30 Jul 2007 22:10:30 -0500, Bint 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)

Thanks!
B

Well, as others have said, the best way is to avoid the need for shifting.
If you can't, the code below works, I believe. The basic idea is that to
shift n by s you do gcd(n,s) loops which shift a loop round, eg to shift
6 by 4 the loops are 0->4->2->0 and 1->5->3->1.
The code below uses two objects worth of storage for a shift count other
than 1. Could it be done with one objects worth?
If you are going to make heavy use of such a routine for a fixed type
you might want to make a specialised version, where you use assignment
rather than memcpy.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* !! b <= a */
static int gcd( int a, int b)
{
int c;
while ( (c = a % b) != 0)
{ a = b; b = c;
}
return b;
}

static void cshift_r( int nelt, size_t size, void* base, int ns, char* buff)
{
char* b = base;
if ( ns == 1)
{ memcpy( buff, b+(nelt-1)*size, size);
memmove( b+size, b, (nelt-1)*size);
memcpy( b, buff, size);
}
else
{
char* bs[2];
int nloops = gcd( nelt, ns);
int i, iw, p;
bs[0] = buff; bs[1]=buff+size;
for( i=0; i<nloops; ++i)
{ memcpy( bs[0], b+i*size, size);
for( p=0, iw=(i+ns)%nelt; iw != i; iw=(iw+ns)%nelt, p^=1)
{ memcpy( bs[p^1], b+iw*size, size);
memcpy( b+iw*size, bs[p], size);
}
memcpy( b+i*size, bs[p], size);
}
}
}
/* circularly shift the nelt block (of objects of size size)
** staring at base by ns (positive means rightwards)
*/
void cshift( int nelt, size_t size, void* base, int ns)
{
int s;
char* buff;
if ( nelt<0 || size==0 || ns == 0)
{ return;
}
if ( ns 0)
{ s = ns % nelt;
if ( s == 0)
{ return;
}
}
else if ( ns < 0)
{ s = (-ns) % nelt;
if ( s == 0)
{ return;
}
s = nelt-s;
}
if ( (buff = malloc( (s==1 ? 1 : 2)*size)) == NULL)
{ exit( EXIT_FAILURE);
}
cshift_r( nelt, size, base, s, buff);
free( buff);
}