// StringMatch.cpp : Defines the entry point for the console application.
//

// #include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "malloc.h"
#include "ctype.h"
#include "assert.h"

#define D(x, y) d[((maxsize)*(x)) + (y)]

int chBuf1 = 'X';
int chBuf2 = 'X';
char szBuf[2048];
char szBufW[2048];

struct TOK
{
	unsigned iHash;
	char* szTok;
	char* szWhite;
};

#define EQUALTOKS(x, y) (((x).iHash == (y).iHash) && (0 == strcmp((x).szTok, (y).szTok)))

void ErrorExit()
{
	_flushall();
	exit(1);
}

void PrintTOK(TOK* pTok)
{
	printf("%s | %d \n", pTok->szTok, pTok->iHash);
}

void PrintTOKS(TOK* pTok1, TOK* pTok2)
{
	printf("%s | %d |", pTok1->szTok, pTok1->iHash);
	printf("%s | %d |", pTok2->szTok, pTok2->iHash);
}

void InitTOK(TOK* pTok)
{
	pTok->iHash = 0;
	pTok->szTok = 0;
	pTok->szWhite = 0;
}

unsigned HASH(char* p)
{
	unsigned ihash = 0;
	while (*p)
	{
		ihash = ((unsigned)(*p)) ^ (ihash << 7) ^ (ihash >> (32 - 7));
		++p;
	}
	return ihash;
}

void GetTok(int* pch, TOK* pTok, FILE* file)
{
	char* p = szBuf;
	char* pW = szBufW;

	*p = 0;
	*pW = 0;

	if (*pch == 0)
	{
		*pch = fgetc(file);
		while (isspace(*pch) && *pch != EOF)	// flush possible leading whitespace;
		{
			*pch = fgetc(file);
		}
	}
	while (!isspace(*pch) && *pch != EOF)// get non-white token
	{
		*p++ = *pch;
		*p = 0;
		*pch = fgetc(file);
	}
	while (isspace(*pch) && *pch != EOF)// get following white part
	{
		*pW++ = *pch;
		*pW = 0;
		*pch = fgetc(file);
	}

	if (pTok->szTok) free(pTok->szTok);
	if (pTok->szWhite) free(pTok->szWhite);

	pTok->szTok = (char*) malloc(1 + strlen(szBuf));
	strcpy(pTok->szTok, szBuf);

	pTok->szWhite = (char*) malloc(1 + strlen(szBufW));
	strcpy(pTok->szWhite, szBufW);

	pTok->iHash =  HASH(pTok->szTok);

//	PrintTOK(pTok);
}

void GetToks(int* pch, TOK* s, int maxsize, FILE* F1)
{
	++s;
	for (int i = 0; i < maxsize; ++i)
	{
		GetTok(pch, s+i, F1);
	}
}

void FreeTOK(TOK* t)
{
	if (t->szTok)
		free(t->szTok);

	t->szTok = 0;

	if (t->szWhite)
		free(t->szWhite);

	t->szWhite = 0;
}

void ShiftToks(TOK* s, int cTraceback, int maxsize)
{
	++s;
	int i, j;

	for (i = 0; i < cTraceback; ++i)
	{
		FreeTOK(s+i);
	}

	j = cTraceback;

	for (i = 0; i < (maxsize-cTraceback); ++i)
	{
		s[i] = s[j];
		++j;
	}

	for (i = (maxsize-cTraceback); i < maxsize; ++i)
	{
		InitTOK(s+i);
	}
}

void DumpTOKS(TOK* s, TOK* t, int maxsize)
{
	++s;
	++t;
	int i;

	for (i = 0; i < maxsize; ++i)
	{
		PrintTOK(s+i);
	}

	printf("\n");

	for (i = 0; i < maxsize; ++i)
	{
		PrintTOK(t+i);
	}

	fflush(stdout);

//	ErrorExit();
}

