How would you have done this?

[Kieth89]

Make a program to create a permutated index for a given input. For information on what a permutated index is see this thread: http://www.cplusplus.com/forum/beginner/73297/

So I finished my version of this, but feel like I did it in-efficiently, or it could be done a better way. Now I want to see how others would have done it. It'd be awesome if you wanted to take the time to code it all out, but if you don't then just give a summary of how you would do it. If giving a summary answer the following points (Because it is easy to leave important stuff out or over-simplify something when summarizing):
1) How would you grab input?
2) How would you store the index?
3) How would you rotate, alphabetize, and then unrotate?
For reference, all the book (accelerated c++) has taught up to this point is stl List and Vector, references, looping, other basics. But use whatever methods you think would work best! I just want to see different ways of solving this.


Here is my attempt at it. I figured that instead of unrotating by comparing to a set string each time, which would be hard when the user can enter many strings for one go through, it'd be easier to store the times the line had been rotated. I did this through a structure that contains a list of strings (the words of the line) and an int to keep track of the times that line had been rotated. The code (is hopefully) self explanatory:

#include <iostream>
#include <string>
#include <list>
#include <ctype.h>

using std::list;
using std::string;
using std::getline;
using std::cin;
using std::cout;

// struct to hold a line of input split into words, and the number of times it's been rotated.
struct indexLine
{
	list<string> LineWords;
	int timesRotated;
};

list<string> getWords(const string& line);	// used to split the string line into a list<string> containing the words
string mergeWords(const list<string>& words);	// combines a list<string> of a lines words into one string
bool compare(const indexLine& line1, const indexLine& line2);	// predicate used for alphabetizing indexLine structures

int main()
{
	list<indexLine> inputLines;
	string inputBuffer;
	indexLine currentLine;
	cout << "Enter EOF on a new line to end input\n";
	while (getline(cin, inputBuffer))
	{
		currentLine.LineWords = getWords(inputBuffer);
		currentLine.timesRotated = 0;
		inputLines.push_back(currentLine);
	}

	// store all possible line rotations in indexContextLines
	list<indexLine> indexContextLines;
	for (list<indexLine>::const_iterator structItr = inputLines.begin();  structItr != inputLines.end(); ++structItr) 
	{
		currentLine = *structItr;
		for (list<string>::size_type stringSizeCounter = 0; stringSizeCounter < structItr->LineWords.size(); 
                ++stringSizeCounter)
		{
			currentLine.LineWords.push_back(currentLine.LineWords.front());
			currentLine.LineWords.pop_front();
			currentLine.timesRotated += 1;
			indexContextLines.push_back(currentLine);
		}
	}

	indexContextLines.sort(compare);	// alphabetize

	// store the keyword (word that the line is sorted by) in indexKeyWords
	list<string> indexKeyWords;
	for (list<indexLine>::const_iterator itr = indexContextLines.begin(); itr != indexContextLines.end(); ++itr)
	{
		indexKeyWords.push_back(itr->LineWords.front());
	}

	// unrotate the lines,
        // note that if a line is rotated x times, where x is the number of words in it, then no unrotation is necessary
	for (list<indexLine>::iterator structItr = indexContextLines.begin(); structItr != indexContextLines.end(); ++structItr)
	{
		while ( structItr->timesRotated != structItr->LineWords.size() && structItr->timesRotated > 0)
		{
			structItr->LineWords.push_front(structItr->LineWords.back());
			structItr->LineWords.pop_back();
			structItr->timesRotated -= 1;
		}
	}

	//display permutated index
	list<string>::iterator stringItr = indexKeyWords.begin();
	for (list<indexLine>::iterator structItr = indexContextLines.begin(); structItr != indexContextLines.end();
        ++structItr, ++stringItr)
	{
		cout << *stringItr << '\t' << mergeWords(structItr->LineWords) << std::endl;
	}
	return 0;
}


list<string> getWords(const string& line)
{
	list<string> words;
	std::string::const_iterator itr = line.begin(); 

	while (itr < line.end())
	{
		if (isspace(*itr)) { ++itr;}
		else
		{
			string currentWord;
			while (itr < line.end() && !isspace(*itr))
			{
				currentWord += *itr;
				++itr;
			}
			words.push_back(currentWord);
		}
	}
	return words;
}

string mergeWords(const list<string>& words)
{
	string merged;
	for (list<string>::const_iterator itr = words.begin(); itr != words.end(); ++itr)
	{
		merged += *itr + " ";
	}
	return merged;
}

bool compare(const indexLine& line1, const indexLine& line2)
{
	string string1 = mergeWords(line1.LineWords);
	string string2 = mergeWords(line2.LineWords);
	for( string::const_iterator str1Itr = string1.begin(), str2Itr = string2.begin();
 str1Itr != string1.end() && str2Itr != string2.end(); ++str1Itr, ++str2Itr )
	{
		if( tolower( *str1Itr ) < tolower( *str2Itr ) ) { return true; }
		else if( tolower( *str1Itr ) > tolower( *str2Itr ) ) { return false; }
	}
	if( string1.size() < string2.size() ) { return true; }
	else { return false; }
}

And a test run (the 3 lines after the first line are user input):

Enter EOF on a new line to end input
The quick brown fox
jumped over the fence
^Z

brown      The quick brown fox
fence      jumped over the fence
fox        The quick brown fox
jumped     jumped over the fence
over       jumped over the fence
quick      The quick brown fox
the        jumped over the fence
The        The quick brown fox
Press any key to continue...

[MrHutch]

Noooooo! Permuted index returns!

I'll take a look at this a little later when I finish work if I get the chance. :-)

[Kieth89]

lol...It was harder than it looked at first glance. :P

[Kieth89]

Only bump I'll do. Critique my code! :)