#include <iostream>
#include <fstream>
#include <string>
#include <map> //a binary search tree
#include <unordered_map> //a hash table
using namespace std;

//Should finish in : O(n log n) time at most.
int main()
{
	//Open the file
	ifstream infile("whale.txt");

	//Read in each word, increment count in map
	//Run time: O(n log n)
	string word;
	map<string, int> wordCounts;

	while (infile >> word)
	{ //Run time of loop body: O(log n)
		if (wordCounts.count(word) == 0) //word not yet insert
			wordCounts[word] = 1;
		else //word is already in the map
			wordCounts[word]++;
	}

	//Traverse items in map, write words and counts to outfile
	//run time: O(n)
	ofstream outfile("wordCounts.txt");
	for (auto x : wordCounts)
		outfile << x.first << " : " << x.second << endl;

	return 0;
}