/*
 ReverseWords.cpp
 Author: Hai Vu (haivu2004 on G mail) 
 
 This program implements and tests a popular interview question: reverse
 the words in a sentence. Words are separated by one or more spaces and
 punctuations are treated as normal characters. 
 
 For example, given the string:
 “He loves to  eat apples.”
 (note there are two spaces between to and eat), we should end up with:
 “apples. eat  to loves He”
 You should note the two spaces between eat and to. Also, you should note
 the capitalization and the position of the period. 
 
 Credit for solving this problem goes to Mongan, Suojanen, and Giguere
 (ISBN: 9780470121672) 
 
 Algorithm:
 First, reverse the whole string (”Je t’aime” would becomes “emia’t eJ”)
 loop until we exhaust the string
 locate the start of the next word
 locate the end of that word
 reverse that word in place
 end loop 
 
 In this program, I implemented the following functions:
 ReverseWords - this is the work horse to carry out the heavy lifting
 ReverseString - a helper to reverse any string in place 
 
 Please note that while I can use strrev() instead of writing my own
 ReverseString() function, I assume the interviewer will probably
 want me to roll my own. Similarly, I try to avoid the use of strlen().
 The only string function I use is _strdup(), but that is for testing.
 */   

#include <iostream>
#include <string>
using namespace std;

// This is a homemade strrev()
void ReverseString(char *left, char *right)
{
    char temp;
    while (left < right)
    {
        temp = *left;
        *left = *right;
        *right = temp;
        ++left;
        --right;
    }
}

void ReverseWords(char *buffer)
{
    // Find the end of the buffer, we can use strlen() for it, but
    // just assume that we are forced to do this on our own.
    char *start = buffer;
    char *end = buffer;
    while (*end != '\0')
        ++end;
    --end; // backup to point to the last non-null char
	
    // Reverse the whole string
    ReverseString(start, end);
	
    // Now, reverse each words
    while (*start != '\0')
    {
        // skip to the beginning of a word, at the end of the loop,
        // start points to the beginning of a word
        for ( ; *start != '\0' && *start == ' '; start++)
            ;
		
        // At the end of this loop, end will point to the end of the word
        for (end = start; *end != '\0' && *end != ' '; end++)
            ;
        --end;
		
        // Now reverse the string
        ReverseString(start, end);
		
        // Move on to the next word
        start = ++end;
    }
}
int main (int argc, char * const argv[]) {
	char * sample = "He loves to  eat apples.";
	cout << "Before, sample = '" << sample << "'" << endl;
	ReverseWords(sample);
	cout << "After, sample  = '" << sample << "'" << endl;
    return 0;
}