// TextLine.h: interface for the CTextLine class.
//
//////////////////////////////////////////////////////////////////////

#ifndef _TEXTLINE_H__
#define _TEXTLINE_H__

#pragma warning(disable: 4786) 
#pragma warning(disable: 4503)
#pragma warning(disable: 4996)

#include "ConnectedComponents.h"
#include "Spaces.h"

#include <vector>
#include <set>
#include <algorithm>
using namespace std;
//#include "BMPFuncs.h"

#include <string.h>

#include "BaseCCElements.h"

#define SMALL_FXT_PNT_SHIFT 8

extern BOOL g_bCancelProcessing;

#define CHECK_CANCEL if(g_bCancelProcessing) {return;}

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class CLineCover : public CRect {
	int m_nHeight;
	vector<CPoint> m_vPoints;
	vector<int> m_vSpine;
	int m_nQuadErr;

public:
	CLineCover() : m_nHeight(0), m_nQuadErr(0) {
	}

	int GetSpineY(int nX)const{
		for(int i = 0; i < int(m_vSpine.size()) - 1; ++i){
			if(nX >= m_vPoints[i].x && nX <= m_vPoints[i + 1].x){
				int d = m_vPoints[i + 1].x - m_vPoints[i].x;
				float fC = (d == 0) ? 1.0f : (m_vPoints[i + 1].x - nX) / float(d);
				return int(m_vSpine[i] * fC + m_vSpine[ i + 1] * (1.0f - fC)); 
			}	
		}
		return 0;
	}

	void SetHeight(int nHeight){m_nHeight = nHeight;}

	CPoint Start()const{
		return CPoint(left, m_vSpine.front());
	}

	CPoint End()const{
		return CPoint(right, m_vSpine.back());
	}

	void Draw(IplImage *pImg, const char * color, bool bFill)const{
		if(left < 0 || left >= pImg->width || right < 0 || right >= pImg->width
			|| top < 0 || top >= pImg->height || bottom < 0 || bottom >= pImg->height)
			return;
		int nYStep = bFill ? pImg->widthStep : pImg->widthStep * (m_nHeight);
		int x = left;
		int nY = GetSpineY(x) - m_nHeight / 2;
		if(nY < 0) nY = 0;
		if(nY >= pImg->height - m_nHeight) nY = pImg->height - 1 - m_nHeight;
		char *pI = pImg->imageData + pImg->widthStep * nY + x * pImg->nChannels, *pIend;
		for(pIend = pI + pImg->widthStep * m_nHeight; pI <= pIend; pI += pImg->widthStep){
			memcpy(pI, color, pImg->nChannels);
		}
		for(; x < right; ++x){
			nY = GetSpineY(x) - m_nHeight / 2;
			if(nY < 0) nY = 0;
			if(nY >= pImg->height - m_nHeight) nY = pImg->height - 1 - m_nHeight;
			pI = pImg->imageData + pImg->widthStep * nY + x * pImg->nChannels;
			for(pIend = pI + pImg->widthStep * m_nHeight; pI <= pIend; pI += nYStep){
				memcpy(pI, color, pImg->nChannels);
			}
		}
		nY = GetSpineY(x) - m_nHeight / 2;
		if(nY < 0) nY = 0;
		if(nY >= pImg->height - m_nHeight) nY = pImg->height - 1 - m_nHeight;
		pI = pImg->imageData + pImg->widthStep * nY + x * pImg->nChannels;
		for(pIend = pI + pImg->widthStep * m_nHeight; pI <= pIend; pI += pImg->widthStep){
			memcpy(pI, color, pImg->nChannels);
		}
		for(UINT i = 0; i< m_vPoints.size(); ++i){
			int x = m_vPoints[i].x;// + CenterPoint().x;
			int y = m_vPoints[i].y;// + CenterPoint().y;
			cvRectangle(pImg, cvPoint(x-2, y-2), cvPoint(x+2, y+2), CV_RGB(255, 255, 255));
			if(m_vSpine.size() > 0){
				int sy = m_vSpine[i];// + CenterPoint().y;
				cvRectangle(pImg, cvPoint(x-2, sy-2), cvPoint(x+2, sy+2), CV_RGB(255,0, 0));
			}
		}
		
		for(x = left; x < right; ++x){
			nY = GetSpineY(x);
			if(nY < 0) nY = 0;
			if(nY >= pImg->height - m_nHeight) nY = pImg->height - 1 - m_nHeight;
			cvRectangle(pImg, cvPoint(x-1, nY-1), cvPoint(x+1, nY+1), CV_RGB(255, 0, 255));
		}
	}

	int CalcSpineBelow5(float fRegCoef) {
		m_vSpine.clear();
		int nPoints = m_vPoints.size();
		if(nPoints < 2 || nPoints > 4) return -1;
		if(nPoints == 2) {
			m_vSpine.push_back(m_vPoints[0].y);
			m_vSpine.push_back(m_vPoints[1].y);
			return m_nQuadErr = 0;
		}
		float **ppB = fmatrix(nPoints, 1);
		int i;
		for(i = 1; i <= nPoints; ++i) {
			ppB[i][1] = float(m_vPoints[i - 1].y);
		}
		float **ppM = fmatrix(nPoints, nPoints);
		ppM[1][1] = 1 + fRegCoef;
		ppM[1][2] = -2 * fRegCoef;
		ppM[1][3] = fRegCoef;
		if(nPoints > 3) {
			ppM[1][4] = 0;
		
			ppM[2][1] = -2 * fRegCoef;
			ppM[2][2] = 1 + 5 * fRegCoef;
			ppM[2][3] = -4 * fRegCoef;
			ppM[2][4] = fRegCoef;
	
			ppM[3][1] = fRegCoef;
			ppM[3][2] = -4 * fRegCoef;
			ppM[3][3] = 1 + 5 * fRegCoef;
			ppM[3][4] = -2 * fRegCoef;

			ppM[4][1] = 0;
			ppM[4][2] = fRegCoef;
			ppM[4][3] = -2 * fRegCoef;
			ppM[4][4] = 1 + fRegCoef;
		}
		else {
			ppM[2][1] = -2 * fRegCoef;
			ppM[2][2] = 1 + 4 * fRegCoef;
			ppM[2][3] = -2 * fRegCoef;

			ppM[3][1] = fRegCoef;
			ppM[3][2] = -2 * fRegCoef;
			ppM[3][3] = 1 + fRegCoef;
		}
		gaussj(ppM, nPoints, ppB, 1);
		float fQuadErr = 0;
		for(i = 1; i <= nPoints; ++i) {
			m_vSpine.push_back(int(ppB[i][1]));
			float fErr = float(m_vPoints[i - 1].y - ppB[i][1]);
			fQuadErr += fErr * fErr;
		}
		free_fmatrix(ppB, nPoints);
		free_fmatrix(ppM, nPoints);
		m_nQuadErr = int(fQuadErr / float(nPoints));
		return m_nQuadErr;
	}

	void Create(const CRect & bb, int nHeight, const vector<CPoint> & vPoints) {
		CopyRect(bb);
		m_nHeight = nHeight;
		m_vPoints.assign(vPoints.begin(), vPoints.end());
		float fRegCoef = 55.5f;
		int nPoints = m_vPoints.size();
		if(nPoints < 5){
			CalcSpineBelow5(fRegCoef);
			return;
		}
		int i;
		float *pB = new float[nPoints + 1];
		for(i = 1; i <= nPoints; ++i) {
			pB[i] = float(m_vPoints[i - 1].y);
		}
		float **ppM = fmatrix(nPoints, 5);
		ppM[1][1] = 0;
		ppM[1][2] = 0;
		ppM[1][3] = 1 + fRegCoef;
		ppM[1][4] = -2 * fRegCoef;
		ppM[1][5] = fRegCoef;

		ppM[2][1] = 0;
		ppM[2][2] = -2 * fRegCoef;
		ppM[2][3] = 1 + 5 * fRegCoef;
		ppM[2][4] = -4 * fRegCoef;
		ppM[2][5] = fRegCoef;

		for(int i = 3; i <= nPoints - 2; ++i) {
			ppM[i][1] = fRegCoef;
			ppM[i][2] = -4 * fRegCoef;
			ppM[i][3] = 1 + 6 * fRegCoef;
			ppM[i][4] = -4 * fRegCoef;
			ppM[i][5] = fRegCoef;
		}
		ppM[nPoints - 1][1] = fRegCoef;
		ppM[nPoints - 1][2] = -4 * fRegCoef;
		ppM[nPoints - 1][3] = 1 + 5 * fRegCoef;
		ppM[nPoints - 1][4] = -2 * fRegCoef;
		ppM[nPoints - 1][5] = 0;

		ppM[nPoints][1] = fRegCoef;
		ppM[nPoints][2] = -2 * fRegCoef;
		ppM[nPoints][3] = 1 + fRegCoef;
		ppM[nPoints][4] = 0;
		ppM[nPoints][5] = 0;
		float **al = fmatrix(nPoints, 2);
		unsigned long *indx = new unsigned long[nPoints + 1];
		float d;
		bandec(ppM, nPoints, 2, 2, al, indx, &d);
		banbks(ppM, nPoints, 2, 2, al, indx, pB);

		m_vSpine.clear();
		float fQuadErr = 0;
		for(i = 1; i <= nPoints; ++i) {
			m_vSpine.push_back(int(pB[i]));
			float fErr = float(m_vPoints[i - 1].y - pB[i]);
			fQuadErr += fErr * fErr;
		}
		m_nQuadErr = int(fQuadErr / float(nPoints)); 
		free_fmatrix(al, nPoints);
		delete [] indx;
		free_fmatrix(ppM, nPoints);
		delete [] pB;
	}
	
	int GetSpine(vector<CPoint> & vSpine) const {
		vSpine.clear();
		int nPoints = m_vPoints.back().x;
		for(int i = m_vPoints.front().x; i <= nPoints; i+=10){
			vSpine.push_back(CPoint(i, GetSpineY(i)));
		}
		return m_nQuadErr;
	}

	int GetQuadErr()const {
		return m_nQuadErr;
	}
};

