To reverse a string

[Richard Tobin]

You don't even need one - you can use the nul at the end of the
string...

Yes, if saving a single temporary object is worth writing abominably
ugly code.[/QUOTE]

I repeatedly see people people denouncing the use of smilies on the
grounds that intelligent readers don't need them, but I'm beginning
to doubt it.

-- Richard

 

[Ben Pfaff]

Yes, if saving a single temporary object is worth writing abominably
ugly code.

I repeatedly see people people denouncing the use of smilies on the
grounds that intelligent readers don't need them, but I'm beginning
to doubt it.[/QUOTE]

You think the articles from folks who think XOR is a good way to
swap two variables are all jokes then?

 

[Herbert Rosenau]

Sure. It may not be very fast for such a size, but assuming you
can create the string in the first place it should reverse it.
Don't forget to #include <string.h>. This avoids extra calls on
strlen by returning its value.

/* ======================= */
/* reverse string in place */
size_t revstring(char *stg)
{
char *last, temp;
size_t lgh;

lgh = strlen(stg);
if (lgh > 1) {
last = stg + lgh; /* points to '\0' */
while (last-- > stg) {
temp = *stg; *stg++ = *last; *last = temp;
}
}
return lgh;
} /* revstring */

Too complicated because superflous statements.

strictly conforming, best optimised:

/* reverse a string of 0 or more bytes in length in place */
/* caller is responsible for NOT calling with a null pointer */
/* or NOT calling with a string constant */
/* return: size of the string to reverse */

size_t revstring(void *p) {
char *l = p;
/* size is needed only to get it returned!
r should be calculated: = l + strlen(l) -1; */
size_t size = strlen(p);
char *r = l + size - 1;
char c;

while (l < r) { /* when l >= r we're done */
c = *l;
*l++ = *r;
*r-- = c;
}
return size;
}

Remarks:
size < 2: nothing is done, except setup the variables.
size is uneven: the middlest char lefts untouched as it has no
counterpart

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2 Deutsch ist da!

 

[CBFalconer]

Too complicated because superflous statements.

strictly conforming, best optimised:

/* reverse a string of 0 or more bytes in length in place */
/* caller is responsible for NOT calling with a null pointer */
/* or NOT calling with a string constant */
/* return: size of the string to reverse */

size_t revstring(void *p) {

The type of a string is char *, not void *.

char *l = p;
/* size is needed only to get it returned!
r should be calculated: = l + strlen(l) -1; */
size_t size = strlen(p);
char *r = l + size - 1;

Undefined behaviour when the string is empty.

char c;

while (l < r) { /* when l >= r we're done */
c = *l;
*l++ = *r;
*r-- = c;
}
return size;
}

Remarks:
size < 2: nothing is done, except setup the variables.
size is uneven: the middlest char lefts untouched as it has no
counterpart

Both of which characteristics are present in my code, without the
undefined behaviour. In fact for size < 2 nothing whatsoever is
done in my code.

 

[Julian V. Noble]

The type of a string is char *, not void *.


Undefined behaviour when the string is empty.


Both of which characteristics are present in my code, without the
undefined behaviour. In fact for size < 2 nothing whatsoever is
done in my code.

IIRC, Bentley's Programming Pearls has several algorithms
including a clever one. I think he even gives the code in
the back of the book.

--
Julian V. Noble
Professor Emeritus of Physics

http://galileo.phys.virginia.edu/~jvn/

"For there was never yet philosopher that could endure the
toothache patiently."

-- Wm. Shakespeare, Much Ado about Nothing. Act v. Sc. 1.

 

[pete]

sudharsan opined:


Why do you think it would be different to
the one for strings less than 1MB?

Because a conforming implementation of C,
is not required to be able to translate and execute
a program which excedes the minimum translation limits.

strlen isn't required to work right on a string that long.

The business in the standard about the ptrdiff_t type
not being guaranteed to be able to do its job,
is most appropriately applied to code with objects
which exceede the translation limits.
I've seen strlen implemented on this newsgroup
in ways which depend upon the ptrdiff_t type
being able to do its job.

 

[Vladimir S. Oka]

Because a conforming implementation of C,
is not required to be able to translate and execute
a program which excedes the minimum translation limits.

strlen isn't required to work right on a string that long.

The business in the standard about the ptrdiff_t type
not being guaranteed to be able to do its job,
is most appropriately applied to code with objects
which exceede the translation limits.
I've seen strlen implemented on this newsgroup
in ways which depend upon the ptrdiff_t type
being able to do its job.

All you say is fine, but I don't see how it applies to your quote of
what I said.

Unless you took to the word "code" in the OP to meant "exact
implementation detail", while I read it as "the [general] method". In
that case we actually agree, but are talking about diferent parts of
the problem.

The fact that you may have to implement your own `strlen()`, or
whatever, to me, does not change the way this is done.

 

[pete]

Vladimir S. Oka wrote:

