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);
}
