Rotate a array of char

[FIFO]

Hi,

Can you suggest me a (time) efficient way to "rotate" a array of char?

In particular:

- The array of char have a fixed (26) length
- The array of char will not be modified in the code
- The rotation is by only one char to the right side

Example:

array: abcdefghijklmno pqrstuvwxyz
array after the rotation: zabcdefghijklmn opqrstuvwxy

Thaks for all ideas ;)

[Eric Sosman]

Re: Rotate a array of char

FIFO wrote:[color=blue]
> Hi,
>
> Can you suggest me a (time) efficient way to "rotate" a array of char?
>
> In particular:
>
> - The array of char have a fixed (26) length
> - The array of char will not be modified in the code
> - The rotation is by only one char to the right side
>
> Example:
>
> array: abcdefghijklmno pqrstuvwxyz
> array after the rotation: zabcdefghijklmn opqrstuvwxy[/color]

Doesn't this violate your second requirement?

If the second requirement can be ignored, one way
to proceed is

char array[] = ...;
char temp;
temp = array[sizeof array - 1];
memmove(array + 1, array, sizeof array - 1);
array[0] = temp;

Depending on what you're actually trying to do, it
might not actually be necessary to rotate the array at
all. What problem are you trying to solve?

--
Eric.Sosman@sun .com

[FIFO]

Re: Rotate a array of char

On Wed, 18 Aug 2004 12:55:23 -0400, Eric Sosman <Eric.Sosman@su n.com>
wrote:
[color=blue]
> Doesn't this violate your second requirement?[/color]

Sorry for my error. I would to explain that the array is only modified
by the "rotation" operation .

[cut]

Thanks for your solution.
[color=blue]
>Depending on what you're actually trying to do, it
>might not actually be necessary to rotate the array at
>all. What problem are you trying to solve?[/color]

I'm trying to write a simluator of a cypher rotor machine where an
alphabet is printed on a circular disc that rotates respect a fixed
disc with engraved the english alphabet.

[Eric Sosman]

Re: Rotate a array of char

FIFO wrote:[color=blue]
> On Wed, 18 Aug 2004 12:55:23 -0400, Eric Sosman <Eric.Sosman@su n.com>
> wrote:
>
>[color=green]
>> Doesn't this violate your second requirement?[/color]
>
>
> Sorry for my error. I would to explain that the array is only modified
> by the "rotation" operation .
>
> [cut]
>
> Thanks for your solution.
>
>[color=green]
>>Depending on what you're actually trying to do, it
>>might not actually be necessary to rotate the array at
>>all. What problem are you trying to solve?[/color]
>
>
> I'm trying to write a simluator of a cypher rotor machine where an
> alphabet is printed on a circular disc that rotates respect a fixed
> disc with engraved the english alphabet.[/color]

Then you might do better to "rotate" by manipulating
the array indices rather than the array contents. The
straightforward approach uses modular arithmetic to
convert a "virtual" index to an "actual" index:

char array[] = ...;
int rot = ...; /* rotation amount: 0, 1, 2, ... */
int idx = ...; /* index: 0 .. arraylen-1 */
char result = array[ (idx + rot) % arraylen ];
++rot;

However, it may be easier (and perhaps faster, although
timing details will vary from one implementation to another)
to concatenate two copies of the array:

char array[] = ... ...; /* two copies */
int off = ...; /* rotation offset: 0 .. arraylen-1 */
char result = array[off];
if (++off == arraylen)
off = 0;

--
Eric.Sosman@sun .com

[Eric Sosman]

Re: Rotate a array of char

Eric Sosman wrote:[color=blue]
>
> However, it may be easier (and perhaps faster, although
> timing details will vary from one implementation to another)
> to concatenate two copies of the array:
>
> char array[] = ... ...; /* two copies */
> int off = ...; /* rotation offset: 0 .. arraylen-1 */
> char result = array[off];
> if (++off == arraylen)
> off = 0;[/color]

Woops: Forgot the other index. That should have been

char array[] = ... ...; /* two copies */
int off = ...; /* rotation offset: 0 .. arraylen-1 */
int idx = ...; /* index: 0 .. arraylen-1 */
char result = array[idx + off];
if (++off == arraylen)
off = 0;


--
Eric.Sosman@sun .com

[Malcolm]

Re: Rotate a array of char


"FIFO" <FIFO@LIFO.or g> wrote[color=blue]
>
> Can you suggest me a (time) efficient way to "rotate" a array of char?
>
> In particular:
>
> - The array of char have a fixed (26) length
> - The array of char will not be modified in the code
> - The rotation is by only one char to the right side
>
> Example:
>
> array: abcdefghijklmno pqrstuvwxyz
> array after the rotation: zabcdefghijklmn opqrstuvwxy
>[/color]
Declare an array a-za-z.

Now store an offset into that array (intitally zero), and replace the second
'a' with a NUL.
To rotate, increment your pointer, replace the second 'a', and write a NUL
to the second 'b'.
Always check for hitting the second 'a', at which point you wrap.

(Actually this will rotate in the wrong direction, but you get the idea.
Store a travelling pointer, and manipulate the NUL, and have 52 letters
insrtead of 26, so you don't have to move 26 characters for each rotation.)

[kal]

Re: Rotate a array of char

"Malcolm" <malcolm@55bank .freeserve.co.u k> wrote in message news:<cg08h2$6a c$1@news6.svr.p ol.co.uk>...
[color=blue]
> and have 52 letters instead of 26, so you don't have to
> move 26 characters for each rotation.[/color]

Wouldn't 51 do? Such as a-za-y or b-za-z ?

[pete]

Re: Rotate a array of char

FIFO wrote:[color=blue]
>
> Hi,
>
> Can you suggest me a (time) efficient way to "rotate" a array of char?
>
> In particular:
>
> - The array of char have a fixed (26) length
> - The array of char will not be modified in the code
> - The rotation is by only one char to the right side
>
> Example:
>
> array: abcdefghijklmno pqrstuvwxyz
> array after the rotation: zabcdefghijklmn opqrstuvwxy[/color]


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

#define STRING "abcdefghijklmn opqrstuvwxyz"

void rotate(char *string)
{
char temp;
size_t length;

length = strlen(string) - 1;
temp = string[length];
memmove(string + 1, string, length);
*string = temp;
}

int main(void)
{
char array[sizeof STRING] = STRING;

puts(array);
rotate(array);
puts(array);
return 0;
}

[Malcolm]

Re: Rotate a array of char


"kal" <k_amir7@yahoo. com> wrote[color=blue]
>[color=green]
> > and have 52 letters instead of 26, so you don't have to
> > move 26 characters for each rotation.[/color]
>
> Wouldn't 51 do? Such as a-za-y or b-za-z ?
>[/color]
Yes, but it complicates the algorithm, because you need to handle
replacement of the NUL at the end of the y separately.
(Actually even that is not quite true, but you would end up with a
non-terminated character array, which will be more trouble that it is worth
for debugging.)