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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
|
#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...
|