#define PROJECT_BACK			0x1
#define IS_SALIENT				0x2
#define IS_EMBEDDED				0x4
#define IS_BOW					0x8
#define HAS_AMBIGUOUS_NEIGHBORS 0x10
#define IS_CLOSE_TO_SALIENT		0x20
#define IS_LONELY_NO_NEIGHBORS	0x40
#define IS_LONELY_BAD_NEIGHBORS	0x80

class CTextLines;

template <class T> 
struct CompareLefts{
	bool operator () (const T & a, const T & b) const {
		return a.left < b.left;
	}
};

template <class T> 
struct CompareTops{
	bool operator () (const T & a, const T & b) const {
		return a.top < b.top;
	}
};

typedef set<CBaseCCElement, CompareLefts<CBaseCCElement> > BaseElemSet;

class CTextLine : 
	public CRect
{
	UINT m_nFeatures;
	BaseElemSet m_setCC;
	set<int> m_rights, m_lefts, m_ups, m_downs, m_all;
	int m_nRightId, m_nLeftId;
	int m_nId, m_nRegionId;
	int m_nBlackPoints;
	int m_nGreyValSum;
	int m_nAvgBackGrnd;
	int m_nHeight, m_nHeightQuadStd, m_nMaxHeight, m_nCoverArea;
	vector<CRect> m_vCover;
	CRect RebuildBoundBox();
	CRect m_firstRect, m_lastRect;
	vector<CSpace *> m_vSpaces;
	vector<string> m_vTextWords;
	CLineCover m_cover;
	vector<CPoint> m_vSpine;
	int  m_nDistToClosestRightCC, m_nDistToClosestLeftCC;
	int m_nTotSpaces;
	void ClearSpaces();
	pair<int, int> *CreateEnvelop(int & nEnvSize)const;
	bool GetQuadStdForRightAndLeftPart(int nXDivider, int & nLeftHeight, int & nLeftQuadStd, int & nRightHeight, int & nRightQuadStd, int nMinPartCount2Height)const;

public:
	CTextLine();
	CTextLine(CConnectedComponent *pCC);
	virtual ~CTextLine();
	void Init(const CBaseCCElement & bccel);
	inline const CTextLine & operator = (const CRect & rect){
		left = rect.left; top = rect.top; right = rect.right; bottom = rect.bottom;
		return *this;
	}

	inline bool IsProjected()const{return GetFeature(PROJECT_BACK);}
	inline int GetHeight()const{return m_nHeight;}

	int GetSpine(vector<CPoint> & vSpine) const {
		return m_cover.GetSpine(vSpine);
	}

	bool CleanBelow(const CTextLines & textLines, int nClean2Not)const;
	
	CRect RebuildCover();
	void SetId(int nId);
	void SetProjectBack(bool bProjectBack){SetFeature(PROJECT_BACK, bProjectBack);}
	void Merge(CTextLine & textLine);
	bool OnTheSameLine(const CTextLine & textLine,  int nMaxDist2Height = 20) const;
	inline int GetId()const{return m_nId;}
	inline set<int> & GetRightNeighbors() { return m_rights; }
	inline set<int> & GetLeftNeighbors() { return m_lefts; }
	inline set<int> & GetUpNeighbors() { return m_ups; }
	inline set<int> & GetDownNeighbors() { return m_downs; }
	inline set<int> & GetAllNeighbors() { return m_all; }
	bool SetLeftNeighborId(CTextLines &textLines, int nDist2Height, bool bNoMatchChecking = false);
	bool SetRightNeighborId(CTextLines &textLines, int nDist2Height, bool bNoMatchChecking = false);
	inline int GetRightId()const{return m_nRightId;}
	inline int GetLeftId()const{return m_nLeftId;}
	inline void SetRightId(int nId){m_nRightId = nId;}
	inline void SetLeftId(int nId){m_nLeftId = nId;}
	inline bool VerticalyOverlaps(const CTextLine & tl)const{ return min((int)bottom, (int)tl.bottom) - max((int)top, (int)tl.top) > 0;} 
	inline int GetRegionId()const{return m_nRegionId;}
	inline void SetRegionId(int nRegionId){m_nRegionId = nRegionId;}
	const set<int> * GetUps()const{ return &m_ups;}
	const set<int> * GetDowns()const{ return &m_downs;}
	void ResetNeighbors(){m_nRightId = m_nLeftId = 0; m_rights.clear();m_lefts.clear(); m_ups.clear(); m_downs.clear(); /*m_touching.clear();*/}
	void GetSpaces(CSpaces & spaces);
	CTextLine  *SplitOnSpace(const CRect & space, int nRightId);
	CTextLine  *Split(int nDiv, int nRightId);
	CTextLine *SplitInconsistentLine(int nTolerance, int nMaxDiff2Height);
	void RemoveIroneousEndElements();
	int GetVerticalDistance(const CTextLine & tl, int &nMaxHeight)const;
	int GetBestInconsistentDivider(int nMinPartCount2Height, int nTolerance, int nMaxDiff2Height)const;
	const vector<CRect> & GetCover()const{return m_vCover;}
	bool CheckIfSalient()const;
	bool IsDeformed()const;
	inline void AddRightNeighbor(int nId){m_rights.insert(nId);}
	inline void AddLeftNeighbor(int nId){m_lefts.insert(nId);}
	inline void AddNeighbor(int nId){m_all.insert(nId);}
	inline void AddDownNeighbor(int nId){
		m_downs.insert(nId);
	}
	inline void AddUpNeighbor(int nId){
		m_ups.insert(nId);
	}
	inline CRect GetFirstRect()const{return m_firstRect;}
	inline CRect GetLastRect()const{return m_lastRect;}
	inline int size()const{return m_setCC.size();}

	inline void Add(const CBaseCCElement & bccel){
		if(m_setCC.empty()){
			Init(bccel);
		}
		else{
			m_setCC.insert(bccel);
			*this |= bccel;
			return;
		}
	}

	void Add(CBaseCCElement * pBCC, set<int> & setIds){
		if(pBCC->GetLineId() >= 0){
			if(pBCC->GetLineId() != m_nId){
				setIds.insert(pBCC->GetLineId());
			}
			return;
		}
		Add(*pBCC);
		pBCC->SetLineId(m_nId);
		if(pBCC->GetRightNeighbor() && !pBCC->GetRightNeighbor()->IsAmbiguous()){
			Add(pBCC->GetRightNeighbor(), setIds);
		}
		if(pBCC->GetLeftNeighbor() && !pBCC->GetLeftNeighbor()->IsAmbiguous()){
			Add(pBCC->GetLeftNeighbor(), setIds);
		}
	}

	inline int GetDistToLeftNeighbor(const CTextLines & tl) const;

	inline int GetDistToRightNeighbor(const CTextLines & tl) const;
	CRect CalcLastRect(const pair<int, int> *pEnv, int nEnvSize)const;
	CRect CalcFirstRect(const pair<int, int> *pEnv, int nEnvSize)const;
	void AddDownNeighbor(CTextLine *pTl, const CTextLines & tl);
	void AddUpNeighbor(CTextLine *pTl, const CTextLines & tl);

	inline void SetEmbedded(bool bEmbedded){
		SetFeature(IS_EMBEDDED, bEmbedded);
	}
	inline bool IsEmbedded()const{return GetFeature(IS_EMBEDDED);}
	bool BelongToSameMegaRegion(const CTextLine & tl)const;
	inline const CBaseCCElement  * GetFirstCC()const{return m_setCC.empty() ? NULL : &(*m_setCC.begin());}
	inline const CBaseCCElement * GetLastCC()const{return m_setCC.empty() ? NULL : &(*m_setCC.rbegin());}
	CPoint GetAverageSlope()const;
	inline bool GetBoW()const{return GetFeature(IS_BOW);}
	inline void SetBoW(bool bBoW){
		SetFeature(IS_BOW, bBoW);
	}
	bool IsMoreSalient(const CTextLine *pTl);

	void ProjectBack(int *pBp, int nWidth, int nHeight, int nId)const;
	void Draw(IplImage *img, const char * color, bool bFill)const{
		m_cover.Draw(img, color, bFill);
		BaseElemSet::const_iterator i, j;
		for(i = j = m_setCC.begin(); i != m_setCC.end(); ++i){
			++j;
			if(j != m_setCC.end()){
				cvLine(img, cvPoint(i->right, (i->top + i->bottom) / 2), 
					cvPoint(j->left, (j->top + j->bottom) / 2), CV_RGB(0, 0, 255));
			}
			cvRectangle(img, cvPoint(i->left, i->top), cvPoint(i->right, i->bottom), CV_RGB(0, 255, 0));
		}
		if(GetFeature(IS_LONELY_BAD_NEIGHBORS)) {
			cvLine(img, cvPoint(left, top), cvPoint(right, bottom), CV_RGB(255, 0, 0));
			cvLine(img, cvPoint(left, bottom), cvPoint(right, top), CV_RGB(255, 0, 0));
		}
		if(GetFeature(IS_LONELY_NO_NEIGHBORS)) {
			cvLine(img, cvPoint(left, top), cvPoint(right, bottom), CV_RGB(0, 0, 255));
			cvLine(img, cvPoint(left, bottom), cvPoint(right, top), CV_RGB(0, 0, 255));
		}
	}

	void Print(FILE *fp, const char *sDescription)const{
		if(strlen(sDescription) > 0){
			fprintf(fp, "%s\n", sDescription);
		}
		fprintf(fp, "Region id = %d\r\n", m_nRegionId);
		fprintf(fp, "right id = %d\r\n", m_nRightId);
		fprintf(fp, "left id = %d\r\n", m_nLeftId);
		BaseElemSet::const_iterator i, j;
		for(i = j = m_setCC.begin(); i != m_setCC.end(); ++i){
			++j;
			if(j != m_setCC.end()){
			fprintf(fp, "Line(0, 0, 255)\r\n");
			fprintf(fp, "x1 = %d\ty1 = %d\tx2 = %d\ty2 = %d\r\n", i->right, (i->top + i->bottom) / 2, 
				j->left, (j->top + j->bottom) / 2);
			}
			fprintf(fp, "Rectangle (0, 255, 0)\r\n");
			fprintf(fp, "left = %d\ttop = %d\tright = %d\tbottom = %d\r\n", i->left,  i->top, i->right, i->bottom);
		}
		if(HasAmbiguousNeighboirs() || (m_rights.empty() && m_lefts.empty())){
			if(HasAmbiguousNeighboirs()){
				fprintf(fp, "Cross(255, 0, 0)\r\n");
			}
			else{
				fprintf(fp, "Cross(0, 0, 255)\r\n");
			}
			fprintf(fp, "x1 = %d\ty1 = %d\tx2 = %d\ty2 = %d\r\n", left, top, right, bottom);
			fprintf(fp, "x1 = %d\ty1 = %d\tx2 = %d\ty2 = %d\r\n", left, bottom, right, top);
		}
	}

	void UpdateDistToClosestRightCC(int nDist);
	void UpdateDistToClosestLeftCC(int nDist);
	inline void SetHasAmbiguousNeighboirs(bool bHasAmbiguousNeighboirs){
		SetFeature(HAS_AMBIGUOUS_NEIGHBORS, bHasAmbiguousNeighboirs);
	}

	inline bool HasAmbiguousNeighboirs()const{
		return GetFeature(HAS_AMBIGUOUS_NEIGHBORS);
	}

	inline int GetTotSpacesLength()const{
		return 	m_nTotSpaces;
	}

	inline void SetSalient(bool bIsSalient){
		SetFeature(IS_SALIENT, bIsSalient);
	}

	inline bool IsSalient()const{
		return GetFeature(IS_SALIENT);
	}

	inline bool IsSalientOrClose()const{
		return (m_nFeatures & (IS_SALIENT | IS_CLOSE_TO_SALIENT) ) != 0;
	}
	inline void SetCloseToSalient(bool bCloseToSalient){
		SetFeature(IS_CLOSE_TO_SALIENT, bCloseToSalient);
	}
	inline bool IsCloseToSalient()const{
		return GetFeature(IS_CLOSE_TO_SALIENT);
	}

	int Overlap(const CTextLine *pTl){
		CRect intersect;
		intersect.IntersectRect(*this, *pTl);
		if(intersect.IsRectEmpty()){
			return 0;
		}
			
		BaseElemSet::const_iterator i, j;
		int nIntr = 0;	
		for(i = m_setCC.begin(); i != m_setCC.end(); ++i){
			for(j = pTl->m_setCC.begin(); j != pTl->m_setCC.end(); ++j){
					intersect.IntersectRect(*i, *j);
					if(!intersect.IsRectEmpty()){
						nIntr += intersect.Width() * intersect.Height();
					}
			}
		}
		return nIntr;
	}
				

	int GetArea()const{return m_nCoverArea;}
	void SetFirstSpaces(int nWidth){
		if(m_nDistToClosestLeftCC < 0 && m_nDistToClosestRightCC < 0){
			return;
		}
		int nHeight = Height();
		if(m_nDistToClosestLeftCC >= nHeight){
			int x = max(int(0), int(left - m_nDistToClosestLeftCC));  
			m_vSpaces.push_back(new CSpace(CRect(x, top, left, bottom), m_nId));
		}
		if(m_nDistToClosestLeftCC < 0){
			int x = max(int(0), int(left - nHeight * 3));  
			m_vSpaces.push_back(new CSpace(CRect(x, top, left, bottom), m_nId));//, true));
		}
		if(m_nDistToClosestRightCC >= nHeight){
			int x = min(int(nWidth - 1), int(right + m_nDistToClosestRightCC));  
			m_vSpaces.push_back(new CSpace(CRect(right, top, x, bottom), m_nId));
		}
		if(m_nDistToClosestRightCC < 0){
			int x = min(int(nWidth - 1), int(right + nHeight * 3));  
			m_vSpaces.push_back(new CSpace(CRect(right, top, x, bottom), m_nId));//, true));
		}
	}

	void GetBCCSpaces(int nWidth, const CBaseCCElement & bcc, CRect & leftSpace, CRect & rightSpace){
		leftSpace.SetRectEmpty();
		rightSpace.SetRectEmpty();
		int nHeight = bcc.Height();
		int nMaxD = nHeight * 3; 
		int nMaxLeftDist = min(bcc.GetMaxLeftDist(), nMaxD);
		int nMaxRightDist = min(bcc.GetMaxRightDist(), nMaxD);
		if(nMaxLeftDist < 0 && nMaxRightDist < 0){
			return;
		}
		if(nMaxLeftDist >= nHeight){
			int x = max(int(0), int(bcc.left - nMaxLeftDist));
			leftSpace.SetRect(x, bcc.top, bcc.left, bcc.bottom);
		}
		if(nMaxLeftDist < 0){
			int x = max(int(0), int(bcc.left - nHeight * 3));  
			leftSpace.SetRect(x, bcc.top, bcc.left, bcc.bottom);
		}
		if(nMaxRightDist >= nHeight){
			int x = min(int(nWidth - 1), int(bcc.right + nMaxRightDist));  
			rightSpace.SetRect(bcc.right, bcc.top, x, bcc.bottom);
		}
		if(nMaxRightDist < 0){
			int x = min(int(nWidth - 1), int(bcc.right + nHeight * 3));  
			rightSpace.SetRect(bcc.right, bcc.top, x, bcc.bottom);
		}

	}

	void SetSpaces(int nWidth){
		CRect leftSpace, rightSpace;
		for(BaseElemSet::iterator i = m_setCC.begin(); i != m_setCC.end(); ++i){
			GetBCCSpaces(nWidth, *i, leftSpace, rightSpace);
			if(leftSpace.Width() >= m_nHeight){
				if(!m_vSpaces.empty()){
					CRect ovlp;
					ovlp.IntersectRect(*m_vSpaces.back(), leftSpace);
					if(ovlp.IsRectEmpty()){
						m_vSpaces.push_back(new CSpace(leftSpace, m_nId));
					}
				}
				else{
						m_vSpaces.push_back(new CSpace(leftSpace, m_nId));
				}
			}
			if(rightSpace.Width() >= m_nHeight){
				m_vSpaces.push_back(new CSpace(rightSpace, m_nId));
			}
		}
	}

	const BaseElemSet & GetSetCC()const{
		return m_setCC;
	}

	void CopyWords(vector<CRect> & m_vOrigWords)const;
	const vector<string> & GetTextWords()const{return m_vTextWords;}

	inline void SetFeature(UINT nMask, bool bOn){
		if(bOn){
			m_nFeatures |= nMask;
		}
		else{
			m_nFeatures &= ~nMask;
		}
	}

	inline bool GetFeature(UINT nMask)const{return (nMask & m_nFeatures) != 0;}
	int CalcOverlapArea(const CTextLine & textLine) const;
	const vector<CPoint> & GetSpine() const {return m_vSpine;}
	vector<CPoint> & GetSpine() {return m_vSpine;}
	int GetAverageDistance(const CTextLine *pTl) const;
	int GetMinDistance(const CTextLine *pTl) const;
	int GetAvgBackGrnd() const { return m_nAvgBackGrnd;}
	int GetAvgGrey() const { 
		return (m_nBlackPoints > 0) ? m_nGreyValSum / m_nBlackPoints : 0;
	}
};

