/*
* This program reads its input and finds all the words. It then counts each
* one and produces a report of all the words and counts, ordered by count.
* A word is a maximal group of alphanumeric characters.
*/
#include <cctype>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// Sorting function. Used for a sort near the bottom of main to order
// the results descending by the count, then ascending by the word within
// matching counts.
bool order_by_second_descending
(map<string,int>::iterator a, map<string,int>::iterator b)
{
if(a->second == b->second) return a->first < b->first;
else return a->second > b->second;
}
int main()
{
// Map of counts.
map<string,int> counts;
// Read the input. Read it one character at a time and discard
// puntuation to form words.
string current_word = "";
char next_char;
while(cin.get(next_char)) {
if(isalnum(next_char)) {
// This a wordish character (letter or digit). Add it
// to the current word.
current_word.push_back(next_char);
} else if(current_word != "") {
// The current character is not wordish, but there are
// some characters in the current word. So, we need to
// add the word to the count.
// Add to the count. This finds and returns a reference
// to the data (integer count) associated with the
// current_word. Magically, if it doesn't exist,
// the subscript operator adds the entry with a
// count of the default integer, zero, and returns
// a reference to that. Then we increment.
counts[current_word]++;
// Make sure we don't count this occurrance again.
current_word = "";
}
}
// Now, we have counts for all the words. They're ordered by word,
// but we want to order them by count. We could do this by making a
// reverse map<int,string> and simply copying all the entries over,
// but lets try out another way to do it.
// Make a vector for sorting purposes. The vector contains iterators
// which point to entries in the map.
vector<map<string,int>::iterator> count_order;
// Fill it with those iterators to map items. (Think of it as an
// array of pointers to all the map pairs.) The reserve asks for more
// space, which can be more efficient to do once than have the system
// adjust each time it needs more. It doesn't change the size; just
// allocates space for future use.
count_order.reserve(counts.size());
for(auto i = counts.begin(); i != counts.end(); ++i)
count_order.push_back(i);
// Now, we sort the list of iterators based on the count and
// then the word represented in the map pair they point to.
// The sort() fuction is from the algorithms header, and takes
// an iterator to the first item, and an iterator one past the
// last item.
sort(count_order.begin(), count_order.end(),
order_by_second_descending);
// Print the values in the sorted order descending count,
// increasing word within each count value.
for(auto j: count_order) {
cout << setw(8) << right << j->second << " "
<< left << j->first << endl;
}
}