squeeze function

S

sara

Hi,

I have implemented the following method to remove all the occurences
of c from string s.

void squeeze(char* s, char c)
{
char string[]="";
strcpy(string,s);

int src=0;
int dst=0;

while(string[src]!='\0')
{
while (string[src]!='c')
{
src++;
if (string[src]!='\0')
dst++;
}

if (string[src]=='\0')
break;

while(string[src]=='c')
src++;
string[dst]=string[src];
}

string[dst+1]=0;

return;

}

How can I change the fucntion to return the string variable? If I make
the function 'char[] squeeze(char* s, char c)' it does not compile and
if I make it 'char* squeeze(char* s, char c)' I got some weird error.
Also, is it possible to write the functon more efficiently?
 
J

jameskuyper

sara said:
Hi,

I have implemented the following method to remove all the occurences
of c from string s.

void squeeze(char* s, char c)

You declare a variable named 'c' here, but never use it.
{
char string[]="";
strcpy(string,s);

int src=0;
int dst=0;

while(string[src]!='\0')
{
while (string[src]!='c')

Here, you have a string literal 'c' where I would have expected to see
a reference to the variable named c.

Note: '\0' != 'c'; are you sure you want this inner loop to keep going
when string[src]=='\0'?
{
src++;
if (string[src]!='\0')
dst++;
}

if (string[src]=='\0')
break;

while(string[src]=='c')
src++;
string[dst]=string[src];
}

string[dst+1]=0;

return;

}

How can I change the fucntion to return the string variable? If I make
the function 'char[] squeeze(char* s, char c)' it does not compile

Correct: C functions cannot return arrays. They can return pointers to
an array, and if you used "char array[]" in the argument list of a
function, it would automatically be converted into "char *array".
However, that does not apply to the return type of a function.

... and
if I make it 'char* squeeze(char* s, char c)' I got some weird error.

We can't help you very much if all you tell us about the error is that
it's weird. Was it a compile-time error message, or a run-time
malfunction? If there was a message, please give us the full text of
that message. If it malfunctioned at run-time, we need more details
about how it malfunctioned.

Was the only change you made to the function the return type? In that
case, the problem is obvious: the "return;" statement is incompatible
with a declared return type of "char*". Did you make any other changes
to the code? If so, the only way we'll be able to help you is if you
post the actual code, as modified.
Also, is it possible to write the functon more efficiently?

Yes. But first concentrate on getting it to work properly - the fact
that the inner loop doesn't stop at the end of the input string is a
very serious error.
 
N

Nick Keighley