class IsTextLineAbove{
public:
	bool operator () (const CTextLine *pTL1,  const CTextLine *pTL2){
		if(pTL2 == NULL) return false;
		if(pTL1 == NULL) return true;
		return pTL1->top < pTL2->top;
	}
};

class IsWidth2HeightRatioHigher{
public:
	bool operator () (const CTextLine *pTL1,  const CTextLine *pTL2){
		if(pTL2 == NULL) return true;
		if(pTL1 == NULL) return false;
		return pTL1->Width() * pTL2->Height() > pTL2->Width() * pTL1->Height();
	}
};

int GetYinSegement(CPoint x0, CPoint x1, int nX);

inline bool IsLineInRegionBefore(const CTextLine *pL1, const CTextLine *pL2) {
	if(pL2 == NULL) return false;
	if(pL1 == NULL) return true;
	const vector<CPoint> & vSpine1(pL1->GetSpine()), & vSpine2(pL2->GetSpine());
	for(vector<CPoint>::const_iterator i = vSpine1.begin() + 1, j = vSpine2.begin() + 1;
		i != vSpine1.end() && j != vSpine2.end();) {
			if(min(i->x, j->x) > max((i-1)->x, (j-1)->x)) {
				int nX = (min(i->x, j->x) + max((i-1)->x, (j-1)->x)) / 2;
				return GetYinSegement(*(i-1), *i, nX) < GetYinSegement(*(j-1), *j, nX);
			}
			if(i->x < j->x) {
				++i;
			}
			else {
				++j;
			}
	}
	return pL1->top < pL2->top;
}

