#include "TextMerger.h"
#include "Dictionary.h"
#include "PreprocFuncs.h"

WCHAR g_emptychar('\0');
PWCHAR CTextMerger::EMPTYPCHAR = &g_emptychar;

template <class T>
int GetLength(const T* pLine){
	if(sizeof(T) == 1){
		return (int)strlen((char*)pLine);
	}
	int n = 0;
	while(*pLine) { ++n; ++pLine;}
	return n;
}

int GetLineLength(const WCHAR *pLine){
	int n = 0;
	while(*pLine != '\n' && *pLine != '\r' && *pLine != '\0'){
		++pLine;
		++n;
	}
	return n;
}

const WCHAR *CopyLine(const WCHAR *pLine, TextContainer &dest){
	int n = GetLineLength(pLine);
	dest.SetSize(n + 1);
	memcpy(dest.m_pData, pLine, n);
	dest.m_pData[n] = '\0';
	return dest.m_pData;
}

const WCHAR *CopyLine(const WCHAR *pLine, WCHAR *pDest){
	int n = GetLineLength(pLine);
	memcpy(pDest, pLine, n);
	pDest[n] = '\0';
	return pDest;
}

template <class T>
const MatchTableElement  *FillMatchTable(MatchTable & matchTable,
								   const T *pLine0, const T *pLine1, int ( *Compare )(const void *a, const void *b, SHORT indx), 
								   int nInsertion, int nDeletion){
	int nLn0 = GetLength(pLine0);
	int nLn1 = GetLength(pLine1);
	int W = nLn1 + 1, H = nLn0 + 1;
	matchTable.SetSize(W, H);
	MatchTableElement *pMatchTable = matchTable.m_pData;
	int i,j;
	for(i=0; i<H; ++i){
		pMatchTable[i * W ].nVal = 0;
		pMatchTable[i * W ].nIndx = 0;
	}
	for(j=1; j<W; ++j){
		pMatchTable[j].nVal = 0;
		pMatchTable[j].nIndx = 0;
	}

	MatchTableElement *pM;
	SHORT tmp;
	int nIns, nDel;
	for(i=1; i<H; ++i){
		pM = pMatchTable + i * W + 1;
		nIns = (i == nLn0) ? 0 : nInsertion;
		for(j=1; j<W; ++j, ++pM){
			nDel = (j == nLn1) ? 0 : nDeletion;
			pM->nVal = pM[- W - 1].nVal + Compare(pLine0 + i - 1, pLine1 + j - 1, pM[- W - 1].nIndx);
			pM->nIndx = 0;
			if((tmp = pM[ -1 ].nVal + nIns) > pM->nVal){
				pM->nVal = tmp;
				pM->nIndx = 1;
			}
			if((tmp = pM[ -W ].nVal + nDel) > pM->nVal){
				pM->nVal = tmp;
				pM->nIndx = 2;
			}
		}
	}
	return pMatchTable;
}

template <class T>
void FlipSequence(T *pSeq){
	T tmp;
	T *pEnd = pSeq + GetLength(pSeq) - 1;
	while(pSeq < pEnd){
		tmp = *pSeq;
		*pSeq++ = *pEnd;
		*pEnd-- = tmp;
	}
}

template <class T>
int TraceMatchTableBack(const MatchTableElement *pMatchTable, const T *pLine0, const T *pLine1, T *pRes0, T *pRes1, T space = ' ', T end = '\0'){
	int i = GetLength(pLine0);
	int j = GetLength(pLine1);
	int W = j + 1;
		
	T *pR0 = pRes0, *pR1 = pRes1;
	const MatchTableElement *pM;

	int nRetVal = pMatchTable[i * W + j].nVal;
	while( i > 0 && j > 0){
		pM = pMatchTable + i * W + j;
		switch(pM->nIndx){
		case 0:
			*pR0++ = pLine0[--i];
			*pR1++ = pLine1[--j];
			break;
		case 1:
			*pR0++ = space;
			*pR1++ = pLine1[--j];
			break;
		case 2:
			*pR0++ = pLine0[--i];
			*pR1++ = space;
			break;
		}
	}
	
	while( i > 0){ 
		*pR0++ = pLine0[--i];
		*pR1++ = space;
	}
	while( j > 0){ 
		*pR0++ = space;
		*pR1++ = pLine1[--j];
	}
	
	*pR0 = end;
	*pR1 = end;

	FlipSequence(pRes0);
	FlipSequence(pRes1);
	return nRetVal;
}

