// ConectedComponents.h: interface for the CConectedComponents class.
//
//////////////////////////////////////////////////////////////////////

#ifndef __CONECTEDCOMPONENTS_H__
#define __CONECTEDCOMPONENTS_H__

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

#include "HoughTransform.h"
#include <deque>
#include <set>

using namespace std;

////////////////

struct CConnectedComponent{
	int m_nIndx;
	int m_nSize;
	int m_nValSum; // sum of the grey values of the component;
	int m_nAvgBackGrnd; // average of above and below lines grey values
	int left, right, top, bottom;
	BOOL m_bCurrent;
	CConnectedComponent *m_pEqCC;

	CConnectedComponent(){
		m_nIndx = -1;
		left = right = top = bottom = 0;
		m_nSize = m_nValSum = m_nAvgBackGrnd = 0;
		m_bCurrent = FALSE;
		m_pEqCC = NULL;
	}

	CConnectedComponent(const CConnectedComponent & cc){
		m_nIndx = cc.m_nIndx;
		left = cc.left;
		right = cc.right;
		top = cc.top;
		bottom = cc.bottom;
		m_nSize = cc.m_nSize;
		m_nValSum = cc.m_nValSum;
		m_pEqCC = cc.m_pEqCC;
	}

	void Set(int nIndx, int nVal, int nX, int nY){
		m_nIndx = nIndx;
		left = right = nX;
		top = bottom = nY;
		m_nSize = 1;
		m_nValSum = nVal;
		m_pEqCC = NULL;
	}

	CConnectedComponent *Add(int nVal, int nX, int nY){
		if(m_pEqCC){
			return  m_pEqCC = m_pEqCC->Add(nVal, nX, nY);
		}
		if(nX < left){
			left = nX;
		}
		else if(nX > right){
			right = nX;
		}
		if(nY < top){
			top = nY;
		}
		else if(nY > bottom){
			bottom = nY;
		}
		++m_nSize;
		m_nValSum += nVal;
		return this;
	}

	CConnectedComponent *Merge(CConnectedComponent *pCC){
		if(pCC == this){
			return this;
		}
		if(m_pEqCC){
			return m_pEqCC = m_pEqCC->Merge(pCC);
		}
		if(pCC->m_pEqCC){
			Merge(pCC->m_pEqCC);
			return pCC->m_pEqCC = this;
		}
		if(pCC->left < left) left = pCC->left;
		if(pCC->right > right) right = pCC->right;
		if(pCC->top < top) top = pCC->top;
		if(pCC->bottom > bottom) bottom = pCC->bottom;
		m_nSize += pCC->m_nSize;
		m_nValSum += pCC->m_nValSum;
		return pCC->m_pEqCC = this;
	}		

	int GetEndIndx()const{
		return m_pEqCC ? m_pEqCC->GetEndIndx() : m_nIndx;
	}

	CConnectedComponent *GetEndCC(){
		return m_pEqCC ? m_pEqCC->GetEndCC() : this;
	}

	void Draw(IplImage *pImg){
		cvRectangle(pImg, cvPoint(left, top), cvPoint(right, bottom), CV_RGB(255, 0, 255));
	}
};

class CConnectedComponents {
	set<int> m_setFreeCC;
	CConnectedComponent *m_pComponents;
	int m_nComponents;
	typedef CConnectedComponent* iterator;

public:
	iterator begin(){return m_pComponents;}
	iterator end(){return m_pComponents + m_nComponents;}

	CConnectedComponents(int nImgWidth){
		m_nComponents = 0;
		m_pComponents = new CConnectedComponent[nImgWidth / 2 + 1];
	}

	~CConnectedComponents(){
		if(m_pComponents){
			delete [] m_pComponents;
		}
	}

	CConnectedComponent *NewComponent(int nVal, int nX, int nY, const ImgRotationInfo &iri){
		int nIndx;
		if(m_setFreeCC.empty()){
			nIndx = m_nComponents++;
		}
		else{
			set<int>::iterator i = m_setFreeCC.begin();
			if(*i < m_nComponents){
				nIndx = *i;
				m_setFreeCC.erase(i);
			}
			else{
				m_setFreeCC.clear();
				nIndx = m_nComponents++;
			}
		}
		iri.ConvertOriginal2Rotated(nX, nY);
		m_pComponents[nIndx].Set(nIndx, nVal, nX, nY);
		return &m_pComponents[nIndx];
	}

	void AddToComponent(CConnectedComponent *pCC, int nVal, int nX, int nY, const ImgRotationInfo &iri){
		iri.ConvertOriginal2Rotated(nX, nY);
		pCC->Add(nVal, nX, nY);
	}

	CConnectedComponent *Merge(CConnectedComponent *pCC1, CConnectedComponent *pCC2){
		int nIndx1 = pCC1->GetEndIndx();
		int nIndx2 = pCC2->GetEndIndx();
		if(nIndx1 < nIndx2){
			return pCC1->Merge(pCC2);
		}
		if(nIndx1 > nIndx2){
			return pCC2->Merge(pCC1);
		}
		return pCC1->GetEndCC();
	}

	void Erase(CConnectedComponent *pCC){
		m_setFreeCC.insert(pCC->m_nIndx);
		pCC->m_nIndx = -1;
	}