////////////////////////////////////////// CTectLines ////////////////////////////////////////////////////////////////////////
class CMegaRegions;

class CTextRegion : public CRect, public vector<CTextLine*> {
	int m_nId, m_nMegaRegionId;
	int m_nTotalHeight, m_nTotalCount;
	set<CTextRegion*> m_rights, m_lefts, m_ups, m_downs;
	set<int> m_overlaps;
	bool m_bIsEmbedded, m_bTouchingFrame;	
	set<const CTextRegion*> m_setOverlapingRegions;
	vector<CTextRegion*> * m_pRegions;
	CTextLines *m_pTextLines;
	int nMinLineDistFromFrame;
	bool m_bBoW;
public:

	CTextRegion(int nId, vector<CTextRegion*> *pRegions, CTextLines *pTextLines) : 
	  m_nId(nId), m_nMegaRegionId(-1), m_nTotalHeight(0), m_nTotalCount(0), m_bIsEmbedded(false),m_bTouchingFrame(false),
		  m_pRegions(pRegions), m_pTextLines(pTextLines){
		  SetRectEmpty();
		  nMinLineDistFromFrame = 0xffff;
		  m_bBoW = true;
	}
	inline void AddLeftNeighbor(CTextRegion* pR){
		m_lefts.insert(pR);
	}
	inline void AddRightNeighbor(CTextRegion* pR){
		m_rights.insert(pR);
	}
	inline void AddUpNeighbor(CTextRegion* pR){
		m_ups.insert(pR);
	}
	inline void AddDownNeighbor(CTextRegion* pR){
		m_downs.insert(pR);
	}

	inline set<CTextRegion*> & GetLeftNeighbors(){return m_lefts;}
	inline set<CTextRegion*> & GetRightNeighbors(){return m_rights;}
	inline set<CTextRegion*> & GetUpNeighbors(){return m_ups;}
	inline set<CTextRegion*> & GetDownNeighbors(){return m_downs;}


	inline const set<CTextRegion*> & GetLeftNeighbors()const{return m_lefts;}
	inline const set<CTextRegion*> & GetRightNeighbors()const{return m_rights;}
	inline const set<CTextRegion*> & GetUpNeighbors()const{return m_ups;}
	inline const set<CTextRegion*> & GetDownNeighbors()const{return m_downs;}

	inline void SetEmbedded(bool bIsEmbedded){m_bIsEmbedded = bIsEmbedded;} 
	inline bool IsEmbedded()const{return m_bIsEmbedded;} 

	inline void AddOverlapingRegion(CTextRegion* pRegion){
		m_setOverlapingRegions.insert(pRegion);
	}

	inline void ClearOverlapingRegion(){
		m_setOverlapingRegions.clear();
	}

	inline const set<const CTextRegion*>  & GetOverlapingRegions()const{return m_setOverlapingRegions;}

	void AddTextLine(CTextLine & tl){
		m_nTotalHeight += tl.GetHeight() * tl.size();
		m_nTotalCount += tl.size();
		(*this) |= tl;
		push_back(&tl);
	}
	
	bool RemoveTextLine(CTextLine & tl) {
		for(reverse_iterator i =  rbegin(); i != rend(); ++i) {
			if(*i && (*i)->GetId() == tl.GetId()) {
				(*i)->SetRegionId(0);
				(*i) = NULL;
				return true;
			}
		}
		return false;
	}

	bool Merge(CTextRegion & tr){
		if(GetBoW() != tr.GetBoW()) return false;
		if(tr.size() < 1 || tr.m_nId == m_nId) return false;
		m_nTotalHeight += tr.m_nTotalHeight;
		m_nTotalCount += tr.m_nTotalCount;
		(*this) |= tr;
		for(iterator i = tr.begin(); i !=  tr.end(); ++i){
			if(*i){
				(*i)->SetRegionId(m_nId);
				push_back(*i);
			}
		}
		tr.clear();
		tr.SetRectEmpty();
		return true;
	}

	void ClearAllNeighbors(){
		m_lefts.clear();
		m_rights.clear();
		m_ups.clear();
		m_downs.clear();
	}

	inline int GetHeight()const{return (m_nTotalCount > 0) ? (m_nTotalHeight / m_nTotalCount) : 0;}
	inline int GetId()const { return m_nId; }
	int GetDist2Line(const CTextLine & tl)const{
		int nMinDist = -1, nMaxWidth = 0;
		for(const_iterator i = begin(); i != end(); ++i){
			if(*i) {
				int nDist = (*i)->GetVerticalDistance(tl, nMaxWidth);
				if(nDist > 0 && (nMinDist < 0 || nMinDist > nDist)){
					nMinDist = nDist;
				}
			}
		}
		return nMinDist;
	}

	bool operator < (const CTextRegion & tr)const{
		if(IsVerticalySeparated(&tr) || YOverlap(*this, tr) > max(GetHeight(), tr.GetHeight()) * 3){
			return left < tr.left;
		}
		return top < tr.top;
	}
	
	void Sort(){sort(begin(), end(), IsLineInRegionBefore);}

	bool IsNarrowColumn()const{
		if(size() < 3) return false;
		int nH = GetHeight();
		int nCount  = 0;
		for(const_iterator i = begin(); i != end(); ++i){
			if(*i && (*i)->Height() * 3 > nH * 2 && nH * 3 > (*i)->Height()){
				++nCount;
			}
		}
		return nCount > int(max(int(3), int(size() / 2)));
	}

	bool IsSalient()const{
		int nSalientWidth = 0, nNotSalientWidth = 0;
		for(const_iterator i = begin(); i != end(); ++i){
			if(*i ){
				if((*i)->IsSalient()){
					nSalientWidth += (*i)->Width();
				}
				else{
					nNotSalientWidth += (*i)->Width();
				}
			}
		}
		return nSalientWidth >= nNotSalientWidth || IsNarrowColumn();
	}
	

	void SetId(int nId){
		m_nId = nId;
		for(iterator i = begin(); i != end(); ++i) if(*i)(*i)->SetRegionId(m_nId);
	}

	bool CheckIfOverlaped(const CTextRegion *pRegion)const{
		if(m_setOverlapingRegions.find(pRegion) != m_setOverlapingRegions.end()
			|| pRegion->m_setOverlapingRegions.find(this) != pRegion->m_setOverlapingRegions.end()){
				return true;
		}
		set<const CTextRegion *> setIntersection;
		set_intersection(m_setOverlapingRegions.begin(), m_setOverlapingRegions.end(), 
			pRegion->m_setOverlapingRegions.begin(), pRegion->m_setOverlapingRegions.end(), 
			insert_iterator<set<const CTextRegion * > >(setIntersection, setIntersection.begin()));
		int nTop = max(top, pRegion->top);
		int nBottom = min(bottom, pRegion->bottom);
		for(set<const CTextRegion *>::const_iterator i = setIntersection.begin(); i != setIntersection.end(); ++i){
			if(((*i)->top >= nBottom && (*i)->top <= nTop) || ((*i)->bottom >= nBottom && (*i)->bottom <= nTop)){
				return true;
			}
		}
		return false;
	}
	
