Re: circular shift array

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
.

Relevant Pages

  • Re: Packages and returning errors
    ... > array intact. ... sub is_a_instance_method { ... my $class = shift; ... You need to fix the scope of $error by moving its declaration outside ...
    (comp.lang.perl.misc)
  • Re: Packages and returning errors
    ... The perldoc function guide says about shift (which is ... "Shifts the first value of the array off and returns it, ... If an array of values are passed to a sub, ... Back to my package (which I am currently thinking might be out of my depth, ...
    (comp.lang.perl.misc)
  • Re: MS SQL geek wants to jump ship, plz help on first Perl script
    ... Next step is the MEAT inside the loop. ... Then you don't understand shift(). ... automatically works on the @_ array (ie, ... # a lot of memory, coz it reads the whole arrary into memory first, ...
    (comp.lang.perl.misc)
  • Re: bit shifts by multiple bytes
    ... The last byte was added to the end, and then it was a matter of moving right to left across the array, using two bytes in a UInt16 at a time to shift. ... You have a function composed of two parts: how many whole bytes will you shift followed by how many remainder bits will you shift. ... I'd start by breaking your starting number into bytes and store each byte in the low order bits of an array of 16 bit words. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Shift em bits
    ... The language won't allow it. ... Shift operators only apply to integer ... you might find that you have defined an "8 uchar array" as your ... If you really are trying to write portable code (avoiding ASM for ...
    (comp.arch.embedded)