short min3(short i, short j, short k)
{
	int t = i;
	if (j < t) t = j;
	if (k < t) t = k;
	return t;
}


void LD(int maxsize, short* d, TOK* s, TOK* t)
{
	int m = maxsize;
	int n = maxsize;
	int i, j, k, iJunk;

	for (i = 0; i <= m; ++i)
		D(i, 0) = i;

	for (j = 0; j <= n; ++j)
		D(0, j) = j;

	for (j = 1; j <= n; ++j)
	{
		for (i = 1; i <= m; ++i)
		{
			if (EQUALTOKS(s[i],t[j]))
			{
				D(i, j) = D(i-1, j-1);
				iJunk = D(i, j);
			}
			else
			{
				k = min3  (
									D(i-1, j) + 1,	// deletion
									D(i, j-1) + 1,	// insertion
									D(i-1, j-1) + 1	// substitution
								);
				D(i, j) = k;
			}
		}
	}
}

void traceback(int maxsize, char* rg, short* d, int m, int n)
{
	char* p = rg;
	char* p2;
	
	int i = m;
	int j = n;

	char cT;

	while ((i > 0) && (j > 0))
	{
		int min;
		cT = 0;

	
		min = D(i-1, j-1);
		cT = 's';	// assume substitute

		if (D(i-1, j) < min)
		{
			min = D(i-1, j);
			cT = 'd';	// assume delete
		}
		else if (D(i, j-1) < min)
		{
			min = D(i, j-1);
			cT = 'i';	// insert
		}

		if (cT == 's' && (D(i-1, j-1) == D(i, j)))
		{		
			cT = 'e';	// emit, actually
		}

		*p++ = cT;
		*p = 0;

		if ((cT == 's') || (cT == 'e'))
		{
			i--;
			j--;
		}
		else if (cT == 'd')
		{
			i--;
		}
		else // t == i
		{
			j--;
		}
	}

	*p-- = 0;
	p2 = rg;

	// reverse string in place

	while (p2 < p)
	{
		cT = *p2;
		*p2 = *p;
		*p = cT;
		++p2;
		--p;
	}
}

int truncateTraceback(int maxsize, char* ptraceback)
{
	char* p;

	int truncatePoint = maxsize / 2;

	int cHits = 0;

	p = ptraceback;

	while (*p)
	{
		if (*p == 'e')
			++cHits;
		++p;
	}

	if (cHits < truncatePoint)
	{
		fprintf(stderr, "Too many errors while matching words -- lost syncronization, aborting -- try running again with a larger -w option value!\n");
		fprintf(stderr, "%s\n", ptraceback);
		ErrorExit();
	}

	p = ptraceback + truncatePoint;

	while (*p != 'e')
		--p;

	*p = 0;

	return p - ptraceback;
}

int strcpycount(char* p, char* sz, char* szWhite)
{
	int i, iW;
	i = strlen(sz);
	iW = strlen(szWhite);
	strcpy(p, sz);
	strcpy(p + i, szWhite);
	return i + iW;
}

int strcpyTok(char* p, TOK* t)
{
	return strcpycount(p, t->szTok, t->szWhite);
}

int strcpycountNoWhite(char* p, char* sz)
{
	int i;
	i = strlen(sz);
	strcpy(p, sz);
	return i;
}

int strcpyTokNoWhite(char* p, TOK* t)
{
	return strcpycountNoWhite(p, t->szTok);
}