int CompareChars(const void *a, const void *b, SHORT indx){
	if((*(char*)a) == (*(char*)b)){
		if(indx == 0){
			return 3;
		}
		return 2;
	}
	if((*(char*)a) == ' ' || (*(char*)b) == ' ')
		return -1;
	return -2;
}

int CompareLines(const void *a, const void *b, SHORT indx){
	TextContainer text0, text1;
	int nInsertion = -10, nDeletion  = -10;
	const WCHAR *pLine0 = CopyLine((*(PWCHAR*)a), text0);
	const WCHAR *pLine1 = CopyLine((*(PWCHAR*)b), text1);

	MatchTable matchTable;
	const MatchTableElement  *pMT = FillMatchTable(matchTable, pLine0, pLine1, CompareChars, nInsertion, nDeletion);
	int nLn0 = (int)wcslen((wchar_t*)pLine0);
	int nLn1 = (int)wcslen((wchar_t*)pLine1);
	int nRetVal = pMT[(nLn0 + 1) * (nLn1 + 1) - 1].nVal;
	if(indx == 0){
		return nRetVal * 2;
	}
	return nRetVal;// - 10;
}

CTextMerger::CTextMerger(int nMaxLines){
	m_nMaxLines = nMaxLines;
	m_pLines0 = new PWCHAR[m_nMaxLines];
	m_pLines1 = new PWCHAR[m_nMaxLines];
	m_pRes0 = new PWCHAR[m_nMaxLines * 2];
	m_pRes1 = new PWCHAR[m_nMaxLines * 2];
	
	m_pLine0 = new WCHAR[MAX_LINE_LENGTH];
	m_pLine1 = new WCHAR[MAX_LINE_LENGTH];
	m_pM0  = new WCHAR[MAX_LINE_LENGTH];
	m_pM1  = new WCHAR[MAX_LINE_LENGTH];
	m_pLine  = new WCHAR[MAX_LINE_LENGTH];
}

CTextMerger::~CTextMerger(){
	delete [] m_pLine; 
	
	delete [] m_pM1; 
	delete [] m_pM0;
	delete [] m_pLine1; 
	delete [] m_pLine0; 


	delete [] m_pRes1;
	delete [] m_pRes0;
	delete [] m_pLines1;
	delete [] m_pLines0;
}	


void CTextMerger::SetSize(int nMaxLines){
	if(nMaxLines <= m_nMaxLines){
		return;
	}
	m_nMaxLines = nMaxLines;
	delete [] m_pRes1;
	delete [] m_pRes0;
	delete [] m_pLines1;
	delete [] m_pLines0;
	m_pLines0 = new PWCHAR[m_nMaxLines];
	m_pLines1 = new PWCHAR[m_nMaxLines];
	m_pRes0 = new PWCHAR[m_nMaxLines * 2];
	m_pRes1 = new PWCHAR[m_nMaxLines * 2];
}

int CTextMerger::MatchLines(const WCHAR *pLine0, const WCHAR *pLine1, WCHAR *pRes0, WCHAR *pRes1, int nInsertion, int nDeletion){
	MatchTable matchTable;
	const MatchTableElement  *pMT = FillMatchTable(matchTable, pLine0, pLine1, CompareChars, nInsertion, nDeletion);
	int nRetVal = TraceMatchTableBack(pMT, pLine0, pLine1, pRes0, pRes1);
	return nRetVal;
}