besides what other posters said
I have implemented the following method to remove all the occurences
of c from string s.

        while(string[src]!='\0')
        {
                while (string[src]!='c')

this compares one of the charcaters in the string with the character
'c' you meant

while (string [src] != c)

you could a bit more whitespace into your code to make it more
readable...


<snip>
 
C

Chris M. Thomasson

sara said:
Hi,

I have implemented the following method to remove all the occurences
of c from string s.

void squeeze(char* s, char c)
{
char string[]="";
strcpy(string,s);

int src=0;
int dst=0;

while(string[src]!='\0')
{
while (string[src]!='c')
{
src++;
if (string[src]!='\0')
dst++;
}

if (string[src]=='\0')
break;

while(string[src]=='c')
src++;
string[dst]=string[src];
}

string[dst+1]=0;

return;

}

How can I change the fucntion to return the string variable? If I make
the function 'char[] squeeze(char* s, char c)' it does not compile and
if I make it 'char* squeeze(char* s, char c)' I got some weird error.
Also, is it possible to write the functon more efficiently?

Perhaps something like:
___________________________________________________________
#include <string.h>
#include <stdio.h>


char*
squeeze_ex(char* buf,
char cmp,
size_t size,
size_t* pnew_size)
{
if (buf && *buf)
{
char* cur;
size_t count;

for (cur = strchr(buf, cmp),
count = 0;
cur && *cur;
cur = strchr(cur, cmp),
++count)
{
memmove(cur, cur + 1, size - (cur - buf));
}

count = size - count;

if (pnew_size)
{
*pnew_size = size - count;
}
}

return buf;
}


char*
squeeze(char* buf,
char cmp,
size_t* pnew_size)
{
return squeeze_ex(buf, cmp, strlen(buf), pnew_size);
}


int
main(void)
{
char buffer[] = "Hello World";

puts(squeeze(buffer, ' ', NULL));
puts(squeeze(buffer, 'l', NULL));
puts(squeeze(buffer, 'o', NULL));
puts(squeeze(buffer, 'W', NULL));
puts(squeeze(buffer, 'r', NULL));
puts(squeeze(buffer, 'd', NULL));
puts(squeeze(buffer, 'H', NULL));
puts(squeeze(buffer, 'e', NULL));

return 0;
}
___________________________________________________________
 
S

sara

I have changed my code as following and now it works thanks to the
suggestions. I have two questions. First, is it possible to modify s
in the function without using a temporary and return it? Second, is
there anyway to make my function more readable?
Thanks a lot.

char* squeeze(char* s, char c)
{
char* string=(char*)malloc(strlen(s)+1);
strcpy(string,s);

int src=0;
int dst=0;

while(string[src]!='\0')
{
while (string[src]!=c && string[src]!='\0')
{
src++;
if (string[src]!='\0')
{
dst++;
string[dst]=string[src];
}
}

if (string[src]=='\0')
break;

while(string[src]==c)
src++;
string[dst]=string[src];
}

string[dst+1]=0;

return string;
}
 
C

Chris M. Thomasson

[...]
___________________________________________________________
#include <string.h>
#include <stdio.h>


char*
squeeze_ex(char* buf,
char cmp,
size_t size,
size_t* pnew_size)
{
if (buf && *buf)
{
char* cur;
size_t count;

for (cur = strchr(buf, cmp),
count = 0;
cur && *cur;
cur = strchr(cur, cmp),
++count)
{
memmove(cur, cur + 1, size - (cur - buf));
}

count = size - count;

if (pnew_size)
{
*pnew_size = size - count;
}
}

return buf;
}

BTW, this is example of a highly non-efficient implementation. You should
take a look at Richard's implementation, he basically gave you the answer.
 
S

sara

I know that I use a temporary (string variable) but I wonder if I can
work with s directly and update it instead of using another temporary
variable.
 
C

Chris M. Thomasson

Thanks but still you are using a temporary (t).
I want to work only with s.

What do you mean by temporary here? `t' is simply a pointer into the `s'
buffer.
 
B

bartc

Others have offered code, so sod it, here's another approach using
memmove which makes it real readable and easy to follow :-

,----
|
| #include <stdio.h>
| #include <string.h>
|
| char *squeeze(char *s, char c)
| {
| char *p = s;
| int count;
| for(count=strlen(s);count;p++,count--){
| if(*p==c)
| memmove(p,p+1,count);
| }
| return s;
| }
|
| int main()
| {
| char s[]="testme";
| printf("%s\n",squeeze(s,'e'));
| }
`----

So, for a million-char string consisting, for example, of one million 'e'
characters, this does about a million memmove calls?

I was going to test the efficiency of this but your code doesn't seem to
work when the character occurs consecutively (as in "meet").

(And here's the code I was going to compare with:

char* squeeze(char *s, char c) {
char *p=s;
char *t=s;
char d;

while (d=*t++) if (d!=c) *p++=d;
*p=0;
return s;
}
)
 
C

Chris M. Thomasson

[...]

char*
squeeze_ex(char* buf,
char cmp,
size_t size,
size_t* pnew_size)
{
if (buf && *buf)
{
char* cur;
size_t count;

for (cur = strchr(buf, cmp),
count = 0;
cur && *cur;
cur = strchr(cur, cmp),
++count)
{
memmove(cur, cur + 1, size - (cur - buf));
}

count = size - count;

LOL!

The line above is erroneous; it should be removed.

if (pnew_size)
{
*pnew_size = size - count;
}
}

return buf;
}




char*
squeeze_ex(char* buf,
char cmp,
size_t size,
size_t* pnew_size)
{
if (buf && *buf)
{
char* cur;
size_t count;

for (cur = strchr(buf, cmp),
count = 0;
cur && *cur;
cur = strchr(cur, cmp),
++count)
{
memmove(cur, cur + 1, size - (cur - buf));
}

if (pnew_size)
{
*pnew_size = size - count;
}
}

return buf;
}





Sorry about that non-sense!


;^(...
 
T

Tim Rentsch

sara said:
I have changed my code as following and now it works thanks to the
suggestions. I have two questions. First, is it possible to modify s
in the function without using a temporary and return it?

Apparently what you're looking for is a function that modifies
the original array in place, and uses array indexing in preference
to pointer manipulation.
Second, is there anyway to make my function more readable?
Thanks a lot. [code snipped]

The function you wrote is way too complicated for what it is
you want to do. This problem can be solved in short order:

void
squeeze( char *s, char c ){
unsigned to = 0, from = 0;

do {
s[to] = s[from];
if( s[to] != c ) to++;
} while( s[from++] );
}

Essentially the same algorithm can be done using pointer
manipulation instead of array indexing:

void
squeeze_using_pointers( char *s, char c ){
char *to = s, *from = s;

do {
*to = *from;
if( *to != c ) to++;
} while( *from++ );
}

You can (and perhaps should) try different variations on
these functions. But in any case you should be aiming for
something more like these than what you wrote. Any function
definition for this problem that's more than 20 lines long
should be viewed with suspicion.
 
H

Hallvard B Furuseth

sara said:
Thanks but still you are using a temporary (t).
I want to work only with s.

What are you talking about? s is a variable. So is t.
Your version also uses several variables other than s and c.

And why do you want to avoid variables anyway? Are you under the
impression that this is somehow an optimization, or is it just for play?

Anyway, if that's really what you want, you can do it moderately sanely
if you do not return s, but instead return void, so that it's ok to
modify s and thus forget its original value:

void squeeze(char *s, char c) {
if (c != '\0')
while ((s = strchr(s, c)) != NULL)
memmove(s, s + 1, strlen(s));
}

A saner program would only traverse the string (or part of it) once like
Richard's program does, instead of twice per number of c characters in
the string (the strlen and the memmove) - doing all this work is not
exactly an optimization.

If you do want to return the string, and not use variables, you cannot
modify s before returning it. Can still do it though: Instead of a
variable (s), use a library function (strchr) which computes what the
variable's value would be.

char *squeeze(char *s, char c) {
if (c != '\0')
while (strchr(s, c) != NULL)
memmove(strchr(s, c), strchr(s, c) + 1, strlen(strchr(s, c)));
return s;
}

There you are - no extra variables, and "all" it costs is 6 extra
traversals of part of the string for every c it contains.
 
F

Fred

What are you talking about?  s is a variable.  So is t.
Your version also uses several variables other than s and c.

And why do you want to avoid variables anyway?  Are you under the
impression that this is somehow an optimization, or is it just for play?

Anyway, if that's really what you want, you can do it moderately sanely
if you do not return s, but instead return void, so that it's ok to
modify s and thus forget its original value:

  void squeeze(char *s, char c) {
    if (c != '\0')
      while ((s = strchr(s, c)) != NULL)
        memmove(s, s + 1, strlen(s));
  }

A saner program would only traverse the string (or part of it) once like
Richard's program does, instead of twice per number of c characters in
the string (the strlen and the memmove) - doing all this work is not
exactly an optimization.

If you do want to return the string, and not use variables, you cannot
modify s before returning it.  Can still do it though: Instead of a
variable (s), use a library function (strchr) which computes what the
variable's value would be.

  char *squeeze(char *s, char c) {
    if (c != '\0')
      while (strchr(s, c) != NULL)
        memmove(strchr(s, c), strchr(s, c) + 1, strlen(strchr(s, c)));
    return s;
  }

There you are - no extra variables, and "all" it costs is 6 extra
traversals of part of the string for every c it contains.

However, without creating a new string, the whole thing might cause
a crash if the application passes a read-only string to the function:

str = squeeze( " remove blanks from me", ' ' );
 
H

Hallvard B Furuseth

Fred said:
However, without creating a new string, the whole thing might cause
a crash if the application passes a read-only string to the function:

str = squeeze( " remove blanks from me", ' ' );

Sure, but that's no different from the original variant.

The way to create a new string is to malloc() a a new object long enough
for the new string, and then copy the string (sans any c characters)
into it. Then the caller must free the memory with free().
 
P

Phil Carmody

Richard Heathfield said:
Yes. See below.


Yes. See below.

char *squeeze(char *s, char c)
{
char *t = s;
char *r = s;
for(; *s != '\0'; *s++)
*?

{
if(*s != c)
{
*t++ = *s;
}
}
*t = '\0';
return r;
}

From a performance perspective, I've found that always doing *t=*s,
and only incrementing t if the write was a desired one is a win.
Suitably squeezed, something like:
char*squeeze(char*r,char c){char*w=r;do{*w=*r;w+=*r!=c;}while(*r++);}

Phil
 
B

Ben Bacarisse

Phil Carmody said:
From a performance perspective, I've found that always doing *t=*s,
and only incrementing t if the write was a desired one is a win.
Suitably squeezed, something like:
char*squeeze(char*r,char c){char*w=r;do{*w=*r;w+=*r!=c;}while(*r++);}

Very neat, but there is a nit to pick: you need to change the type of
squeeze or you need to return something.
 
U

user923005

Very neat, but there is a nit to pick: you need to change the type of
squeeze or you need to return something.


char *squeeze(char *r, char c)
{
char *w = r;
char *s = w;
do {
*w = *r;
w += *r != c;
} while (*r++);
return s;
}
 
C

Curtis Dyer

I know that I use a temporary (string variable) but I wonder if
I can work with s directly and update it instead of using
another temporary variable.

Perhaps this is what you're misunderstanding. Richard's squeeze
function *does* update the original string.

`t' simply points to the same char as `s' points. The string data
is not actually copied before hand. It's needed to know where to
overwrite characters in the loop. `r' is used to simply remember
where the beginning of the string is.

Perhaps an example usage of Richard's function will be clearer:

#include <stdio.h>

/* Assume Richard's function definition is here */

int main(void)
{
char data[] = "foo bar baz";

puts(squeeze(data, ' '));
puts(data);

return 0;
}
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top