The fact that you may have to implement your own `strlen()`, or
whatever, to me, does not change the way this is done.

To me, whether or not you have to implement your own strlen,
does change the way this is done.

char *str_rev(char *s)
{
char *t, swap;
char *const p = s;

if (*s != '\0') {
t = s + strlen(s + 1);
while (t > s) {
swap = *t;
*t-- = *s;
*s++ = swap;
}
}
return p;
}

 

[pete]

for size < 2 nothing whatsoever is
done in my code.

Not so.
You have a function call to strlen even when (size < 2).

char *str_rev(char *s)
{
char *t, swap;
char *const p = s;

if (s[0] != '\0' && s[1] != '\0') {
t = s + 1 + strlen(s + 2);
do {
swap = *t;
*t-- = *s;
*s++ = swap;
} while (t > s);
}
return p;
}

 

[CBFalconer]

To me, whether or not you have to implement your own strlen,
does change the way this is done.

char *str_rev(char *s)
{
char *t, swap;
char *const p = s;

if (*s != '\0') {
t = s + strlen(s + 1);
while (t > s) {
swap = *t;
*t-- = *s;
*s++ = swap;
}
}
return p;
}

Er - that doesn't work. Check the boundary conditions. See my
revstring function elsethread. It is also a design mistake to
return the string pointer, because of such innocent looking code
as:

printf("%s\n%s\n", str, str_rev(str));

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

 

[CBFalconer]

for size < 2 nothing whatsoever is
done in my code.

Not so.
You have a function call to strlen even when (size < 2).

char *str_rev(char *s)
{
char *t, swap;
char *const p = s;

if (s[0] != '\0' && s[1] != '\0') {
t = s + 1 + strlen(s + 2);
do {
swap = *t;
*t-- = *s;
*s++ = swap;
} while (t > s);
}
return p;
}

I think a strlen call is somewhat better than all that, and you end
up calling strlen anyhow. If strlen returns 1 or less it won't
take very long to execute. I haven't bothered to check the end
conditions of your code, but based on your other posting I am
suspicious.

Please mark areas where you snip material. ... will do.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

 

[Vladimir S. Oka]

pete opined:

To me, whether or not you have to implement your own strlen,
does change the way this is done.

How so?

char *str_rev(char *s)
{
char *t, swap;
char *const p = s;

if (*s != '\0') {
t = s + strlen(s + 1);

What's wrong with:

t = s + my_strlen(s + 1);

while (t > s) {
swap = *t;
*t-- = *s;
*s++ = swap;
}
}
return p;
}

It seems Chuck thinks the above doesn't work -- I didn't check myself.

 

[pete]

Herbert Rosenau wrote:
sudharsan wrote:

could any one please give me a code to reverse a string of more
than 1MB .???

Sure. It may not be very fast for such a size, but assuming you
can create the string in the first place it should reverse it.
Don't forget to #include <string.h>. This avoids extra calls on
strlen by returning its value.