void performEdit(char* pOutT, char* ptraceback, TOK* s, TOK* t, int* pcTraceback1, int* pcTraceback2)
{
	++s;
	++t;
	char c = 0;
	char cT = 0;
	int fOpen = 0;
	TOK* sT = s;
	TOK* tT = t;

	char* pOut = pOutT;

	while (c = *ptraceback++)
	{
		if (c == 'e') // emit
		{
//			assert(0 == strcmp(s->szTok, t->szTok));
			if (fOpen)
			{
				*pOut++ = '}';
				*pOut++ = ' ';
				*pOut = 0;
				fOpen = 0;
			}
			pOut += strcpyTok(pOut, s++);
			*pOut = 0;
			++t;

			cT = 'e';
		}
		else if (c == 's') // substitute
		{
			if (cT == 'e')
			{
				if (fOpen)
				{
					*pOut++ = '}';
					*pOut++ = ' ';
					*pOut = 0;
				}
				
				*pOut++ = '{';
				*pOut++ = ' ';
				*pOut = 0;
				fOpen = 1;
			}

			if (cT != 'd')
				pOut += strcpyTokNoWhite(pOut, t++);
			else
				pOut += strcpyTokNoWhite(pOut, s++);

			*pOut++ = ' ';
			*pOut++ = '|';
			*pOut++ = ' ';
			*pOut = 0;

			if (cT != 'd')
				pOut += strcpyTok(pOut, s++);
			else
				pOut += strcpyTok(pOut, t++);

			*pOut = 0;

			cT = 's';
		}
		else if (c == 'd') // delete
		{
			if (cT == 'e')
			{
				if (fOpen)
				{
					*pOut++ = '}';
					*pOut++ = ' ';
					*pOut = 0;
				}
			
				*pOut++ = '{';
				*pOut++ = ' ';
				*pOut = 0;
				fOpen = 1;
			}

			pOut += strcpyTok(pOut, s++);
			*pOut = 0;

			cT = 'd';
		}
		else if (c == 'i') // insert
		{
			if (cT == 'e')
			{
				if (fOpen)
				{
					*pOut++ = '}';
					*pOut++ = ' ';
					*pOut = 0;
				}
				
				*pOut++ = '{';
				*pOut++ = ' ';
				*pOut = 0;
				fOpen = 1;
			}

			pOut += strcpyTok(pOut, t++);
			*pOut = 0;

			cT = 'i';
		}
	}

	if (fOpen)
	{
		*pOut++ = '}';
		*pOut++ = ' ';
		*pOut = 0;
	}

	*pOut = 0;

	*pcTraceback1 = s - sT;
	*pcTraceback2 = t - tT;
}

int strcpyTokCloneWhite(char* p, TOK* s, TOK* t)
{
	return strcpycount(p, s->szTok, t->szWhite);
}

int strcpyJustCloneWhite(char* p, TOK* t)
{
	return strcpycount(p, "", t->szWhite);
}

// try to clone linebreaks and whitespace from File2 to File1
void performLinebreaks(char* pOutT, char* ptraceback, TOK* s, TOK* t, int* pcTraceback1, int* pcTraceback2)
{
	++s;
	++t;
	char c = 0;
	TOK* sT = s;
	TOK* tT = t;

	char* pOut = pOutT;

	while (c = *ptraceback++)
	{
		if (c == 'e') // emit
		{
			pOut += strcpyTokCloneWhite(pOut, s++, t++);
		}
		else if (c == 's') // substitute
		{
			pOut += strcpyTokCloneWhite(pOut, s++, t++);
		}
		else if (c == 'd') // delete
		{
			pOut += strcpyTok(pOut, s++);
		}
		else if (c == 'i') // insert
		{
			pOut += strcpyJustCloneWhite(pOut, t++);
		}
	}

	*pcTraceback1 = s - sT;
	*pcTraceback2 = t - tT;
}

char* szUsage = "pgdiff [options] inputFile1 inputFile2 > outputFile\n"
"\n"
"Attempts to find and display in curly braces word mismatches between\n"
"inputFile1 and inputFile2 while retaining the linebreaks of inputFile1 --\n"
"IE inputFile1 and inputFile2 DO NOT have to have corresponding lines of text\n"
"simply similar lists of words within their texts. The algorithm tends to be\n"
"relatively insensitive to differences in whitespace and linebreaks.\n"
"\n"
"options:\n"
"\n"
"-w ddddd -- set the approx. size of how many words in a row that\n"
"            can be mismatched before the algorithm gives up.\n"
"            note: running time of the algorithm is proportional\n"
"            to this number -- which can be slow if greater than about 10000\n"
"\n"
"-linebreaks -- suppresses display of mismatched words in the output\n"
"            and instead simply attempts to clone the linebreaks from\n"
"            inputFile2 to inputFile1. This is useful in attempting\n"
"            to recover the linebreaks of an original text when they\n"
"            have been lost in an previously editting OCR effort.\n"
"            The outputFile with recovered linebreaks can then be\n"
"            for example resubmitted to DP.\n";

