#ifndef __RECT_ELEMENT_MAPPING__
#define __RECT_ELEMENT_MAPPING__

#include <vector>
#include <map>
#include <algorithm>

#include "ChipMonkTypes.h"

using namespace std;

extern BOOL g_bCancelProcessing;

template <class T>
inline int XOverlap(const T &r1, const T &r2){
	return min(int(r1.right), int(r2.right)) - max(int(r1.left), int(r2.left));
}

template <class T>
int YOverlap(const T &r1, const T &r2){
	return min(int(r1.bottom), int(r2.bottom)) - max(int(r1.top), int(r2.top));
}

struct Vertice{
	int m_nId; 
	BOOL m_bStart;
	Vertice(int nId = -1, BOOL bStart = -1) : m_nId(nId), m_bStart(bStart){}
};

typedef pair<int, Vertice> PositionMapNode;
typedef vector<PositionMapNode> PositionMap;

template <class T>
void AddToPositionMapsV(PositionMap & vMapV, const T * pRect, int nId){
	vMapV.push_back(PositionMapNode(pRect->top, Vertice(nId, TRUE)));
	vMapV.push_back(PositionMapNode(pRect->bottom, Vertice(nId, FALSE)));
}

template <class T>
void AddToPositionMapsH(PositionMap & vMapH, const T * pRect, int nId){
	vMapH.push_back(PositionMapNode(pRect->left, Vertice(nId, TRUE)));
	vMapH.push_back(PositionMapNode(pRect->right, Vertice(nId, FALSE)));
}

inline bool CompPositionMapNode(const PositionMapNode &p1, const PositionMapNode &p2){
	return p1.first < p2.first;
}

template <class T>
void BuildPositionMapV(PositionMap & vMapV, const T & elements){
	vMapV.clear();
	vMapV.reserve(elements.size() * 2);
	for(typename T::const_iterator i = elements.begin(); i != elements.end(); ++i){
		if(g_bCancelProcessing) return;
		if(*i){
			AddToPositionMapsV(vMapV, *i, (*i)->GetId());
		}
	}
	sort(vMapV.begin(), vMapV.end(), CompPositionMapNode);
}

template <class T>
void BuildPositionMapH(PositionMap & vMapH, const T & elements){
	vMapH.clear();
	vMapH.reserve(elements.size() * 2);
	for(typename T::const_iterator i = elements.begin(); i != elements.end(); ++i){
		if(g_bCancelProcessing) return;
		if(*i){
			AddToPositionMapsH(vMapH, *i, (*i)->GetId());
		}
	}
	sort(vMapH.begin(), vMapH.end(), CompPositionMapNode);
}

inline int GetArea(const CRect & rect){return rect.Width() * rect.Height();}

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

typedef pair<multimap <int, Vertice>::iterator, multimap <int, Vertice>::iterator> MM_IT_PAIR;

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);


template <class T>
void IterateThroughRows(const vector<T*> & vElements, ProccessRow onAddElement, ProccessRow onDeleteElement, 
						void *pParams, const PositionMap *pMapV = NULL){
							const PositionMap *pPMV;
							PositionMap *pM = NULL;
							if(pMapV){
								pPMV = pMapV;
							}
							else{
								pM = new PositionMap;
								BuildPositionMapV(*pM, vElements);
								pPMV = pM;
							}
							multimap <int, Vertice> mapX2indx;
							vector<MM_IT_PAIR> vIndx2it(vElements.size()), vToAdd, vToErase;
							int nCurrPos = -1;
							for(PositionMap::const_iterator i = pPMV->begin(); i != pPMV->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){
									if(i->second.m_bStart){
										multimap <int, Vertice>::iterator it0 = mapX2indx.insert(PositionMapNode(pEl->left, Vertice(pEl->GetId(), TRUE)));
										multimap <int, Vertice>::iterator it1 = mapX2indx.insert(PositionMapNode(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);
							if(!pMapV) delete pM;
}

template <class T>
void IterateThroughColumns(const vector<T*> & vElements, ProccessRow onAddElement, ProccessRow onDeleteElement, 
						void *pParams, const PositionMap *pMapH = NULL){
							const PositionMap *pPMH;
							PositionMap *pM = NULL;
							if(pMapH){
								pPMH = pMapH;
							}
							else{
								pM = new PositionMap;
								BuildPositionMapH(*pM, vElements);
								pPMH = pM;
							}
							multimap <int, Vertice> mapY2indx;
							vector<MM_IT_PAIR> vIndx2it(vElements.size()), vToAdd, vToErase;
							int nCurrPos = -1;
							for(PositionMap::const_iterator i = pPMH->begin(); i != pPMH->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){
									if(i->second.m_bStart){
										multimap <int, Vertice>::iterator it0 = mapY2indx.insert(PositionMapNode(pEl->top, Vertice(pEl->GetId(), TRUE)));
										multimap <int, Vertice>::iterator it1 = mapY2indx.insert(PositionMapNode(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);
							if(!pMapH) delete pM;
}

#endif // __RECT_ELEMENT_MAPPING__
