wordwrap function

Question

Hey guys, I'm writing a word wrap function to format console text in C++. My problem is either A) I don't understand exactly what std::string::iterators do, or B) one of my iterators is not being set properly. Can anyone shed some light on the reason this code fails?

by the way: sorry if this goes into too much detail. I'm not sure if most programmers (I'm a "newbie") have a C++ compiler installed on their machine.

std::string wordWrap(std::string sentence, int width)
{    
   //this iterator is used to optimize code; could use array indice 
   //iterates through sentence till end 
   std::string::iterator it = sentence.begin();
   //this iterator = it when you reach a space; will place a newline here
   //if you reach width;
   std::string::iterator lastSpace = sentence.begin();

   int distanceToWidth = 0;

   while (it != sentence.end())
   {
      while (it != sentence.end() && distanceToWidth < width)
      {
         if (*it == ' ')
         {
           lastSpace = it;
         }

         distanceToWidth++;
         it++;
     }

     distanceToLength = 0;
     *lastSpace = '\n';   

      //skip the space
      if (it != sentence.end())
      {
         it++;
      }
   }

   return sentence;    
}

I'm not getting correct output. Assuming I called it like this:

std::cout << wordWrap("a b c abcde abcdef longword shtwd", 5) << std::endl << std::endl;
std::cout << wordWrap("this is a sentence of massive proportions", 4) << std::endl;

I get unsatisfying output of this:

a b 
c
abcde
abcdef
longword
shtwd

//yes I get his, instead of this
his is
a
sentence
of
massive
proportions
Press any key to continue . . .

My problem is that I'm am getting newlines when inappropiate. I am getting newlines too often, and I don't see any obvious error as to why that is. I was hoping someone independent (I've spent a few hours on this algorithm, and to not have the right results is quite frusturating) of the problem could look at it. Also, any obvious optimization tips?

Answer 1

You are probably mixing unicode and ANSI strings and chars. Your iterators point to characters in a unicode string, whereas when you overwrite their contents you are using ANSI characters... Evidently with ugly results.

Try TCHAR('\n') instead of just '\n', TCHAR(' ') instead of ' '.

Answer 2

Your output is correct from what your code shows. What you got wrong is the algorithm. Use a debugger to find out what actually happens.

Answer 3

The lastSpace iterator starts on the first character of sentence:

//this iterator = it when you reach a space; will place a newline here
//if you reach width;
std::string::iterator lastSpace = sentence.begin();

When you reach the fifth character of "this is a..." (the space), the inner while loop exits (because distanceToWidth == width), before it is recognized that the current character is a space. Then a newline is inserted in position lastSpace, which still points to the first character of the string. This way the "t" of "this" is lost.

Next distanceToWidth is reset to zero and another width characters are appended, although the line was not split at the current position, but some characters before (at lastSpace). So this line can end up containing more characters than expected. In the example, "is" is still on the same line as "this" while it should be wrapped to the next line.

You probably need to:

• change the condition of the inner while to <= so that the correct width is checked
• not initialize lastSpace to the first character of the string. Probably better:

std::string::iterator lastSpace;
...
if (lastSpace) {
   *lastSpace = '\n';
}

• count how many characters were found since the last space, and uses this to reset distanceToWidth after inserting a line break

Answer 4

The problem is that the word this is 4 characters, and you are wrapping at four characters. So it is trying to wrap before it has set lastSpace to something reasonable.

Look at it from the point of stepping through the code:

lastSpace points to the "t" from the beginning of "this"
distanceToWidth=0
iterator=this is
         ^

check if we should loop (distanceToWidth<4)
is the current character a space? no
distanceToWidth=1
iterator=this is
          ^

check if we should loop (distanceToWidth<4)
is the current character a space? no
distanceToWidth=2
iterator=this is
           ^

check if we should loop (distanceToWidth<4)
is the current character a space? no
distanceToWidth=3;
iterator=this is
            ^

check if we should loop (distanceToWidth<4)
is the current character a space? no
distanceToWidth=4;
iterator=this is
             ^

check if we should loop (distanceToWidth<4) NO! Because distanceToWidth equals four!

We break out of the loop.

Recall that lastSpace was never modified it still points to the first character in the string!
now we set the "t" character from "this" to be a newline!!

ETC

Thus we output an extra newline instead of the "t" in "this"

about fixing it... well... you can figure it out

Answer 5

Update: here is my latest code, showing correct output. Please comment if you read this again. Sorry for bad formatting, but it's a hassle to add four spaces in front of each line and it is 1:45 AM.

std::string wordWrap(std::string sentence, int width)
{    
//this iterator is used to optimize code; could use array indice 
//iterates through sentence till end 
std::string::iterator it = sentence.begin();
//this iterator = it when you reach a space; will place a newline here
//if you reach width; also kind of hackish (used instead of comparing to NULL)
std::string::iterator lastSpace = sentence.begin();

int distanceToWidth = 0;

//used in rare instance that there is a space
//at the end of a line
bool endOfLine = false;

while (it != sentence.end())
{
   //TODO: possible to stop recomparing against .end()?
   while (it != sentence.end() && distanceToWidth <= width)
   {
      distanceToWidth++;

      if (*it == ' ')
      {
         lastSpace = it;

         //happens if there is a space after the last character
         if (width == distanceToWidth)
         {
            *lastSpace = '\n'; 
         }
      }

      ++it;
   }

   //happens when lastSpace did encounter a space
  //otherwise
   if (lastSpace != sentence.begin())
   {
      *lastSpace = '\n';   
   }       

   lastSpace = sentence.begin();
   distanceToWidth = 0;
   }

   return sentence;    
}