Here's a nice tweak for those who liked the question... what if the alphabet comprising the swapped words is smaller than 16 chars (16 including "space")? there are many examples for such alphabets: the numeric chars [01234567890.-+] , the genome letters [GATC] , the hawaiian alphabet [aeiouhklmnpv?], morse code [-.] , musical notes [ABCDEFG#m], etc. This allows encoding the chars as nibbles (4bits) and storing two encoded chars inside one 8bit char.
It's still not trivial doing the words swap in a single loop with one cursor moves left-to-right and the other right-to-left. There are actually 4 types of word-copying: copy a word from the left string's side to the right, from the right string's side to the left and the two equivalent copies that involves read/write overlapping: position X->X+y and X->X-y, where y is smaller than X's length.
The nice optimization is that during the first half of the loop words from the right side are encoded into the left (preserving the original left values), but then on the second half words from the left can be copied directly to right and then the left chars are rewritten with their final values...
Here's the C code, which takes any alphabet as parameter:
#define WORDS_DELIMITER ' '
#define UNMAPPED 0xFF
#define BITS_IN_NIBBLE 4
#define BITS_IN_BYTE 8
#define CHARS_IN_NIBBLE (1 << BITS_IN_NIBBLE)
#define CHARS_IN_BYTE (1 << BITS_IN_BYTE)
typedef union flip_char_ {
unsigned char clear;
struct {
unsigned char org:4;
unsigned char new:4;
} encoded;
} flip_char_t;
typedef struct codec_ {
unsigned char nibble2ascii[CHARS_IN_NIBBLE];
unsigned char ascii2nibble[CHARS_IN_BYTE];
} codec_t;
static int
codec_init (const unsigned char *alphabet, codec_t *codec)
{
size_t len = strlen(alphabet), i;
if (len > CHARS_IN_NIBBLE) {
fprintf(stderr, "alphabet is too long!\n");
return -1;
}
if (strchr(alphabet, WORDS_DELIMITER) == NULL) {
fprintf(stderr, "missing space in the alphabet\n");
return -1;
}
strcpy(codec->nibble2ascii, alphabet);
memset(codec->ascii2nibble , UNMAPPED, CHARS_IN_BYTE);
for (i=0; i<len; i++) {
codec->ascii2nibble[ alphabet[i] ] = i;
}
return 0;
}
static inline int
is_legal_char (const codec_t *codec, const unsigned char ch)
{
return codec->ascii2nibble[ch] != UNMAPPED;
}
static inline unsigned char
encode_char (const codec_t *codec, unsigned char org, unsigned char new)
{
flip_char_t flip;
flip.encoded.org = codec->ascii2nibble[org];
flip.encoded.new = codec->ascii2nibble[new];
return flip.clear;
}
static inline unsigned char
decode_org (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.org];
}
static inline unsigned char
decode_new (const codec_t *codec, unsigned char ch)
{
flip_char_t flip = { .clear = ch };
return codec->nibble2ascii[flip.encoded.new];
}
// static void inline
// encode_char (const char *alphabet, const char *
static int
flip_words (const unsigned char *alphabet, unsigned char *a, size_t len)
{
codec_t codec; /* mappings of the 16char-alphabet to a nibble */
int r=len-1; /* right/reader cursor: moves from right to left scanning for words */
int l=0; /* left/writer cursor: moves from left to right */
int i=0; /* word iterator */
int start_word=-1,end_word=-1; /* word boundaries */
unsigned char org_r=0; /* original value pointed by the right cursor */
int encode=0, rewrite=0; /* writing states */
if (codec_init(alphabet, &codec) < 0) return -1;
/* parse the buffer from its end backward */
while (r>=0) {
if (r>=l && !is_legal_char(&codec, a[r])) {
fprintf(stderr, "illegal char %c in string\n", a[r]);
return -1;
}
/* read the next charachter looking for word boundaries */
org_r = (r<l) ? decode_org(&codec, a[r]) : a[r];
/* handle word boundaries */
if (org_r == WORDS_DELIMITER) {
/* mark start of word: next char after space after non-space */
if (end_word>0 && start_word<0) start_word = r/*skip this space*/+1;
/* rewrite this space if necessary (2nd half) */
if (r<l) a[r] = decode_new(&codec,a[r]);
} else {
/* mark end of word: 1st non-space char after spaces */
if (end_word<0) end_word = r;
/* left boundary is a word boundary as well */
if (!r) start_word = r;
}
/* Do we have a complete word to process? */
if (start_word<0 || end_word<0) {
r--;
continue;
}
/* copy the word into its new location */
for(i=start_word; i<=end_word; i++, l++) {
if (i>=l && !is_legal_char(&codec, a[l])) {
fprintf(stderr, "illegal char %c in string\n", a[l]);
return -1;
}
/* reading phase: value could be encoded or not according to writer's position */
org_r= (i<l) ? decode_org(&codec, a[i]) : a[i];
/* overlapping words in shift right: encode and rewrite */
encode=rewrite=(l>=start_word && l<=end_word && i<l);
/* 1st half - encode both org and new vals */
encode|=(start_word-1>l);
/* 2nd half - decode and rewrite final values */
rewrite|=(i<l);
/* writing phase */
a[l]= encode ? encode_char(&codec, a[l], org_r) : org_r;
if (rewrite) {
a[i]=decode_new(&codec, a[i]);
}
}
/* done with this word! */
start_word=end_word=-1;
/* write a space delimiter, unless we're at the end */
if (r) {
a[l] = l<r ? encode_char(&codec, a[l], WORDS_DELIMITER) : WORDS_DELIMITER;
l++;
}
r--;
}
a[l]=0;
return 0; /* All Done! */
}