const WCHAR *CTextMerger::GetMergedLines(const WCHAR *pLn0, const WCHAR *pLn1, Dictionary *pDict, int nInsertion, int nDeletion){
	CopyLine(pLn0, m_pLine0);
	CopyLine(pLn1, m_pLine1);
	MatchLines(m_pLine0, m_pLine1, m_pM0, m_pM1, nInsertion, nDeletion);
	if(pDict){
		WCHAR *pRes = pDict->MergeLines(m_pM0,  m_pM1, m_pLine);
		return pRes;
	}
	return MarkCorrectMatches(m_pM0,  m_pM1, m_pLine);
}

const WCHAR *CTextMerger::GetMergedText(PWCHAR *pLines0, PWCHAR *pLines1, Dictionary *pDict, int nInsertion, int nDeletion){
	int nLn0, nLn1, nNewLines0, nNewLines1;
	PWCHAR *pL = pLines0;
	while(*pL){
		if(*pL != EMPTYPCHAR){
			nLn0 = (int)wcslen((wchar_t*)*pL);
			nNewLines0 = CountNewLines(*pL);
			break;
		}
		++pL;
	}
	pL = pLines1;
	while(*pL){
		if(*pL != EMPTYPCHAR){
			nLn1 = (int)wcslen((wchar_t*)*pL);
			nNewLines1 = CountNewLines(*pL);
			break;
		}
		++pL;
	}
	m_text.SetSize(nLn0 + nLn1 + nNewLines0 * 2 + nNewLines1 * 2 + 1);
	WCHAR *pR = m_text.m_pData;
	int nLn = GetLength(pLines0);
	for(int i=0; i<nLn; ++i){
		if(pLines0[i] != EMPTYPCHAR && pLines1[i] != EMPTYPCHAR){
			const WCHAR *pLine = GetMergedLines(pLines0[i],  pLines1[i], pDict, nInsertion, nDeletion);
			int n = (int)wcslen((wchar_t*)pLine);
			memcpy(pR, pLine, n);
			pR += n;
			*pR++ = '\r';
			*pR++ = '\n';
		}
		WCHAR *pLn;
		if(pLines0[i] != EMPTYPCHAR && pLines1[i] == EMPTYPCHAR){
			pLn = pLines0[i];
			if(pDict){
				while(*pLn != '\n' && *pLn != '\0'){
					*pR++ = *pLn++;
				}
			}
			else{
				while(*pLn != '\n' && *pLn != '\0'){
					*pR++ = 'F';
					++pLn;
				}
			}
			*pR++ = '\r';
			*pR++ = '\n';
		}
		if(pLines0[i] == EMPTYPCHAR && pLines1[i] != EMPTYPCHAR){
			pLn = pLines1[i];
			if(pDict){
				while(*pLn != '\n' && *pLn != '\0'){
					*pR++ = *pLn++;
				}
			}
			else{
				while(*pLn != '\n' && *pLn != '\0'){
					++pLn;
				}
			}
			*pR++ = '\r';
			*pR++ = '\n';
		}
	}
	*pR = '\0';
	return 	m_text.m_pData;
}


PWCHAR *CTextMerger::GetLines(WCHAR *pText){
	int nNewLines = CountNewLines(pText);
	PWCHAR *pLines = new PWCHAR[nNewLines + 2];
	int n = 0;
	pLines[n++] = pText++;
	for(; *pText != '\0'; ++pText){
		if(pText[-1] == '\n'){
			pLines[n++] = pText;
		}
	}
	pLines[n] = NULL;
	return pLines;
}

const PWCHAR *CTextMerger::GetLines(WCHAR *pText, PWCHAR *pLines){
	int n = 0;
	pLines[n++] = pText;
	if(*pText != '\0'){
		for(++pText; *pText != '\0'; ++pText){
			if(pText[-1] == '\n'){
				pLines[n++] = pText;
			}
		}
	}
	pLines[n] = NULL;
	return pLines;
}