	bool CheckIfOverlaped(int startTop, int startBottom, const CTextRegion *pEndRegion, set<const CTextRegion*> & alreadyChecked)const{
		if((top - startTop) * (top - pEndRegion->top) > 0 || (bottom - startBottom) * (bottom - pEndRegion->bottom) > 0 
			|| pEndRegion->bottom > top
			|| !alreadyChecked.insert(this).second){
			return false;
		}
		if(m_setOverlapingRegions.find(pEndRegion) == m_setOverlapingRegions.end()){
			for(set<const CTextRegion*>::const_iterator i = m_setOverlapingRegions.begin(); i != m_setOverlapingRegions.end(); ++i){
				if((*i)->bottom <= top 
					&& (*i)->CheckIfOverlaped(startTop, startBottom, pEndRegion, alreadyChecked)){
					return true;
				}
			}
		}
		else{
			return pEndRegion->bottom <= top;
		}
		return false;
	}

	bool IsVerticalySeparated(const CTextRegion *pRegion)const;

	void RebuildBoundBox(){
		SetRectEmpty();
		for(iterator i = begin(); i != end(); ++i) {
			if(*i){
				*this |= **i;
			}
		}
	}
	
	bool BelongToSameMegaRegion(const CTextRegion *pTr)const{
		if(pTr) {
			int nXovlp = XOverlap(*this, *pTr);
			int nH = GetHeight(), nH1 = pTr->GetHeight();
			int nMaxH = max(nH, nH1);
			if(nH * 3 < nH1 * 2 || nH1 * 3 < nH * 2) {
				return false;
			}
			int nYovlp = YOverlap(*this, *pTr);
			if(nXovlp * 3 >= min(Width(), pTr->Width()) * 2) {
				if(nYovlp >= -nMaxH * 3) {
					return true;
				}
			}
		}
		return false;
	}
			
	bool ShareCommonMegaRegion(const set<CTextRegion*> & set1, const set<CTextRegion*> & set2)const{
		set<CTextRegion*>::const_iterator i, j;
		for(i = set1.begin(); i != set1.end(); ++i){
			for(j = set2.begin(); j != set2.end(); ++j){
				if(*i && *j && (*i)->BelongToSameMegaRegion(*j)){
					return true;
				}
			}
		}
		return false;
	}

	void UndoIroneousEmbeddedRegion(){
		if(!m_bIsEmbedded) return;
		set<CTextRegion*>::const_iterator i;
		for(i = m_ups.begin(); i != m_ups.end(); ++i){
			if(*i && !(*i)->m_bIsEmbedded && BelongToSameMegaRegion(*i)){
				m_bIsEmbedded = false;
				return;
			}
		}
		for(i = m_downs.begin(); i != m_downs.end(); ++i){
			if(*i && !(*i)->m_bIsEmbedded && BelongToSameMegaRegion(*i)){
				m_bIsEmbedded = false;
				return;
			}
		}
	}

	bool CheckIfEmbedded(){
		int nCount = 0;
		if(ShareCommonMegaRegion(m_ups, m_lefts)) ++nCount;
		if(ShareCommonMegaRegion(m_ups, m_rights)) ++nCount;
		if(ShareCommonMegaRegion(m_downs, m_lefts)) ++nCount;
		if(ShareCommonMegaRegion(m_downs, m_rights)) ++nCount;
		return (m_bIsEmbedded = nCount >= 2);
	}

	int SalientSize()const{
		int nCount = 0;
		for(const_iterator i = begin(); i != end(); ++i){
			if(*i && (*i)->IsSalient()){
				++nCount;
			}
		}
		return nCount;
	}

	int NotNullSize()const{
		int nCount = 0;
		for(const_iterator i = begin(); i != end(); ++i){
			if(*i){
				++nCount;
			}
		}
		return nCount;
	}

	void MergeBrokenLines();
	void RebuildCover(){
		for(iterator i = begin(); i != end(); ++i){
			if(*i)(*i)->RebuildCover();
		}
	}
	
	inline bool IsProjected(){return true;}
	void AddOverlapingRegionId(int nId){m_overlaps.insert(nId);}
	inline set<int> & GetOverlapingRegionsIds(){return m_overlaps;}
	inline void ClearOverlapingRegionsIds(){m_overlaps.clear();}
	inline bool GetBoW()const {return m_bBoW;}
	inline void SetBoW(bool bBoW){m_bBoW = bBoW;}
	inline int GetMegaRegionId()const {return m_nMegaRegionId;}
	inline void SetMegaRegionId(int nId){m_nMegaRegionId = nId;}
	void MarkMegaRegions(CMegaRegions *pMegaRegions);
	inline void SetTouchingFrame(bool bTouchingFrame){m_bTouchingFrame = bTouchingFrame;}
	void FilterOverlapedNonSalientLines();
	void DeleteTextLines();
};

void SetOverlapedTexRegions(vector<CTextRegion*> & vRegions);
void SortRegions(vector<CTextRegion*> & vRegions);

class CMegaRegion : public CTextRegion{
	vector<CTextRegion*> m_vRegions;

public:
	void Add(CTextRegion *pTextRegion){
		m_vRegions.push_back(pTextRegion);
		UnionRect(*this, *pTextRegion);
	}

	void Add(CMegaRegion *pMr){
		for(vector<CTextRegion*>::const_iterator i = pMr->m_vRegions.begin(); i != pMr->m_vRegions.end(); ++i){
			if(*i){
				Add(*i);
			}
		}
	}
		
	CMegaRegion(int nId, vector<CTextRegion*> *pMegaRegions, CTextLines *pTextLines) : 
	CTextRegion(nId, pMegaRegions, pTextLines){
	}

	void Sort(){
		SortRegions(m_vRegions);
	}
	vector<CTextRegion*> & GetRegions(){return m_vRegions;}
	const vector<CTextRegion*> & GetRegions()const{return m_vRegions;}

};

class CMegaRegions : public vector<CMegaRegion*> {
	map<int, int> m_mapRegionToMegaRegion;
	vector<CTextRegion*> m_vMegaRegions;
	CTextLines *m_pTextLines;

	int MergeMegaRegions(int nId1, int nId2){
		if(nId1 == nId2) return nId1;
		int nMinId = min(nId1, nId2);
		int nMaxId = max(nId1, nId2);
		const CMegaRegion *pMr = at(nMaxId);
		for(vector<CTextRegion*>::const_iterator i = pMr->GetRegions().begin(); i != pMr->GetRegions().end(); ++i){
			if(*i){
				m_mapRegionToMegaRegion.erase((*i)->GetId());
				m_mapRegionToMegaRegion.insert(pair<int, int>((*i)->GetId(), nMinId));
			}
		}
		at(nMinId)->Add(at(nMaxId));
		delete at(nMaxId);
		at(nMaxId) = NULL;
		m_vMegaRegions[nMaxId] = NULL;
		return nMinId;
	}

public:
	vector<CTextRegion*> *GetMegaRegions(){return &m_vMegaRegions;}

	int Add(CTextRegion *pTr){
		if(!pTr) return -1;
		map<int, int>::iterator i = m_mapRegionToMegaRegion.find(pTr->GetId());
		if(i == m_mapRegionToMegaRegion.end()) {
			int nId = size();
			CMegaRegion *pMr = new CMegaRegion(nId, &m_vMegaRegions, m_pTextLines);
			pMr->Add(pTr);
			push_back(pMr);
			m_vMegaRegions.push_back(pMr);
			m_mapRegionToMegaRegion.insert(pair<int, int> (pTr->GetId(), nId));
			return nId;
		 }
		return i->second;
	}


	int MergeRegions(CTextRegion *pTr1, CTextRegion *pTr2){
		map<int, int>::iterator i1 = m_mapRegionToMegaRegion.find(pTr1->GetId());
		map<int, int>::iterator i2 = m_mapRegionToMegaRegion.find(pTr2->GetId());
		if(i1 == m_mapRegionToMegaRegion.end() && i1 == m_mapRegionToMegaRegion.end()){
			int nId = size();
			CMegaRegion *pMr = new CMegaRegion(nId, &m_vMegaRegions, m_pTextLines);
			pMr->Add(pTr1);
			pMr->Add(pTr2);
			push_back(pMr);
			m_vMegaRegions.push_back(pMr);
			m_mapRegionToMegaRegion.insert(pair<int, int> (pTr1->GetId(), nId));
			m_mapRegionToMegaRegion.insert(pair<int, int> (pTr2->GetId(), nId));
			return nId;
		}
		if(i1 == m_mapRegionToMegaRegion.end()){
			m_mapRegionToMegaRegion.insert(pair<int, int> (pTr1->GetId(), i2->second));
			at(i2->second)->Add(pTr1);
			return i2->second;
		}
		if(i2 == m_mapRegionToMegaRegion.end()){
			m_mapRegionToMegaRegion.insert(pair<int, int> (pTr2->GetId(), i1->second));
			at(i1->second)->Add(pTr2);
			return i1->second;
		}
		return MergeMegaRegions(i1->second, i2->second);
	}

