#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>

// Stänger av vissa varningar i Visual Studio 2005
#pragma warning(disable : 4996)


using namespace std;

// Lagra vårt trie frekvenssorterat för att spara minne
int charmap[256] = {0};

int chunk(int subpos)
{
	return (subpos / 400) % 16;
}

// Struktur för poängdata, används ej i denna version (se "collapse")
struct scoredata
{
	int pos;
	double score;
	char* stem;

	scoredata(int pos, double score, char* stem)
	{
		this->pos = pos;
		this->score = score;
		this->stem = stem;
	}
};

// Konstanter för antalet element i matrisen
const int sizebuckets = 1;
const int fractionbuckets = 1;
const int tagcount = 400;

// Används för optimeringen, positioner större än 9 används för en binärsökning
// i vissa optimeringsvarianter
double matrix[30][tagcount * sizebuckets * fractionbuckets];
double stats[10][2][tagcount * sizebuckets * fractionbuckets];
double delta[10][tagcount * sizebuckets * fractionbuckets];
int delta2[10][tagcount * sizebuckets * fractionbuckets];
int delta3[10][tagcount * sizebuckets * fractionbuckets];

// Ger pekare till element i matrix beroende på parametrar
// På så vis kan vi bryta ut det ur work-metoden.
double* score(int id, int revpos, int max, int size, int subsize)
{
	int coord = (id) * sizebuckets * fractionbuckets;
	int sub = subsize / 5;
	if (sub >= sizebuckets)
	{
		sub = sizebuckets - 1;
	}

	if (revpos >= 10) revpos = 9;

	int sub2 = max * fractionbuckets / (size + 1);

	coord += sub * sizebuckets + sub2;

	int apa = &matrix[revpos][coord] - matrix[0];
//	fprintf(stderr, "%d %d\n", apa, id);
	return &matrix[revpos][coord];
}

// Själva datastrukturen
struct trie
{
	// Frekvenssorterad lista med döttrar
	vector<trie*> children;

	// Total storlek på trädet med underträd, alla ord
	int size;
	// Antal ord på DENNA nivå
	int size2;
	// Högsta poäng på denna nivå
	int max;
	// Är listan sorterad?
	bool sorted;

	// Koppling mellan frekvenser och suffix på just denna nivå
	vector<pair<int, char*> > scores;

	// Konstruera ett trie
	trie()
	{
		size = 0;
		size2 = 0;
		max = 0;
		sorted = true;
	}

	// Returnera dottertrie för aktuellt tecken, frekvenssortering
	trie* get(char c)
	{
		unsigned int val = charmap[(unsigned char) c];
		if (val >= children.size())
		{
			return 0;
		}

		return children[val];
	}

	// Ange dottertrie för aktuellt tecken, frekvenssortering
	void set(char c, trie* trieval)
	{
		unsigned int val = charmap[(unsigned char) c];
		if (val >= children.size())
		{
			children.resize(val + 1);
		}

		children[val] = trieval;
	}

	// Fyll på trädet nedåt
	void add(int length, int homogenlength, int pos, char* word, char* stem)
	{
		size++;

		// Fyll in suffixdata om vi har nått punkten då strängarna är lika
		if (pos <= homogenlength)
		{
			size2++;
			char* partstem = &stem[pos];
			unsigned int i;
			for (i = 0; i < scores.size(); i++)
			{
				if (strcmp(partstem, scores[i].second) == 0)
				{
					break;
				}
			}

			if (i == scores.size())
			{
				scores.push_back(make_pair(0, partstem));
			}

			scores[i].first++;

			if (max < scores[i].first)
			{
				max = scores[i].first;
			}
			sorted = false;
		}

		// > eller >= ?
		if (pos > 0)
		{
			trie* subtree = get(word[pos - 1]);
			if (subtree == 0)
			{
				subtree = new trie();
				set(word[pos - 1], subtree);
			}

			subtree->add(length, homogenlength, pos - 1, word, stem);
		}
	}