const WCHAR *CTextMerger::Merge(WCHAR *pText0, WCHAR *pText1, Dictionary *pDict, int nCharInsertion, int nCharDeletion){
	int nInsertion = -2, nDeletion = -2;
	int nLines0 = CountNewLines(pText0);
	int nLines1 = CountNewLines(pText1);
	SetSize(max(nLines0, nLines1) + 1);
	GetLines(pText0, m_pLines0);
	GetLines(pText1, m_pLines1);
	const MatchTableElement  *pMT = FillMatchTable(m_MatchTable, m_pLines0, m_pLines1, CompareLines, nInsertion, nDeletion);
	int nVal = TraceMatchTableBack(pMT, m_pLines0, m_pLines1, m_pRes0, m_pRes1, EMPTYPCHAR, (PWCHAR)NULL);
	const WCHAR *pNewText = GetMergedText(m_pRes0, m_pRes1, pDict, nCharInsertion, nCharDeletion);
	return pNewText;
}

int CTextMerger::GetMergeScore(WCHAR *pText0, WCHAR *pText1){
	int nInsertion = -2, nDeletion = -2;
	int nLines0 = CountNewLines(pText0);
	int nLines1 = CountNewLines(pText1);
	SetSize(max(nLines0, nLines1) + 1);
	GetLines(pText0, m_pLines0);
	GetLines(pText1, m_pLines1);
	const MatchTableElement  *pMT = FillMatchTable(m_MatchTable, m_pLines0, m_pLines1, CompareLines, nInsertion, nDeletion);
	return pMT[(GetLength(m_pLines0) + 1) * (GetLength(m_pLines1) + 1) - 1].nVal; 
}

WCHAR *CTextMerger::MarkCorrectMatches(const WCHAR *pLine, const WCHAR *pCorrectLine, WCHAR *pRes){
	int ln = int(wcslen((wchar_t*)pLine));
	if(!pRes){
		pRes = new WCHAR[ln];
	}
	WCHAR *pR = pRes;
	for(int i=0; i<ln; ++i){
		if(pLine[i] != ' ' ){
			if(pLine[i] == pCorrectLine[i]){
				*pR++ = 'T';
			}
			else{
				*pR++ = 'F';
			}
		}
	}
	*pR = '\0';
	return pRes;
}

const WCHAR *CTextMerger::MergeTheBestPair(WCHAR **ppTexts, int nTexts, int nThreshold, Dictionary *pDict, int &mi, int &mj){
	int val, mval = 0;
	mi = 0;
	mj = 1;
	for(int i=0; i<nTexts-1; ++i){
		for(int j=i+1; j<nTexts; ++j){
			if(ppTexts[i] && ppTexts[j]){
				if((val = GetMergeScore(ppTexts[i], ppTexts[j])) > mval){
					mval = val;
					mi = i;
					mj = j;
				}
			}
		}
	}
	if(mval < nThreshold){
		return NULL;
	}
	return Merge(ppTexts[mi], ppTexts[mj], pDict);
}


WCHAR *CTextMerger::OptimalMerge(WCHAR **ppTexts,  int nTexts, int nThreshold, Dictionary *pDict, BOOL *pNotOverlap){
	int mi, mj, mIndx = -1, i;
	const WCHAR *pText;
	for(i=0; i<nTexts; ++i)pNotOverlap[i] = TRUE;
	for(i=0; i<nTexts - 1; ++i){
		if((pText = MergeTheBestPair(ppTexts, nTexts, nThreshold, pDict, mi, mj)) == NULL){
			break;
		}
		mIndx = mi;
		delete [] ppTexts[mj];
		ppTexts[mj] = NULL;
		pNotOverlap[mj] = FALSE;
		if(wcslen((wchar_t*)ppTexts[mi]) < wcslen((wchar_t*)pText)){
			delete [] ppTexts[mi];
			ppTexts[mi] = new WCHAR[wcslen((wchar_t*)pText)+1];
		}
		wcscpy((wchar_t*)ppTexts[mi], (wchar_t*)pText);
	}
	if(mIndx < 0){
		//return NULL;
		mIndx = 0;
	}
	WCHAR *pMergedText = ppTexts[mIndx];
	ppTexts[mIndx] = NULL;
	pNotOverlap[mIndx] = FALSE;
	return pMergedText;
}