	bool MergeOverlapedRegions(CTextRegion *pTr1, CTextRegion *pTr2){
		map<int, int>::iterator i1 = m_mapRegionToMegaRegion.find(pTr1->GetId());
		map<int, int>::iterator i2 = m_mapRegionToMegaRegion.find(pTr2->GetId());
		if(i1 == m_mapRegionToMegaRegion.end() || i2 == m_mapRegionToMegaRegion.end()
			|| i1->second == i2->second){
			return false;
		}
		CRect rect;
		if(rect.IntersectRect(*m_vMegaRegions[ i1->second], *m_vMegaRegions[i2->second])) {
			MergeMegaRegions(i1->second, i2->second);
			return true;
		}
		return false;
	}

	void Sort(){
		for(iterator i = begin(); i != end(); ++i){
			if(*i)(*i)->Sort();
		}
		SortRegions(m_vMegaRegions);
	}

	void GetRegions(vector<CTextRegion*> & vRegions){
		vRegions.clear();
		set<CTextRegion*> setRegions;
		for(vector<CTextRegion*>::iterator i = m_vMegaRegions.begin(); i != m_vMegaRegions.end(); ++i){
			if(*i){
				CMegaRegion *pMr = ((CMegaRegion*)(*i));
				vector<CTextRegion*>::iterator j;
				for(j = pMr->GetRegions().begin(); j != pMr->GetRegions().end(); ++j){
					if(*j && setRegions.find(*j) == setRegions.end()){
						vRegions.push_back(*j);
						setRegions.insert(*j);
					}
				}
			}
		}
	}

	void SetTextLines(CTextLines * pTextLines){
		m_pTextLines = pTextLines;
	}

	CMegaRegions(): m_pTextLines(NULL){}

	~CMegaRegions(){
		for(iterator i = begin(); i != end(); ++i){
			if(*i) delete *i;
		}
	}
};

class CTextLines : public vector<CTextLine *> {
	vector <CTextRegion*> m_vRegions;
	CMegaRegions m_megaRegions; 
	CSpaces m_spaces;
	vector <pair<int, Vertice> > m_vMapH, m_vMapV;
	set<CRect, CompareTops<CRect> > m_setHorizontalSeparators;

public:
	typedef void (CTextLines:: *ProccessRow)(multimap <int, Vertice>::const_iterator itLeft,
									   multimap <int, Vertice>::const_iterator itRight, const multimap <int, Vertice> & mapX2indx, 
									   void *pParams);
	CTextLines(UINT nReserve = 0);
	virtual ~CTextLines();
	void ProjectBack(int *pBp, int nWidth, int nHeight);
	void ProjectBackRegions(int *pBp, int nWidth, int nHeight);
	void ProjectBackRegions(int *pBp, int nWidth, int nHeight, bool bSalientOnly);
	void RebuildCover();
	void Add(CConnectedComponent *pCC);
	void Add(CTextLine *pTextLine);
	void FilterTouchingLines(int *pBp, int nScale, int nWidth, int nHeight, int nClean2Not, bool bProjectedOnly);
	void FilterTouchingLines(int nClean2Not, bool bProjectedOnly);
	void FilterTouchingLongLines(int nClean2Not, bool bProjectedOnly,  int nW2H, int nH2W);
	void FilterDeformedLines(bool bProjectedOnly);
	CTextLine *Merge(int nId1, int nId2);
	void MergeBrokenLines(int *pBp, int nWidth, int nHeight, int nScale, int nDist2Height = 5, bool bProjectedOnly = false);
	void MergeBrokenLines(bool bProjectedOnly = false);
	inline CTextLine *GetTextLine(int nIndx){ return (nIndx < 0 || nIndx >= (int)size()) ? NULL : at(nIndx);}
	inline const CTextLine *GetTextLine(int nIndx)const{ return (nIndx < 0 || nIndx >= (int)size()) ? NULL : at(nIndx);}
	void SetNeighborIds(const int *pBp, int nWidth, int nHeight, int nScale, int nDist2Height, bool bProjectedOnly = false, bool bNoMatchChecking = false);
	void SetNeighborIds(int nDist2Height, int nHeight2Ovlp, bool bNoMatchChecking = false);
	void SelectUnambiguousPairs();
	void SetToProjectUnambiguousPairs();
	bool MergeUnambiguousLines(bool bProjectedOnly = false);
	void SetTextRegions();
	void SetTextRegions(CTextLine *pFirstLine, CTextRegion  & firstRegion);
	void SetTextRegionsUp(CTextLine *pFirstLine, CTextRegion  & firstRegion);
	void SetTextRegionsDown(CTextLine *pFirstLine, CTextRegion  & firstRegion);
	const vector <CTextRegion*> *GetRegions()const{return & m_vRegions;} 
	vector <CTextRegion*> *GetRegions(){return & m_vRegions;} 
	void GetRegions(vector<CRect> & vRegions, bool bSalientOnly = false)const;
	void GetMegaRegions(vector<CRect> & vMegaRegions)const;
	void ResetNeighbors();
	void SetSpaces();
	CSpaces & GetSpaces();
	void SplitOnVerticalSeparators();
	void SplitInconsistentLines(int nTolerance, int nMaxDiff2Height);
	void MergeUnMatchedComponentsToTheNearestLine(int *pBp, int nWidth, int nHeight, int nScale, int nH2MxH, int nMxH2H, int nProjected, int nMaxWidth = -1,  bool bMerge = true);
	void SetToProjectLongSingleLines(int nMinHeight, int nMinWidth2Height, int nMinHeight2Width);
	void MergeHeavilyOverlapedRegions();
	void MergeOrphanLines();
	void SortRegions();
	void FilterNonSalientRegions();
	void Write(UCHAR *pSrc, int nSrcWidth, int nWidth, int nHeight, const char *sPrefix)const;
	void MergeCloseRegions();
	void SetToprojectSalientLines();
	void MergeComponentsUnderline(int *pBp, int nWidth, int nHeight, int nScale, int nH2MxH, int nMxH2H, int nProjected, int nMaxWidth = -1);
	void EraseTouchingLines(int *pBp, int nScale, int nWidth, int nHeight, int nClean2Not, bool bProjectedOnly);
	void EraseTouchingLines(int nClean2Not, bool bProjectedOnly);
	void ProjectShortLines(int *pBp, int nScale, int nWidth, int nHeight, int nW2H, int nH2W);
	void ProjectLongLines(int *pBp, int nScale, int nWidth, int nHeight, int nW2H, int nH2W);
	void EraseTouchingLongLines(int *pBp, int nScale, int nWidth, int nHeight, int nClean2Not, bool bProjectedOnly,  int nW2H, int nH2W);
	void EraseTouchingLongLines(int nClean2Not, bool bProjectedOnly,  int nW2H, int nH2W);
	int FindIntersectingWithHorizontalLine(int nX0, int nX1, int nY, vector<int> & vIds)const;
	void LookForLeftRightNeighbors(int nDist2Height,  int nHeight2Ovlp, bool bProjectedOnly = false);
	void LookForUpDownNeighbors(int nDist2Height/* * (1 << SMALL_FXT_PNT_SHIFT) */, bool bProjectedOnly = false, bool bSalientOnly = false);
	void BuildProjections();
	void LookForLeftNeighbors(CTextLine *pTl, multimap <int, Vertice>::const_iterator itRight, const multimap <int, Vertice> & mapX2indx, 
		int nDist2Height, int nHeight2Ovlp);
	void LookForRightNeighbors(CTextLine *pTl, multimap <int, Vertice>::const_iterator itLeft, const multimap <int, Vertice> & mapX2indx, 
		int nDist2Height, int nHeight2Ovlp);
	void LookForLeftRightNeighbors(multimap <int, Vertice>::const_iterator itLeft, 
		multimap <int, Vertice>::const_iterator itRight, const multimap <int, Vertice> & mapX2indx, void *pParams);
	
