How can i Right Trim all the spaces of a very long (2000 chars) Charecter string ?

[Durgesh Sharma]

Hi All,
Pleas help me .I am a starter as far as C Language is concerned .

How can i Right Trim all the white spaces of a very long (2000 chars)
Charecter string ( from the Right Side ) ? or how can i make a fast
Right Trim Function in c,using Binary search kind of fast algorithm ?

Offcourse...I can use the classical approach too.
like :
Start from the right most charecter of the string to the left of the
string and stop where we find the first none-whitespace charecter and
insert a NULL charecter,after increasing one place.It is working
fine.But problem is that suppose my string can hold 2000
charecters,but in a particular case i have only 1 charecter in my
string ,then i will have to sequentially traverse from charecter
position 2000 to 1 (1999 sequential searches) to put a NULL char at
position number 2.

String is of varying length sometime it can be of 2 charecters long
and other time it can have 2000 charecters too.

How can i use Binary search kind of fast search mechanism in the above
scenario in my function.

Please help me.
Thanks in advance.

Regards,
Durgesh Sharma

 

[Mac]

Hi All,
Pleas help me .I am a starter as far as C Language is concerned .

How can i Right Trim all the white spaces of a very long (2000 chars)
Charecter string ( from the Right Side ) ? or how can i make a fast
Right Trim Function in c,using Binary search kind of fast algorithm ?

Offcourse...I can use the classical approach too.
like :
Start from the right most charecter of the string to the left of the
string and stop where we find the first none-whitespace charecter and
insert a NULL charecter,after increasing one place.It is working
fine.But problem is that suppose my string can hold 2000
charecters,but in a particular case i have only 1 charecter in my
string ,then i will have to sequentially traverse from charecter
position 2000 to 1 (1999 sequential searches) to put a NULL char at
position number 2.

String is of varying length sometime it can be of 2 charecters long
and other time it can have 2000 charecters too.

How can i use Binary search kind of fast search mechanism in the above
scenario in my function.

Please help me.
Thanks in advance.

Regards,
Durgesh Sharma

I don't think there is any better way to solve your problem in general.

But if the string satisfies some special constraints, it may be possible.

Is the string allowed to contain white spaces in the significant part? If
so, I don't see any way to find the last white space except to start from
the end of the string and work backwards as you are currently doing.

If the string is NOT allowed to contain white spaces in the significant
part, then you can use a binary search algorithm. Something like the
following, which I threw together far too fast and didn't test:

#include <string.h>
void right_trim(char *s, long len)
{
long part_len, current;

part_len = len;
current = len/2;
while(part_len > 1)
{
part_len /= 2;
if (isspace(s[current]))
current -= part_len;
else
{
if ((current < len)
{
if (isspace(s[current+1]))
{
s[current + 1] = '\0';
return;
}
else
current += part_len;
}
}
}
}

Like I said, it is untested and probably won't work as written, but you
will hopefully get the idea.

--Mac

 

[Jack Klein]

Hi All,
Pleas help me .I am a starter as far as C Language is concerned .

How can i Right Trim all the white spaces of a very long (2000 chars)
Charecter string ( from the Right Side ) ? or how can i make a fast
Right Trim Function in c,using Binary search kind of fast algorithm ?

Offcourse...I can use the classical approach too.
like :
Start from the right most charecter of the string to the left of the
string and stop where we find the first none-whitespace charecter and
insert a NULL charecter,after increasing one place.It is working
fine.But problem is that suppose my string can hold 2000
charecters,but in a particular case i have only 1 charecter in my
string ,then i will have to sequentially traverse from charecter
position 2000 to 1 (1999 sequential searches) to put a NULL char at
position number 2.

String is of varying length sometime it can be of 2 charecters long
and other time it can have 2000 charecters too.

How can i use Binary search kind of fast search mechanism in the above
scenario in my function.

Please help me.
Thanks in advance.

Regards,
Durgesh Sharma

Note that nothing at all in your question is specific to the C
language, you are looking for an algorithm. That makes your question
more topical for a group line and even though I
am adding a few ideas here, you might well want to post there as well.

Binary search is useful if there is either zero or one of what you are
searching for in the data being searched. From your description
above, that obviously is not the case here. With a binary search, you
would first look at the character in the middle of the string. Even
if that is a white space character, it does not tell you anything at
all about what the half of the characters after it.

There are a few things you might try, if you haven't already, although
the last time I did this sort of thing processors did not have cache
like they do on desk top machines now.

Warning: uncompiled and untested.

#include <ctype.h>

char *right_trim(char *cp)
{
unsigned char *iter = (unsigned char *)cp;
unsigned char *term = iter;
int ch;

while ('\0' != (ch = *iter++))
{
if (!isspace(ch))
{
term = iter;
}
}
*term = '\0';
return cp;
}

This still reads every character in the string, there's really no way
to avoid this. But it doesn't waste a lot of time storing 1998 '\0'
characters in your string that starts with two non-blank characters
followed by that many white space characters.

When the loop ends, term either points to the first character of the
string, if it was '\0', or to the character immediately following the
last non-blank.

So while you still need to do 2000 reads, you only do one write.

 

[Bart]

Hi All,
Pleas help me .I am a starter as far as C Language is concerned .

How can i Right Trim all the white spaces of a very long (2000 chars)
Charecter string ( from the Right Side ) ? or how can i make a fast
Right Trim Function in c,using Binary search kind of fast algorithm ? ....
String is of varying length sometime it can be of 2 charecters long
and other time it can have 2000 charecters too.

Just some ideas..

Assuming you know the length of the string already: copy the string
pointer to to a pointer to ints (32 bits). Then you can test the
majority of the 2000 chars as <500 ints (each int will be 0x20202020
if all spaces), which should be faster.

You may have to test some 1..3 odd chars at the end first, then 1..3
odd chars as soon as the ints values aren't 0x20202020. Also it is
best if the int pointer is aligned to a 32-bit boundary.

Generally very messy and only worth doing for the longest strings.

You may want to test the trivial cases first of empty string and
whether the first char is a space. Then your loop doesn't need to
count, it is guaranteed to meet a non-space at some point.

If you don't already know the string length, create your own strlen(0
function that notes the last non-space character encountered. Then
trimming is trivial.

Bart

 

[Lawrence Kirby]

Hi All,
Pleas help me .I am a starter as far as C Language is concerned .

How can i Right Trim all the white spaces of a very long (2000 chars)
Charecter string ( from the Right Side ) ?

or how can i make a fast
Right Trim Function in c,using Binary search kind of fast algorithm ?

Binary searches work on sorted data. Since you don't have sorted data here
the approach is not applicable.

Offcourse...I can use the classical approach too. like : Start from the
right most charecter of the string to the left of the string and stop
where we find the first none-whitespace charecter and insert a NULL
charecter,after increasing one place.It is working fine.But problem is
that suppose my string can hold 2000 charecters,but in a particular case
i have only 1 charecter in my string ,then i will have to sequentially
traverse from charecter position 2000 to 1 (1999 sequential searches) to
put a NULL char at position number 2.

A non-whitespace character in any of those 1999 positions would affect the
result, and since there isn't any ordering in the data an algorithm that
didn't end up checking every position beyond the actual last
non-whitespace character would be broken. Any character it didn't check
might contain a non-whitespace character.

....

How can i use Binary search kind of fast search mechanism in the above
scenario in my function.

Not usefully.

Lawrence

 

[kyle york]

Greetings,

Binary searches work on sorted data. Since you don't have sorted data here
the approach is not applicable.

Not entirely true, but we've not enough information to determine if it's
true or not. If the string cannot contain spaces except for padding on
the right then it is sorted where space is greater than any other
character, and a binary search is possible.

Also, if it's known that the string can have at most one space between
any non-space characters, then a binary search can also be implemented.

If an unknown number of spaces can occur between non-space characters,
then a binary search is not feasible.

 

[Joe Wright]

Greetings,




Not entirely true, but we've not enough information to determine if it's
true or not. If the string cannot contain spaces except for padding on
the right then it is sorted where space is greater than any other
character, and a binary search is possible.

Sorted? The spaces to the right of the non-spaces would be of course
less that the non-spaces. The task would be to find not just any,
but the first space after the last non-space. The binary search
would be a little perverse. Also the problem it is trying to solve
is contrived. Nobody has asked to trim "maryhadalittlelamb " of
its trailing spaces.

Also, if it's known that the string can have at most one space between
any non-space characters, then a binary search can also be implemented.

Not that I doubt you, but I don't know exactly how I would do that.
Plase code it up and show me how.

 

[Alex Fraser]

Sorted? The spaces to the right of the non-spaces would be of course
less that the non-spaces.

It doesn't really matter, but I think Kyle meant "It is sorted in ascending
order if you consider space greater than any other character".

The task would be to find not just any, but the first space after the
last non-space. The binary search would be a little perverse.

How would /you/ find the first of the set of equal items in a sorted array?
Or are you saying you'd never want to do that?

Also the problem it is trying to solve is contrived.

That I agree with.

Not that I doubt you, but I don't know exactly how I would do that.
Plase code it up and show me how.

I'm sure you can write something very much like a binary search (not
complete and almost certainly not quite correct, but hopefully illustrates
the idea):

low = 0;
high = strlen(s);

for (; {
mid = (low + high) / 2;
if (mid == low) break;
if (s[mid] == ' ') {
for (i = mid + 1; i < high; ++i)
if (s != ' ') break;
if (i < high) low = i + 1; else high = mid;
} else {
low = mid + 1;
}
}

Alex

 

[Richard Bos]

Not that I doubt you, but I don't know exactly how I would do that.
Plase code it up and show me how.

Search on two-character chunks. Chunks with zero or one space are low,
two spaces are high. No order within the low range is necessary. Once
you've found either the first two-space chunk or none at all, check
whether the last non-two-space chunk end in an odd space.
This is not likely to be very useful, especially since...

....this is very probably the case.

Richard

 

[Lawrence Kirby]

On Mon, 06 Dec 2004 08:52:11 -0800, kyle york wrote:

....

Not entirely true, but we've not enough information to determine if it's
true or not.

Specifically there is nothing in the problem specification that allows us
to consider the data "sorted" for our purposes. So I stand by my statement.

Lawrence