	// Fyll i data om olika lemman
	void work(int id, int length, int pos, char* word, map<string, double> &result, double partscore, string target, double limit)
	{
		// Bryt om det verkar vara slut
		if (!size) return;
		if (partscore < limit) return;

		// Plocka fram poäng
		double* subpart = score(id, length - pos, max, size, size2);

		double herepart = partscore * (*subpart);
		double subpart2 = /*partscore - herepart*/ 1;

		trie* subtree = get(word[pos - 1]);

		// Dividera med storleken på nivån, så länge den inte är 0. §§
		if (size2)
		{
			herepart /= size2;
		}
		else
		{
		}

		//double base = result[target];
		// Förbered grunden som suffix läggs till
		static char str[255];
		strncpy(str, word, pos);
		str[pos] = 0;

		char* suffix = &str[pos];

		// Sortera, om det inte är gjort, så vi kan bryta så fort ett tal kommer under gränsen
		if (!sorted)
		{
			sort(scores.begin(), scores.end());
			sorted = true;
		}

		// Lägg till dem
		for (int i = (int) scores.size() - 1; i >= 0; i--)
		{
			strcpy(suffix, scores[i].second);

			double addition = herepart * scores[i].first;
			result[str] += addition;
			if (target == str)
			{
				subpart[tagcount * sizebuckets * fractionbuckets * 10] += addition;
			}
			subpart[tagcount * sizebuckets * fractionbuckets * 20] += addition;
			if (addition < limit)
			{
				//fprintf(stderr, "%d %d\n", i, scores.size());
				break;
			}
			//			result.push_back(scoredata(length - pos - 1, herepart * scores[i].second, scores[i].first));
		}

		//double mid = result[target];

		// Rekursionsanropet, resten gäller optimeringskoden, som ej fungerar
		if (subtree && pos > 0)
		{
			subtree->work(id, length, pos - 1, word, result, subpart2, target, limit);
		}

		/*double hi = result[target];

		if (subpart2 && partscore && subpart)
		{
			hi = (hi - mid) / subpart2;
			mid = (mid - base) / (partscore * (*subpart));

			int index = subpart - &matrix[0][0];
			/*delta[0][index] += partscore;
			delta[0][index] -= 2 * ((hi - mid) >= 0) * partscore;*/
			//delta[0][index] -= ((hi - mid)) * partscore;
			/*corr[((hi - mid) < 0) ^ (delta[0][index] < 0)]++;
			if (corr[0] % 1024 == 0) fprintf(stderr, "%d %d\n", corr[0], corr[1]);*/
		//}
	}
};


// Omvandla scoredata till en map, används inte nu
void collapse(vector<scoredata> &nostruct, map<string, double> &structure, char* word)
{
	size_t len = strlen(word);
	string str = word;
	for (size_t i = 0; i < nostruct.size(); i++)
	{
		string suffix = str.substr(0, len - nostruct[i].pos - 1);
		suffix += nostruct[i].stem;

		structure[suffix] += nostruct[i].score;
	}
}

map<string, int> tags;
vector<string> tags2int;
int nowtagID = 0;

// Skapa taggnummer från strängar, unika
const int tagCode(string tag)
{
	map<string, int>::iterator i;
	if ((i = tags.find(tag)) == tags.end())
	{
		tags[tag] = nowtagID;

		tags2int.push_back(tag);

		printf("%d\n", nowtagID);
		return nowtagID++;
	}

	return i->second;
}

// Alla ord lagras här
struct word
{
	char* verbatim;
	char* stem;
	unsigned char tag;
	bool changed;

	word(char* verbatim, char* stem, unsigned char tag)
	{
		this->verbatim = verbatim;
		this->stem = stem;
		this->tag = tag;
		changed = false;
	}
};

// Då vi har en massa ord och suffix av samma strängar lönar det sig mycket att själva hålla reda
// på pekarna
char words[20000000];
char stems[20000000];
char* curword = words;
char* curstem = stems;

trie tries[tagcount];
map<string, char*> verygood[tagcount];
map<string, int> backgood;
map<string, char*> backwords[tagcount];

vector<word> worddata;