	void LookForUpNeighbors(CTextLine *pTl, multimap <int, Vertice>::const_iterator itBottom, int nDist2Height, const multimap <int, Vertice> & mapY2indx);
	void LookForDownNeighbors(CTextLine *pTl, multimap <int, Vertice>::const_iterator itTop, int nDist2Height, const multimap <int, Vertice> & mapY2indx);
	void LookForUpDownNeighbors(multimap <int, Vertice>::const_iterator itTop, 
		multimap <int, Vertice>::const_iterator itBottom, const multimap <int, Vertice> & mapY2indx, void *pParams);
	int GetCommonUpNeighbor(const set<int> & set1, const set<int> & set2);
	int GetCommonDownNeighbor(const set<int> & set1, const set<int> & set2);
	void SetSplitOnVerticalSeparators(bool bProjectedOnly, int nMinOrder);
	pair<int, int> LookForNeighborSpacesUp(multimap <int, Vertice>::iterator itBottom, multimap <int, Vertice> & mapY2indx, set<int> & setSpaces, CSpace **ppLastSpace);
	pair<int, int> LookForNeighborSpacesDown(multimap <int, Vertice>::iterator itTop, multimap <int, Vertice> & mapY2indx, set<int> & setSpaces, CSpace **ppLastSpace);
	void RebuildPositionMaps();
	void RebuildPositionMapsV();
	void AddToPositionMaps(const CRect & rect, int nId);
	void AddToPositionMapsV(const CRect & rect, int nId);
	void LookForMatchingLeftNeighbors(CTextLine *pTl, multimap <int, Vertice>::const_iterator itRight, const multimap <int, Vertice> & mapX2indx, 
											  int nDist2Height);
	void LookForMatchingRightNeighbors(CTextLine *pTl, multimap <int, Vertice>::const_iterator itRight, const multimap <int, Vertice> & mapX2indx, 
		int nDist2Height);
	
	void LookForMatchingLeftRightNeighbors( multimap <int, Vertice>::const_iterator itLeft,  multimap <int, Vertice>::const_iterator itRight, 
		const multimap <int, Vertice> & mapX2indx, void *pParams);

	void LookForMatchingLeftRightNeighbors(int nDist2Height, bool bProjectedOnly);
	void SetMatchedIds(bool bProjectedOnly);
	void AddElementsToMap(vector<MM_IT_PAIR> & vElemsToAdd, ProccessRow onAddElement, multimap <int, Vertice> & mapVal2indx, void *pParams);
	void DeleteElementsFromMap(vector<MM_IT_PAIR> & vElemsToErase, ProccessRow onDeleteElement, multimap <int, Vertice> & mapVal2indx, void *pParams);
	void AddLineToRegion(multimap <int, Vertice>::const_iterator itLeft,  multimap <int, Vertice>::const_iterator itRight, 
		const multimap <int, Vertice> & mapX2indx, void *pParams);
	bool IsAnyRegionOverlapedByRect(const CRect & rect, int nRegionIdToExclude, int nMaxOverLapArea)const;
	void GetRegionOverlapedByRect(const CRect & rect, int nMaxOverLapArea, set<int> & setOvlpdRegions)const;
	void CheckAddedLine(multimap <int, Vertice>::const_iterator itLeft,  multimap <int, Vertice>::const_iterator itRight,
		const multimap <int, Vertice> & mapX2indx, void *pParams);
	void AddSingleLineRegions();
	void MarkEmbeddedRegions();
	void SetRegionNeighbors();
	bool CheckIfNewOverlapedRegionsCreated(const CRect & r1, const CRect & r2, int nMinArea)const;
	int CalcNewOverlapedArea(const CRect & r1, const CRect & r2, bool bIgnoreOrphan = true)const;
	int CountValidNeighboirs(const set<int> & setIds)const;
	int CalcWhiteSeparatorWidth(const set<int> & setSpaces)const;
	void ConnectBrokenLinesWithinRegions();
	void FilterOverlapedNonSalientLines();
	int GetNumberOfRegions()const{return m_vRegions.size();}
	void RebuildPositionMapsForRegions();
	void SetRegionsLeftRightNeightbors();

	void IterateThroughRows(const vector<CTextLine*> & vElements, ProccessRow onAddElement, ProccessRow onDeleteElement, 
						bool bProjectedOnly, bool bSalientOnly, void *pParams);
	void IterateThroughRows(const vector<CTextRegion*> & vElements, ProccessRow onAddElement, ProccessRow onDeleteElement, 
						bool bProjectedOnly, bool bSalientOnly, void *pParams);

	void IterateThroughColumns(const vector<CTextLine*> & vElements, ProccessRow onAddElement, ProccessRow onDeleteElement, 
			bool bProjectedOnly, bool bSalientOnly, void *pParams);
	/*template <class T>
	void IterateThroughRows(const vector<T*> & vElements, ProccessRow onAddElement, ProccessRow onDeleteElement, 
							bool bProjectedOnly, bool bSalientOnly, void *pParams){
		multimap <int, Vertice> mapX2indx;
		vector<MM_IT_PAIR> vIndx2it(size()), vToAdd, vToErase;
		int nCurrPos = -1;
		for(vector<pair<int, Vertice> >::const_iterator i = m_vMapV.begin(); i != m_vMapV.end(); ++i){
			if(i->first > nCurrPos){
				AddElementsToMap(vToAdd, onAddElement, mapX2indx, pParams);
				vToAdd.clear();
				DeleteElementsFromMap(vToErase, onDeleteElement, mapX2indx, pParams);
				vToErase.clear();
				nCurrPos = i->first;
			}
			T *pEl = vElements[i->second.m_nId];
			if(*pEl && (!bProjectedOnly || pEl->IsProjected()) && (!bSalientOnly || pEl->IsSalient())){
				if(i->second.m_bStart){
					multimap <int, Vertice>::iterator it0 = mapX2indx.insert(pair<int, Vertice>(pEl->left, Vertice(pEl->GetId(), TRUE)));
					multimap <int, Vertice>::iterator it1 = mapX2indx.insert(pair<int, Vertice>(pEl->right, Vertice(pEl->GetId(), FALSE)));
					MM_IT_PAIR mmitp(it0, it1);
					vIndx2it[pEl->GetId()] = mmitp;
					vToAdd.push_back(mmitp);
				}
				else{
					MM_IT_PAIR mmitp = vIndx2it[pEl->GetId()];
					vToErase.push_back(mmitp);
				}
			}
		}
		AddElementsToMap(vToAdd, onAddElement,mapX2indx, pParams);
		DeleteElementsFromMap(vToErase, onDeleteElement, mapX2indx, pParams);
	}*/
	
	/*template <class T>
	void IterateThroughColumns(const vector<T*> & vElements, ProccessRow onAddElement, ProccessRow onDeleteElement, 
		bool bProjectedOnly, bool bSalientOnly, void *pParams){
		multimap <int, Vertice> mapY2indx;
		vector<MM_IT_PAIR> vIndx2it(size()), vToAdd, vToErase;
		int nCurrPos = -1;
		for(vector<pair<int, Vertice> >::const_iterator i = m_vMapH.begin(); i != m_vMapH.end(); ++i){
			if(i->first > nCurrPos){
				AddElementsToMap(vToAdd, onAddElement, mapY2indx, pParams);
				vToAdd.clear();
				DeleteElementsFromMap(vToErase, onDeleteElement, mapY2indx, pParams);
				vToErase.clear();
				nCurrPos = i->first;
			}
			T *pEl = vElements[i->second.m_nId];
			if(*pEl && (!bProjectedOnly || pEl->IsProjected()) && (!bSalientOnly || pEl->IsSalient())){
				if(i->second.m_bStart){
					multimap <int, Vertice>::iterator it0 = mapY2indx.insert(pair<int, Vertice>(pEl->top, Vertice(pEl->GetId(), TRUE)));
					multimap <int, Vertice>::iterator it1 = mapY2indx.insert(pair<int, Vertice>(pEl->bottom, Vertice(pEl->GetId(), FALSE)));
					MM_IT_PAIR mmitp(it0, it1);
					vIndx2it[pEl->GetId()] = mmitp;
					vToAdd.push_back(mmitp);
				}
				else{
					MM_IT_PAIR mmitp = vIndx2it[pEl->GetId()];
					vToErase.push_back(mmitp);
				}
			}
		}		
		AddElementsToMap(vToAdd, onAddElement,mapY2indx, pParams);
		DeleteElementsFromMap(vToErase, onDeleteElement, mapY2indx, pParams);
	}*/

	void FindOverlapedRegionsAdd(multimap <int, Vertice>::const_iterator itLeft,  multimap <int, Vertice>::const_iterator itRight, 
								  const multimap <int, Vertice> & mapX2indx, void *pParams);
	void FindOverlapedRegionsDelete(multimap <int, Vertice>::const_iterator itLeft,  multimap <int, Vertice>::const_iterator itRight, 
								  const multimap <int, Vertice> & mapX2indx, void *pParams);
	void FindOverlapedRegions();
	CPoint GetAverageSlope()const;
	void SetBoW(bool bBoW){
		for(iterator i = begin(); i != end(); ++i){
			if(*i)(*i)->SetBoW(bBoW);
		}
	}


