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: abcdefghijklmnopqrstuvwxyz
array after the rotation: zabcdefghijklmnopqrstuvwxy

Thaks for all ideas

 

[Eric Sosman]

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: abcdefghijklmnopqrstuvwxyz
array after the rotation: zabcdefghijklmnopqrstuvwxy

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?

 

[FIFO]

Doesn't this violate your second requirement?

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

[cut]

Thanks for your solution.

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?

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]

Doesn't this violate your second requirement?

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

[cut]

Thanks for your solution.

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?

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.

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]

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;

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;

 

[Malcolm]

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: abcdefghijklmnopqrstuvwxyz
array after the rotation: zabcdefghijklmnopqrstuvwxy

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]

and have 52 letters instead of 26, so you don't have to
move 26 characters for each rotation.

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

 

[pete]

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: abcdefghijklmnopqrstuvwxyz
array after the rotation: zabcdefghijklmnopqrstuvwxy

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

#define STRING "abcdefghijklmnopqrstuvwxyz"

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]

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

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.)