cmpmngr.cpp

A File Comparer with visual output

//////////////////////////////////////////////////////////////////////
// CmpMngr.cpp: implementation of the CCmpMngr class.
//////////////////////////////////////////////////////////////////////

#include "CmpMngr.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////


CCmpMngr::CCmpMngr():LCSBitMatrix(1,1)
{

}

CCmpMngr::~CCmpMngr()
{

}

//////////////////////////////////////////////////////////////////////////////////////
// A utility function
//////////////////////////////////////////////////////////////////////////////////////
void myGetline(ifstream& ifs, std::string& s, char d = '\n' )
{   
 char getbuff[400];   
	
 ifs.getline(getbuff,400,d);
 s = std::string(getbuff);
}

std::string strReplace(std::string s,char *toFind, char* replaceWith)
{
	while (s.find(toFind,0) != std::string::npos) 
	{
			s.replace(s.find(toFind,0),1,std::string(replaceWith));
	}

	return s;
}

//////////////////////////////////////////////////////////////////////////////////////
//  Interface function for client, To be called after 'baseFile' & 'compFile' 
//  assigned with aexisting filename
//////////////////////////////////////////////////////////////////////////////////////
bool CCmpMngr::compare()
{
	ifstream base(baseFile.c_str());
	ifstream comp(compFile.c_str());
	//CFileException e;

   //match_pair diffmap;

	if ( (base.is_open()) &&
		 (comp.is_open())    )
	{
		// Read the file into vectors
		readInto(base,baseFileMap);
		readInto(comp,compFileMap);
		base.close();comp.close();
		// Hash the vectors
		hash(baseFileMap,baseHmap);hash(compFileMap,compHmap);
		compare_hashed_files(baseHmap,compHmap,match_pairs,std::string("LCS"));
	}
	else
	{
		//afxMessageBox(e.m_cause,MB_OK,0);ifstream
	}
	return true;
}

//////////////////////////////////////////////////////////////////////////////////////
//  Read line-by-line from a input stream and store into filemap
//////////////////////////////////////////////////////////////////////////////////////
bool CCmpMngr::readInto(ifstream &file, filemap &f)
{
 std::string s;
 int lineNo;

	lineNo = 1;
	do
	{			
		myGetline(file,s,'\n');
		f.push_back(line (lineNo,s));
		lineNo++;
	}while(!file.eof());

	return true;
}

bool CCmpMngr::sort(filemap &fm)
{	
	// Yet to beimplemented
	return false;
}

//////////////////////////////////////////////////////////////////////////////////////
//  Hash each line into a numeric value
//////////////////////////////////////////////////////////////////////////////////////
bool CCmpMngr::hash(filemap &f, hashed_filemap &hf)
{
 hashed_line hl;
 std::string toBeHashed;
 
	for (int i=0 ; i <= (f.size()-1); i++)
	{
		hl.first = f[i].first;
		toBeHashed = f[i].second;
		toBeHashed = strReplace(toBeHashed," ","");// Ignaore Space
		hl.second = hash_string(toBeHashed);	
		hf.push_back(hl);
	}
	return false;
}

//////////////////////////////////////////////////////////////////////////////////////
// Implementation of Hashing for a single line of text
// simple hashing
// hash_string(ABCW) = 65*1 + 66*2 + 67*3 + 87*4
//                   = 65 + 132 + 201 + 348
//						   = 746
// Please note....     
// hash_string(ABCW) != hash_string(AWBC)
// because..
// 65*1 + 66*2 + 67*3 + 87*4  != 65*1 + 87*2 + 66*3 + 67*4	
//////////////////////////////////////////////////////////////////////////////////////
int CCmpMngr::hash_string(std::string &s)
{
	int value,len;

	value = 0;len = s.length()-1;
	for (int i=0;i<=len;i++)
	{
		value = value + (s[i] * (i+1));
	}
	return value;
}

//////////////////////////////////////////////////////////////////////////////////////
//  Select the desired comparison algorithm.
//////////////////////////////////////////////////////////////////////////////////////
bool CCmpMngr::compare_hashed_files(hashed_filemap &bHm,hashed_filemap& cHm,match& dHm,std::string theAlgorithm)
{	
	std::string alg(theAlgorithm);

	if (alg == "LCS") 
	{
		return compare_hashed_files_LCS(bHm, cHm, dHm);
	}
	else 	
		return compare_hashed_files_default(bHm, cHm, dHm);
}