	void CleanRightOvelapingWoB(CTextLine *pTl, multimap <int, Vertice>::const_iterator itLeft, const multimap <int, Vertice> & mapX2indx,  set<int> & idsToClean){ 
		for(multimap <int, Vertice>::const_iterator i = itLeft; i != mapX2indx.end(); ++i){
			CTextLine *pTln = GetTextLine(i->second.m_nId);
			if(pTl == pTln) continue;

			//if(pTl->GetBoW() != pTln->GetBoW()){
			int intArea = pTl->Overlap(pTln) * 3;
			int nMinArea = min(pTl->GetArea(), pTln->GetArea());
			if(intArea > nMinArea){
				if(pTl->IsMoreSalient(pTln)){
					idsToClean.insert(pTln->GetId());
				}
				else{
					idsToClean.insert(pTl->GetId());
				}
			}
			//}
		}
	}

	void CleanLeftOvelapingWoB(CTextLine *pTl, multimap <int, Vertice>::const_iterator itRight, const multimap <int, Vertice> & mapX2indx, set<int> & idsToClean){
		for(multimap <int, Vertice>::const_iterator i = itRight; ; --i){
			CTextLine *pTln = GetTextLine(i->second.m_nId);
			//if(pTl->GetBoW() != pTln->GetBoW()){
			if(pTl != pTln){
				int intArea = pTl->Overlap(pTln) * 3;
				int nMinArea = min(pTl->GetArea(), pTln->GetArea());
				if(intArea > nMinArea){
					if(pTl->IsMoreSalient(pTln)){
							idsToClean.insert(pTln->GetId());
					}
					else{
						idsToClean.insert(pTl->GetId());
					}
				}
			}
			//}
			if(i == mapX2indx.begin())
				return;
		}
	}

	void CleanOvelapingWoB(multimap <int, Vertice>::const_iterator itLeft,  multimap <int, Vertice>::const_iterator itRight, 
												   const multimap <int, Vertice> & mapX2indx, void *pParams){
		CTextLine *pTl = GetTextLine(itLeft->second.m_nId);
		 set<int> *pIdsToClean = (set<int> *)pParams;
		CleanLeftOvelapingWoB(pTl, itRight, mapX2indx, *pIdsToClean);
		CleanRightOvelapingWoB(pTl, itLeft, mapX2indx, *pIdsToClean);
	}

	void CleanOvelapingWoB(){
		set<int> idsToClean;
		IterateThroughRows(*this, &CTextLines::CleanOvelapingWoB, NULL, true, false, & idsToClean);	
		for(set<int>::const_iterator i = idsToClean.begin(); i != idsToClean.end(); ++i){
			GetTextLine(*i)->SetProjectBack(false);
		}
	}

	void ResetIds(){
		for(int i = 0; i < (int)size(); ++i){
			if(at(i))at(i)->SetId(i);
		}
	}

	void Draw(IplImage *img, const char * color, bool bFill, bool bSalientOnly = false)const{
		char invColor[3];
		invColor[0] = 255 - color[0];
		invColor[1] = 255 - color[1];
		invColor[2] = 255 - color[2];
		for(const_iterator i = begin(); i != end(); ++i){
			if(*i && (*i)->IsProjected()){
				if(bSalientOnly){
					if((*i)->IsSalient()){
						(*i)->Draw(img, color, bFill);
					}
					else if((*i)->IsCloseToSalient()){
						(*i)->Draw(img, invColor, true);
					}
				}
				else{
					(*i)->Draw(img, color, bFill);
				}
			}
		}
	}
	
	void Draw(const char *sFileName, int nWidth, int nHeight, bool bSalientOnly = false){
		IplImage *img = cvCreateImage( cvSize(nWidth, nHeight), 8, 3);
		memset(img->imageData, 0, img->imageSize); 
		char color[] = {char(0), char(255), char(255)};
		Draw(img, color, false, bSalientOnly);
		cvSaveImage(sFileName, img);
		cvReleaseImage(&img);
	}
	
	void Print(const char *sFileName, bool bSalientOnly = false)const{
		FILE *fp = fopen(sFileName, "wb");
		int cnt = 0;
		for(const_iterator i = begin(); i != end(); ++i){
			if(*i && (*i)->IsProjected()){
				fprintf(fp, "%d) ", cnt++);
				if(bSalientOnly){
					if((*i)->IsSalient()){
						(*i)->Print(fp, "Salient");
					}
					else if((*i)->IsCloseToSalient()){
						(*i)->Print(fp, "CloseToSalient");
					}
				}
				else{
					(*i)->Print(fp, "");
				}
			}
		}
		fprintf(fp, "Num of Regions = %d\r\n", m_vRegions.size());
		fprintf(fp, "Num of Mega Regions = %d\r\n", m_megaRegions.size());
		fclose(fp);
	}

	void LookForGoodLeftNeighbors(CTextLine *pTl, 
		multimap <int, Vertice>::const_iterator itRight, 
		const multimap <int, Vertice> & mapX2indx, 
		int nDist2Height);

	void LookForGoodRightNeighbors(CTextLine *pTl, 
		multimap <int, Vertice>::const_iterator itLeft, 
		const multimap <int, Vertice> & mapX2indx, 
		int nDist2Height);

	void LookForGoodLeftRightNeighbors(multimap <int, Vertice>::const_iterator itLeft,  
		multimap <int, Vertice>::const_iterator itRight, 
		const multimap <int, Vertice> & mapX2indx, void *pParams);

	void LookForGoodLeftRightNeighbors(int nDist2Height, bool bProjectedOnly);

	void AssembleGoodLines();
	void CleanGoodRightNeighbors(CTextLine *pTl);
	void CleanGoodLeftNeighbors(CTextLine *pTl);
	void CleanGoodNeighbors();
	void MergeRightNeighbors(CTextLine *pTl);
	void SetClosestRightGoodNeighbor(CTextLine *pTl);
	void SetClosestLeftGoodNeighbor(CTextLine *pTl);
	void SetClosestLeftRightGoodNeighbors();
	void CleanAmbiguousNeighboirs(CTextLine *pTl);
	void CleanAmbiguousNeighboirs();
	void MarkAmbiguousNeighboirs(int nDist2Height);
	void MarkAmbiguousNeighboirs(const set<int> &setIndexes, int nDist2Height);
	CTextLine * ChooseMostAmbiguousLine(CTextLine *pTl1, CTextLine *pTl2);
	void DeleteAmbiguousNeighboirs(set<int> & indexes);

	void LookForCloseToSalientLeftNeighbors(CTextLine *pTl, 
		multimap <int, Vertice>::const_iterator itRight, 
		const multimap <int, Vertice> & mapX2indx, 
		int nDist2Height);

	void LookForCloseToSalientRightNeighbors(CTextLine *pTl, 
		multimap <int, Vertice>::const_iterator itLeft, 
		const multimap <int, Vertice> & mapX2indx, 
		int nDist2Height);

	void LookForCloseToSalientLeftRightNeighbors(multimap <int, Vertice>::const_iterator itLeft,  
		multimap <int, Vertice>::const_iterator itRight, 
		const multimap <int, Vertice> & mapX2indx, void *pParams);

	void LookForCloseToSalientLeftRightNeighbors(int nDist2Height, bool bProjectedOnly);
		
	void LookForCloseToSalientUpNeighbors(CTextLine *pTl, multimap <int, Vertice>::const_iterator itBottom, int nDist2Height, const multimap <int, Vertice> & mapY2indx);
	void LookForCloseToSalientDownNeighbors(CTextLine *pTl, multimap <int, Vertice>::const_iterator itTop, int nDist2Height, const multimap <int, Vertice> & mapY2indx);
	void LookForCloseToSalientUpDownNeighbors(multimap <int, Vertice>::const_iterator itTop, 
		multimap <int, Vertice>::const_iterator itBottom, const multimap <int, Vertice> & mapY2indx, void *pParams);
	void LookForCloseToSalientUpDownNeighbors(int nDist2Height/* * (1 << SMALL_FXT_PNT_SHIFT) */, bool bProjectedOnly = false);
	void LookForCloseToSalientNeighbors(int nDist2Height, int nHDist2Height /* * (1 << SMALL_FXT_PNT_SHIFT) */);
	void FilterSalientAndClose();
	void SetFirstSpaces(int nWidth){
		for(iterator i = begin(); i != end(); ++i){
			if(*i){
				(*i)->SetFirstSpaces(nWidth);
			}
		}
	}
	void SetSpaces(int nWidth){
		for(iterator i = begin(); i != end(); ++i){
			if(*i){
				(*i)->SetSpaces(nWidth);
			}
		}
	}
	void MarkMegaRegions();
	void Add(CBaseCCElements & baseCCElements);
	void FindHorizontalSeparators(const vector<CTextRegion*> & vRegions, 
		set<CRect, CompareTops<CRect> > & setHorizontalSeparators)const;
	void FindHorizontalSeparators(int nWidth);
	BOOL CheckIfHorizontalySeparated(const CTextRegion *pTr1, const CTextRegion *pTr2)const;
	void CopyWords(vector<CRect> & m_vOrigWords)const;
	bool CheckSpaces(const CSpace *pSpace, const set<int> & setSpaces)const;
};

////////////////////////////////////////// CTextRegion ////////////////////////////////////////////////////////////////////////


#endif // _TEXTLINE_H__