int main(int argc, char** argv)
{
	setlocale(LC_ALL, "");
	char line[1024];
	vector<pair<int, char> > chardist;
	for (int i = 0; i < 256; i++)
	{
		chardist.push_back(make_pair(0, i));
	}

	chardist[0].first = -1 << 28;
	bool lastvalid = true;

	// Läs in data från deg2-filer från stdin, lagra
	while (gets(line))
	{
		char* stem = strstr(line, "lem='");
		char* tag = strstr(line, "msd='");
		char* verbatim = strstr(line, ">");
		//printf("%s\n", line);
		int gt = 0;

		char* str = line;
		// Vissa filer innehåller ogiltig XML, < och > från ordformer har inte skrivits som &lt; eller &gt;
		// Detta är ett fulhack som i alla fall gör att vi inte kraschar p.g.a. detta.
		while (*str)
		{
			switch (*str)
			{
			case '<': gt--;
				break;
			case '>': gt++;
				break;
			}
			str++;
		}

		// Mismatch
		if (gt) continue;

		if (stem && tag && verbatim)
		{
			if (!lastvalid)
			{
				worddata.push_back(word(0, 0, 0));
				lastvalid = true;
			}
			stem = strchr(stem, '\'');
			tag = strchr(tag, '\'');
			stem++;
			tag++;

			*strchr(stem, '\'') = 0;
			*strchr(tag, '\'') = 0;

			verbatim++;
			*strchr(verbatim, '<') = 0;

			strcpy(curword, verbatim);
			strcpy(curstem, stem);

			worddata.push_back(word(curword, curstem, tagCode(tag)));
			int length = strlen(curword);			

			// Gemener
			for (int i = 0; i < length; i++)
			{
				curword[i] = tolower(curword[i]);
				chardist[(unsigned char) curword[i]].first--;
			}

			int stemlength = strlen(curstem);
			for (int i = 0; i < stemlength; i++)
			{
				curstem[i] = tolower(curstem[i]);
			}

			// Vi borde även göra gemener av lemmat, men då jag hade glömt detta i den kod som låg till grund
			// för rapportens evaluering görs det ej!

			curword += length + 1;
			curstem += stemlength + 1;
		}
		else
		{
			// Håller reda på meningsgränser
			lastvalid &= ! ((bool) strstr(line, "</s>"));
		}
		// På väg att förbruka minnet?
		if ((curword - words) > 19000000) printf("VARNING!\n");
	}

	// Bygg upp teckenfrekvensdata
	sort(chardist.begin(), chardist.end());
	for (int i = 0; i < 256; i++)
	{
		charmap[(unsigned char) chardist[i].second] = i;
	}	

//	const double templat[] = {0.055217939, 0.089693943, 0.107455643, 0.118083899, 0.119047788, 0.118038512, 0.113844447, 0.105352552, 0.091304787, 0.081960489};

	for (int i = 0; i < 10 * tagcount * sizebuckets * fractionbuckets; i++)
	{
//		matrix[0][i] = templat[i / tagcount / sizebuckets / fractionbuckets];
		matrix[0][i] = 0.05/* / (1 - 0.05 * (i / tagcount / sizebuckets / fractionbuckets))*/;
		//matrix[0][i] = 0;
	}

	int subpos = 0;
	
	// För in orden i tries, samt verygood
	// (verygood är Lista 1, förutom verygood[tagcount - 1] där Lista 2 får trängas

	for (int i = 0; i < worddata.size(); i++)
	{		
		if (worddata[i].verbatim)
		{
			int homogenlength = 0;
			char* curword = worddata[i].verbatim;
			char* curstem = worddata[i].stem;

			while (curword[homogenlength] && curstem[homogenlength] && curword[homogenlength] == curstem[homogenlength])
			{
				homogenlength++;
			}

			/*if (!curword[homogenlength] && !curstem[homogenlength])
			{
			homogenlength++;
			}*/

			//			printf("%s %s1\n", curword, curstem);

			int length = strlen(curword);

			if (verygood[worddata[i].tag].find(curword) == verygood[worddata[i].tag].end())
			{
				backgood[curstem]++;
				backwords[worddata[i].tag][curstem] = curword;
			}
			verygood[worddata[i].tag][curword] = curstem;				
			verygood[tagcount - 1][curword] = curstem;

			tries[worddata[i].tag].add(length, homogenlength, length, curword, curstem);
		}

		if (!worddata[i].verbatim)
		{
			subpos++;
		}
	}

	subpos = 0;

	int startpoint = worddata.size();
	if (argc < 2)
	{
		printf("Du borde ge en TNT-taggad fil som parameter.\n");
	}

	// Läs in den taggade filen
	FILE* tagged = fopen(argv[1], "rt");
	while (fgets(line, 1023, tagged))
	{
		if (line[0] == '%') continue;
		// Kommentar
		char tag[1024];

		if (sscanf(line, "%s %s", curword, tag) == 2)
		{
			int length = strlen(curword);
			for (int i = 0; i < length; i++)
			{
				curword[i] = tolower(curword[i]);
			}

			worddata.push_back(word(curword, 0, tagCode(tag)));

			curword += length + 1;
		}
	}

	// Den här loopen är onödigt komplicerad, då den egentligen skall kunna optimera.
	// steget 1000 beror på att det "råkade" bli hårdkodade konstanter överallt.
	// step kan sedan modereras för att justera antalet steg, när den stackars studenten blir otålig.
	// Tanken var att justera varje positionssteg för sig och sedan börja om från position 0 igen.
	int step = 1000;
	for (int j = 0; j < 1; j+= step)
	{
		int correct = 0;
		int tot = 0;
		int known = 0;
		int corr2 = 0;
		int known3 = 0;
		int corr3 = 0;

		subpos = 0;
		for (int i = startpoint; i < worddata.size(); i++)
		{
			// Välj ut om detta är något av det vi skall tagga.
			if (worddata[i].verbatim)
			{
				int length = strlen(worddata[i].verbatim);
				//vector<scoredata> results;
				map<string, double> collapsed;
				bool part = false;

				// "Lista 1"
				map<string, char*>::iterator lista1;
				if ((lista1 = verygood[worddata[i].tag].find(worddata[i].verbatim)) != verygood[worddata[i].tag].end())
				{				
					collapsed[lista1->second] = -1;
					known++;
				}
				else
				{
					// "Lista 2"
					if (verygood[tagcount - 1].find(worddata[i].verbatim) != verygood[tagcount - 1].end())
					{										
						part = true;
						// 0.16
						collapsed[(verygood[tagcount - 1].find(worddata[i].verbatim))->second] = 0.13;
						known3++;
						//if (stricmp((verygood[tagcount - 1].find(worddata[i].verbatim))->second, worddata[i].stem) == 0) corr3++;
					}

					// Trie-algoritmen
					// Här med separata serier för med och utan hjälp för lista 2 (olika poängsättning kunde vara motiverad)
					// Fast nu är ju alla poängvärden lika.
					tries[worddata[i].tag].work(worddata[i].tag + tagcount / 2 * part, length, length, worddata[i].verbatim, collapsed, 1, "", 0.00000001);
				}

				// Gissar bäst som gissar sist!
				if (collapsed.size() == 0)
				{
					collapsed[worddata[i].verbatim] = 0;
				}

				for (map<string, double>::iterator t = collapsed.begin(); t != collapsed.end(); t++)
				{
					int base = 0;
					map<string, int>::iterator k;
					if ((k = backgood.find(t->first)) != backgood.end())
					{
						base = k->second;					
					}


					if (false && backwords[worddata[i].tag].find(t->first) != backwords[worddata[i].tag].end())
					{
						if (strcmp(backwords[worddata[i].tag][t->first], worddata[i].verbatim))
						{
							base /= 2;
						}
					}

					t->second *= 30 * base + 1;
				}

				map<string, double>::iterator j = collapsed.begin();
				for (map<string, double>::iterator i = collapsed.begin(); i != collapsed.end(); i++)
				{
					if (j->second < i->second)
					{
						j = i;
					}
				}

				// Återanvänd hittade lemman -- lemmpligt?
				if (j->second && false)
				{
					if (verygood[worddata[i].tag].find(worddata[i].verbatim) == verygood[worddata[i].tag].end())
					{
						backgood[j->first]++;
						int len = j->first.length();
						strcpy(curstem, j->first.c_str());

						verygood[worddata[i].tag][worddata[i].verbatim] = curstem;
						
						curstem += len;
						curstem++;

//						backwords[worddata[i].tag][j->first] = worddata[i].verbatim;
					}
				}

				printf("%s\t%s\n", worddata[i].verbatim, j->first.c_str());
			}
		}		
		// THE END
	}
}