473,226 Members | 1,720 Online

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

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.

Regards,
Durgesh Sharma
Nov 14 '05 #1
9 6247
On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote:
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.

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

Nov 14 '05 #2
On 4 Dec 2004 04:10:33 -0800, du******@compucomtech.co.in (Durgesh
Sharma) wrote in comp.lang.c:
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.

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 news:comp.programming, 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.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
Nov 14 '05 #3
On 4 Dec 2004 04:10:33 -0800, du******@compucomtech.co.in (Durgesh
Sharma) wrote:
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
Nov 14 '05 #4
On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote:
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
Nov 14 '05 #5
Greetings,

Lawrence Kirby wrote:
On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote:

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.

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.

--
Kyle A. York
Sr. Subordinate Grunt
Nov 14 '05 #6
kyle york wrote:
Greetings,

Lawrence Kirby wrote:
On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote:

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.

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
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.
If an unknown number of spaces can occur between non-space characters,
then a binary search is not feasible.

--
Joe Wright mailto:jo********@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Nov 14 '05 #7
"Joe Wright" <jo********@comcast.net> wrote in message
news:tr********************@comcast.com...
kyle york wrote:
Lawrence Kirby wrote:
On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote:

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

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

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[i] != ' ') break;
if (i < high) low = i + 1; else high = mid;
} else {
low = mid + 1;
}
}

Alex
Nov 14 '05 #8
Joe Wright <jo********@comcast.net> wrote:
kyle york wrote:
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.

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...
If an unknown number of spaces can occur between non-space characters,
then a binary search is not feasible.

....this is very probably the case.

Richard
Nov 14 '05 #9
On Mon, 06 Dec 2004 08:52:11 -0800, kyle york wrote:

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

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

Nov 14 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

 8 by: DrBob | last post by: gcc 3.3 MAC OS X. I have a string that has trailing spaces in it that I want removed. So i have a variable: string x("abcd "); x.trim() isn't an implemented method. Is there a method I... 22 by: Simon | last post by: Hi, I have written a function to trim char *, but I have been told that my way could be dangerous and that I should use memmove(...) instead. but I am not sure why my code could be 'dangerous'... 3 by: Andy B | last post by: I've tried using Trim or RTrim to strip trailing space characters from my data. When I check on the transformed data space characters are still there. We have an address table containing two... 8 by: sengkok | last post by: I have develop a smart card device reading and writing program, but I am facing a problem that when I read the value from the smart card, I get "A19\0 \0\0\0", (actually I have store the value A19... 6 by: mwazir | last post by: Can someone please explain this to me Dim str As String = Chr(12) Debug.WriteLine(str) ' Output shows the line feed junk character Dim iLen As Integer = str.Trim.Length... 11 by: Darren Anderson | last post by: I have a function that I've tried using in an if then statement and I've found that no matter how much reworking I do with the code, the expected result is incorrect. the code: If Not... 3 by: Pascal | last post by: bonjour hello I would like to trim a string of all its white spaces so i used myString.trim() but it doesn't work as supposed : unsecable space are remaining in the middle of my string... i... 3 by: ayan4u | last post by: well i need to deal with white spaces in charecter arrays... with static arrays its fine.. char ss; cin.getline(ss, sizeof ss); .... //deals with white spaces 15 by: cj | last post by: I've got a long string to be written to a field in a sql db table via stored procedure. For some reason I find only 258 chars are being written. Any ideas? relevant bits of my VB2005 code: ... 1 by: isladogs | last post by: The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike... 0 by: veera ravala | last post by: ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow... 0 by: VivesProcSPL | last post by: Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for... 0 by: jianzs | last post by: Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from... 0 by: abbasky | last post by: ### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method... 2 by: jimatqsi | last post by: The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art... 0 by: stefan129 | last post by: Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific... 0 by: egorbl4 | last post by: Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ... 0 by: MeoLessi9 | last post by: I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....