void ShowUsage()
{
	fprintf(stderr, "%s", szUsage);
	ErrorExit();
}

int main(int argc, char *argv[])
{
	int i;
	int cloop = 0;
	int maxsize = 120;

	int cThrough = 0;

	int fLinebreaks = 0;

	if (argc < 3)
		ShowUsage();

	for (i = 1; i < argc-2; ++i)
	{
		if (0 == strcmp("-w", (const char*)argv[i]))
		{
			maxsize = (atoi((const char*)argv[i+1]));
			maxsize += 2;
		}
		
		if (0 == strcmp("-linebreaks", (const char*)argv[i]))
		{
			fLinebreaks = 1;
		}
	}

	if (maxsize < 30)
		maxsize = 30;

	if (maxsize > 10000)
	{
		fprintf(stderr, "Setting a -w parameter larger than 10,000 results in excessive run times\n");
		ErrorExit();
	}

	int cTraceback1 = maxsize;
	int cTraceback2 = maxsize;

	assert(maxsize < 100000);

	short* d = (short*) malloc(sizeof(short) * (maxsize+1) * (maxsize+1));

	assert(d);

	char* pOut = (char*) malloc(20*(maxsize + 1));

	assert(pOut);

	TOK* s = (TOK*) malloc(sizeof(TOK) * (maxsize+1));
	TOK* t = (TOK*) malloc(sizeof(TOK) * (maxsize+1));

	assert(s);
	assert(t);

	for (i = 0; i <= maxsize; ++i)
	{
		InitTOK(s+i);
		InitTOK(t+i);
	}

	FILE* F1 = fopen((const char*)argv[argc-2], "r");
	FILE* F2 = fopen((const char*)argv[argc-1], "r");

	if (!F1)
	{
		fprintf(stderr, "Couldn't open file named '%s'\n\n", argv[argc-2]);
		ShowUsage();
		ErrorExit();
	}

	if (!F2)
	{
		fprintf(stderr, "Couldn't open file named '%s'\n\n", argv[argc-1]);
		ShowUsage();
		ErrorExit();
	}
	

	char* ptraceback = (char*) malloc(3 + 2 * maxsize);

	while ( (++cThrough >= 0) && (!( (chBuf1 == EOF) && (chBuf2 == EOF) ) ) )
	{
		++cloop;

		GetToks(&chBuf1, s+maxsize-cTraceback1, cTraceback1, F1);
		GetToks(&chBuf2, t+maxsize-cTraceback2, cTraceback2, F2);

		LD(maxsize, d, s, t);

		traceback(maxsize, ptraceback, d, maxsize, maxsize);

		int iTruncatePoint;
		if ((chBuf1 != EOF) && (chBuf2 != EOF))
			iTruncatePoint = truncateTraceback(maxsize, ptraceback);
		else
			iTruncatePoint = strlen(ptraceback);

		if (iTruncatePoint < 0)
			DumpTOKS(s, t, maxsize);

		if (!fLinebreaks)
			performEdit(pOut, ptraceback, s, t, &cTraceback1, &cTraceback2);
		else
			performLinebreaks(pOut, ptraceback, s, t, &cTraceback1, &cTraceback2);

		printf("%s", pOut);

		ShiftToks(s, cTraceback1, maxsize);	
		ShiftToks(t, cTraceback2, maxsize);
	}

	return 0;
}