/* ======================= */
/* reverse string in place */
size_t revstring(char *stg)
{
char *last, temp;
size_t lgh;

lgh = strlen(stg);

for size < 2 nothing whatsoever is
done in my code.

Not so.
You have a function call to strlen even when (size < 2).

char *str_rev(char *s)
{
char *t, swap;
char *const p = s;

if (s[0] != '\0' && s[1] != '\0') {
t = s + 1 + strlen(s + 2);
do {
swap = *t;
*t-- = *s;
*s++ = swap;
} while (t > s);
}
return p;
}

I think a strlen call is somewhat better than all that,

I'm not saying that it isn't.

and you end up calling strlen anyhow.

Only when the length is greater than one.

If strlen returns 1 or less it won't
take very long to execute.
True.

I haven't bothered to check the end
conditions of your code,
but based on your other posting I am
suspicious.

Check them.

Please mark areas where you snip material. ... will do.

I hadn't thought about it at first,
but since your function returned length and mine didn't,
they were not really the same.

size_t str_rev(char *s)
{
char *t, swap;
size_t length;

if (s[0] != '\0') {
if (s[1] != '\0') {
length = strlen(s);
t = s + length - 1;
do {
swap = *t;
*t-- = *s;
*s++ = swap;
} while (t > s);
} else {
length = 1;
}
} else {
length = 0;
}
return length;
}

 

[pete]

Er - that doesn't work. Check the boundary conditions.

I can't find a problem.

/* BEGIN new.c */

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

char *str_rev(char *s)
{
char *t, swap;
char *const p = s;

if (*s != '\0') {
t = s + strlen(s + 1);
while (t > s) {
swap = *t;
*t-- = *s;
*s++ = swap;
}
}
return p;
}

int main(void)
{
char string[] = "abc";

puts(str_rev(string));
str_rev(string);
string[2] = '\0';
puts(str_rev(string));
str_rev(string);
string[1] = '\0';
str_rev(string);
string[0] = '\0';
puts(str_rev(string));
return 0;
}

/* END new.c */

 

[pete]

pete opined:


How so?


What's wrong with:

Why would you write your own strlen to reverse a string,
instead of using the one in the standard library?

 

[Vladimir S. Oka]

Why would you write your own strlen to reverse a string,
instead of using the one in the standard library?

I was replying to what you said earlier:

Because a conforming implementation of C,
is not required to be able to translate and execute
a program which excedes the minimum translation limits.

strlen isn't required to work right on a string that long.

Which you snipped.

To expand: if `strlen()` won't necessarilly work on huge strings (your
assertion above, I didn't check the Standard), then rolling your own
may help.

 

[pete]

To expand: if `strlen()` won't necessarilly work on huge strings (your
assertion above, I didn't check the Standard),
then rolling your own may help.

That's the answer to your original question:

"Why do you think it would be different to the one
for strings less than 1MB?"

This is a c language newsgroup, not an algorithm newsgroup.

 

[pete]

CBFalconer wrote:

I can't find a problem.

int main(void)
{
char string[] = "abc";

puts(str_rev(string));
str_rev(string);
string[2] = '\0';
puts(str_rev(string));
str_rev(string);
string[1] = '\0';
str_rev(string);
string[0] = '\0';
puts(str_rev(string));
return 0;
}

This might be better, unless I don't understand
what you mean by "boundary conditions".

int main(void)
{
char string[sizeof "abc"] = "";
size_t n;

for (n = 0; n != sizeof "abc" - 1; ++n) {
str_rev(string);
puts(string);
str_rev(string);
string[n] = "abc"[n];
}
str_rev(string);
puts(string);
return 0;
}

 

[Vladimir S. Oka]

pete wrote:
Vladimir S. Oka wrote:

sudharsan opined:

could any one please give me a code to reverse a string of more than
1MB .???

Why do you think it would be different to
the one for strings less than 1MB?

Because a conforming implementation of C,
is not required to be able to translate and execute
a program which excedes the minimum translation limits.

strlen isn't required to work right on a string that long.

The business in the standard about the ptrdiff_t type
not being guaranteed to be able to do its job,
is most appropriately applied to code with objects
which exceede the translation limits.
I've seen strlen implemented on this newsgroup
in ways which depend upon the ptrdiff_t type
being able to do its job.

All you say is fine, but I don't see how it applies to your quote of
what I said.

Unless you took to the word "code" in the OP to meant "exact
implementation detail", while I read it as "the [general] method". In
that case we actually agree, but are talking about diferent parts of
the problem.

The fact that you may have to implement your own `strlen()`, or
whatever, to me, does not change the way this is done.

To me, whether or not you have to implement your own strlen,
does change the way this is done.

How so?

char *str_rev(char *s)
{
char *t, swap;
char *const p = s;

if (*s != '\0') {
t = s + strlen(s + 1);

What's wrong with:

t = s + my_strlen(s + 1);

while (t > s) {
swap = *t;
*t-- = *s;
*s++ = swap;
}
}
return p;

}

It seems Chuck thinks the above doesn't work -- I didn't check myself.

Why would you write your own strlen to reverse a string,
instead of using the one in the standard library?

I was replying to what you said earlier:

Because a conforming implementation of C,
is not required to be able to translate and execute
a program which excedes the minimum translation limits.
strlen isn't required to work right on a string that long.

Which you snipped.

To expand: if `strlen()` won't necessarilly work on huge strings (your
assertion above, I didn't check the Standard), then rolling your own
may help.

That's the answer to your original question:

"Why do you think it would be different to the one
for strings less than 1MB?"

This is a c language newsgroup, not an algorithm newsgroup.

I have now, painstaikingly, re-built the whole exchange. Without
snipping *anything* will you, please, point to exact things that I said
that you have an issue with, and exactly why?

 

[pete]

pete wrote:
Vladimir S. Oka wrote:

sudharsan opined:

could any one please give me a code to reverse a string of more than
1MB .???

Why do you think it would be different to
the one for strings less than 1MB?

Because a conforming implementation of C,
is not required to be able to translate and execute
a program which excedes the minimum translation limits.

strlen isn't required to work right on a string that long.

The business in the standard about the ptrdiff_t type
not being guaranteed to be able to do its job,
is most appropriately applied to code with objects
which exceede the translation limits.
I've seen strlen implemented on this newsgroup
in ways which depend upon the ptrdiff_t type
being able to do its job.

All you say is fine,
but I don't see how it applies to your quote of
what I said.

Unless you took to the word "code" in the OP to meant "exact
implementation detail",
while I read it as "the [general] method". In

I took it to mean exact "implementation detail"
and the reason that I did,
is because the exact implementation detail
depends on the length of the string.

The difference in methodology,
depending on the length of the string, is a c language issue.
To me, "the [general] method" sounds like an algorithm issue.
This is a c language newsgroup, not an algorithm newsgroup.

Too bad that you didn't.
You could have opinion of your own about the code, if you had.