#include<iostream>
#include<string>
#include<vector>
#include<sstream> // To use istringstream
#include<algorithm> // To use transform()
using namespace std;

struct TokenFreq
{
	string token;
	int freq = 1;
};

void matrixInit(vector<vector<int> > &matrix, int numRows, int numCols) {
	int i, j;
	matrix.resize(numRows, vector<int>(numCols)); // Resizing vector
	for (i = 0; i < numRows; i++) { // Initializing
		for (j = 0; j < numCols; j++)
			matrix[i][j] = i * j;
	}
}

void getTokenFreqVec(const string &istr, vector<TokenFreq> &tfVec) {
	string tkn;
	int i, flag;
	TokenFreq t;
	istringstream isStream(istr);
	while (getline(isStream, tkn, ' '))
	{ // Tokenizing string
		transform(tkn.begin(), tkn.end(), tkn.begin(), ::tolower); // Converting all to lower case
		flag = 1;

		for (i = 0; i < tfVec.size(); i++) { // If tfVec contains the frequency for token
			if (tfVec[i].token == tkn) {
				tfVec[i].freq += 1; // Increment it
				flag = 0;
			}
		}
		if (flag) { // Inserting new word into vector if token is not present in it
			t.token = tkn;
			tfVec.push_back(t);
		}
	}
}

void selectionSort(vector<TokenFreq> &tokFreqVector) {
	int i, j, min;
	TokenFreq tkn;
	for (i = 0; i < tokFreqVector.size() - 1; i++)
	{
		min = i;
		for (j = i + 1; j < tokFreqVector.size(); j++) {
			if (tokFreqVector[j].freq < tokFreqVector[min].freq) { // Swap values if new minimum element is found
				tkn = tokFreqVector[min];
				tokFreqVector[min] = tokFreqVector[j];
				tokFreqVector[j] = tkn;
			}
		}
	}
}

void insertionSort(vector<TokenFreq> &tokFreqVector) {
	int i, j;
	TokenFreq token;
	for (i = 1; i < tokFreqVector.size(); i++) {
		token = tokFreqVector[i];
		for (j = i - 1; j >= 0 && tokFreqVector[j].freq < token.freq; j--)
			tokFreqVector[j + 1] = tokFreqVector[j];
		tokFreqVector[j + 1] = token;
	}
}

int main() {
	string istr = "And no, I'm not a walking C++ dictionary. I do not keep every technical detail in my head at all times. If I did that, I would be a much poorer programmer. I do keep the main points straight in my head most of the time, and I do know where to find the details when I need them. by Bjarne Stroustrup";
	vector<TokenFreq> tfVec;
	vector<vector<int> > matrix;
	int i, j;


	matrixInit(matrix, 3, 4);
	cout << "\nTesting matrix.\n";
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 4; j++)
			cout << "\nmatrix[" << i << "][" << j << "]=" << matrix[i][j];
	}
	getTokenFreqVec(istr, tfVec);
	cout << "\n\n\nTesting Tokenizer.\n\nSize: " << tfVec.size() << endl;
	for (i = 0; i < tfVec.size(); i++)
		cout << "\nToken: " << tfVec[i].token << ", Freq: " << tfVec[i].freq;
	selectionSort(tfVec);
	cout << "\n\n\nTesting selection sort.\n\n";
	for (i = 0; i < tfVec.size(); i++)
		cout << "\nToken: " << tfVec[i].token << ", Freq: " << tfVec[i].freq;
	insertionSort(tfVec);
	cout << "\n\n\nTesting insertion sort.\n\n";
	for (i = 0; i < tfVec.size(); i++)
		cout << "\nToken: " << tfVec[i].token << ", Freq: " << tfVec[i].freq;
	return 0;
}