//////////////////////////////////////////////////////////////////////////////////////
// Following routine implements LCS algorithm to find difference between two files. //
// LCS stands for Longest Common Sequence, It is a linear space algorithm for       //
// computing maximal common subsequences.                                           //
// more info on LCS (with practical demonstration)                                  //
//    http://www.ics.uci.edu/~eppstein/161/960229.html                              //
// Dan Hirschberg's Publications on LCS                                             //  
//    http://www.ics.uci.edu/~dan/topic.html#lcs                                    //
//////////////////////////////////////////////////////////////////////////////////////
bool CCmpMngr::compare_hashed_files_LCS(hashed_filemap &bHm,hashed_filemap& cHm,match& dHm)
{	
	int i,j,k,m,n;	
	m = bHm.size(); n= cHm.size();
	LCSBitMatrix.resizeTo(m+2,n+2);
	std::vector<int> ci,ci1;
 
	nRange = n * m;
	nProgress = 0;
	ci.resize(n+2,0);ci1.resize(n+2,0);
	for (i=0;i<=n;i++) {ci[i]=0;ci1[i]=0;}

	// Prepare LCS matrix
	for (i = m; i >= 0; i--)
	{		
		for (k=0;k<=n;k++) {ci1[k]=ci[k];} 
		for (k=0;k<=n;k++) {ci[k]=0;}
	    for (j = n; j >= 0; j--)
	    {
			//if (bHm[i].second == 0 || cHm[j].second == 0) // beyond end
			//	LCSMatrix(i,j) = 0;
			//else 
			{	
				nProgress++;	
				if (bHm[i].second == cHm[j].second)
				{					
					//LCSMatrix(i,j) = 1 + LCSMatrix(i+1, j+1);
					ci[j] = 1 + ci1[j+1];
				}
				else 
				{
					//LCSMatrix(i,j) = max(LCSMatrix(i+1, j), LCSMatrix(i, j+1));
					if (ci1[j] > ci[j+1])
					{
						LCSBitMatrix.put(i,j,true);
						//LCSMatrix(i,j) = LCSMatrix(i+1, j);
						ci[j] = ci1[j];
					}
					else
					{
						LCSBitMatrix.put(i,j,false);
						//LCSMatrix(i,j) = LCSMatrix(i, j+1);
						ci[j] = ci[j+1];
					}
				}				
								
				/* Same above done with huuuuge 2D array LCSMatrix.
				if (bHm[i].second == cHm[j].second)
				{
					LCSMatrix(i,j) = 1 + LCSMatrix(i+1, j+1);
				}
				else 
				{
					//LCSMatrix(i,j) = max(LCSMatrix(i+1, j), LCSMatrix(i, j+1));
					if (LCSMatrix(i+1, j) > LCSMatrix(i, j+1))
					{
						LCSBitMatrix.put(i,j,true);
						LCSMatrix(i,j) = LCSMatrix(i+1, j);
					}
					else
					{
						LCSBitMatrix.put(i,j,false);
						LCSMatrix(i,j) = LCSMatrix(i, j+1);
					}
				}
				*/
			}
	    }
	}	

                                                              
	dHm.empty();
    i = 0;j = 0;
	// Following link walks through the bitmatrix we created by the loop above
	// and produces a LCS, A LCS here is a 
    while (i < m && j < n)
    {
		if (bHm[i].second == cHm[j].second)
		{
			dHm.push_back(match_pair (i,j)); // A pair match added to LCS.
			i++; j++;
		}
		else 
		{
			// In case we were using that Huuuuge 2D array, The condition would
			// will be like below 			
			// if (LCSMatrix(i+1,j) >= LCSMatrix(i,j+1)) 
			if (LCSBitMatrix.get(i,j) == true) 
				i++;
			else
				j++;
		}
    }
	//print_diff_in_HTML(std::string(""));
	return true;
}

//////////////////////////////////////////////////////////////////////////////////////
// This routine does a blind comparison of two files                                //
//////////////////////////////////////////////////////////////////////////////////////
bool CCmpMngr::compare_hashed_files_default(hashed_filemap &bHm,hashed_filemap& cHm,match& dHm)
{	
	hashed_filemapIt i,j,start,last_match;
	int compValue;	
	int ordi,ordj,start_ordj,last_match_orj,z;
	//hashed_line hl;

	//AfxMessageBox("Comparing",MB_OK,0);
	ofstream ofs("out.txt");

	start = cHm.begin();start_ordj = 0;
	last_match = cHm.begin();last_match_orj = 0;