	BOOL CheckCC(const CConnectedComponent *pCC, const UCHAR *p8bppImg, const ImgRotationInfo &iri, BOOL bBoW,
		int nMinHeight, int nMaxHeight, int nMinWidth, int nMaxWidth, int nMinThreshold){
			if(pCC->m_pEqCC){
				return FALSE;
			}
			int nW = pCC->right - pCC->left;
			int nH = pCC->bottom - pCC->top;
			if(nH < nMinHeight ||
				((nH > nMaxHeight || nW < nMinWidth || nW > nMaxWidth) && (nW > 500 || nW <= nH * 4))){
					return FALSE;
			}

			switch(bBoW){
			case TRUE:
				if(pCC->m_nAvgBackGrnd - pCC->m_nValSum / pCC->m_nSize < nMinThreshold) {
					return FALSE;
				}
				break;
			case FALSE:
				if(pCC->m_nValSum / pCC->m_nSize - pCC->m_nAvgBackGrnd < nMinThreshold) {
					return FALSE;
				}
				break;
			}
			return TRUE;
	}

	template <class T> 
	void Collect(const UCHAR *p8bppImg, const ImgRotationInfo &iri, BOOL bBoW,
		int nMinHeight, int nMaxHeight, int nMinWidth, int nMaxWidth, int nBverWThreshold,
		BOOL bAll, T & outputContainer){
			int nLastN = 0;
			CConnectedComponent *pCC, *pCCend;
			if(bAll){
				for(pCC = begin(), pCCend = end(); pCC < pCCend; ++pCC){
					if(pCC->m_nIndx >= 0){
						if(!pCC->m_bCurrent){
							pCC->m_nAvgBackGrnd	= iri.GetAvgTopAndBottom(p8bppImg, pCC);
							if(CheckCC(pCC, p8bppImg, iri, bBoW, 
								nMinHeight, nMaxHeight, nMinWidth, nMaxWidth, nBverWThreshold)){
								outputContainer.Add(pCC);
							}
							Erase(pCC);
						}
					}

				}
				return;
			}
			for(pCC = begin(), pCCend = end(); pCC < pCCend; ++pCC){
				if(pCC->m_nIndx >= 0){
					nLastN = pCC->m_nIndx;
					if(!pCC->m_bCurrent){
						if(!pCC->m_pEqCC){
							pCC->m_nAvgBackGrnd	= iri.GetAvgTopAndBottom(p8bppImg, pCC);
							if(CheckCC(pCC, p8bppImg, iri, bBoW, 
								nMinHeight, nMaxHeight, nMinWidth, nMaxWidth, nBverWThreshold)){
								outputContainer.Add(pCC);
							}
						}
						Erase(pCC);
					}
				}
			}
			m_nComponents = nLastN + 1;
			nLastN = 0;
			for(pCC = begin(), pCCend = end(); pCC < pCCend; ++pCC){
				if(pCC->m_nIndx >= 0){
					nLastN = pCC->m_nIndx;
					pCC->m_bCurrent = FALSE;
				}
			}
			m_nComponents = nLastN + 1;
	}

	void Draw(IplImage *pImg, int nMinHeight, int nMaxHeight, int nMinWidth, int nMaxWidth){
		for(iterator i = begin(); i != end(); ++i) {
			if(i->m_pEqCC) continue;
			int nW = i->right - i->left;
			int nH = i->bottom - i->top;
			if(nH >= nMinHeight && //nW * 3 >= nH &&
				((nH <= nMaxHeight && nW >= nMinWidth && nW <= nMaxWidth) || (nW <= 500 && nW > nH * 4))){
					i->Draw(pImg);
			}
		}
	}

	void Draw(const char *fileName, int nWidth, int nHeight){
		IplImage *pImg = cvCreateImage( cvSize(nWidth, nHeight), 8, 3);
		Draw(pImg, 6, 200, 2, 200);
		cvSaveImage(fileName, pImg);
		cvReleaseImage(&pImg);
	}
};

typedef CConnectedComponent * CCPtr;

void NextCcRow(const BYTE *p8bppImg, const BYTE *p1bppImg, 
			   int nWidth, int nY, 
			   CConnectedComponent **pPrevRow, 
			   CConnectedComponent **pCurrRow, 
			   const ImgRotationInfo &iri, CConnectedComponents & cc);

template <class T>
void FindConnectedComponents(const UCHAR *p8bppImg, const UCHAR *p1bppImg,
							 const ImgRotationInfo &iri, BOOL bBoW,
							 							 int nMinHeight, int nMaxHeight, int nMinWidth, int nMaxWidth, int nBverWThreshold,
							 T & outputContainer){
								 int nWidth = iri.nOrigWidth;
								 int nHeight = iri.nOrigHeight;
								 CConnectedComponents cc(nWidth);
								 const UCHAR *pOrigImg = p8bppImg;
								 CConnectedComponent **pPrevRow = new CCPtr[nWidth + 2];
								 CConnectedComponent **pCurrRow = new CCPtr[nWidth + 2];
								 memset(pPrevRow, NULL, sizeof(CCPtr) * (nWidth + 2));
								 int nRowSize = nWidth / 8;
								 for(int i=0; i<nHeight; ++i, p1bppImg += nRowSize, p8bppImg += nWidth){
									 if(g_bCancelProcessing) break;
									 NextCcRow(p8bppImg, p1bppImg, nWidth, i, pPrevRow, pCurrRow, iri, cc);
									 CConnectedComponent **pTmp = pPrevRow;
									 pPrevRow = pCurrRow;
									 pCurrRow = pTmp;
									 cc.Collect(pOrigImg, iri, bBoW, nMinHeight, nMaxHeight, nMinWidth, nMaxWidth, nBverWThreshold,
										 FALSE, outputContainer);
								 }
								 delete [] pCurrRow;
								 delete [] pPrevRow;
								 cc.Collect(pOrigImg, iri, bBoW, nMinHeight, nMaxHeight, nMinWidth, nMaxWidth, nBverWThreshold,
										 TRUE, outputContainer);
}


#endif // __CONECTEDCOMPONENTS_H__
